Transposition Tables and ply depth

[stegemma]

I'm debugging the TT in Freccia (still doesn't work...) and i'm curious about the cache hit that one's can get. Supposing a middle game position, what could be the percent of positions found in TT? I'm interested to know if this value will rise or not depending on the ply depth. I means, if i found, let's say, 10% of the position already in TT when i'm examining a ply 5 move, i can expect something similar to 10% at ply 8 or more? anybody does such kind of statistics?

[bob]

I'm debugging the TT in Freccia (still doesn't work...) and i'm curious about the cache hit that one's can get. Supposing a middle game position, what could be the percent of positions found in TT? I'm interested to know if this value will rise or not depending on the ply depth. I means, if i found, let's say, 10% of the position already in TT when i'm examining a ply 5 move, i can expect something similar to 10% at ply 8 or more? anybody does such kind of statistics?

10% to 20% for MG positions is about all you can do. Good test is fine #70 which will have a huge hit rate and often finds bugs you did not know were there as it will screw up finding the solution.

[stegemma]

10% to 20% for MG positions is about all you can do. Good test is fine #70 which will have a huge hit rate and often finds bugs you did not know were there as it will screw up finding the solution.

Now that something seems to works... i've in fact found about 15/18% of TT hit rate. There are still some other bug, because using the value found in TT will multiply x3 the time of the search

Disabling the use of the value of found positions, i get an hit rate up to 67%. I suppose (if it not depends on bugs) that this one could be the maximum, not reacheable hit rate. It can be reached from starting position, with pure alfa-beta and an evaluation function that counts only piece value, no extensions, no ID, no null-move. Obviously if you use the position value found in the TT (to avoid the next call to alfa-beta), this hit rate becomes the ones you said and that i've found.

But i don't understand what is "fine #70" (sometimes your english is too complex, for me).

[Gerd Isenberg]

But i don't understand what is "fine #70" (sometimes your english is too complex, for me).

I think it is position #70 from Reuben Fine's Basic Chess Endings:
[d] 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - -

[bob]

10% to 20% for MG positions is about all you can do. Good test is fine #70 which will have a huge hit rate and often finds bugs you did not know were there as it will screw up finding the solution.

Now that something seems to works... i've in fact found about 15/18% of TT hit rate. There are still some other bug, because using the value found in TT will multiply x3 the time of the search

Disabling the use of the value of found positions, i get an hit rate up to 67%. I suppose (if it not depends on bugs) that this one could be the maximum, not reacheable hit rate. It can be reached from starting position, with pure alfa-beta and an evaluation function that counts only piece value, no extensions, no ID, no null-move. Obviously if you use the position value found in the TT (to avoid the next call to alfa-beta), this hit rate becomes the ones you said and that i've found.

But i don't understand what is "fine #70" (sometimes your english is too complex, for me).

Couple of points. Hash table does not _always_ make the tree smaller. Sometimes it will make it bigger. It will, almost always, make the search qualitatively better, which is why it sometimes slows it down a bit.

Fine #70 is a classic endgame position from Reuben Fine's "Basic Chess Endings" book. It is position #70 in the book, one where there are locked pawns and white has to play Kb1 to win, any other move draws.

[Allard Siemelink]

But i don't understand what is "fine #70" (sometimes your english is too complex, for me).

I think it is position #70 from Reuben Fine's Basic Chess Endings:
[d] 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - -

Last time a checked Spark found the mate in a couple of minutes, somehow, the latest version takes a little longer.
Can anybody confirm that mate in 32 is actually correct?

Code: Select all

...
 [20/19]    0.062   15584       98  Kb2 Kb8 Kc2 Kc8 Kd3 Kc7 Ke3 Kc8 Kd2 Kb8 Kd1 Kc7 Ke1 Kb7 Ke2 Kc8 Kf2 Kc7 Kf3 Kb6
 [20/19]    0.062   15707       98  ok/1.2
 [21/20]    0.062   22918       94  Kb2 Ka8 Kc2 Kb8 Kd1 Kc7 Ke1 Kd7 Kd2 Kc8 Kc1 Kb7 Kb1 Ka7 Ka2 Kb7 Ka3 Kc8 Kb2 Kc7 Kc3
 [21/20]    0.062   23058       94  ok/1.5
 [22/21]    0.078   24472      106  Kb2 Ka8 Kc2 Kb8 Kd1 Kc7 Ke1 Kd7 Kd2 Kc8 Kc1 Kb7 Kb1 Ka7 Ka2 Kb7 Ka3 Kb8 Kb3 Kc7 Kb2 Kc8
 [22/21]    0.078   24631      126  ++2/3 Ka1b1
 [22/21]    0.078   24704      126  Kb1
 [22/21]    0.078   25433      126  Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kd7 Kc3 Kc7 Kd3 Kb7 Ke2 Kc8 Kf2 Kd7 Kg3 Ke7 Kh4 Kf6 Kh5 Ke7 Kg5
 [22/21]    0.078   25448      126  ok/1.1
 [23/22]    0.078   26678      126  Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kd7 Kc3 Kc7 Kd3 Kb7 Ke2 Kc8 Kf2 Kd7 Kg3 Ke7 Kh4 Kf6 Kh5 Ke7 Kg5
 [23/22]    0.078   26748      126  ok/1.1
 [24/23]    0.078   28709      181  Kb1
 [24/23]    0.078   29588      212  Kb1
 [24/23]    0.094   32702      276  Kb1
 [24/23]    0.094   34170      279  Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kd7 Kc3 Kc7 Kd3 Kb7 Ke2 Kc8 Kf2 Kd7 Kg3 Ke7 Kh4 Kf6 Kh5 Kf7 Kg5 Ke7 Kxf5
 [24/23]    0.094   34247      279  ok/1.3
 [25/24]    0.094   35641      279  Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kd7 Kc3 Kc7 Kd3 Kb7 Ke2 Kc8 Kf2 Kd7 Kg3 Ke7 Kh4 Kf6 Kh5 Kf7 Kg5 Ke7 Kxf5
 [25/24]    0.094   35715      279  ok/1.0

...

 [50/54]    4.297    6483k    1183  Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kd7 Kc3 Kc7 Kd3 Kb7 Ke2 Kc8 Kf2 Kd7 Kg3 Ke7 Kh4 Kf6 Kh5 Kf7 Kg5 Kg7 Kxf5 Kf7 Kg5 Kg7 f5 Kf7 f6 Kf8 Kf4 Ke8 Kg4 Kf8 Kg5 Kf7 Kf5 Kf8 Ke6 Ke8 Kxd6 Kf7 Ke5 Kf8 Ke6 Ke8 d6 Kd8 f7
 [50/54]    4.297    6483k    1183  ok/1.1
 [51/59]    4.469    6766k    1208  Kb1
 [51/59]    4.516    6838k    1258  Kb1
 [51/59]    4.562    6933k    1333  Kb1
 [51/59]    5.219    7814k    1533  Kb1
 [51/60]    5.891    8915k    1733  Kb1
 [51/60]   20.187   32170k    2098  Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kd7 Kc3 Kc7 Kd3 Kb7 Ke2 Kc8 Kf2 Kd7 Kg3 Ke7 Kh4 Kf6 Kh5 Kf7 Kg5 Kg7 Kxf5 Kf7 Kg5 Kg7 f5 Kf7 f6 Kf8 Kf4 Ke8 Kg4 Kf8 Kg5 Kf7 Kf5 Kf8 Ke6 Ke8 Kxd6 Kf7 Ke5 Kg6 Ke6 Kg5 f7 Kf4 f8=Q+ Ke4
 [51/60]   20.203   32170k    2098  ok/5.0

...

 [59/84]  0:02:46     237m    3308  Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2 Kd7 Kc3 Kc7 Kd3 Kb7 Ke2 Kc8 Kf2 Kd7 Kg3 Ke7 Kh4 Kf6 Kh5 Kf7 Kg5 Kg7 Kxf5 Kf7 Kg5 Kg7 f5 Kf7 f6 Kf8 Kf4 Ke8 Kg4 Kf8 Kg5 Kg8 Kg6 Kh8 Kf7 Kh7 Ke7 Kg6 f7 Kf5 f8=Q+ Ke4 Kxd6 Kxd4 Kc6 Kc3 d6 Kb2 d7 Kc1 d8=Q Kc2 Qxa5
 [59/84]  0:02:46     237m    3308  ok/1.8
 [60/84]  0:02:54     247m    3333  Kb1
 [60/84]  0:02:59     253m    3383  Kb1
 [60/84]  0:03:05     261m    3458  Kb1
 [60/84]  0:03:27     287m    3658  Kb1
 [60/84]  0:03:36     297m    3858  Kb1
 [60/84]  0:03:36     297m   28832  Kb1
 [60/84]  0:08:16     713m     +32# Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2 Kd7 Kc3 Kc7 Kd3 Kb7 Ke2 Kc8 Kf2 Kd7 Kg3 Ke7 Kh4 Kf6 Kh5 Kf7 Kg5 Kg7 Kxf5 Kf7 Kg5 Kg7 f5 Kf7 f6 Kf8 Kf4 Ke8 Kg4 Kf8 Kg5 Kf7 Kf5 Kf8 Ke6 Ke8 Kxd6 Kf7 Ke5 Kg6 d6 Kg5 f7 Kh4 f8=Q Kg4 d7 Kg3 d8=Q Kg4 Qf4+ Kh3 Qdh4+ Kg2 Qff2+
 [60/84]  0:08:16     713m     +32# ok/3.0
 [61/84]  0:08:18     716m     +32# Kb1 Kb7 Kc1 Kc7 Kd1 Kd8 Kc2 Kc8 Kd2 Kd7 Kc3 Kc7 Kd3 Kb7 Ke2 Kc8 Kf2 Kd7 Kg3 Ke7 Kh4 Kf6 Kh5 Kf7 Kg5 Kg7 Kxf5 Kf7 Kg5 Kg7 f5 Kf7 f6 Kf8 Kf4 Ke8 Kg4 Kf8 Kg5 Kf7 Kf5 Kf8 Ke6 Ke8 Kxd6 Kf7 Ke5 Kg6 d6 Kg5 f7 Kh4 f8=Q Kg4 d7 Kg3 d8=Q Kg4 Qf4+ Kh3 Qdh4+ Kg2 Qff2+
 [61/84]  0:08:18     716m     +32# ok/1.0

[stegemma]

...Fine #70 is a classic endgame position from Reuben Fine's "Basic Chess Endings" book. It is position #70 in the book, one where there are locked pawns and white has to play Kb1 to win, any other move draws.

Thanks for the hint and thanks to Gerd for the FEN provided. I will buy on Amazon that book.

Now i'm trying this variation on Zobrist key. I generate an array of 64 bit random keys, as standard Zobrist algorithm does. To avoid accessing this array, i do the following:

- i've two array: pieces and squares
- at start, i keep a key from the array and store that key near any piece and near any square (i've added the 64 bit key member to the two struct that i use for Piece and Square)
- when i execute a move, i adjourn the whole position key in this way:

PK = piece_key
SK = square_key
NK = new_key = PK +' SK

The +' operation is done with MMX instruction paddb so it is the sum byte per byte of the two keys (i use MMX because i've a 32 bit CPU) . This gives a 64 bit unique key for any (piece, square) couple. I think, but i've not veryfied, that this way i can use better the CPU cache, because i access the Piece struct and the Square struct that should already be in the cache itself (they are related to the move that i've just executed). I avoid that way to have to compute an address on the Zobrist table at any move. The paddb should take only 1 clock cycle so it is very fast.

so, instead to have a Zobrist key array is like to have a Zobrist function:

OldKey = Zobrist(piece_key, source_square_key)
NewKey = Zobrist(piece_key, destination_square_key)
PositionKey = PositionKey ^ OldKey ^ NewKey

where Zobrist(a, b) = a +' b

If i capture a piece, i just xor with the last PK of captured piece, that i save in Piece structure at any move.

I like to test for new way to do anything

[bob]

...Fine #70 is a classic endgame position from Reuben Fine's "Basic Chess Endings" book. It is position #70 in the book, one where there are locked pawns and white has to play Kb1 to win, any other move draws.

Thanks for the hint and thanks to Gerd for the FEN provided. I will buy on Amazon that book.

Now i'm trying this variation on Zobrist key. I generate an array of 64 bit random keys, as standard Zobrist algorithm does. To avoid accessing this array, i do the following:

- i've two array: pieces and squares
- at start, i keep a key from the array and store that key near any piece and near any square (i've added the 64 bit key member to the two struct that i use for Piece and Square)
- when i execute a move, i adjourn the whole position key in this way:

PK = piece_key
SK = square_key
NK = new_key = PK +' SK

The +' operation is done with MMX instruction paddb so it is the sum byte per byte of the two keys (i use MMX because i've a 32 bit CPU) . This gives a 64 bit unique key for any (piece, square) couple. I think, but i've not veryfied, that this way i can use better the CPU cache, because i access the Piece struct and the Square struct that should already be in the cache itself (they are related to the move that i've just executed). I avoid that way to have to compute an address on the Zobrist table at any move. The paddb should take only 1 clock cycle so it is very fast.

so, instead to have a Zobrist key array is like to have a Zobrist function:

OldKey = Zobrist(piece_key, source_square_key)
NewKey = Zobrist(piece_key, destination_square_key)
PositionKey = PositionKey ^ OldKey ^ NewKey

where Zobrist(a, b) = a +' b

If i capture a piece, i just xor with the last PK of captured piece, that i save in Piece structure at any move.

I like to test for new way to do anything

I'd much prefer to access a from and to value from an array of zobrist random numbers as opposed to doing any sort of function call, which will probably be slower... There are not that many zobrist random numbers. In fact, something like 12 * 64. That will fit into cache easily and be quite fast to use.

[stegemma]

...I'd much prefer to access a from and to value from an array of zobrist random numbers as opposed to doing any sort of function call, which will probably be slower... There are not that many zobrist random numbers. In fact, something like 12 * 64. That will fit into cache easily and be quite fast to use.

Mine is not a function call. The function is just for the sample, to explain how i think about that. I've done this logic:

for standard Zobrist array:
- i need a piece type index
- i need a square index
- i should combine both to access Zobrist array

that's not so bad, but i don't have piece type index and square index, only pointers (to piece and to square). In my implementation, retrieving index from pointers to use them to access an array is not so good. That's not true for standard implementations, of course, where you have piece/square indexes. Of course i could store piece and square indexes in piece/square struct, retrieving them and at end access the array. I can try this way and let you know if something change, in TT hits and/or speed.

[bob]

...I'd much prefer to access a from and to value from an array of zobrist random numbers as opposed to doing any sort of function call, which will probably be slower... There are not that many zobrist random numbers. In fact, something like 12 * 64. That will fit into cache easily and be quite fast to use.

Mine is not a function call. The function is just for the sample, to explain how i think about that. I've done this logic:

for standard Zobrist array:
- i need a piece type index
- i need a square index
- i should combine both to access Zobrist array

that's not so bad, but i don't have piece type index and square index, only pointers (to piece and to square). In my implementation, retrieving index from pointers to use them to access an array is not so good. That's not true for standard implementations, of course, where you have piece/square indexes. Of course i could store piece and square indexes in piece/square struct, retrieving them and at end access the array. I can try this way and let you know if something change, in TT hits and/or speed.

I don't quite follow what you are doing. In my case, I have an array

random[12][64], where there are 12 distinct piece types, and 64 possible squares a piece can be on. To move a white knight from f3 to g5, I do this:

zobrist_signature ^= random[white knight][f3];
zobrist_signature ^= random[white knight][g5];

and I am done. When I unmake that move, I do this:

zobrist_signature ^= random[white knight][g5];
zobrist_signature ^= random[white knight][f3];

And I am done. And the order of the above is irrelevant, although I did it in the order the piece moves for clarity. Is that what you are doing? If so, that is how everybody is doing it.