Transposition table problem

[marion]

For example you must not:

- use a TT score from a larger depth
- use TT for move ordering
- use killer heuristic (the move in the TT might have been computed with different killers; having cutoffs by TT also fills the killers with different values)
- use history tables (same reasons)
- use PV scores (with more extensions) when you probe on non-PV positions
- and much more

It surprises me. I don't use any heuristics mentioned (but I'm planning), apart from using a TT from a larger depth. This would explain, that this difference doesn't occurs when the search depth is small...

[marion]

Well, I expected that my wrong expectations were caused by some bug. But now I starting to thing more and more, that it is not necessary.

[Gerd Isenberg]

It might be helpful to use the almost-standard position for transposition table testing:
[d]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1
This is from Reuben Fine's Basic Chess Endings, position #70. The winning move is 1 Kb1 and a program with a working transpostion subsystem should find the move in under a second.

It is fine to call it Fine #70, but for the record, it is the Lasker-Reichhelm position from a game between World Champion Emanuel Lasker and Gustavus Charles Reichhelm in 1901, described 1932 in Treatise L'opposition et cases conjuguées sont réconciliées (Opposition and Sister Squares are Reconciled), by Vitaly Halberstadt and Marcel Duchamp, and 1941, in Reuben Fine's Basic Chess Endings.

[Desperado]

It might be helpful to use the almost-standard position for transposition table testing:
[d]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1
This is from Reuben Fine's Basic Chess Endings, position #70. The winning move is 1 Kb1 and a program with a working transpostion subsystem should find the move in under a second.

i am not sure that a program not using any move ordering heuristics,
maybe insufficient evaluation terms, and maybe no repetition detection
will solve that even with a working TT, or within the second...
(how many plies for the pawn capture ? about 25 i guess ?? ) but who knows ...

[sje]

It might be helpful to use the almost-standard position for transposition table testing:
[d]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1
This is from Reuben Fine's Basic Chess Endings, position #70. The winning move is 1 Kb1 and a program with a working transpostion subsystem should find the move in under a second.

i am not sure that a program not using any move ordering heuristics,
maybe insufficient evaluation terms, and maybe no repetition detection
will solve that even with a working TT, or within the second...
(how many plies for the pawn capture ? about 25 i guess ?? ) but who knows ...

One second:

Code: Select all

[+0.716/1/0.546/1/0] 1 Kb2
[+0.630/2/0.547/10/0] 1 Kb2 Kb6
[+0.716/3/0.547/33/0] 1 Kb2 Kb6 2 Kc3
[+0.844/4/0.547/95/0] 1 Kb2 Kb6 2 Kc3 Kc7
[+0.828/5/0.547/207/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kc4
[+0.899/6/0.548/377/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kc4 Kd7
[+0.771/7/0.548/776/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kd7 4 Kc4
[+0.902/8/0.549/1,373/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kc4 Kb6 4 Kd3 Kc7
[+0.722/9/0.549/2,183/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kd8 4 Kc4 Kd7 5 Kb5
[+0.776/10/0.550/3,463/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Kc7 5 Ke3 Kd7
[+0.771/11/0.551/4,948/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Kc7 5 Kc3 Kd7 6 Kc4
[+0.776/12/0.553/7,124/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Kb6 5 Ke2 Kc7 6 Ke3 Kd7
[+0.771/13/0.554/9,767/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Kb6 5 Kc2 Kc7 6 Kc3 Kd7 7 Kc4
[+0.854/14/0.557/13,462/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Ka6 5 Kc3 Ka7 6 Kc4 Kb6 7 Kb3 Kb7
[+0.828/15/0.559/18,119/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Ka6 5 Kc3 Ka7 6 Kc4 Kb6 7 Kb3 Kc7 8 Kc4
[+0.790/16/0.563/25,051/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Ka6 5 Kc3 Ka7 6 Kc2 Kb6 7 Kd1 Kc7 8 Kd2 Kb6
[+0.774/17/0.568/33,741/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Ka6 5 Kc3 Ka7 6 Kc2 Kb6 7 Kd1 Kc7 8 Kd2 Kb6 9 Kd3
[+0.902/18/0.579/55,446/0] 1 Kb2 Kb6 2 Kc3 Kb7 3 Kd3 Kc7 4 Kc2 Kb7 5 Kc3 Kc7 6 Kd3 Kb7 7 Ke3 Kc7 8 Ke2 Kd7 9 Kd2 Kc8
[+0.886/19/0.586/65,623/0] 1 Kb2 Kb6 2 Kc3 Kb7 3 Kd3 Kc7 4 Kc2 Kb7 5 Kc3 Kc7 6 Kd3 Kb7 7 Ke3 Kc7 8 Ke2 Kd7 9 Kd2 Kc8 10 Kd3
[+0.854/20/0.622/127,189/23] 1 Kb2 Ka8 2 Kc3 Kb7 3 Kd3 Kc7 4 Kc2 Kb8 5 Kd2 Kc8 6 Ke3 Kd7 7 Ke2 Kd8 8 Kf3 Ke7 9 Kf2 Kf7 10 Ke3 Kf6
[+1.079/20/0.631/142,920/25] 1 Kb1 Ka8 2 Kb2 Ka7 3 Kb3 Kb7 4 Kc3 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kd2 Kd7 8 Kc2 Ke7 9 Kd3 Kf6 10 Kc4 Kg6
[+0.951/21/0.635/147,969/25] 1 Kb1 Ka8 2 Kb2 Ka7 3 Kb3 Kb7 4 Kc3 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kd2 Kd7 8 Kc2 Ke7 9 Kd3 Kf6 10 Kc3 Kg6 11 Kc4
[+1.534/22/0.656/182,991/44] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Ke7 5 Kd3 Kf6 6 Kc4 Kg6 7 Kb5 Kh5 8 Kc6 Kg4 9 Kxd6 Kxf4 10 Kc5 Ke4 11 d6 f4 12 d7
[+1.700/23/0.706/219,923/113] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kf3 Kd7 8 Kg3 Ke7 9 Kh4 Kf6 10 Kh5 Ke7 11 Kg5 Kd7 12 Kxf5
[+1.713/24/0.721/242,397/235] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kf3 Kd7 8 Kg3 Ke7 9 Kh4 Kf6 10 Kh5 Kg7 11 Kg5 Kf7 12 Kxf5 Ke7 13 Kg5
[+1.763/25/0.743/275,601/430] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kf3 Kd7 8 Kg3 Ke7 9 Kh4 Kf6 10 Kh5 Kg7 11 Kg5 Kf7 12 Kxf5 Ke7 13 Kg5 Kd7
[+1.842/26/0.766/308,810/705] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kf3 Kd7 8 Kg3 Ke7 9 Kh4 Kf6 10 Kh5 Kg7 11 Kg5 Kf7 12 Kxf5 Ke7 13 Kg5 Kd7 14 f5
[+1.864/27/0.803/361,783/1,114] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kf3 Kd7 8 Kg3 Ke7 9 Kh4 Kf6 10 Kh5 Ke7 11 Kg5 Kd8 12 Kxf5 Kd7 13 Ke4 Kd8 14 Kd3
[+2.043/28/0.850/423,433/1,786] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kf3 Kd7 8 Kg3 Ke7 9 Kh4 Kf6 10 Kh5 Ke7 11 Kg5 Kd8 12 Kxf5 Kd7 13 Kg5 Kc7 14 f5 Kb6 15 f6
[+2.150/29/0.933/527,228/3,005] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kf3 Kd7 8 Kg3 Ke7 9 Kh4 Kf6 10 Kh5 Ke7 11 Kg5 Kd8 12 Kxf5 Kd7 13 Kg5 Kd8 14 f5 Ke7 15 f6+ Ke8 16 Kf4

[Onno Garms]

Well, I expected that my wrong expectations were caused by some bug. But now I starting to thing more and more, that it is not necessary.

Regression tests a good idea. When you have unexpected differences you should always think about them until you understand what caused them. Using this technique
http://talkchess.com/forum/viewtopic.php?p=410462
you would have found yourself that it's OK to get other moves after the introduction of the TT.

[Desperado]

It might be helpful to use the almost-standard position for transposition table testing:
[d]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1
This is from Reuben Fine's Basic Chess Endings, position #70. The winning move is 1 Kb1 and a program with a working transpostion subsystem should find the move in under a second.

i am not sure that a program not using any move ordering heuristics,
maybe insufficient evaluation terms, and maybe no repetition detection
will solve that even with a working TT, or within the second...
(how many plies for the pawn capture ? about 25 i guess ?? ) but who knows ...

One second:

Code: Select all

[+0.716/1/0.546/1/0] 1 Kb2
[+0.630/2/0.547/10/0] 1 Kb2 Kb6
[+0.716/3/0.547/33/0] 1 Kb2 Kb6 2 Kc3
[+0.844/4/0.547/95/0] 1 Kb2 Kb6 2 Kc3 Kc7
[+0.828/5/0.547/207/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kc4
[+0.899/6/0.548/377/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kc4 Kd7
[+0.771/7/0.548/776/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kd7 4 Kc4
[+0.902/8/0.549/1,373/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kc4 Kb6 4 Kd3 Kc7
[+0.722/9/0.549/2,183/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kd8 4 Kc4 Kd7 5 Kb5
[+0.776/10/0.550/3,463/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Kc7 5 Ke3 Kd7
[+0.771/11/0.551/4,948/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Kc7 5 Kc3 Kd7 6 Kc4
[+0.776/12/0.553/7,124/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Kb6 5 Ke2 Kc7 6 Ke3 Kd7
[+0.771/13/0.554/9,767/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Kb6 5 Kc2 Kc7 6 Kc3 Kd7 7 Kc4
[+0.854/14/0.557/13,462/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Ka6 5 Kc3 Ka7 6 Kc4 Kb6 7 Kb3 Kb7
[+0.828/15/0.559/18,119/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Ka6 5 Kc3 Ka7 6 Kc4 Kb6 7 Kb3 Kc7 8 Kc4
[+0.790/16/0.563/25,051/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Ka6 5 Kc3 Ka7 6 Kc2 Kb6 7 Kd1 Kc7 8 Kd2 Kb6
[+0.774/17/0.568/33,741/0] 1 Kb2 Kb6 2 Kc3 Kc7 3 Kd3 Kb7 4 Kd2 Ka6 5 Kc3 Ka7 6 Kc2 Kb6 7 Kd1 Kc7 8 Kd2 Kb6 9 Kd3
[+0.902/18/0.579/55,446/0] 1 Kb2 Kb6 2 Kc3 Kb7 3 Kd3 Kc7 4 Kc2 Kb7 5 Kc3 Kc7 6 Kd3 Kb7 7 Ke3 Kc7 8 Ke2 Kd7 9 Kd2 Kc8
[+0.886/19/0.586/65,623/0] 1 Kb2 Kb6 2 Kc3 Kb7 3 Kd3 Kc7 4 Kc2 Kb7 5 Kc3 Kc7 6 Kd3 Kb7 7 Ke3 Kc7 8 Ke2 Kd7 9 Kd2 Kc8 10 Kd3
[+0.854/20/0.622/127,189/23] 1 Kb2 Ka8 2 Kc3 Kb7 3 Kd3 Kc7 4 Kc2 Kb8 5 Kd2 Kc8 6 Ke3 Kd7 7 Ke2 Kd8 8 Kf3 Ke7 9 Kf2 Kf7 10 Ke3 Kf6
[+1.079/20/0.631/142,920/25] 1 Kb1 Ka8 2 Kb2 Ka7 3 Kb3 Kb7 4 Kc3 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kd2 Kd7 8 Kc2 Ke7 9 Kd3 Kf6 10 Kc4 Kg6
[+0.951/21/0.635/147,969/25] 1 Kb1 Ka8 2 Kb2 Ka7 3 Kb3 Kb7 4 Kc3 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kd2 Kd7 8 Kc2 Ke7 9 Kd3 Kf6 10 Kc3 Kg6 11 Kc4
[+1.534/22/0.656/182,991/44] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Ke7 5 Kd3 Kf6 6 Kc4 Kg6 7 Kb5 Kh5 8 Kc6 Kg4 9 Kxd6 Kxf4 10 Kc5 Ke4 11 d6 f4 12 d7
[+1.700/23/0.706/219,923/113] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kf3 Kd7 8 Kg3 Ke7 9 Kh4 Kf6 10 Kh5 Ke7 11 Kg5 Kd7 12 Kxf5
[+1.713/24/0.721/242,397/235] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kf3 Kd7 8 Kg3 Ke7 9 Kh4 Kf6 10 Kh5 Kg7 11 Kg5 Kf7 12 Kxf5 Ke7 13 Kg5
[+1.763/25/0.743/275,601/430] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kf3 Kd7 8 Kg3 Ke7 9 Kh4 Kf6 10 Kh5 Kg7 11 Kg5 Kf7 12 Kxf5 Ke7 13 Kg5 Kd7
[+1.842/26/0.766/308,810/705] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kf3 Kd7 8 Kg3 Ke7 9 Kh4 Kf6 10 Kh5 Kg7 11 Kg5 Kf7 12 Kxf5 Ke7 13 Kg5 Kd7 14 f5
[+1.864/27/0.803/361,783/1,114] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kf3 Kd7 8 Kg3 Ke7 9 Kh4 Kf6 10 Kh5 Ke7 11 Kg5 Kd8 12 Kxf5 Kd7 13 Ke4 Kd8 14 Kd3
[+2.043/28/0.850/423,433/1,786] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kf3 Kd7 8 Kg3 Ke7 9 Kh4 Kf6 10 Kh5 Ke7 11 Kg5 Kd8 12 Kxf5 Kd7 13 Kg5 Kc7 14 f5 Kb6 15 f6
[+2.150/29/0.933/527,228/3,005] 1 Kb1 Kb7 2 Kc1 Kc7 3 Kd1 Kd7 4 Kc2 Kc7 5 Kd3 Kb7 6 Ke3 Kc8 7 Kf3 Kd7 8 Kg3 Ke7 9 Kh4 Kf6 10 Kh5 Ke7 11 Kg5 Kd8 12 Kxf5 Kd7 13 Kg5 Kd8 14 f5 Ke7 15 f6+ Ke8 16 Kf4

blindfold

well, i am curious what features are enabled ? i ask because when writing
a engine from scratch, and you are at a point where you have
material+PST evaluater, alphaBeta, and introduce TT (no heuristics,nor any other stuff)
the one second is really reallistic ?

[Onno Garms]

Where the TT problem is a bad example to introduce EventLogger, because the search is expected to go differently, just the results should be the same.

So instead of testing against a version without TT, you would have to test against a version that uses TT but ignores results for the search. If the hit would result in a cutoff, disable logging and TT use until the node is completed

[Desperado]

just for the record.

The last minutes(i hacked my engine,hopefully without bugs) i introduced a plain ab-search, no move ordering beside
mvvLva for captures, using my original q-search.
The evalution was reduced to material + PST.
using my working ( ) TT-Scheme, which in this setup only profits
from TT-Cuts.(setting 256 MB).
no-repetition draw detection,mate distance pruning,no extensions,no prunings ..... plain AB.

now the result: about 18 sec to reach ply 18 which is definitely _NOT_
enough to solve the position....

Michael

[sje]

Repetition detection is strongly recommended for searching any endgame position.