handling repetition in the hash question

[Uri Blass]

The problem that I think about is the following:

imagine that your program got the following position in the search

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

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

[hgm]

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...

[Harald]

The problem that I think about is the following:

imagine that your program got the following position in the search

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

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

I do nothing. That is normal behaviour and has nothing to do with repetition.
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 

I am not even sure without looking in the code whether I react to the
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

[Uri Blass]

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

[Uri Blass]

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

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

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

[Allard Siemelink]

I found that movei could not find the draw by f5 in the following position in the same depth

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

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

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.
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

[bob]

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...

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?

[Uri Blass]

I found that movei could not find the draw by f5 in the following position in the same depth

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

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

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.
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

Detecting draw score at depth 15 is very good.
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

[Allard Siemelink]

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

You understand correctly.
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:

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

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

[Uri Blass]

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