• Create Account

## Hashing connect -4 board (for Transposition table)..need some help :)

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

82 replies to this topic

### #61patishi  Members

212
Like
0Likes
Like

Posted 16 July 2013 - 10:23 AM

Again.. the first 8 plies are book plies right? After that (my engine is white) it depends on position on the board if the engine takes a minute to figure out the move, or 4 5 seconds...
It happens that only when playing the velena engine, because of its drawish play style, it takes my engine more than a minute to calculate the move. (Because the position on the board)

### #62Álvaro  Members

20267
Like
0Likes
Like

Posted 16 July 2013 - 11:54 AM

Oh, I see. How long does your program take in this position?

_ _ _ _ _ _ _
_ _ _ 1 _ _ _
_ _ _ 2 _ _ _
_ _ _ 1 _ _ _
_ 1 _ 2 _ _ _
_ 2 _ 1 2 _ _


### #63patishi  Members

212
Like
0Likes
Like

Posted 16 July 2013 - 02:12 PM

2 whole minutes!         And it happens in this kind of positions exactly.    in other positions (played by weaker engines) it takes only a few seconds for the engine to find a move.    what is the reason for that??   do you think its related to the TT and move ordering?     my code suppose to be fast ,  except for the move ordering part

Edited by patishi, 16 July 2013 - 02:16 PM.

### #64Álvaro  Members

20267
Like
0Likes
Like

Posted 16 July 2013 - 02:18 PM

If you are searching as many positions per second as John Tromp's program, you either have much worse ordering, much worse transposition tables, bugs, or a combination of all of the above.

It's hard to give you advice, other than testing every change and every decision. Also, don't get too discouraged if you can't make your program as good as John's. I know him well and he is extremely smart.

I have never read all the code in Fhourstones carefully, but it is rather short, so you can probably learn a lot by reading it.

### #65patishi  Members

212
Like
0Likes
Like

Posted 16 July 2013 - 02:28 PM

thx i will try to improve it as much as i can.  it is probably have a lot to do with the move ordering and TT implementation, my bitboard code is not very different from john tromp's implementation.   my getMoves()  method is probably not that fast but i don't believe that the problem lies there.     thx again for all the help

Edited by patishi, 16 July 2013 - 02:29 PM.

### #66SillyCow  Members

1334
Like
0Likes
Like

Posted 16 July 2013 - 05:17 PM

By the way. You do not need to use a bit aligned system to hash a base 3 numerical format.

You can easily achieve 40 base-3 digits in 64 bits.

Just use division by three instead of bit rotation (division by 4).

Granted you are still two digits short...
But still, there is no reason to cling to bit-wise math when your number scale isn't a power of 2.

Edited by SillyCow, 16 July 2013 - 05:17 PM.

My browser game: Vitrage - A game of stained glass

My android games : Enemies of the Crown &  Killer Bees

### #67patishi  Members

212
Like
0Likes
Like

Posted 17 July 2013 - 05:38 AM

And another thing that may be causing my some troubles,  right now i am not doing anything in the root negamax function but passing through all the root moves one by one and only changing alpha if the score is higher than the best score so far. and in the end i am returning the best move.       should i also check for TT entry in the root function ? should i insert to the TT at the end of this function?    should i try to play the hash move?   i don't do any of those things at the moment,  and maybe that's one of the reasons that the engine is slow.

this is my root negamax function:   is there a point in doing -    if(alpha >= beta){ break;}  ? )  cause the beta value is not changing in the root function...only the alpha!

public int rootNegamax(int depth,int alpha,int beta,int side){
int bestMove = -1;
ArrayList<Integer>moves = board.getMoves(depth);
for(Integer move:moves){
board.makeMove(move);
int value = -negamax(depth+1,-beta,-alpha,-side);
board.unmakeMove(move);

if(value>alpha){
alpha = value;
bestMove = move;
}
if(alpha>=beta){
break;
}
}
return bestMove;
}

in the inner negamax functions i am doing all the TT operation and getMoves() etc.  no point in posting it out here

### #68Álvaro  Members

20267
Like
0Likes
Like

Posted 17 July 2013 - 05:51 AM

You don't need to handle transpositions in the root function. You could try the hash move first, if there is one from a previous search, but it won't chance things much: If this position has been visited before, chances are the TT has enough stored about it that the search will be very very fast.

You are correct: You don't need to check for beta cutoffs at the root, since they can't happen. Also, there is no point in passing alpha and beta to the root function: You are probably passing -Infinity, +Infinity or something like that, which you can hard-code into the function.

### #69patishi  Members

212
Like
0Likes
Like

Posted 17 July 2013 - 06:05 AM

thx for the approval Alvaro!      ok..so i now testing the engine with a new size of the TT (8306069!! , Just like in fhourstones code )  and a simple alwauys replace scheme..i will also try to play with  other replacement schemes later,  but this seems to work ok...    + killer moves which also seems to do the job quite nicely.    like i said,  testing it against my weak AI factory "four in a row"  app ,  my engine calculated the first (non-book) move in seconds!     i will now test it against the more problematic positions..  hope that some tweaking with move ordering and TT will help.

### #70patishi  Members

212
Like
0Likes
Like

Posted 18 July 2013 - 04:32 AM

Since i can't get over the problematic positions issue,  i am now trying the last resource:   using an evaluation function for one move!  (the 9th ply), just to get another token on the board (two to be more correct..there is a black move too)  and make the calculation easier for the engine.     right now, testing it against the velena engine (plays always the same moves) my engine seem to find the correct 9th move in order to win the game.   now i will test it against the john tromp engine, which plays in more varied fashion.. just to see how it goes.     It may turn out that this simple evaluation function ,when taken to a depth of 18 plies,can catch the correct move.     but i still got more tests to do
I am anxious to finish this project so i can move to the next challange..a chess engine (which is my favourite game).    the knowledge i earned in the connect 4 project will help me a lot in the process,  so again.. special thx to Alvaro for all your help and also the rest of the participants in this thread.

EDIT: for now seems to work great!  (tested it also against the john tromp machine with  100% success)

Edited by patishi, 18 July 2013 - 05:02 AM.

### #71patishi  Members

212
Like
0Likes
Like

Posted 19 July 2013 - 11:41 AM

good news, i have been able to improve my code a little, and the engine's thinking time is less than before.   but one thing i think that's holding me back is my Transposition table operation.   right now whenever i want to insert an entry to the table i create an Entry object with all the neccesary variables inside.   but creating a java object takes time (and also memory,but i don't think that's an issue in my case)  .        is there another way of doing this?   If i understood correctly from looking at john tromp's code, he is not using a standart Entry object,  but using a Long instead..?     but how can i save all this data into a Long type?    only the hashTable key is a 64 but long itself...
any ideas on how i can improve this area?

### #72Álvaro  Members

20267
Like
0Likes
Like

Posted 19 July 2013 - 12:33 PM

As I explained elsewhere, you should avoid dynamic memory allocation in this type of performance-bound program. The transposition table should be that, a table, with a fixed size that is allocated once at the beginning of the program and then just written to or read from.

A hash key only needs 49 bits in connect 4, as was discussed earlier in this thread. Also, where you are in the table gives you partial information as to what the hash key is, so you can afford to store fewer bits to avoid collisions. [EDIT: I think you need 27 bits.]

Edited by Álvaro, 19 July 2013 - 12:35 PM.

### #73patishi  Members

212
Like
0Likes
Like

Posted 19 July 2013 - 01:04 PM

I am using the zobrist hashing at the moment, which gives me a 64  bit hash keys..  (or am i mistaken?).    and besides that,  whithout using an Entry object which holds all the TT Entry info (score,key,valueType etc.) than how can i store all that in a single array index?    should i bunch it all into the bits of a 64 bit Long variable?  I really don't know how to do it.

### #74Álvaro  Members

20267
Like
0Likes
Like

Posted 19 July 2013 - 01:39 PM

You can pack several fields in a single integer, by deciding that bits 0-2 will encode the score, 3-4 the bound type, 5-63 the higher bits of the Zobrist key (for instance). The bit manipulations are pretty straight forward.

long encode_TT_entry(int score, long key, int valueType) {
return score + (valueType<<3) + (key & 0xffffffffffffffe0L);
}

int get_score_from_TT(long TT_value) {
return TT_value & 7;
}

int get_valueType_from_TT(long TT_value) {
return (TT_value>>3) & 3;
}

long get_key_from_TT(long TT_value) {
return TT_value & 0xffffffffffffffe0L;
}


John Tromp seems to use small positive integers as scores, perhaps so he can do this type of thing easily. Handling signed numbers can also be done, but it's trickier.

[EDIT: 42 bits should be enough to distinguish all 64-bit patterns, if you have 8306069 separate locations in the TT.]

Edited by Álvaro, 19 July 2013 - 01:41 PM.

### #75patishi  Members

212
Like
0Likes
Like

Posted 19 July 2013 - 04:46 PM

thank you very much for the code, i will investigate it

And another small thing before i get on with the code, when i am doing key%tableSize to get the entry index, should i do it with the complete 64 bit hash key and only after that (when creating the entry integer) cut it down to 58 bits? Or should i do the mod operation already with the shorter key..

EDIT:  by the way, how do you store -1  in the 3 right most bits?  i know that java only supports sign numbers, so the left most bit of a number is a "sign" bit.  (that means that -1 needs to look something like this:  10000001  if this is a Byte type)  so how can i put a "-1"  in the entry pattern and than add some other information?        I can always store a -1 as a 3 (11 in binary)  and just manually translate it into -1

Edited by patishi, 20 July 2013 - 06:13 AM.

### #76patishi  Members

212
Like
0Likes
Like

Posted 20 July 2013 - 07:39 AM

This is my New Transposition Table code  (in my own simple way  )    please give me corrections

private final int N = 8306069;
private long[] table;

public NewTT(){
table = new long[N];
}

public void initTable(){
for(int i = 0; i<table.length; i++){
table[i] = 0L;
}
}

private int compress(long key){
return (int)(key % N);
}

public void insert(long key,int value,int valueType){
int index = compress(key);
long entry = 0;
if(value == -1){
entry = 3 + (valueType << 2) + (key & 9223372036854775792L);     // if the value is  -1  i translate it to 3  ( 11  in binary )
}
else{
entry = value + (valueType << 2) + (key & 9223372036854775792L);
}
table[index] = entry;

}

public long find(long key){
int index = compress(key);
if((key & 9223372036854775792L) == (table[index] & 9223372036854775792L)){
return table[index];
}
else{
return 0;
}

}

public int getValue(long entry){
if((entry & 3) == 3){               //  here i again translate the 3 back to -1
return -1;
}
else{
return (int)(entry & 3);
}
}

public int getValueType(long entry){      //   1 = EXACT_VALUE,   2 = LOWERBOUND,   3 = UPPERBOUND
return (int)((entry >> 2) & 3);
}

EDIT:  OH MAN!!  what a major improvement in speed!  still not like john tromp engine, but much much better than what i had before
Alvaro,  now only 3 seconds with the position you showed above!!   OH man i am so happy

Edited by patishi, 20 July 2013 - 08:48 AM.

### #77patishi  Members

212
Like
0Likes
Like

Posted 23 July 2013 - 08:45 AM

Update:  I improved my engine's speed incredibely!  the trick was actually to change the static move ordering (combined with killer moves ofcourse).  now my default columns order is {1,5,4,3,2,0,6}  starting at the root node and changing dynamically with the help of killer moves.  I will try to improve the move ordering by maybe trying (again) to use the hash move.    No matter what variant of the history heuristic i tried to use, the killer moves gives me greatest boost in speed.

Now my engine analyses the most complex position i encountered so far (took 2-3 minutes in the beginning),  now only in 16-17 seconds!  which is exactly the same time as john tromp engine take to solve the exact position.

Another question i have is:    is it ok if i use only 47 bits in my TT entry  for the hash key?  (the most left ones).    is it enough in order to be unique?

I just want to mention that when i am saving to the table, i am using the full hash key (zobrist) for the compression process (key % Size of Table)  to find the index in the table,and only when actually saving iam cutting it  to 53 bits only  (cause i also store the depth,score,valueType...)

Edited by patishi, 23 July 2013 - 08:47 AM.

### #78Álvaro  Members

20267
Like
0Likes
Like

Posted 23 July 2013 - 09:55 AM

Another question i have is: is it ok if i use only 47 bits in my TT entry for the hash key? (the most left ones). is it enough in order to be unique?

I just want to mention that when i am saving to the table, i am using the full hash key (zobrist) for the compression process (key % Size of Table) to find the index in the table,and only when actually saving iam cutting it to 53 bits only (cause i also store the depth,score,valueType...)

Yes, that's enough. You can probably prove it formally using the Chinese remainder theorem.

How many positions per second does your program examine?

### #79patishi  Members

212
Like
0Likes
Like

Posted 23 July 2013 - 11:02 AM

can you advice me how can i measure the nodes per second rate?   i assume that i need to put some sort of a counter somwhere in the alpha beta, but can't figure out where exactly?    (maybe inside the for loop where i go through each possible move? )      right now i am just measuring the start and end time of the calculation so i have the total seconds.    if i have the total number of nodes i can just divide it by the seconds

### #80Álvaro  Members

20267
Like
0Likes
Like

Posted 23 July 2013 - 11:07 AM

The two popular options for counting nodes are:

(1) Count calls to the alpha-beta function

(2) Count calls to make_move

I use (1), and so does Fhourstones, so that's the number I am more interested in.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.