The problem that I think about is the following:
imagine that your program got the following position in the search
[d]4k3/b7/8/7P/7P/7Q/r6P/5K2 b - - 0 1
imagine that the program searched
Ra1+ Kg2 Ra2+ Kf1
Do you store draw score for the position after Kf1
Draw score is not correct because white is winning by Ke2.
The problem is that not storing draw score may also lead to problems because the program may record draw score after Ra1+ Kg2 Ra2+ (because of the fact that Kf1 cause the program to return draw even without storing it in the hash and there is nothing better)
This score is of course not correct and the program may use this not correct score later in the search to get wrong conclusions.
The alternative is of course after undoing moves from draw by repetition node to store in the hash that the position is not reliable for pruning and not use the hash for pruning but in that case the program may not see a draw because of not trusting correct scores that it got.
I wonder what do you do about it.
Uri
handling repetition in the hash question
Moderator: Ras
-
- Posts: 10787
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
-
- Posts: 28351
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: handling repetition in the hash question
Yes, bad problem...
To avoid this 'hash contamination' Joker only stores scores in hash that the position would have if none of the other tree nodes had been visited yet (but nodes from game history have). This requires the path between first and second occurrence to be run twice, once to deteremene the score with rep-draws included, a second time ignoring them, to fill the hash.
Unfortunately you then get the opposite poblem: it overlooks draws, because positions that are not repeats, but for which the opponent can go to a repeat to secure the draw, are listed as wins, and it might naively play them.
Perhaps this could be fixed by, after each move at game level of the side that wants to draw, retrogradely moving from the new position, look up the positions in the hash, and reduce their score to draw. And then retry all the predecessors of those positions in one-ply forward search to see if the accidentally do not derive their good score from a hash move to a position that just got deprecated, etc. Much like building a tablebase. Haven't tried it yet...
To avoid this 'hash contamination' Joker only stores scores in hash that the position would have if none of the other tree nodes had been visited yet (but nodes from game history have). This requires the path between first and second occurrence to be run twice, once to deteremene the score with rep-draws included, a second time ignoring them, to fill the hash.
Unfortunately you then get the opposite poblem: it overlooks draws, because positions that are not repeats, but for which the opponent can go to a repeat to secure the draw, are listed as wins, and it might naively play them.
Perhaps this could be fixed by, after each move at game level of the side that wants to draw, retrogradely moving from the new position, look up the positions in the hash, and reduce their score to draw. And then retry all the predecessors of those positions in one-ply forward search to see if the accidentally do not derive their good score from a hash move to a position that just got deprecated, etc. Much like building a tablebase. Haven't tried it yet...
-
- Posts: 318
- Joined: Thu Mar 09, 2006 1:07 am
Re: handling repetition in the hash question
I do nothing. That is normal behaviour and has nothing to do with repetition.Uri Blass wrote:The problem that I think about is the following:
imagine that your program got the following position in the search
[d]4k3/b7/8/7P/7P/7Q/r6P/5K2 b - - 0 1
imagine that the program searched
Ra1+ Kg2 Ra2+ Kf1
Do you store draw score for the position after Kf1
Draw score is not correct because white is winning by Ke2.
The problem is that not storing draw score may also lead to problems because the program may record draw score after Ra1+ Kg2 Ra2+ (because of the fact that Kf1 cause the program to return draw even without storing it in the hash and there is nothing better)
This score is of course not correct and the program may use this not correct score later in the search to get wrong conclusions.
The alternative is of course after undoing moves from draw by repetition node to store in the hash that the position is not reliable for pruning and not use the hash for pruning but in that case the program may not see a draw because of not trusting correct scores that it got.
I wonder what do you do about it.
Uri
Every engine does false evaluations sometimes and stores them in the
hash table. If it believes it is one pawn ahead it may in fact lose the game
from this position. Typically later in the iterative search the error is
detected and another value is assigned because with the bigger depth
the hash entry is no longer valid and hash pruning is forbidden.
My weak engine does this (reversed because it is a copy from winboard output):
Code: Select all
9 -4.94 86.8M 6:45.95 Ke8-e7 Qh3-g4 Ra2-a1 Kf1-e2 Ra1-a2 Ke2-d1 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-c3 Ba7-f2 Qg4-g7 Ke7-d6 Qg7-f6 Kd6-c7 Qf6-f4 Kc7-b6 Qf4-d6 Kb6-a7
9 -4.97 73.1M 5:38.32 Ra2-a1 Kf1-e2 Ra1-a2 Ke2-d1 Ra2-a1 Kd1-c2 Ra1-e1 h5-h6 Re1-e2 Kc2-d1 Re2-e5 Qh3-c8 Ke8-e7 Qc8-c7 Ke7-f8 Qc7xe5
9 -4.61 26.7M 2:02.17 Ra2-a1 Kf1-e2 Ra1-a2 Ke2-d1 Ke8-f8 Qh3-f5 Kf8-e7 Qf5-e5 Ke7-f7 h5-h6
8 -4.51 14.7M 1:08.98 Ra2-a1 Kf1-e2 Ra1-a2 Ke2-d1 Ke8-f8 Qh3-f5 Kf8-e7 Qf5-e5 Ke7-f7 h5-h6
8 -4.64 14.6M 1:08.31 Ra2-a1 Kf1-e2 Ra1-a2 Ke2-d1 Ke8-e7 Qh3-c3 Ba7-f2 Qc3-c4 Ra2-b2 Qc4-e2 Rb2xe2 Kd1xe2 Bf2xh4 h2-h3
8 -4.79 11.0M 0:51.21 Ke8-e7 Qh3-c3 Ra2-f2 Kf1-e1 Rf2-f7 h5-h6 Ke7-e6 h4-h5 Rf7-e7 Qc3-h3 Ke6-d5 Ke1-d2
6 -4.74 6.6M 0:30.37 Ke8-e7 Qh3-c3 Ra2-f2 Kf1-e1 Rf2-a2 h5-h6 Ba7-f2 Ke1-f1 Bf2-e1 Kf1xe1 Ke7-d7 h6-h7 Ra2xh2
6 -4.75 6.1M 0:27.75 Ra2-f2 Kf1-e1 Rf2-f7 Qh3-c8 Ke8-e7 h5-h6 Ke7-f6 Ke1-d2 Kf6-e5 Qc8-e8 Ke5-f6 Qe8-c6 Kf6-e5
6 -5.37 5.4M 0:24.53 Ke8-d8 Qh3-d3 Kd8-e7 h5-h6 Ra2-a1 Kf1-g2 Ra1-a2 Kg2-h3 Ra2xh2 Kh3xh2 Ba7-b8 Kh2-g2
6 -0.13 3.4M 0:15.87 Ke8-d8 Kf1-e1 Ba7-f2 Ke1-d1 Kd8-e7 Qh3-d3 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2
6 -0.15 2.4M 0:11.39 Ke8-d8 Kf1-e1 Ba7-f2 Ke1-d1 Kd8-e7 Qh3-d3 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2
6 -0.18 1.7M 0:07.85 Ke8-d8 Kf1-e1 Ba7-f2 Ke1-d1 Kd8-e7 Qh3-d3 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2
5 0.00 1.7M 0:07.76 Ke8-d8 Kf1-e1 Ba7-f2 Ke1-d1 Kd8-e7 Qh3-d3 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2
5 0.00 1.7M 0:07.76 Ke8-d8 Kf1-e1 Ba7-f2 Ke1-d1 Kd8-e7 Qh3-d3 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2 Kd2-d1 Ra2-a1 Kd1-d2 Ra1-a2
5 -3.45 1.6M 0:07.57 Ra2-a1 Kf1-e2 Ra1-a2 Ke2-d1 Ra2-a1 Kd1-c2 Ra1-a2 Kc2-b3 Ra2-e2 Qh3-c8 Ke8-f7 Qc8-f5
5 -3.22 449843 0:02.07 Ra2-a1 Kf1-e2 Ra1-a2 Ke2-d1 Ra2-a1 Kd1-d2 Ke8-e7
4 -3.12 17813 0:00.10 Ra2-a1 Kf1-e2 Ra1-a2 Ke2-d1 Ra2-a1 Kd1-d2 Ke8-e7
4 -3.12 8366 0:00.06 Ra2-a1 Kf1-e2 Ra1-a2 Ke2-d1 Ra2-a1 Kd1-d2 Ke8-e7
3 -3.05 2503 0:00.03 Ra2-a1 Kf1-e2 Ra1-a2 Ke2-e1 Ke8-e7
2 -3.05 1965 0:00.03 Ra2-a1 Kf1-e2 Ra1-a2 Ke2-e1 Ke8-e7
2 -3.82 1313 0:00.01 Ra2-f2
1 -3.46 458 0:00.01 Ra2-f2
first or second repetition. But there is a 0.00 score in the search which
is changed at higher depths.
Why do you think the general problem is worse with repetition draws?
Harald
-
- Posts: 10787
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: handling repetition in the hash question
The reason that it seems to me worse is because in this case the engine may perform worse because of using hash tables when without hash tables it can score repetition as draw.
I think that correct use of hash tables should be productive at fixed depth and having situation when the program need bigger depth because of hash is something that I dislike.
Uri
I think that correct use of hash tables should be productive at fixed depth and having situation when the program need bigger depth because of hash is something that I dislike.
Uri
-
- Posts: 10787
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: handling repetition in the hash question
I simply did not store direct repetition in the hash but stored repetition in case of getting them by search.
I thought about that problem when I tried to add code for better repetition detection in order to detect draws one ply earlier in case of moves like
Ra1-b1 Ra8-b8 Rb1-a1.
I found that movei could not find the draw by f5 in the following position in the same depth
[d]8/3R1P2/1ppP1p2/3r4/8/8/K4k2/8 b - - 0 1
After thinking about the problem I understood that the reason is probably that movei did not store the draws of my smart repetition detection in the hash when earlier I stored them in the hash.
The result is that I am not sure if my code for detecting draws one ply earlier is productive together with hash.
Uri
I thought about that problem when I tried to add code for better repetition detection in order to detect draws one ply earlier in case of moves like
Ra1-b1 Ra8-b8 Rb1-a1.
I found that movei could not find the draw by f5 in the following position in the same depth
[d]8/3R1P2/1ppP1p2/3r4/8/8/K4k2/8 b - - 0 1
After thinking about the problem I understood that the reason is probably that movei did not store the draws of my smart repetition detection in the hash when earlier I stored them in the hash.
The result is that I am not sure if my code for detecting draws one ply earlier is productive together with hash.
Uri
-
- Posts: 297
- Joined: Fri Jun 30, 2006 9:30 pm
- Location: Netherlands
Re: handling repetition in the hash question
I also use a form of early repetition detection, not dissimilar to what Gerd described a couple of months ago. I am doing nothing special with the hash, or it must be that repetition draws are not stored on the ply where they are detected.Uri Blass wrote: I found that movei could not find the draw by f5 in the following position in the same depth
[d]8/3R1P2/1ppP1p2/3r4/8/8/K4k2/8 b - - 0 1
The result is that I am not sure if my code for detecting draws one ply earlier is productive together with hash.
Uri
Bright finds the draw at ply 15, does that look ok?
Code: Select all
[14/52] 11.386 3949k -828 ok/2.2
[15/52] 24.936 8386k -890 Rd5a5+ Ka2b3 Ra5b5+ Kb3c3 Rb5c5+ Kc3d3 f6f5 Rd7a7 Rc5d5+ Kd3c3 Rd5xd6 Qf7f8=Q Rd6d5 Ra7c7 c6c5 Rc7c6 Kf2f3 Qf8f7 Rd5d4 Rc6xb6
[15/52] 27.490 9115k -889 ++2/23 f6f5
[15/52] 30.274 10246k 0 f6f5 Rd7a7 Rd5e5 Rf7f8=R Re5e2+ Ka2b3 Re2e3+ Kb3c4 Re3e4+ Kc4d3 Re4e3+ Kd3d2 Re3e2+ Kd2c3 Re2e3+ Kc3b2 Re3e2+ Kb2c1 Re2e1+ Kc1b2 Re1e2+
[15/52] 30.454 10333k 0 ok/2.6
[16/52] 30.804 10499k 0 f6f5 Rd7a7 Rd5e5 Rf7f8=R Re5e2+ Ka2b3 Re2e3+ Kb3c4 Re3e4+ Kc4d3 Re4e3+ Kd3d2 Re3e2+ Kd2c3 Re2e3+ Kc3b2 Re3e2+ Kb2b1 Re2e1+ Kb1c2 Re1e2+ Kc2b1
[16/52] 31.085 10644k 0 ok/1.0
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: handling repetition in the hash question
I don't see why anyone worries about this. It is just the tip of the iceberg. You get an exact score from the hash. But before you reach that terminal position you encounter a forced draw this time, where when you stored it you did not. That's wrong. Same thing happens for _all_ hash results, because scores are path-dependent due to the repetition and 50 move counter, yet the hash signature does not include the path information. If you don't fix 'em all, why worry about fixing just one case?hgm wrote:Yes, bad problem...
To avoid this 'hash contamination' Joker only stores scores in hash that the position would have if none of the other tree nodes had been visited yet (but nodes from game history have). This requires the path between first and second occurrence to be run twice, once to deteremene the score with rep-draws included, a second time ignoring them, to fill the hash.
Unfortunately you then get the opposite poblem: it overlooks draws, because positions that are not repeats, but for which the opponent can go to a repeat to secure the draw, are listed as wins, and it might naively play them.
Perhaps this could be fixed by, after each move at game level of the side that wants to draw, retrogradely moving from the new position, look up the positions in the hash, and reduce their score to draw. And then retry all the predecessors of those positions in one-ply forward search to see if the accidentally do not derive their good score from a hash move to a position that just got deprecated, etc. Much like building a tablebase. Haven't tried it yet...
-
- Posts: 10787
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: handling repetition in the hash question
Detecting draw score at depth 15 is very good.Allard Siemelink wrote:I also use a form of early repetition detection, not dissimilar to what Gerd described a couple of months ago. I am doing nothing special with the hash, or it must be that repetition draws are not stored on the ply where they are detected.Uri Blass wrote: I found that movei could not find the draw by f5 in the following position in the same depth
[d]8/3R1P2/1ppP1p2/3r4/8/8/K4k2/8 b - - 0 1
The result is that I am not sure if my code for detecting draws one ply earlier is productive together with hash.
Uri
Bright finds the draw at ply 15, does that look ok?
Code: Select all
[14/52] 11.386 3949k -828 ok/2.2 [15/52] 24.936 8386k -890 Rd5a5+ Ka2b3 Ra5b5+ Kb3c3 Rb5c5+ Kc3d3 f6f5 Rd7a7 Rc5d5+ Kd3c3 Rd5xd6 Qf7f8=Q Rd6d5 Ra7c7 c6c5 Rc7c6 Kf2f3 Qf8f7 Rd5d4 Rc6xb6 [15/52] 27.490 9115k -889 ++2/23 f6f5 [15/52] 30.274 10246k 0 f6f5 Rd7a7 Rd5e5 Rf7f8=R Re5e2+ Ka2b3 Re2e3+ Kb3c4 Re3e4+ Kc4d3 Re4e3+ Kd3d2 Re3e2+ Kd2c3 Re2e3+ Kc3b2 Re3e2+ Kb2c1 Re2e1+ Kc1b2 Re1e2+ [15/52] 30.454 10333k 0 ok/2.6 [16/52] 30.804 10499k 0 f6f5 Rd7a7 Rd5e5 Rf7f8=R Re5e2+ Ka2b3 Re2e3+ Kb3c4 Re3e4+ Kc4d3 Re4e3+ Kd3d2 Re3e2+ Kd2c3 Re2e3+ Kc3b2 Re3e2+ Kb2b1 Re2e1+ Kb1c2 Re1e2+ Kc2b1 [16/52] 31.085 10644k 0 ok/1.0
Latest Movei needs at least depth 19 or depth 20 and more time(maybe I should use more extensions).
If I understand repetition are not stored at the ply that they happen but only one ply earlier(this is exactly what I did and when I tried to add detecting future repetition the result was worse in this position.
Uri
-
- Posts: 297
- Joined: Fri Jun 30, 2006 9:30 pm
- Location: Netherlands
Re: handling repetition in the hash question
You understand correctly.Uri Blass wrote: If I understand repetition are not stored at the ply that they happen but only one ply earlier(this is exactly what I did and when I tried to add detecting future repetition the result was worse in this position.
Uri
Incidentally, I do use check extensions (always 1 ply) and if I turn off the early repeat detection, it needs three more plies and three more minutes to find a position that it evaluates/guesses to be drawn:
[d]8/5R2/1pNr4/8/4k3/1K6/5p2/8 w - - 0 23
Code: Select all
[15/59] 32.677 10574k -903 ok/2.9
[16/59] 40.519 13177k -915 Rd5a5+ Ka2b3 Ra5b5+ Kb3c3 Rb5c5+ Kc3d3 f6f5 Rd7a7 Rc5d5+ Kd3c4 b6b5+ Kc4b4 Rd5xd6 Qf7f8=Q Rd6d4+ Kb4a5 Rd4d5 Ka5b6 c6c5 Kb6xb5 Kf2e3 Kb5c4
[16/59] 51.294 16516k -915 ok/1.6
[17/62] 0:02:24 41385k -1033 Rd5a5+ Ka2b3 Ra5b5+ Kb3c3 Rb5c5+ Kc3d3 f6f5 Rd7a7 Rc5d5+ Kd3c2 Rd5c5+ Kc2b1 Rc5b5+ Kb1a1 Rb5e5 Ra7a2+ Kf2f1 Qf7f8=Q Re5e1+ Ka1b2 Re1e2+ Kb2c3 Re2e3+ Kc3d4 Re3e4+ Kd4d3 Re4f4 Ra2a1+ Kf1f2 d6d7
[17/65] 0:02:49 45351k -1032 ++2/23 f6f5
[17/65] 0:03:23 52983k -18 f6f5 Nf7f8=N f5f4 Nf8h7 f4f3 Nh7f6 Rd5d4 Nf6e8 Kf2e3 Rd7e7+ Ke3f4 Re7f7+ Kf4e3 Ne8g7 Rd4d2+ Ka2b3 f3f2 Ng7f5+ Ke3f3 Nf5h6+ Kf3g2 Rf7g7+ Kg2f3
[17/65] 0:03:24 53385k -18 ok/3.2
[18/65] 0:03:41 57783k 0 f6f5 Nf7f8=N f5f4 Nf8h7 f4f3 Nh7f6 Rd5d4 Nf6e8 Kf2e3 Rd7e7+ Ke3f4 Re7f7+ Kf4e3 Ne8g7 Rd4d2+ Ka2b3 f3f2 Ng7f5+ Ke3f3 Nf5d4++ Kf3e4 Nd4xc6 Rd2xd6
[18/65] 0:03:43 58161k 0 ok/1.1
[19/65] 0:03:59 62942k 0 f6f5 Nf7f8=N f5f4 Nf8h7 f4f3 Nh7f6 Rd5d4 Nf6e8 Kf2e3 Rd7e7+ Ke3f4 Re7f7+ Kf4e3 Ne8g7 Rd4d2+ Ka2b3 f3f2 Ng7f5+ Ke3f3 Nf5d4++ Kf3e4 Nd4xc6 Rd2xd6 Nc6b4
[19/65] 0:04:00 63504k 0 ok/1.1
-
- Posts: 10787
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: handling repetition in the hash question
I may have something wrong in my implementation.
I also extend every relevant check by at least one ply(and part of them may be extended even more than it) but I cannot see the draw at depth 15.
Note that I am unsure what to do about the hash.
I have pruning based on evaluation and other factors.
psuedo code
if (depth<=5)
if (eval is enough bigger than beta and other conditions)
return beta and if the difference is not enough only reduce the depth by 1.
I do not store the results of this pseudo code in the hash(in case of pruning) and I wonder if I should store it in the hash or maybe write it different(some test positions suggest that the results come faster if I store it in the hash but they are less reliable and I may see things at bigger depth in part of the cases).
I also think that it may be better to delay the reduction of the depth by 1 to later nodes when I have more information and decide to do only pruning based on evaluation and other factors when the remaining depth is small.
Uri
I also extend every relevant check by at least one ply(and part of them may be extended even more than it) but I cannot see the draw at depth 15.
Note that I am unsure what to do about the hash.
I have pruning based on evaluation and other factors.
psuedo code
if (depth<=5)
if (eval is enough bigger than beta and other conditions)
return beta and if the difference is not enough only reduce the depth by 1.
I do not store the results of this pseudo code in the hash(in case of pruning) and I wonder if I should store it in the hash or maybe write it different(some test positions suggest that the results come faster if I store it in the hash but they are less reliable and I may see things at bigger depth in part of the cases).
I also think that it may be better to delay the reduction of the depth by 1 to later nodes when I have more information and decide to do only pruning based on evaluation and other factors when the remaining depth is small.
Uri