loop detection and hash table

[TAILLE]

Hi Rein,

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

I expected this question but I consider it is a secret idea.
At least I will give you a clue : this algorithm is specific to draughts game; it would be very inefficient for chess game!
Of course I accept to tell you the result of this algorithm for any position you choose. Maybe you will discover my secret by some relevant test positions! I noted Bert is skillful for discovering such secret ideas. Good challenge isn't it?

[Rein Halbersma]

Hi Rein,

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

I expected this question but I consider it is a secret idea.
At least I will give you a clue : this algorithm is specific to draughts game; it would be very inefficient for chess game!
Of course I accept to tell you the result of this algorithm for any position you choose. Maybe you will discover my secret by some relevant test positions! I noted Bert is skillful for discovering such secret ideas. Good challenge isn't it?

From your previous posts, I gather that you do not modify the hash table in any way, and only store additional information in the search. I know that this will solve the "draw-first" case of the GHI problem, and the implementation is very easy. But did you also solve the "draw-last" case of the GHI-problem? For a good explanation of those cases see Kishimoto's thesis or the attached paper by Campbell.

It is not very instructive for me to present various positions to you. One reason is that various GHI-problems only occur with a specific move ordering. It's easy to construct examples but it would be hard to let an engine run the variations in the same order as in the example. The other reason is that such "black-box" testing is not much fun to me. If you don't want to explain or discuss the algorithm itself, how can you convince me or others that it is correct? E.g. it is by now standard procedure in the encryption community to only discuss public algorithms. A final reason is that I cannot imagine why you would want to keep it a secret in the first place. Even if it is of scientific interest (which I don't doubt!), I cannot imagine it will have a big performance impact on the overall strength of competing engines should they copy your algorithm.

[TAILLE]

Hi Rein,

From your previous posts, I gather that you do not modify the hash table in any way, and only store additional information in the search. I know that this will solve the "draw-first" case of the GHI problem, and the implementation is very easy. But did you also solve the "draw-last" case of the GHI-problem? For a good explanation of those cases see Kishimoto's thesis or the attached paper by Campbell.

I already know this thesis but I have to confess that I do not quite understand this "draw-last" case. Two lines are described:
line A : X ...Y...X...
line B : X.......Y....
If you first explore line B and you discover a win, that means that after lineB moves X.......Y you discovered a path to the win avoiding position X and that means that lineA up to Y is also a win isn't it.
Can you clarify the problem?

It is not very instructive for me to present various positions to you. One reason is that various GHI-problems only occur with a specific move ordering. It's easy to construct examples but it would be hard to let an engine run the variations in the same order as in the example. The other reason is that such "black-box" testing is not much fun to me. If you don't want to explain or discuss the algorithm itself, how can you convince me or others that it is correct? E.g. it is by now standard procedure in the encryption community to only discuss public algorithms. A final reason is that I cannot imagine why you would want to keep it a secret in the first place. Even if it is of scientific interest (which I don't doubt!), I cannot imagine it will have a big performance impact on the overall strength of competing engines should they copy your algorithm.

You clearly understand my problem. My algorithm is not intending to solve only the loop detection problem. The major point was to build a algorithm that greatly improves the global performances of the program when kings are present in both sides. It was for me a known weakness of Damy because my previous algorithm was optimised for positions with only men and positions with kings on one side only.
I am now running a lot of tests to validate my new specific approach and I will soon be able to give you some results.

[Rein Halbersma]

Hi Rein,

From your previous posts, I gather that you do not modify the hash table in any way, and only store additional information in the search. I know that this will solve the "draw-first" case of the GHI problem, and the implementation is very easy. But did you also solve the "draw-last" case of the GHI-problem? For a good explanation of those cases see Kishimoto's thesis or the attached paper by Campbell.

I already know this thesis but I have to confess that I do not quite understand this "draw-last" case. Two lines are described:
line A : X ...Y...X...
line B : X.......Y....
If you first explore line B and you discover a win, that means that after lineB moves X.......Y you discovered a path to the win avoiding position X and that means that lineA up to Y is also a win isn't it.
Can you clarify the problem?

In the Campbell paper, the lines are slightly different to what you sketch:

line A: root ... X ... Y ... X
line B: root ........Y.....X...

If you search A before B, you can detect the repetition of X, and flag all intermediate positions such as Y. If you then search B and find Y, then you can prevent line B from falsely returning a draw score. This is called the draw-first case. I suppose that this is at least part of your algorithm.

However, if you now search B before A, you will have stored a score for Y in the hash table (there are no repetitions in B). Then you search A and if you encounter Y, you will use the hash table score and you will miss the repetition. It seems impossible to detect this using search tree information when you reach Y in line A.

The Kishimoto-Muller solution solves this by storing path information in the hash table. In particular, if X was proven to be a win/loss in line B, it will use the hash table in line A on the first occurance of position X, and then it will first try the stored hash move of X, and this will prevent the exploration of Y and the second occurance of X in line A.

Note that Campbell claims that the draw-last case is not a problem if B's score is not smaller than a draw. So depending on the score of line B, and also depending on the depth where you will find Y in lines A and B, draw-last could be a problem.

You clearly understand my problem. My algorithm is not intending to solve only the loop detection problem. The major point was to build a algorithm that greatly improves the global performances of the program when kings are present in both sides. It was for me a known weakness of Damy because my previous algorithm was optimised for positions with only men and positions with kings on one side only.
I am now running a lot of tests to validate my new specific approach and I will soon be able to give you some results.

Can you tell me what kind of inefficiencies there are when both sides have multiple kings? It seems that this should not be much different from say rook endgames in chess? I don't think the chess people have special code to handle this situation.

[TAILLE]

In the Campbell paper, the lines are slightly different to what you sketch:

line A: root ... X ... Y ... X
line B: root ........Y.....X...

If you search A before B, you can detect the repetition of X, and flag all intermediate positions such as Y. If you then search B and find Y, then you can prevent line B from falsely returning a draw score. This is called the draw-first case. I suppose that this is at least part of your algorithm.

However, if you now search B before A, you will have stored a score for Y in the hash table (there are no repetitions in B). Then you search A and if you encounter Y, you will use the hash table score and you will miss the repetition. It seems impossible to detect this using search tree information when you reach Y in line A.

Sorry Rein but I continue to have an understanding problem of the point.
line A: root ... X ... Y ... X
line B: root ........Y.....X...
If you search B before A and you find a win that means that after lineB root ........Y.....X, you found a path to the win avoiding the position Y (to avoid a repetition).
If it is the case that means that lineA is also a winning line because after line A: root ... X it exists a winning path avoiding position Y. As a concequence there is no harm to conclude to a win after the "wrong" path line A: root ... X ... Y.

Can you tell me what kind of inefficiencies there are when both sides have multiple kings? It seems that this should not be much different from say rook endgames in chess? I don't think the chess people have special code to handle this situation.

The basic inefficiency is the following : with kings in both sides the program will analyse a lot of lines wtihout any progress (without any conversion). In such situation you have to try and find as soon as possible a good conversion. This is the hint behind my algorithm. For chess game it is very different because it is very common to improve his position by a long suite of non-conversion moves.

[Rein Halbersma]

Sorry Rein but I continue to have an understanding problem of the point.
line A: root ... X ... Y ... X
line B: root ........Y.....X...
If you search B before A and you find a win that means that after lineB root ........Y.....X, you found a path to the win avoiding the position Y (to avoid a repetition).
If it is the case that means that lineA is also a winning line because after line A: root ... X it exists a winning path avoiding position Y. As a concequence there is no harm to conclude to a win after the "wrong" path line A: root ... X ... Y.

When line B returns a win -as was noted by Campbell- the draw-last case is no problem. But what if position Y and ultimately B returns a heuristic score lower than a draw? Whenever that happens, position Y will be looked up in the hash table (it has a lower remaining depth and no exact score) and you will miss the repetition draw.

The basic inefficiency is the following : with kings in both sides the program will analyse a lot of lines wtihout any progress (without any conversion). In such situation you have to try and find as soon as possible a good conversion. This is the hint behind my algorithm. For chess game it is very different because it is very common to improve his position by a long suite of non-conversion moves.

Then my conjecture is that you generate endgame databases during the search for all positions of the kings with the men taken as fixed. This will take care of both the repetitions and also can avoid the tree explosion. For a single king on both sides this can be done very efficiently. Some people also do this in chess (take a look at H.G. Muller's endgame db website), but this is not as efficient as in draughts, especially if there are many sliding pieces.

[BertTuyt]

Interesting remark Rein, as there is only 1 programmer so far who builds (sometimes) DB on the fly.
See below text from 2007

No Ed I am not using the normal engine when in end game with 6 pieces or less on the board. Clearly I agree that it is not possible to find a conversion that need a lot of plies.
I really generate a small DTC db corresponding to the specific men configuration of the live game. In other words I begin a db generation process by generationg all possibles positions with the kings with a classical iterative process to build this DTC db.
With 3 kings the number of position is less than 62500 and, as you know very well, the building of a DTC db of 62500 positions is not a long process !
Gérard

Bert

[Rein Halbersma]

Interesting remark Rein, as there is only 1 programmer so far who builds (sometimes) DB on the fly.
See below text from 2007

No Ed I am not using the normal engine when in end game with 6 pieces or less on the board. Clearly I agree that it is not possible to find a conversion that need a lot of plies.
I really generate a small DTC db corresponding to the specific men configuration of the live game. In other words I begin a db generation process by generationg all possibles positions with the kings with a classical iterative process to build this DTC db.
With 3 kings the number of position is less than 62500 and, as you know very well, the building of a DTC db of 62500 positions is not a long process !
Gérard

Bert

Of course, that's exactly why I wrote that!

[TAILLE]

When line B returns a win -as was noted by Campbell- the draw-last case is no problem. But what if position Y and ultimately B returns a heuristic score lower than a draw? Whenever that happens, position Y will be looked up in the hash table (it has a lower remaining depth and no exact score) and you will miss the repetition draw.

OK Rein now I understand the point and I can answer your question
line A: root ... X ... Y ... X
line B: root ........Y.....X...
The lines above are not a problem for Damy new algorithm. Even if line B is evaluate first with an heuristic value lower than a draw, that does not prevent the algorithm to conclude to a draw score when it will evaluate line A. in rare cases, due to the specific pruning approach included in the algorithm it might happen that the draw in line A is not discovered but in the general case the draw is really discovered

Then my conjecture is that you generate endgame databases during the search for all positions of the kings with the men taken as fixed. This will take care of both the repetitions and also can avoid the tree explosion. For a single king on both sides this can be done very efficiently. Some people also do this in chess (take a look at H.G. Muller's endgame db website), but this is not as efficient as in draughts, especially if there are many sliding pieces.

BTW I worked hard on this idea of generating an endgame databases during the search for all positions of the kings with the men taken as fixed but eventually I was not able to find a efficient solution. I was very disappointed and I almost gave up ... until I found a a new idea more or less related to the work I done.

[TAILLE]

Interesting remark Rein, as there is only 1 programmer so far who builds (sometimes) DB on the fly.
See below text from 2007

No Ed I am not using the normal engine when in end game with 6 pieces or less on the board. Clearly I agree that it is not possible to find a conversion that need a lot of plies.
I really generate a small DTC db corresponding to the specific men configuration of the live game. In other words I begin a db generation process by generationg all possibles positions with the kings with a classical iterative process to build this DTC db.
With 3 kings the number of position is less than 62500 and, as you know very well, the building of a DTC db of 62500 positions is not a long process !
Gérard

Bert

Hi Bert,

That is still up to date! When entering the 2-8 egdb Damy generates (if necessary) the DTC table on the fly in a multithread approach.

[BertTuyt]

Just a wild guess....
What could you learn from a position which does not have ply-depth in terms of DTC.
Otherwise stated you loop through the positions with all man fixed, and then during a next iteration you will not find more positions.
Could these positions be related to loop-draws??

Bert

[TAILLE]

Just a wild guess....
What could you learn from a position which does not have ply-depth in terms of DTC.
Otherwise stated you loop through the positions with all man fixed, and then during a next iteration you will not find more positions.
Could these positions be related to loop-draws??

Bert

I do not quite understand your question. You seem to try to build a kind of DTC table. I yes, I already answered the question i.e. it is surely possible to build such algorithm; I tried this approach but was unable to find an efficient solution with this approach.

[Rein Halbersma]

Just a wild guess....
What could you learn from a position which does not have ply-depth in terms of DTC.
Otherwise stated you loop through the positions with all man fixed, and then during a next iteration you will not find more positions.
Could these positions be related to loop-draws??

Bert

I do not quite understand your question. You seem to try to build a kind of DTC table. I yes, I already answered the question i.e. it is surely possible to build such algorithm; I tried this approach but was unable to find an efficient solution with this approach.

Hi Gerard,

Here's another guess at your algorithm. Whenever there is at least 1 king for each side, you do the following. If you detect a hash hit where the stored remaining depth is at least 2 higher than the remaining depth in the search, you will follow the best moves stored in the hash table and check if one of these new positions has already occured in the current variation. If it does, you treat this position as a repetition. In this way, you can avoid the double symmetric masking of repetition paths that mask each other during iterative deepening. You only have to do this "hash table repetition checking" once, because the next iteratation already knows about the repetition. Only hash table overwrites can occiasionally destroy this information.

How close am I to your algorithm?

Rein

[TAILLE]

Just a wild guess....
What could you learn from a position which does not have ply-depth in terms of DTC.
Otherwise stated you loop through the positions with all man fixed, and then during a next iteration you will not find more positions.
Could these positions be related to loop-draws??

Bert

I do not quite understand your question. You seem to try to build a kind of DTC table. I yes, I already answered the question i.e. it is surely possible to build such algorithm; I tried this approach but was unable to find an efficient solution with this approach.

Hi Gerard,

Here's another guess at your algorithm. Whenever there is at least 1 king for each side, you do the following. If you detect a hash hit where the stored remaining depth is at least 2 higher than the remaining depth in the search, you will follow the best moves stored in the hash table and check if one of these new positions has already occured in the current variation. If it does, you treat this position as a repetition. In this way, you can avoid the double symmetric masking of repetition paths that mask each other during iterative deepening. You only have to do this "hash table repetition checking" once, because the next iteratation already knows about the repetition. Only hash table overwrites can occiasionally destroy this information.

How close am I to your algorithm?

Rein

Hi Rein,

I do not quite understand your proposal.

Let’s take my example

Black to move

Analyse at depth 4 plies :
I) After 1...11-02 2.32-19 (position A) 02-07 3.19-23 (position B) you conclude that you reach a position with a big advantage to white (3 men ahead). I imagine here you store in your hash table that position B leads a big advantage at depth 0, and position A leads to the same big advantage but at depth 2
II) Now you run the second sequence beginning by 1...11-07 2.32-23 (position B) 07-02 3.23-19 (position A) . According to your proposal you look for position A in the hash table and you find a big advantage to white at depth 2, and you look for the best moves recorded in the hash table. You find the moves 02-07 19-23 and you discover that this sequence leads to the position B which was already seen in the sequence. Then, if I understand correctly, you conclude that position B is a draw by repetition.
This seems not a correct conclusion because now you cannot explore any more a sequence like 1…11-07 2.32-23 (position B) 07-02 3.23-46 which leads to a small advantage (1 man ahead) but avoid the repetition. I perfectly know that this sequence leads also to a draw but supposing you do not have the 5 pieces endgame database then your algorithm is not allowed to demonstrate this draw!

I guess I miss something in your proposal.

[Rein Halbersma]

Hi Gerard,

Here's another guess at your algorithm. Whenever there is at least 1 king for each side, you do the following. If you detect a hash hit where the stored remaining depth is at least 2 higher than the remaining depth in the search, you will follow the best moves stored in the hash table and check if one of these new positions has already occured in the current variation. If it does, you treat this position as a repetition. In this way, you can avoid the double symmetric masking of repetition paths that mask each other during iterative deepening. You only have to do this "hash table repetition checking" once, because the next iteratation already knows about the repetition. Only hash table overwrites can occiasionally destroy this information.

How close am I to your algorithm?

Rein

Hi Rein,

I do not quite understand your proposal.

Let’s take my example

Black to move

Analyse at depth 4 plies :
I) After 1...11-02 2.32-19 (position A) 02-07 3.19-23 (position B) you conclude that you reach a position with a big advantage to white (3 men ahead). I imagine here you store in your hash table that position B leads a big advantage at depth 0, and position A leads to the same big advantage but at depth 2
II) Now you run the second sequence beginning by 1...11-07 2.32-23 (position B) 07-02 3.23-19 (position A) . According to your proposal you look for position A in the hash table and you find a big advantage to white at depth 2, and you look for the best moves recorded in the hash table. You find the moves 02-07 19-23 and you discover that this sequence leads to the position B which was already seen in the sequence. Then, if I understand correctly, you conclude that position B is a draw by repetition.
This seems not a correct conclusion because now you cannot explore any more a sequence like 1…11-07 2.32-23 (position B) 07-02 3.23-46 which leads to a small advantage (1 man ahead) but avoid the repetition. I perfectly know that this sequence leads also to a draw but supposing you do not have the 5 pieces endgame database then your algorithm is not allowed to demonstrate this draw!

I guess I miss something in your proposal.

OK, so I slightly modify my proposal. If you have marked position B as a potential repetition, you should again check the hash table moves whenever you encounter it again. This is precisely the simulation procedure in the Kishimoto-Muller solution in their GHI-paper. My proposal was to avoid the "double masking" where you never detect a repetition. In their paper they don't discuss this because I don't think they use iterative deepening. Curiously, Campbell makes the remark that iterative deepening softens the GHI problem. He may be right in the sense that you get less errors because of draw propagation, but you can also miss draws as your example nicely shows!

So in your variation 1... 11-07 2.32-23 (B) 07-02 you first try the hash table moves, and find a repetition. If the alternative 23-46 gives a better score, you take that of course. Why would white want a repetition draw if he can achieve a heuristic advantage? BTW, I think I need to think a bit more carefully about the existence of ways to break out of the loop. In your example, black can force the repetition, but if you would place 3 more black pieces on the board, black would not want to force it. This "outside option effect" is not discussed in the GHI-papers.

Rein