Transposition Tables

[Tony]

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?

that 2 pow 4 equals 16 ?



Remember, you can have short AND long castle rights.

Tony

[bob]

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

There are several ways to handle en passant status. I do it only when it applies. That is, a pawn advances two squares and there is an enemy pawn on either adjacent file. You can just do it when a pawn advances two squares, but the effect there is that you slightly reduce good hash hits. For example, if you reach a position where you play e2-e4 and set the status, and there are no pawns on d4 or f4, then you can not use this entry after you play e2-e3 and then e3-e4. In the former you have the en passant status included, in the latter you don't. While in reality the two positions are identical since no en passant capture can be made in either position.

Hope that helps...

[bob]

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).

1. using exact mate scores is not a "silly" thing.

2. I don't see how your kludge works when you store at ply=10, and probe at ply=16 and get a hit on the ply=10 result. The way most of us do this produces perfect mate scores no matter where we store and then probe...

[bob]

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?

There are 16 states. nobody can castle = 0000, white can castle short, black can't castle at all = 0001, white can castle long, not short, black can't castle = 0010, white can castle long or short, black can't castle = 0011. Repeat each of those four for each of the other three black possibilities and you get 16.

[Colin]

Basically... I have a 4 bit number castRights=ABCD..

if a piece is moved from/to a1, then castRights &= 1101 (13)
if a piece is moved from/to h1, then castRights &= 1110 (14)
if a piece is moved from/to e1, then castRights &= 1100 (12)

So by looking at bits C and D, we can determine if castling is allowed long or short for white.

And similarly for black...
if a piece is moved from/to a8, then castRights &= 0111 (7)
if a piece is moved from/to h8, then castRights &= 1011 (11)
if a piece is moved from/to e8, then castRights &= 0011 (3)

So by looking at bits A and B, we can determine if castling is allowed long or short for black.

And if a piece is moved to/from any other square castRights &= 1111 (15)

So ultimatley I have an array
7 15 15 15 3 15 15 11
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
13 15 15 15 12 15 15 14

Hope that helps

[hgm]

1. using exact mate scores is not a "silly" thing.

2. I don't see how your kludge works when you store at ply=10, and probe at ply=16 and get a hit on the ply=10 result. The way most of us do this produces perfect mate scores no matter where we store and then probe...

Well, if at ply=10 you store a mate-in-2 score, and at ply=16 you reach that same position and probe in, you would find a mate-in-2 score. As the position is a mate in 2.

Of course by the time that score would have propagated to the ply=10 level, it would now be a mate-in-5 score (as the side to be checkmated adds one to the score on each of its intervening plies). The ply=10 mate-in-2 would of course be a mate-in-7 score by the time it reached the root, while the ply=16 hit on it would arrive there as a mate-in-10 score. As from the root it would be a mate in 10.

See it now?

[hgm]

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.

A memory access is not necessarily faster than a multiply. Details can be processor dependent.

On a 32-bit CPU you can save time by only using a 32-bit random here.

In uMax I do't use any random at all. I add Color*epSqr to the hash key (or XOR it, doesn't matter), as both my codes for white and black are nonzero (8 and 16, to be exact). This also works, and I catch two birds with one stone.

Castling rights I don't care about in uMax, which of course is an error, but an error that didn't seem to cost any measurable Elo. So I don't consider it a bug, but a calculated risk.

[Colin]

Thanks,

I'm still unsure about the mate scores thing, but I will take a good look at it, then come back.

The Pseudocode I'm using for my search is on this pdf file...
http://homepages.cwi.nl/~paulk/theses/Carolus.pdf
On pages 14 and 15 is the pseudocode.

Where you have

Code: Select all

if(depth==0 || board.isEnded())

There are 3 possible calls to StoreTTEntry.
None of these seem to do anything with the 'move' field in the TT entry.
Is this irrelevant since we only really want to return the value in this entry since its at the end of the game?

Also, on page 15, there are another 3 calls to StoreTTEntry, this doesn't mention the move either, shouldn't the best move generated previously in the node be passed in as a parameter?

Thanks for any help

[hgm]

Well, the pseudo-code you mention is very incomplete. It does not seem to use the hash move for ordering. Normally you would have to pass GetOrderedMoves() what the hash move was, or it could only do static ordering. In fact, usually you try the hash move before generating or searching moves.

Of course if you don't use the hash move for anything, there is no need to store it either.

It is also very chaotic pseudo-code. Normally you would have only one hash store, at the end of the Search() routine. Only the bound-type would be dependent on the positioning of the Score wrt (Alpha,Beta).

[Colin]

Ok, I'm aware that I should play hash move first and this isn't in the psuedocode, but do I need to pass the best move in at the end...

Code: Select all

if&#40;best<=alpha&#41;
  StoreTTEntry&#40;board.getHashKey&#40;),best,BESTMOVE,LOWERBOUND,depth&#41;
else if&#40;best>=beta&#41;
  StoreTTEntry&#40;board.getHashKey&#40;),best,BESTMOVE,UPPERBOUND,depth&#41;
else
  StoreTTEntry&#40;board.getHashKey&#40;),best,BESTMOVE,EXACT,depth&#41;
return best

I have copied the pseudocode, and added in BESTMOVE (best move for the node)
Does that look right, thanks