Size of Transposition Table Entry

[emadsen]

In my engine, MadChess, I use 8 bytes:

Code: Select all

// CachedPosition bits

// 6 6 6 6 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
// 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
// Partial Key                    |To Horizon |Best From    |Best To      |BMP  |Score                        |SP |Last Accessed

// SP =        Score Precision
// BMP =       Best Move Promoted Piece
// Best To =   Best Move To (needs one extra bit for illegal square)
// Best From = Best Move From (needs one extra bit for illegal square)

Code: Select all

public enum ScorePrecision
{
	LowerBound,
	UpperBound,
	Exact,
	Unknown
}

There's a chance the partial key of the board position matches the partial key of the cached position, yet the cached position was from another position. So I wrote a method to validate the cached position (if it specifies a best move) by verifying the piece is the correct color, to square not occupied by side to move, sliding path is open, etc.

[AlvaroBegue]

In my engine, MadChess, I use 8 bytes:

Code: Select all

// CachedPosition bits

// 6 6 6 6 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
// 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
// Partial Key                    |To Horizon |Best From    |Best To      |BMP  |Score                        |SP |Last Accessed

// SP =        Score Precision
// BMP =       Best Move Promoted Piece
// Best To =   Best Move To (needs one extra bit for illegal square)
// Best From = Best Move From (needs one extra bit for illegal square)

Code: Select all

public enum ScorePrecision
{
	LowerBound,
	UpperBound,
	Exact,
	Unknown
}

There's a chance the partial key of the board position matches the partial key of the cached position, yet the cached position was from another position. So I wrote a method to validate the cached position (if it specifies a best move) by verifying the piece is the correct color, to square not occupied by side to move, sliding path is open, etc.

You are using only 16 bits for verification of the hash key, which seems a bit scary. The verification that the move is legal will help, but I imagine many moves are valid in lots of positions from the same search.

However, this suggests a trick that will turn your move verification into something equivalent to about 12 additional bits of stored hash key: Store your data XORed with the hash key. When you retrieve the data, XOR it with the hash key again to recover the original data. Now if you have a collision the move bits will contain random junk, so the probability of the move being legal is quite small (say, 40/2^17 if there are 40 legal moves in a typical position and you use 17 bits to store the move). You can also check if the lower/upper/exact bits contain an illegal combination, which will happen with probability 1/4.

Turning the probability of confusion into a number of bits, you get -log2((40/2^17) * (3/4)) ~= 12.1 bits.

Is this a well-known trick? I hadn't thought about it before. This may actually make 64-bit hash entries perfectly reasonable to use in my engine.

[emadsen]

Is this a well-known trick? I hadn't thought about it before. This may actually make 64-bit hash entries perfectly reasonable to use in my engine.

Alvaro, I don't know. I wanted to pack the TT entry into a long if possible, so I came up with this on my own. Though I admit I haven't profiled it. I'll add some debug code to determine how often the IsCachedBestMoveValid function returns false. If it's frequent enough, I'll investigate your suggestion.

[hgm]

You are very generous with the 'last accessed' field; personally I would go for two bits there, and more bits in the hash signature. Also not that you could have put the flags ('SP') in the bits the move does not need because of the 0x88 square numbering. And to indicate promotions and such, I usually have just a single bit. When it is set this triggers a table lookup indexed by the to-square, which then gives the move step (implying the true to-square), promotion piece, whether the Rook should be moved, which additional square has to be cleared, etc.

Alvaro's trick is nice; never saw that before. But 16 bits seems enough verification in itself; it seems to be what Stockfish uses. I would still put one byte of the key of each entry in the first word of the bucket, however. Then in most cases you can already exclude that the entry could be a hit without actually looking at the 64-bit word it is in. You should not suffer that much from having 7 entries per bucket instead of 8, and it would speed up the probing a lot.

[BeyondCritics]

Where does "secondmove" come from? Or is this a trade secret?

[cdani]

Where does "secondmove" come from? Or is this a trade secret?

I save a second move to the hash sometimes. Was a little win.
The next Andscacs after 0.92 will be open source. The details will be clear then.

[BeyondCritics]

Wow, great news. I am looking forward to it.

[hgm]

I am often tempted to put a second score and depth in the entry (without a secod move): one for the upper, and one for the lower bound. I never considered a second move.

[Houdini]

I save a second move to the hash sometimes. Was a little win.
The next Andscacs after 0.92 will be open source. The details will be clear then.

Houdini 3 and 4 also used a second hash move, it gained a couple of Elo (less than 5 Elo). Surprisingly few entries actually contained a second move, did you ever verify the statistics on that?
In Houdini 5 and 6 I've dumped the second move in favor of some evaluation-related information, which proved to be a more profitable usage.

[Evert]

I am often tempted to put a second score and depth in the entry (without a secod move): one for the upper, and one for the lower bound. I never considered a second move.

I thought about it the other day (a day or two before Jose announced that he was doing that), but it's not so obvious what the second move would be. The best I could come up with would be to treat the two slots as killer slots: keep the old move and also store the move that ended up causing a cut-off this time around. What that does though is preserve a move that is known to not be good enough (even if it looked good at lower depth), which doesn't seem like it would be very useful.
So I'm curious to see what other move you can keep in there that is useful.

I switched to a dual-bound table a while back, but I haven't really noticed a difference in practice.