Transposition Tables

[cms271828]

Thanks for all the replies, just the en-passant zobrist I'm slightly unsure of.

Suppose we are at a white node in the tree (white to move), there is a white pawn on a2, black pawn on b4, and that we have generated the moves for white, and we are just about to call MAKE_MOVE with the move pawn a2-a4.

Then inside MAKE_MOVE, we XOR out pawn on a2, XOR it back in on a4.
Then we XOR in side to move.
Then must we also XOR in some value on a3 or a4 to represent blacks ability to capture by en-passent???

I was thinking, can't we just just XOR in one of 8 random numbers representing the file the piece capturable by ep lies in? (Since the side to move is XOR'ed in, so its clear which piece is capturable by ep).

Any thoughts?
Thanks

[frankp]

Thanks for all the replies, just the en-passant zobrist I'm slightly unsure of.

Suppose we are at a white node in the tree (white to move), there is a white pawn on a2, black pawn on b4, and that we have generated the moves for white, and we are just about to call MAKE_MOVE with the move pawn a2-a4.

Then inside MAKE_MOVE, we XOR out pawn on a2, XOR it back in on a4.
Then we XOR in side to move.
Then must we also XOR in some value on a3 or a4 to represent blacks ability to capture by en-passent???

I was thinking, can't we just just XOR in one of 8 random numbers representing the file the piece capturable by ep lies in? (Since the side to move is XOR'ed in, so its clear which piece is capturable by ep).

Any thoughts?
Thanks

Yes - I and I guess many other have only 8 ep zobrist numbers. You are also correct that hashing only when an ep is posssible is a gain - and unhashing only when ep was set. Something Bruce Moreland pointed out here years ago IIRC

[hgm]

Indeed, just XORing with a random based on the file does the trick.

Note that you would have to XOR it out again on the next move, as the e.p. rights vaporize. So it might be smarter to not do this in the differentially updated key (saving you the trouble to undo it), but XOR in the e.p. right only in a temporary key used when you access the hash table.

Note that if there was no black pawn on b4, there are no e.p. rights even after a2-a4.

Rather than having a table of 8 randoms, XORing RANDOMCONSTANT*FileNr into the temporary key works just as well (as there will exist at most only one e.p. right at the time, so the fact that the on-the-fly 'randoms' generated by the multiplication are equidistant can never lead to collissions. MicroMax even uses Color*epSqr to account for stm and e.p. rights in one blow, with minimal characters. (It can do this because Color is never zero, but 8 for white and 16 for black to move.)

P.S. why e?

[Colin]

Hi again, I'm finally looking at TTs again now.

I have a few basic questions, if anyone is kind enough to advise.

1. At the top of my alpha-beta method/function, I have...

Code: Select all

TTEntry tte=GetTTEntry(board.getHashKey())

So I was thinking..update the 'pieces' part of the boards hash key sequentially in the MAKE_MOVE / UNDO_MOVE.. then
In the line before the line of code above.. xor in the 'side to move','ep', and 'castling' random numbers... something like...

Code: Select all

long key=piecesRand XOR stmRand XOR epRand XOR castlingRand
TTEntry tte=GetTTEntry(key)

If the previous move, leading to this node was a pawn(2 forward), is that sufficient to XOR in the epRand number(based on the file), or must the pawn that just moved 2, now also be capturable by ep, for us to XOR in epRand?

2. I'm using 2^20+1 elements in my TT, and thus probing at index/index+1.
I'm not entirely sure about storing the hash.
Do I first need to check both positions, to try and find an indentical 64-bit key, then if this is found, I simply overwrite entry with new values?
(I guess if I always overwrite an entry with same key, I cannot get 2 entries with same 64 bit key)
If this entry is not present, and I have 1 or 2 empty entries, do I just store in this empty slot (preferring index to index+1 if both are empty)?
If this entry is not present, and I have 2 non-empty entries, then do I just overwrite the entry with the smallest depth(Depth getting smaller as you go down tree to 0, or below 0 if QS used)?

3. In an older post... I read...

If you store or read mate values then adjust them depending on depth.
You can keep the hash table between moves (and update it while pondering).

I'm not sure about this.. I use return -1000000-D for the side that has been checkmated, which Is always picked up at D=1 on my engine, since at D=0, I don't generate any moves for the node to see if its stale/checkmate.

Thanks for any help

[bob]

Hi again, I'm finally looking at TTs again now.

I have a few basic questions, if anyone is kind enough to advise.

1. At the top of my alpha-beta method/function, I have...

Code: Select all

TTEntry tte=GetTTEntry(board.getHashKey())

So I was thinking..update the 'pieces' part of the boards hash key sequentially in the MAKE_MOVE / UNDO_MOVE.. then
In the line before the line of code above.. xor in the 'side to move','ep', and 'castling' random numbers... something like...

Code: Select all

long key=piecesRand XOR stmRand XOR epRand XOR castlingRand
TTEntry tte=GetTTEntry(key)

If the previous move, leading to this node was a pawn(2 forward), is that sufficient to XOR in the epRand number(based on the file), or must the pawn that just moved 2, now also be capturable by ep, for us to XOR in epRand?

2. I'm using 2^20+1 elements in my TT, and thus probing at index/index+1.
I'm not entirely sure about storing the hash.
Do I first need to check both positions, to try and find an indentical 64-bit key, then if this is found, I simply overwrite entry with new values?
(I guess if I always overwrite an entry with same key, I cannot get 2 entries with same 64 bit key)
If this entry is not present, and I have 1 or 2 empty entries, do I just store in this empty slot (preferring index to index+1 if both are empty)?
If this entry is not present, and I have 2 non-empty entries, then do I just overwrite the entry with the smallest depth(Depth getting smaller as you go down tree to 0, or below 0 if QS used)?

3. In an older post... I read...

If you store or read mate values then adjust them depending on depth.
You can keep the hash table between moves (and update it while pondering).

I'm not sure about this.. I use return -1000000-D for the side that has been checkmated, which Is always picked up at D=1 on my engine, since at D=0, I don't generate any moves for the node to see if its stale/checkmate.

Thanks for any help

two answers.

1. Incremental update of the hash signature is the right way to do things. All you have to remember is that when a pawn advances two squares, and there is an enemy pawn on either adjacent file, that pawn is therefore an EP target and the hash signature should also be modified to reflect this. But then on the next ply you have to remember to undo this EP hash signature modification as one move later the EP right is removed...

2. Think about this: You search from the root and at ply=10 you discover that the opponent is mated, which means you return something like MATE-10, correct? If so that is right. But what do you store at the various hash entries as you back up. For example, at ply=3, the score will still be MATE-10, but that is not what you want to store. Instead, you want to store MATE - 10 + 2, because from _this_ position it is a mate in 4, note a mate in 5. The bottom line is that for any hash entry H, if you are storing anything related to mate, then you store the adjusted score to make it mate in N from this ply, rather than mate in N + something from the root... Once you think about it for a bit, it becomes obvious why...

[Colin]

Thanks very much,

I think you actually answered question 3, regarding the mate scores, instead of 2.
I really need to clarify what I intend doing in question 2, is all correct.

I'm still a little confused about question 1, I wouldn't have thought it mattered if a pawn that has just moved 2, can be captured by en-passent or not, for you to XOR in a value relating to its file.

I planned to XOR in this value in every node, just after any pawn has moved 2 squares, regardless of wether it can actually be taken by an adjacent pawn.
Because its really just saying that in the position a pawn has just moved 2, in contrast to a position with all pieces in the same squares where the last move was not a pawn 2 forward, which will have an entirely different hash key.

Thanks for any help

[Vempele]

I planned to XOR in this value in every node, just after any pawn has moved 2 squares, regardless of wether it can actually be taken by an adjacent pawn.
Because its really just saying that in the position a pawn has just moved 2, in contrast to a position with all pieces in the same squares where the last move was not a pawn 2 forward, which will have an entirely different hash key.

Thanks for any help

You don't want identical positions to have different hash keys depending on the last move. It's not a transposition table if that happens...

[hgm]

1) Not testing if e.p. capture is actuall possible after a double move would not lead to any errors, but it would reduce the number of hash hits, as you would store and two positions in different locations, while they are logically the same (in both of them e.p. capture is not possible, albeit for different reasons). If you do a perft from the opening with hashing, this can really give a large effect (the opening of course has the maximum number of double moves). In uMax I do it like you suggest, as it is a favorable trade of Elo (through speed loss) vs size.

Note that if you also use the hash key for 3-fold repetition detection, this can lead to missing draw claims. But I guess in general, one can live with it.

2) I think you have the right idea. This simple 2-way system already performs close to optimal. Note that if the depth of your empty entries would read as zero, you wouldn't have to do anything special. Just replace the lowest depth of the two (assuming true depths are never smaller than zero).

You might want to prevent that in the long run the deepest entries of each pair all are obsolete (no longer reachable from the game position) put refuse to go away because of their large depths. For this reason people often include an extra 'aging' field in their hash entry, where you could store the search number, and consider the entry as empty when the search number deviates too much from the current one. A much simpler way, which might be competative or even superior, would be to overwrite a depth=N entry at index to be replaced by a depth>=N-1 entry 1 out of 4 times, even if the entry at index+1 has depth<N. So depending on a global counter modulo 4, you would not even look at the depth of the other entry (you would have to look if you had a hit there, of course) if the old entry was not at least 2 deeper than the new one. That way no depth is sacred.

3) Don't bother with that silly 1000000-D stuff. Just start every call to Search with

if(Alpha <= CurEval) Alpha = Alpha - 1;
if(Beta < CurEval) Beta = Beta - 1;

and just before you return or store in the hash table, adjust the score by

if(BestScore < CurEval) BestScore = BestScore + 1;

(For BestScore you can read Alpha if you do fail hard.) That would automatically make your engine prefer the shortest path to any gain (including mate). If you would want to apply this only to mating scores, you would have to replace CurEval by -MATINGRANGE (e.g. -999000).

[Colin]

Thanks very much for the help...

Thinking about it now, regarding the ep thing...
If a white pawn has just moved 2, and we are at the start of a black node, and this white pawn is NOT capturable by ep, then...
This position is equivalent to one where the last move was say the white bishop.
The fact that a pawn just moved 2 is totally irrelevant since it can't be captured by ep, and the new position is just like any other.

Its a simple task anyway to check if a pawn that has just moved 2 is ep capturable.

Regarding the XOR thing for ep.. if the file number is 1-8, then I guess we can just do epRandom*fileNum (epRandom is a random 64 bit number).

This is kind of trivial, but wouldn't it be faster to just access the value from an array of 8.... epRandomArray[fileNum-1] since no calculation is involved.

Also for castling, I use values 0-15 to describe the castling rights for a position, so again, I guess I can do castRandom*castRights, or use an array of 16.... castRandomArray[castRights].

Thanks

[nczempin]

Also for castling, I use values 0-15 to describe the castling rights for a position, so again, I guess I can do castRandom*castRights, or use an array of 16.... castRandomArray[castRights].

Thanks

Why 16, when there are only 8 states:
whiteShort yes/no
whiteLong yes/no
blackShort yes/no
blackLong yes/no

What am I missing?