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

Recommended Posts

patishi    212

An update, I switched from using a 3000017 sized array for the TT into using a 1048583 sized array, but this time it is a two dimentional array that holds another "inner" array of 4 entries in each index.    that means that there is more room for entries (4000000+).        The replacement scheme is roughly the same,  i check to see if an identical position is found,  if not i check to see if i still have room to store a new entry (e.g if there are null entries)  and if not,  i just push out the oldest one out of the array and insert the new one.     so every time the oldest entry get to be dropped out...  and so on.

Actually i don't know what is the difference between using this kind of Table and using a single linear array with more positions. ( like i did before). if it turns out that the two tables are roughly the same, than i suppose that using a single array is better and faster (no need for searching operations, i just immediately replace an entry)

and  If i do a full game tree search i don't use a depth parameter so replacing "by depth" schmeme is useless.

Share on other sites
alvaro    21246
Even in a full game tree search some nodes have enormous subtrees and others don't. You may want to prioritize keeping information about nodes that have large subtrees, because they can potentially save you much more work than a node towards the end of the tree could.

I think what John Tromp used was a table with 2-entry bins, prioritizing by depth.

Share on other sites
patishi    212

ok thaks!    but how can i recognize a node with a large subtree?  should my priority be  the bigger distance from the root is better?  but still...how can i know what was the size of the subtree of a particular node?

EDIT: Ah i think i got it.  silly question, i need to keep the nodes with a bigger distance from the root..that's the sign of a large subtree. :)

Edited by patishi

Share on other sites
alvaro    21246

EDIT: Ah i think i got it.  silly question, i need to keep the nodes with a bigger distance from the root..that's the sign of a large subtree.

I imagine you meant the opposite: The closer to the root, the larger the subtree. You could also have a global counter of positions visited, compute the difference between the value of this counter at the beginning and at the end of the search, and then you'll actually know how much effort was put into the search.

As I have said a couple of times before, you need to test several options to see what works best in your program.

Share on other sites
patishi    212

thx for the tip,  i am right on it !  :)

Share on other sites
patishi    212

I am trying to implement the "Deep + always"  or  the "Two tier System"  .. e.g   at every index in the table, i have one entry that gets replaced by "depth" , that means that only if the depth is higher (i assume that means closer to the root node) it gets replaced by the new entry.      And the second entry always gets replaced no matter what.

The question i have regarding this:     when i want to insert new entry to the table,  than i go to that specific index and first check the "by depth" entry,  and if the depth is higher than the one in the table, i immediately switch between them, i even don't check if this is the same position or just another one hashed to the same index.
But if not (!)  ,e.g, the depth is not higher, than i need now to put the new entry in the second poisition (the "always replace "one).     but i didn't get if i need to check whether the new position is different than the one i already have in the first position (the "depth " entry)  or i allowed to have two identical entries, side by side.

my logic tells me that it is a bit of waste to have two identical positions one next to the other, when in any case,  when probing for the table for an entry, i always check the "depth" entry first anyway...     I hope that the question is clear.       in other words, do i need to check if the two entries are similar or not.

Edited by patishi

Share on other sites
alvaro    21246
The better transposition-table replacement policy is the one that performs better. Did you set up a way to test them? What are the results?

Share on other sites
patishi    212

right now, from checking the time i get an answer from the engine there is not a crucial difference between the TT with the single entry array &&  always replace scheme, and the scheme i am using now  (deep+always).    like i said,so far,the only big difference i noticed is using the killer moves instead of the history heuristic (killer moves are better), but there is a chance that my HH implementation is not the "best".

as for the TT , so far i haven't been using the hash move,  and right now i am working on implementing it,  to see if this will speed up the process.
I must say that now,  after i implemented the 8 ply "book" moves (e.g database) my engine is playing perfect, and against week engines, the answer of the first engine move (the 9th ply) is getting pretty fast, something like 5 6 seconds..  but i want it to be faster!

Edited by patishi

Share on other sites
patishi    212

Actually, the speed in the first engine move is not bad at all (could help just a tiny bit of extra boost)  in most positions.   but when testing it agains a certain (based on the velena engine) connect 4 engine with a perfect play.  than the sequence of moves is always the same.    they play some kind of follow up,  and than the engine gets stuck for a minute or so...      but when testing it against the john tromp machine, in all positions i have tested so far,  it plays the first move after a few seconds only!

Edited by patishi

Share on other sites
alvaro    21246

Wait, how can the opponent make a difference for the time it takes to complete the first search? The opponent hasn't even moved at that point!

Share on other sites
patishi    212
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)

Share on other sites
alvaro    21246

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

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


Share on other sites
patishi    212

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

Share on other sites
alvaro    21246

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.

Share on other sites
patishi    212

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

Share on other sites
SillyCow    1461

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

Share on other sites
patishi    212

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

Share on other sites
alvaro    21246

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.

Share on other sites
patishi    212

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.

Share on other sites
patishi    212

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

Share on other sites
patishi    212

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?

Share on other sites
alvaro    21246

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

Share on other sites
patishi    212

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.

Share on other sites
alvaro    21246

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

Share on other sites
patishi    212

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