Transposition table problem

Discussion of chess software programming and technical issues.

Moderator: Ras

marion

Re: Transposition table problem

Post by marion »

Onno Garms wrote:
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

Re: Transposition table problem

Post by 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
Posts: 2251
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: Transposition table problem

Post by Gerd Isenberg »

sje wrote: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.
User avatar
Desperado
Posts: 879
Joined: Mon Dec 15, 2008 11:45 am

Re: Transposition table problem

Post by Desperado »

sje wrote: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 ... :)
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: Transposition table problem

Post by sje »

Desperado wrote:
sje wrote: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
User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 7:31 pm
Location: Bonn, Germany

Re: Transposition table problem

Post by Onno Garms »

marion wrote: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.
User avatar
Desperado
Posts: 879
Joined: Mon Dec 15, 2008 11:45 am

Re: Transposition table problem

Post by Desperado »

sje wrote:
Desperado wrote:
sje wrote: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


:lol: 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 ?
User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 7:31 pm
Location: Bonn, Germany

Re: Transposition table problem

Post by 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
User avatar
Desperado
Posts: 879
Joined: Mon Dec 15, 2008 11:45 am

Re: Transposition table problem

Post by 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 ( :wink: ) 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
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: Transposition table problem

Post by sje »

Repetition detection is strongly recommended for searching any endgame position.