Size of Transposition Table Entry

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
emadsen
Posts: 195
Joined: Wed Apr 25, 2012 11:51 pm
Location: Naperville, IL, USA
Contact:

Re: Size of Transposition Table Entry

Post by emadsen » Sat Sep 30, 2017 1:24 pm

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.
My C# chess engine: http://www.madchess.net

AlvaroBegue
Posts: 919
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Size of Transposition Table Entry

Post by AlvaroBegue » Sat Sep 30, 2017 2:04 pm

emadsen wrote: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.

User avatar
emadsen
Posts: 195
Joined: Wed Apr 25, 2012 11:51 pm
Location: Naperville, IL, USA
Contact:

Re: Size of Transposition Table Entry

Post by emadsen » Sat Sep 30, 2017 2:32 pm

AlvaroBegue wrote: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.
My C# chess engine: http://www.madchess.net

User avatar
hgm
Posts: 23613
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Size of Transposition Table Entry

Post by hgm » Sat Sep 30, 2017 3:52 pm

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
Posts: 346
Joined: Sat May 05, 2012 12:48 pm
Location: Bergheim

Re: Size of Transposition Table Entry

Post by BeyondCritics » Sat Sep 30, 2017 6:12 pm

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

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Size of Transposition Table Entry

Post by cdani » Sat Sep 30, 2017 6:23 pm

BeyondCritics wrote: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
Posts: 346
Joined: Sat May 05, 2012 12:48 pm
Location: Bergheim

Re: Size of Transposition Table Entry

Post by BeyondCritics » Sat Sep 30, 2017 6:25 pm

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

User avatar
hgm
Posts: 23613
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Size of Transposition Table Entry

Post by hgm » Sat Sep 30, 2017 6:47 pm

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.

User avatar
Houdini
Posts: 1471
Joined: Mon Mar 15, 2010 11:00 pm
Contact:

Re: Size of Transposition Table Entry

Post by Houdini » Sat Sep 30, 2017 8:21 pm

cdani wrote: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.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Size of Transposition Table Entry

Post by Evert » Sat Sep 30, 2017 8:26 pm

hgm wrote: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.

Post Reply