loop detection and hash table

[TAILLE]

Hi,

I am still working hard to improve my algorithm in order to efficiently demonstrate that a given position is a draw. I resolved a number of problems including the well-known GHI problem and I discovered another problem you may not know.


Black to play

In the above position I guess a lot of programs demonstrate the draw by the sequence :
1...11-02 2.23-19 02-07 3.19-23 07-02 = (loop)

But what about the following position :

Black to play

Any human sees immediatly the draw by one of the 2 following sequence :
I) 1...11-02 2.32-19 02-07 3.19-23 07-02 4.23-19 = (loop)
II) 1...11-07 2.32-23 07-02 3.23-19 02-07 4.19-23 = (loop)

Is your algorithm able to find this draw ?

The point is the following :

Analyse at depth 4 plies :
I) After 1...11-02 2.32-19 02-07 3.19-23 you concludes correctly that you reach a position with a big advantage to white
II) After 1...11-07 2.32-23 07-02 3.23-19 you concludes also correctly that you reach a position with a big advantage to white

During sequence I) you save in TT that position A reached after 1...11-02 2.32-19 gives a big advantage to white at depth 2 plies
During sequence II) you save in TT that position B reached after 1...11-07 2.32-23 gives a big advantage to white at depth 2 plies

Analyse at depth 6 plies :
I) After 1...11-02 2.32-19 02-07 3.19-23 you reach position B with 2 plies remaining. You can then trust TT table and conclude without further moves that this sequence gives a big advantage to white. In addition you store in the TT that position A reached after 1...11-02 2.32-19 gives a big advantage to white at depth 4
II) After 1...11-07 2.32-23 07-02 3.23-19 you reach position A with 2 plies remaining. You can then trust TT table ...

This scenario will be repeated when analysing at depth 8, 10 ... and you see you will never find the draw.

Of course this example is very simple and in practise the problem will occur between far more than two positions (here A and B) : a bad use of the TT will prevent you to find a very easy draw.

Did you know this problem ?
Did you solve it ?

[Rein Halbersma]

Hi,
But what about the following position :

Black to play

Of course this example is very simple and in practise the problem will occur between far more than two positions (here A and B) : a bad use of the TT will prevent you to find a very easy draw.

Did you know this problem ?
Did you solve it ?

Very nice position! The symmetry between the two variants is indeed blocking the detection of the repetition draw. I guess the problem was known: in Kishimoto's PhD thesis about the solution for the GHI-problem, it is explicitly stated that heuristic scores are not guaranteed to be correct. Only proven (WIN/DRAW/LOSS) scores are free from false repetition draws. So your example shows that indeed a repetition draw can be missed through these nasty hash effects.

Did you solve this? Can you give us a hint?

Rein

PS My program is acting weird on both positions! The draw detection code is triggered even in the second one, but I will need to debug this to find out along which paths.

[Ed Gilbert]

Did you know this problem ?
Did you solve it ?

Hi Gerard,

Kingsrow does not have any explicit code to avoid the GHI problem, but it happens that it correctly detects repetition draws in these 2 examples. In general, though, it can be vulnerable to the GHI poblem. I tend to feel that the cure is worse than the disease, as solving the problem requires encoding additional path information into transposition table nodes, which is some search speed overhead as well as making tt nodes larger and thus allowing fewer nodes for a given memory usage.

-- Ed

[TAILLE]

Did you know this problem ?
Did you solve it ?

Hi Gerard,

Kingsrow does not have any explicit code to avoid the GHI problem, but it happens that it correctly detects repetition draws in these 2 examples. In general, though, it can be vulnerable to the GHI poblem. I tend to feel that the cure is worse than the disease, as solving the problem requires encoding additional path information into transposition table nodes, which is some search speed overhead as well as making tt nodes larger and thus allowing fewer nodes for a given memory usage.

-- Ed

Ed, Rein etc...

Before solving the problem I had the same opinion as Ed. but I discovered that the problem can be soved without extending the hash table. I only have to manage additionnal information in the search tree but not in the hash table. The point is to store in the hash table an information which is completely independant of the predecessors. As exemple, when you enter in a cycle for the first time, only the position by which the cycle is entered is marked as a draw.
Of course some CPU time is required to manage the additionnal information but the additional code is executed only for positions in which it exists at least one king in each side. As a consequence the introduction of such new mechanism is quite negligeable for handling the other kind of positions.

For the time being I have to finish the corresponding coding and I am not yet able to demonstrate a real improvment. I have to wait some more days.

Happy Xmas for you and your family

[MichelG]

Nice position

Dragon only checked for draw by repetition by comparing to the positions that have occurred during gameplay, but not those played during the search, and found the position very favorable to black until 9 ply.

I solved the issue without relying on the hashtables; I added a bit of code that compares the current position against every position of previous depths (So at depth 10, i compare against depth 0,2,4,6,8)

Now at 5 ply, it judges the position is drawish.

Michel

[Rein Halbersma]

Nice position

Dragon only checked for draw by repetition by comparing to the positions that have occurred during gameplay, but not those played during the search, and found the position very favorable to black until 9 ply.

I solved the issue without relying on the hashtables; I added a bit of code that compares the current position against every position of previous depths (So at depth 10, i compare against depth 0,2,4,6,8)

Now at 5 ply, it judges the position is drawish.

Michel

Hi Michel,

I also have a small array of previously seen positions during the search. However, the point of Gerard's position is that this little piece of history checking during the search could not get called because of hash table effects.

So does Dragon see this position as drawish because of endgame dbs or because it triggers the repetition code?

BTW, why do you compare against depth = 8? A repetition needs at least 4 plies... So at depth = 10, you only need to check the history at depth = 6, 4, 2, 0.

Rein

[MichelG]

I also have a small array of previously seen positions during the search. However, the point of Gerard's position is that this little piece of history checking during the search could not get called because of hash table effects.

I didn't understand that; I can't see how hash table effects prevent this type of history check. In dragon at least it's not possible, but i guess it can happen with a different parallel implementation. (dragon uses the abdada algorithm)

So does Dragon see this position as drawish because of endgame dbs or because it triggers the repetition code?

BTW, why do you compare against depth = 8? A repetition needs at least 4 plies... So at depth = 10, you only need to check the history at depth = 6, 4, 2, 0.

Rein

You are right with the check against depth=8, i'll remove that from my code In the given position, it detects the draw by repetition, but it can't find the database draw. (at least not in the short search i tried)

Michel

[Rein Halbersma]

I also have a small array of previously seen positions during the search. However, the point of Gerard's position is that this little piece of history checking during the search could not get called because of hash table effects.

I didn't understand that; I can't see how hash table effects prevent this type of history check. In dragon at least it's not possible, but i guess it can happen with a different parallel implementation. (dragon uses the abdada algorithm)

Gerard's position has 2 variations. Only the positions of the white and black king are essential for the repetition. In his notation: A = (black king on 2, white king on 19), B = (7, 23). Let's also denote C = (7, 19) and D = (2, 23). Call the root of the diagram X = (11, 32), and also Y = (2, 32) and Z = (7, 32).

A full-width 6-ply search would show:
I) X -> Y -> A -> C -> B -> D -> A (== repetition on A)
II) X -> Z -> B -> D -> A -> C -> B (== repetition on B)

The point is that with a hash table and iterative deepening, the two variations may mask the repetition in the other variation.

Do a 4 ply search:
I) X -> Y -> A -> C -> B (store A with white advantage)
II) X -> Z -> B -> D -> A (store B with white advantage)

Now the 6 ply search:
I) X -> Y -> A (here the hash sees A already stored at lower depth -> return)
II) X -> Z -> B (here the hash sees B already stored at lower depth -> return)

So the repetitions that should happen at ply=6 never occurs.

Does your program find the repetitions on a 6-ply search? How does it circumvent the hash effect?

[gwiesenekker]

GWD sees the draw immediately as GWD does not use transposition table scores in non-minimal window searches and does not store draw scores in the transposition table because draw-by-repetition scores are search history dependent.

Gijsbert

[Rein Halbersma]

GWD sees the draw immediately as GWD does not use transposition table scores in non-minimal window searches and does not store draw scores in the transposition table because draw-by-repetition scores are search history dependent.

Gijsbert

Can you explain in more detail why you don't use the hash table along the PV?

I also pass the complete PV as a separate array through the recursive search. After each depth iteration at the root, I store this PV into the hash table. Immediately thereafter, I search at the next depth and use the PV without any problems.

Interestingly, there is an ongoing thread at open-chess.org where some people have made a Stockfish patch that also uses the hash table along the PV (the original version doesn't).

Rein

[gwiesenekker]

The reason is that I want to make sure that GWD always returns a full PV and that the root score is always equal to the score of the position at the end of the PV (this makes it much easier to understand why GWD plays a certain move). If GWD would use the transposition table score in non-minimal window searches the PV can be cut short if GWD hits a true score, and/or the root score might be different from the score at the end of the PV if GWD used a transposition table score. A simple example is a fail-high based on a high transposition table score, but that transposition table entry gets overwritten during the research, causing the search to fail-low.
I also have the impression that GWD searches more efficiently because the full PV is always available for the next iteration and is very stable.

Gijsbert

[TAILLE]

The reason is that I want to make sure that GWD always returns a full PV and that the root score is always equal to the score of the position at the end of the PV (this makes it much easier to understand why GWD plays a certain move). If GWD would use the transposition table score in non-minimal window searches the PV can be cut short if GWD hits a true score, and/or the root score might be different from the score at the end of the PV if GWD used a transposition table score. A simple example is a fail-high based on a high transposition table score, but that transposition table entry gets overwritten during the research, causing the search to fail-low.
I also have the impression that GWD searches more efficiently because the full PV is always available for the next iteration and is very stable.

Gijsbert

What do you think may happen if GWD reaches my example position in a variation (I mean not in the pv) ? Could the hashtable prevent the detection of the loop ?

[gwiesenekker]

A good point. The example I gave 'a fail-high based on a high transposition table score, but that transposition table entry gets overwritten during the research, causing the search to fail-low' can also occur in the minimal-window searches. As GWD does use the transposition table during minimal-window searches it can happen that a minimal-window search fails high or fails low because of a transposition table entry. If the minimal-window search fails high, the research could fail low if the transposition table entry gets overwritten, but GWD does not research with a window (fail-high-score, beta), but with a window (best-pv-score, beta).
So if GWD reaches your example position in a minimal window search, yes, the transposition table could prevent detection of the loop. If the draw would still be detected depends on the static evaluation of the position: if it makes it into the PV yes, otherwise not, so this is something that needs to be fixed.

Gijsbert

[TAILLE]

Hi,


Black to play

I have just finished the coding of a new loop detection algorithm which is quite efficient in the above example and a lot of other positions. Normaly this algorithm resolves also the GHI problem.

For test purpose I am looking for positions that may cause difficulties with potential loops or GHI problem.
Do you know positions for which you imagine a program may have difficulties in handling potential loops either inside the generated tree or due to positions already seen in the previons moves of the game played?

[Rein Halbersma]

Hi,


Black to play

I have just finished the coding of a new loop detection algorithm which is quite efficient in the above example and a lot of other positions. Normaly this algorithm resolves also the GHI problem.

For test purpose I am looking for positions that may cause difficulties with potential loops or GHI problem.
Do you know positions for which you imagine a program may have difficulties in handling potential loops either inside the generated tree or due to positions already seen in the previons moves of the game played?

That's very interesting! Could you explain how your algorithm works?