Repetitions/50 moves and TT

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Sergei S. Markoff
Posts: 224
Joined: Mon Sep 12, 2011 9:27 pm
Location: Moscow, Russia
Contact:

Repetitions/50 moves and TT

Threefold repetition and 50-moves rule are the worst enemies of Transposition Table. Formally, the same positions (from the point of view of the board state) can be different due to different preceeding "silent" moves. That's why full transposition probe can lead to error (usually too later seeng the repetition or 50th move). One of the probable solutions is to mark TT evaluations with some flag that indicates that score of TT position (1) depends of draw node, that depends on node preceeding to (1). It should be restricted to use this score to cut probing node. Anyone tried it?
The Force Be With You!

bob
Posts: 20817
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Repetitions/50 moves and TT

Sergei S. Markoff wrote:Threefold repetition and 50-moves rule are the worst enemies of Transposition Table. Formally, the same positions (from the point of view of the board state) can be different due to different preceeding "silent" moves. That's why full transposition probe can lead to error (usually too later seeng the repetition or 50th move). One of the probable solutions is to mark TT evaluations with some flag that indicates that score of TT position (1) depends of draw node, that depends on node preceeding to (1). It should be restricted to use this score to cut probing node. Anyone tried it?
how can it work? This problem happens in two ways. You think a score is not a draw, but it is, because the path somewhere between the root and tip where you scored it had no repetition, but the path between the root and tip where you look it up does. Or the path that ends at the repetition and is stored in the transposition table might not be the path that you followed to reach this position on the probe and the draw score is false.

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Repetitions/50 moves and TT

Sergei S. Markoff wrote:Threefold repetition and 50-moves rule are the worst enemies of Transposition Table. Formally, the same positions (from the point of view of the board state) can be different due to different preceeding "silent" moves. That's why full transposition probe can lead to error (usually too later seeng the repetition or 50th move). One of the probable solutions is to mark TT evaluations with some flag that indicates that score of TT position (1) depends of draw node, that depends on node preceeding to (1). It should be restricted to use this score to cut probing node. Anyone tried it?
Your post is interesting because we were recently reported a bug in SF where the engine is unable to mate in a KRK position, we think this could be due to some subtle interaction between 50 moves rule and TT because if you cold start the engine and set it on any of the troubled positions SF immediately finds the correct continuation.

Here is the game (against Houdini):

[Event "DFT8"]
[Site "?"]
[Date "2011.09.06"]
[Round "1"]
[White "Stockfish 2.1.1 JA 64bit"]
[Black "Houdini 1.5a x64"]
[Result "1/2-1/2"]
[ECO "A14"]
[Annotator "-0.12;-0.04"]
[PlyCount "253"]
[EventDate "2011.09.06"]
[EventType "tourn"]
[TimeControl "2400"]

{Intel(R) Core(TM) i7-2600K CPU @ 3.40GHz 3519 MHz W=19.7 plies; 10,021kN/s;
DFritz12.ctg B=23.5 plies; 16,235kN/s; 337,862 TBAs; DFritz12.ctg} 1. Nf3 {
[%eval 0,0] [%emt 0:00:00]} d5 {[%eval 0,0] [%emt 0:00:00]} 2. c4 {[%eval 0,0]
[%emt 0:00:00]} e6 {[%eval 0,0] [%emt 0:00:00]} 3. b3 {[%eval 0,0] [%emt 0:00:
00]} Nf6 {[%eval 0,0] [%emt 0:00:00]} 4. g3 {[%eval 0,0] [%emt 0:00:00]} c5 {
[%eval 0,0] [%emt 0:00:00]} 5. Bg2 {[%eval 0,0] [%emt 0:00:00]} Nc6 {[%eval 0,
0] [%emt 0:00:00]} 6. O-O {[%eval 0,0] [%emt 0:00:00]} Be7 {[%eval 0,0] [%emt
0:00:00]} 7. Bb2 {[%eval 0,0] [%emt 0:00:00]} O-O {[%eval 0,0] [%emt 0:00:00]}
8. e3 {[%eval 0,0] [%emt 0:00:00]} b6 {[%eval 0,0] [%emt 0:00:00]} 9. Nc3 {
[%eval 0,0] [%emt 0:00:00]} dxc4 {[%eval 0,0] [%emt 0:00:00]} 10. bxc4 {[%eval
0,0] [%emt 0:00:00]} Bb7 {[%eval 0,0] [%emt 0:00:00]} 11. Qe2 {[%eval -12,27]
[%emt 0:00:56]} Qc7 {[%eval -4,23] [%emt 0:00:58]} 12. d3 {[%eval 0,26] [%emt
0:00:42] (Rab1)} Rad8 {[%eval -3,23] [%emt 0:01:14] (a6)} 13. Rfd1 {[%eval 0,
29] [%emt 0:00:55] (Rab1)} h6 {[%eval 0,22] [%emt 0:01:07] (Na5)} 14. Ne1 {
[%eval 16,27] [%emt 0:00:53] (Rab1)} Na5 {[%eval -8,21] [%emt 0:00:33] (Ne8)}
15. f4 {[%eval 20,27] [%emt 0:01:13] (Nb5)} Bxg2 {[%eval -8,22] [%emt 0:00:39]
(Rb8)} 16. Kxg2 {[%eval 12,29] [%emt 0:01:46] (Qxg2)} a6 {[%eval -11,24] [%emt
0:00:40] (Qb7+)} 17. Nf3 {[%eval 28,28] [%emt 0:00:57]} Rb8 {[%eval -11,23]
[%emt 0:00:40]} 18. Nb1 {[%eval 16,27] [%emt 0:00:38]} Nd7 {[%eval -9,22]
[%emt 0:00:50] (b5)} 19. Nbd2 {[%eval 20,25] [%emt 0:00:41]} b5 {[%eval -8,21]
[%emt 0:00:57]} 20. Rab1 {[%eval 20,25] [%emt 0:01:11]} Rfd8 {[%eval -11,21]
[%emt 0:00:45]} 21. h3 {[%eval 24,25] [%emt 0:02:44] (a3)} Nc6 {[%eval -17,20]
[%emt 0:00:35]} 22. Rdc1 {[%eval 24,26] [%emt 0:01:49] (Ne4)} b4 {[%eval -23,
20] [%emt 0:00:28] (Qb7)} 23. Ne4 {[%eval 16,24] [%emt 0:01:22] (d4)} Rbc8 {
[%eval -22,20] [%emt 0:00:37]} 24. Rf1 {[%eval 16,25] [%emt 0:00:49] (g4)} f5 {
[%eval -19,21] [%emt 0:00:33] (Nb6)} 25. Ned2 {[%eval 0,26] [%emt 0:00:39]
(Nf2)} Nb6 {[%eval -16,20] [%emt 0:00:26] (a5)} 26. Nb3 {[%eval 16,25] [%emt 0:
00:52] (Ba1)} a5 {[%eval -6,21] [%emt 0:01:20]} 27. e4 {[%eval 8,27] [%emt 0:
00:30] (d4)} Qd7 {[%eval -31,22] [%emt 0:00:40] (Bf8)} 28. Rbd1 {[%eval 0,28]
[%emt 0:00:37]} Na4 {[%eval -23,23] [%emt 0:00:46]} 29. Ba1 {[%eval 0,28]
[%emt 0:00:47]} Nc3 {[%eval -23,23] [%emt 0:00:24]} 30. Bxc3 {[%eval -16,30]
[%emt 0:00:34]} bxc3 {[%eval -24,22] [%emt 0:00:00]} 31. Qc2 {[%eval -24,30]
[%emt 0:00:31]} a4 {[%eval -21,22] [%emt 0:00:23]} 32. Nc1 {[%eval 0,30] [%emt
0:00:51]} Rb8 {[%eval -24,22] [%emt 0:00:23] (Nd4)} 33. Qxc3 {[%eval 0,31]
[%emt 0:00:47]} Nd4 {[%eval -33,23] [%emt 0:00:32]} 34. Nxd4 {[%eval -28,31]
[%emt 0:01:56]} cxd4 {[%eval -33,23] [%emt 0:00:36]} 35. Qe1 {[%eval -36,25]
[%emt 0:00:25]} Rb2+ {[%eval -28,23] [%emt 0:00:34] (Rb1)} 36. Rf2 {[%eval -36,
27] [%emt 0:00:29]} Rdb8 {[%eval -51,23] [%emt 0:00:28]} 37. exf5 {[%eval -28,
28] [%emt 0:00:23]} exf5 {[%eval -48,24] [%emt 0:00:25]} 38. Qe5 {[%eval -66,
29] [%emt 0:01:39]} Ba3 {[%eval -47,25] [%emt 0:00:45] (Qc6+)} 39. Rxb2 {
[%eval -32,30] [%emt 0:00:37]} Rxb2+ {[%eval -46,26] [%emt 0:00:22]} 40. Ne2 {
[%eval -20,31] [%emt 0:00:34]} Be7 {[%eval -38,25] [%emt 0:01:16]} 41. Kf3 {
[%eval 0,30] [%emt 0:00:52]} Bf6 {[%eval -42,26] [%emt 0:00:19]} 42. Qd5+ {
[%eval 0,31] [%emt 0:00:22]} Qxd5+ {[%eval -42,25] [%emt 0:00:00]} 43. cxd5 {
[%eval 0,27] [%emt 0:00:01]} Rxa2 {[%eval -20,27] [%emt 0:02:00]} 44. g4 {
[%eval 0,32] [%emt 0:00:18]} fxg4+ {[%eval -21,27] [%emt 0:01:04]} 45. hxg4 {
[%eval 0,30] [%emt 0:00:19]} Kf7 {[%eval -21,26] [%emt 0:00:53] (a3)} 46. Ng3 {
[%eval 0,31] [%emt 0:00:18]} a3 {[%eval -15,26] [%emt 0:00:46]} 47. Ne4 {
[%eval 0,30] [%emt 0:00:17]} Rc2 {[%eval -17,26] [%emt 0:00:15] (Ke7)} 48. Rb1
{[%eval 4,29] [%emt 0:00:15] (Nxf6)} a2 {[%eval 3,23] [%emt 0:00:15] (Rb2)} 49.
Rb7+ {[%eval 56,29] [%emt 0:00:16]} Be7 {[%eval 3,26] [%emt 0:00:17] (Kf8)} 50.
Ra7 {[%eval 96,31] [%emt 0:00:18]} Kf8 {[%eval 3,26] [%emt 0:00:20]} 51. d6 {
[%eval 96,32] [%emt 0:00:18] (Ra8+)} Bd8 {[%eval 6,24] [%emt 0:00:13]} 52. g5 {
[%eval 60,32] [%emt 0:00:28]} hxg5 {[%eval 11,25] [%emt 0:00:19]} 53. Nxg5 {
[%eval 80,34] [%emt 0:00:12]} Bxg5 {[%eval 10,24] [%emt 0:00:00]} 54. fxg5 {
[%eval 80,37] [%emt 0:00:12]} Ke8 {[%eval 9,30] [%emt 0:00:12]} 55. Ke4 {
[%eval 52,35] [%emt 0:00:13]} Kd8 {[%eval 9,31] [%emt 0:00:12] (Rg2)} 56. Kxd4
{[%eval 52,37] [%emt 0:00:14] (Ra8+)} Rb2 {[%eval 9,30] [%emt 0:00:15] (Re2)}
57. Ke5 {[%eval 707,32] [%emt 0:00:13] (Kd5)} Re2+ {[%eval 130,30] [%emt 0:02:
07] (Ke8)} 58. Kf5 {[%eval 722,36] [%emt 0:00:10] (Kd5)} Kc8 {[%eval 248,21]
[%emt 0:00:22] (Ke8)} 59. d7+ {[%eval 1352,35] [%emt 0:00:43]} Kd8 {[%eval 248,
20] [%emt 0:00:00]} 60. Kg6 {[%eval 1551,31] [%emt 0:00:13]} Re5 {[%eval 303,
24] [%emt 0:01:42]} 61. Rxa2 {[%eval 7708,32] [%emt 0:00:14]} Kxd7 {[%eval 403,
23] [%emt 0:01:24] (Rd5)} 62. Ra7+ {[%eval 8277,36] [%emt 0:00:09]} Kc6 {
[%eval 422,22] [%emt 0:00:54] (Ke6)} 63. Rxg7 {[%eval 8298,37] [%emt 0:00:12]}
Re1 {[%eval 432,21] [%emt 0:00:06] (Rd5)} 64. Ra7 {[%eval 11865,37] [%emt 0:00:
09]} Rb1 {[%eval 455,20] [%emt 0:00:09] (Rg1)} 65. Kg7 {[%eval 9696,30] [%emt
0:00:07] (d4)} Kd6 {[%eval 561,20] [%emt 0:00:14]} 66. g6 {[%eval 11796,29]
[%emt 0:00:11]} Rf1 {[%eval 1156,23] [%emt 0:00:57] (Ke6)} 67. Kh7 {[%eval
11897,32] [%emt 0:00:28] (Rb7)} Kc5 {[%eval 1521,22] [%emt 0:00:47] (Rh1+)} 68.
g7 {[%eval 8924,24] [%emt 0:00:09]} Rh1+ {[%eval 1537,20] [%emt 0:00:10]} 69.
Kg6 {[%eval 32676,23] [%emt 0:00:24]} Kb6 {[%eval 1643,21] [%emt 0:00:07]
(Rg1+)} 70. Re7 {[%eval 32678,23] [%emt 0:00:02] (g8Q)} Rg1+ {[%eval 32728,21]
[%emt 0:00:09]} 71. Kh7 {[%eval 32672,14] [%emt 0:00:00] (Kf7)} Rh1+ {[%eval
32708,20] [%emt 0:00:04]} 72. Kg8 {[%eval 11845,24] [%emt 0:00:00]} Rh3 {
[%eval 32728,22] [%emt 0:00:03] (Rf1)} 73. Kf8 {[%eval 32686,16] [%emt 0:00:00]
(Rf7)} Rf3+ {[%eval 32728,30] [%emt 0:00:16]} 74. Rf7 {[%eval 32688,16] [%emt
0:00:00] (Ke8)} Rxd3 {[%eval 32734,35] [%emt 0:00:03] (Rg3)} 75. g8=Q {[%eval
32686,10] [%emt 0:00:00]} Rd8+ {[%eval 32734,1] [%emt 0:00:00]} 76. Kg7 {
[%eval 32688,10] [%emt 0:00:00]} Rxg8+ {[%eval 32736,1] [%emt 0:00:00]} 77.
Kxg8 {[%eval 32690,8] [%emt 0:00:00]} Kc5 {[%eval 32738,1] [%emt 0:00:00] (Ka6)
} 78. Rg7 {[%eval 32696,5] [%emt 0:00:00]} Kd4 {[%eval 32738,1] [%emt 0:00:00]
(Kb6)} 79. Rg3 {[%eval 32696,10] [%emt 0:00:00] (Rg4+)} Ke5 {[%eval 32738,1]
[%emt 0:00:00] (Ke4)} 80. Rd3 {[%eval 32724,5] [%emt 0:00:00]} Kf4 {[%eval
32738,1] [%emt 0:00:00] (Kf6)} 81. Kf7 {[%eval 32730,5] [%emt 0:00:00]} Ke4 {
[%eval 32740,1] [%emt 0:00:00]} 82. Rd7 {[%eval 32732,6] [%emt 0:00:00]} Ke5 {
[%eval 32742,1] [%emt 0:00:00]} 83. Ke7 {[%eval 32734,5] [%emt 0:00:00]} Kf5 {
[%eval 32742,1] [%emt 0:00:00]} 84. Kf7 {[%eval 32732,5] [%emt 0:00:00]} Ke5 {
[%eval 0,1] [%emt 0:00:00]} 85. Ke8 {[%eval 32726,5] [%emt 0:00:00]} Ke4 {
[%eval 32740,1] [%emt 0:00:00] (Ke6)} 86. Rd6 {[%eval 32712,8] [%emt 0:00:00]
(Re7+)} Kf5 {[%eval 32740,1] [%emt 0:00:00] (Ke3)} 87. Rd4 {[%eval 32724,5]
[%emt 0:00:00] (Ke7)} Ke6 {[%eval 32740,1] [%emt 0:00:00] (Ke5)} 88. Rd3 {
[%eval 32728,5] [%emt 0:00:00]} Ke5 {[%eval 32738,1] [%emt 0:00:00] (Kf6)} 89.
Kf8 {[%eval 32726,5] [%emt 0:00:00]} Ke4 {[%eval 32738,1] [%emt 0:00:00] (Ke6)}
90. Ra3 {[%eval 32698,10] [%emt 0:00:00]} Kf4 {[%eval 32740,1] [%emt 0:00:00]
(Kd5)} 91. Kf7 {[%eval 32702,9] [%emt 0:00:00]} Ke5 {[%eval 32740,1] [%emt 0:
00:00] (Ke4)} 92. Ra4 {[%eval 32706,6] [%emt 0:00:00]} Kf5 {[%eval 32742,1]
[%emt 0:00:00] (Kd5)} 93. Rd4 {[%eval 32732,5] [%emt 0:00:00]} Ke5 {[%eval
32742,1] [%emt 0:00:00]} 94. Rg4 {[%eval 32708,5] [%emt 0:00:00]} Kf5 {[%eval
32742,1] [%emt 0:00:00] (Kd5)} 95. Rg3 {[%eval 32702,5] [%emt 0:00:00]} Kf4 {
[%eval 32740,1] [%emt 0:00:00] (Ke4)} 96. Rb3 {[%eval 32702,8] [%emt 0:00:00]}
Ke4 {[%eval 32740,1] [%emt 0:00:00]} 97. Rb4+ {[%eval 32704,8] [%emt 0:00:00]}
Ke5 {[%eval 32740,1] [%emt 0:00:00] (Kd5)} 98. Rh4 {[%eval 32704,6] [%emt 0:00:
00]} Kf5 {[%eval 32740,1] [%emt 0:00:00] (Kd5)} 99. Ra4 {[%eval 32708,5] [%emt
0:00:00]} Ke5 {[%eval 32742,1] [%emt 0:00:00]} 100. Rb4 {[%eval 32704,7] [%emt
0:00:00]} Kd5 {[%eval 32742,1] [%emt 0:00:00]} 101. Rh4 {[%eval 32706,5] [%emt
0:00:00]} Ke5 {[%eval 32744,1] [%emt 0:00:00] (Kc5)} 102. Kg8 {[%eval 32706,10]
[%emt 0:00:00]} Ke6 {[%eval 32740,1] [%emt 0:00:00] (Kd5)} 103. Rd4 {[%eval
32720,5] [%emt 0:00:00]} Ke5 {[%eval 32738,1] [%emt 0:00:00] (Ke7)} 104. Rd1 {
[%eval 32724,5] [%emt 0:00:00]} Ke4 {[%eval 32740,1] [%emt 0:00:00] (Kf6)} 105.
Rd2 {[%eval 32720,5] [%emt 0:00:00] (Kf7)} Ke3 {[%eval 32738,1] [%emt 0:00:00]
(Kf5)} 106. Rd5 {[%eval 32716,5] [%emt 0:00:00]} Ke4 {[%eval 32740,1] [%emt 0:
00:00] (Kf3)} 107. Rd6 {[%eval 32716,5] [%emt 0:00:00]} Ke5 {[%eval 32738,1]
[%emt 0:00:00] (Kf3)} 108. Rd2 {[%eval 32720,5] [%emt 0:00:00]} Ke6 {[%eval
32738,1] [%emt 0:00:00] (Kf5)} 109. Rd8 {[%eval 32720,5] [%emt 0:00:00]} Ke7 {
[%eval 32740,1] [%emt 0:00:00]} 110. Rd1 {[%eval 32722,5] [%emt 0:00:00]} Ke6 {
[%eval 32740,1] [%emt 0:00:00] (Kf6)} 111. Rd3 {[%eval 32720,7] [%emt 0:00:00]}
Ke5 {[%eval 32738,1] [%emt 0:00:00] (Ke7)} 112. Rd7 {[%eval 32704,7] [%emt 0:
00:00]} Ke6 {[%eval 32738,1] [%emt 0:00:00]} 113. Rh7 {[%eval 32700,9] [%emt 0:
00:00]} Kd5 {[%eval 32738,1] [%emt 0:00:00] (Ke5)} 114. Rh6 {[%eval 32700,5]
[%emt 0:00:00] (Kf7)} Kd4 {[%eval 32738,1] [%emt 0:00:00] (Kc5)} 115. Rh4+ {
[%eval 32704,5] [%emt 0:00:00]} Ke5 {[%eval 32740,1] [%emt 0:00:00] (Kc5)} 116.
Rh3 {[%eval 32686,10] [%emt 0:00:00]} Ke4 {[%eval 32738,1] [%emt 0:00:00] (Ke6)
} 117. Rc3 {[%eval 32698,10] [%emt 0:00:00]} Kd5 {[%eval 32736,1] [%emt 0:00:
00] (Kd4)} 118. Rf3 {[%eval 32686,7] [%emt 0:00:00]} Ke4 {[%eval 32736,1]
[%emt 0:00:00] (Kd6)} 119. Rh3 {[%eval 32698,6] [%emt 0:00:00]} Kd4 {[%eval
32738,1] [%emt 0:00:00]} 120. Ra3 {[%eval 32700,5] [%emt 0:00:00]} Ke4 {[%eval
32738,1] [%emt 0:00:00] (Kc5)} 121. Ra6 {[%eval 32696,12] [%emt 0:00:00]} Kf5 {
[%eval 32738,1] [%emt 0:00:00] (Kd3)} 122. Ra2 {[%eval 32722,5] [%emt 0:00:00]}
Ke4 {[%eval 32738,1] [%emt 0:00:00] (Ke5)} 123. Rg2 {[%eval 32694,8] [%emt 0:
00:00]} Ke3 {[%eval 32738,1] [%emt 0:00:00] (Kd3)} 124. Rg4 {[%eval 32692,12]
[%emt 0:00:00]} Kf3 {[%eval 32740,1] [%emt 0:00:00] (Ke2)} 125. Rg7 {[%eval
32704,6] [%emt 0:00:00]} Ke4 {[%eval 32740,1] [%emt 0:00:00] (Ke2)} 126. Kf7 {
[%eval 0,100] [%emt 0:00:00]} Kf5 {[%eval 32740,1] [%emt 0:00:00] (Kf3)} 127.
Rg2 {[%eval 0,100] [%emt 0:00:00]} 1/2-1/2

JuLieN
Posts: 2948
Joined: Mon May 05, 2008 10:16 am
Location: Nantes (France)
Contact:

Re: Repetitions/50 moves and TT

I never thought about this problem before, but now that I do, I see that it can only lead to the TT being supplied with false draw scores.

Wouldn't a fix be to never store any draw score in the TT?
"The only good bug is a dead bug." (Don Dailey)
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]

Sergei S. Markoff
Posts: 224
Joined: Mon Sep 12, 2011 9:27 pm
Location: Moscow, Russia
Contact:

Re: Repetitions/50 moves and TT

JuLieN wrote:Wouldn't a fix be to never store any draw score in the TT?
I think it's too excessive measure. At first, draw score can be produced by repetition within main line of the search, that results is stored in TT. Also it's not so easy to distinguish draw score from ordinal eval that equals to draw score.
The Force Be With You!

JuLieN
Posts: 2948
Joined: Mon May 05, 2008 10:16 am
Location: Nantes (France)
Contact:

Re: Repetitions/50 moves and TT

Sergei S. Markoff wrote:
JuLieN wrote:Wouldn't a fix be to never store any draw score in the TT?
I think it's too excessive measure. At first, draw score can be produced by repetition within main line of the search, that results is stored in TT. Also it's not so easy to distinguish draw score from ordinal eval that equals to draw score.
Yes, but at worse it would only mean that in the case of a legit 0-eval you'd have to compute it again and, maybe, lose a chance to get a TT cut-off, but that would be very marginal, would very rarely happen (how many times does an eval function return a perfectly equal score?), and would have no other consequences than a very very tiny decrease of search speed. But it would clean up all the non-legit 0-evals from TT, and hence be much more profitable than damageable.

This is just an idea, not tested yet. But easy to try (just one test: if score!=drawscore then store_in_tt...): I'll do that soon and see how it affects my engine's strength.
"The only good bug is a dead bug." (Don Dailey)
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]

Sergei S. Markoff
Posts: 224
Joined: Mon Sep 12, 2011 9:27 pm
Location: Moscow, Russia
Contact:

Re: Repetitions/50 moves and TT

bob wrote:how can it work?
I have such an idea. Let's add to the eval in TT special flag — "repetitionDependent". During probe we can't use this eval, only TT move.

When obtaining repetition in the beginning of Search(), you should return also ply at which this position previously occured ("repetitionPly").

If you got the search result, with repetitionPly < currentPly, you should store this search result in TT with repetitionDependent mark.

And finally the search() should return as repetitionPly the earliest ply from the results of recursive searches.

I think it's also possible to improve this approach to work better in alpha/beta framework, distinguishing repetitions that fails low and repetitions that fails high... It's neccessary to analyse it deeper...
The Force Be With You!

Sergei S. Markoff
Posts: 224
Joined: Mon Sep 12, 2011 9:27 pm
Location: Moscow, Russia
Contact:

Re: Repetitions/50 moves and TT

JuLieN wrote:Yes, but at worse it would only mean that in the case of a legit 0-eval you'd have to compute it again and, maybe, lose a chance to get a TT cut-off, but that would be very marginal, would very rarely happen (how many times does an eval function return a perfectly equal score?), and would have no other consequences than a very very tiny decrease of search speed. But it would clean up all the non-legit 0-evals from TT, and hence be much more profitable than damageable.

This is just an idea, not tested yet. But easy to try (just one test: if score!=drawscore then store_in_tt...): I'll do that soon and see how it affects my engine's strength.
I think you will have a lot of repetitions within main line of TT move, and this is the worst thing. If some endgames there will be a lot of such repetitions which looks completely safe.
So, about exact values equals to draw? Don't forget about alpha/beta. I think there will be lot of >-1 and <1 evals. Most of the evals in TT will not be exact scores, but lower/higher bound fails.
The Force Be With You!

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Repetitions/50 moves and TT

Sergei S. Markoff wrote:
bob wrote:how can it work?
I have such an idea. Let's add to the eval in TT special flag — "repetitionDependent".
I have a much simpler idea.

DRAW_SCORE_50 = DRAW_SCORE + 1

Given that evaluation grain size is bigger than 1 you are sure that if a search returns DRAW_SCORE_50 it is due to some "50 moves" draw to occurred down in the tree and to be the best one.

If instead search returns DRAW_SCORE it is a normal draw.

I know, it's a bit of an hack but is easy and avoids a lots of TT / search() massages...

Sergei S. Markoff
Posts: 224
Joined: Mon Sep 12, 2011 9:27 pm
Location: Moscow, Russia
Contact:

Re: Repetitions/50 moves and TT

mcostalba wrote:I have a much simpler idea.

DRAW_SCORE_50 = DRAW_SCORE + 1

Given that evaluation grain size is bigger than 1 you are sure that if a search returns DRAW_SCORE_50 it is due to some "50 moves" draw to occurred down in the tree and to be the best one.

If instead search returns DRAW_SCORE it is a normal draw.

I know, it's a bit of an hack but is easy and avoids a lots of TT / search() massages...
It will not work. Because of repetition in the subtree not exactly leads to tree draw score. Lets assume that we have two moves from the current position, one with eval +20 and other with eval +10. If the first will be considered as repetition, the search will return 10 for the node, not zero. So this search result will be repetition-dependent, but not drawish. When you stores this eval in TT and, at the other part of tree, retrieves it (but here that repetition is imposible, due to no such a position in the past) — 10 is the wrong eval.
The Force Be With You!