Cycle detection

[FeikeBoomstra]

Upto now I didn't had any cycle detection. But I tried to increase the search depth in case "the other party can capture". Now it is very easy to get an infinite loop, going in recursion until the crash.

My first idea was to use the hash-table, but thinking about it, it is not sure you have a loop if you find the position already in the hash closer to the root. They can be in different branches.

So the only solution is to maintain a stack of the actual sequence of moves (positions) to come to the node you are evaluating?

And if you have such a stack, how about parallel execution? You can't share (part of) the stack, you have to copy it inside the new thread completely.

Comments?

[Rein Halbersma]

Upto now I didn't had any cycle detection. But I tried to increase the search depth in case "the other party can capture". Now it is very easy to get an infinite loop, going in recursion until the crash.

My first idea was to use the hash-table, but thinking about it, it is not sure you have a loop if you find the position already in the hash closer to the root. They can be in different branches.

So the only solution is to maintain a stack of the actual sequence of moves (positions) to come to the node you are evaluating?

And if you have such a stack, how about parallel execution? You can't share (part of) the stack, you have to copy it inside the new thread completely.

Comments?

This problem was solved by people from the GAMES group in Alberta (Muller and Kishimoto). One of their tricks is to hash-encode the search path (see section 3.1.3 of http://www.fun.ac.jp/~kishi/pdf_file/ki ... thesis.pdf). This algorithm was used in Chinook's proof that checkers is a draw.

Rein

[Ed Gilbert]

Upto now I didn't had any cycle detection. But I tried to increase the search depth in case "the other party can capture". Now it is very easy to get an infinite loop, going in recursion until the crash.

My first idea was to use the hash-table, but thinking about it, it is not sure you have a loop if you find the position already in the hash closer to the root. They can be in different branches.

So the only solution is to maintain a stack of the actual sequence of moves (positions) to come to the node you are evaluating?

And if you have such a stack, how about parallel execution? You can't share (part of) the stack, you have to copy it inside the new thread completely.

Comments?

Hi Feike,

In kingsrow I use an array of previously visited positions, indexed by search depth. If I find a repetition, then I return a draw score. This is not perfectly correct, because of the reasons given in the paper referenced by Rein, but it's fast and it works well enough. I don't fully understand the algorithm given in that paper. I know that a lot of chess and checkers programs basically do the same thing that I'm doing.

You're right about parallel search, when you split the search at a node, you have to copy the array of visited positions to each thread that will help search that node.

I don't see why this causes any infinite recursion. Are you extending the search when you see a repetition? If you see a repetition then I think you can return a draw score immediately without further searching. Even if you extend on a capture, this cannot cause infinite extensions, because after a capture the pre-capture position cannot be repeated.

-- Ed

[FeikeBoomstra]

I got repetition because I extend the search in case of a threat and had no mechanism to detect loops.

Loop detection as such is not complicated, but do you things like:
starting only if there is at least one king at each site,
reset the search queue in case of a man-move
do you incorparate the 25-moves rule in this routine

kind regards,
Feike

[Ed Gilbert]

Loop detection as such is not complicated, but do you things like:
starting only if there is at least one king at each site,
reset the search queue in case of a man-move
do you incorparate the 25-moves rule in this routine

When I am looking through the array of previously visited positions along the current path, I do stop looking if I see a man move, or if there is not at least one king of each color.

I do not detect any 25-moves rule, in fact I have completely forgotten what this rule is!

-- Ed

[FeikeBoomstra]

So, if I understand it well, you maintain a stack of the current path of positions in all cases, but you limit how far you are going back due to specific actions.

The 25 move rule is (by head) if you have a king and a man and you move only the king for 25 moves, than it is a draw.

If I am not correct, please let somebody correct me.

Feike

[Ed Gilbert]

So, if I understand it well, you maintain a stack of the current path of positions in all cases, but you limit how far you are going back due to specific actions.

Yes. Also you only have to check each 4th previous move, because those are the only ones that can be a repeat of the position where you started checking.

The 25 move rule is (by head) if you have a king and a man and you move only the king for 25 moves, than it is a draw.

Ok. As a practical matter, kingsrow drives towards conversion moves (man moves or captures) when it is in a winning endgame, and avoids conversions when it is losing, so I don't see why it should be necessary to try to detect this specific rule during the search.

-- Ed

[Rein Halbersma]

So, if I understand it well, you maintain a stack of the current path of positions in all cases, but you limit how far you are going back due to specific actions.

The 25 move rule is (by head) if you have a king and a man and you move only the king for 25 moves, than it is a draw.

If I am not correct, please let somebody correct me.

Feike

These are the rules of the game, coming from the official FMJD document. In the old days, the players actively needed to claim draws under rules 6.1 through 6.4, but now the game is *considered* a draw. This means that rules 6.1 through 6.4 need to be implemented before a program can play completely according to the rules.

Code: Select all

6. The draw

6.1. A game is considered a draw when the same position occurs for the third time, with the same player having to move. 
6.2. If during 25 successive moves, only the kings have moved, without any man moving or without any capture, the game is considered drawn. 
6.3. If only three kings remain, two king plus a man, one king and two men, against one king, the game shall be considered a draw when the players have each played another sixteen moves maximum. 
6.4. The end game with two kings, one king and a man, or one king against one king will be considered a draw when the players have each played another five moves maximum.

7.	The result
7.1. There are two possible results at the end of a game:
7.1.1. A win for one of the opponents, and, by consequence, a loss for the other;
7.1.2. A draw when neither of the players has been able to win.
7.2. A player wins when his opponent:
7.2.1. resigns with or without reason;
7.2.2. has the move but cannot move a piece, as all are blocked;
7.2.3. has no pieces left;
7.2.4. refuses to comply with the rules.
7.3. A draw is obtained when:
7.3.1. both players agree to a draw by mutual consent;
7.3.2. the rules for draws in article 6 apply;
7.3.3. neither player can win. 

[Ed Gilbert]

These are the rules of the game, coming from the official FMJD document. In the old days, the players actively needed to claim draws under rules 6.1 through 6.4, but now the game is *considered* a draw. This means that rules 6.1 through 6.4 need to be implemented before a program can play completely according to the rules.

Rein, if the game is considered a draw regardless of whether a player (or program) actively claims it, then why does a program need to implement anything other than sound conversion strategy in endgames?

-- Ed

[Rein Halbersma]

These are the rules of the game, coming from the official FMJD document. In the old days, the players actively needed to claim draws under rules 6.1 through 6.4, but now the game is *considered* a draw. This means that rules 6.1 through 6.4 need to be implemented before a program can play completely according to the rules.

Rein, if the game is considered a draw regardless of whether a player (or program) actively claims it, then why does a program need to implement anything other than sound conversion strategy in endgames?

-- Ed

All I am saying is that a program should at least recognize a drawn position (either by repetition or by the 25, 16 or 5 move rules) during actual game play (i.e. at the root of a search). Whether or not you implement these rules recursively in your search routine is another matter, and I agree that a sound conversion strategy will probably give the same effect.

But suppose during a future computer tournament you win after 30 consecutive king moves. Would you consider such a result as a valid win or would you accept a reversal to a drawn result?

Rein

[Ed Gilbert]

All I am saying is that a program should at least recognize a drawn position (either by repetition or by the 25, 16 or 5 move rules) during actual game play (i.e. at the root of a search). Whether or not you implement these rules recursively in your search routine is another matter, and I agree that a sound conversion strategy will probably give the same effect.

Ok. I guess for completeness the program should announce draws in those cases.

But suppose during a future computer tournament you win after 30 consecutive king moves. Would you consider such a result as a valid win or would you accept a reversal to a drawn result?

By the rules that is a draw, even if not declared by the opponent program. So one must accept it. I was thinking that it is not really important that the program announce this, because the referee can declare this a draw. But I suppose it would be nice for the program to recognize this, especially in the case where the program would otherwise lose, and perhaps no one else notices the 30-move draw.

-- Ed

[TAILLE]

By the rules that is a draw, even if not declared by the opponent program. So one must accept it.
-- Ed

Hello,

Let me remind you the following position :



Do you accept the draw obtain by black with the following sequence ?

1...35-40 2.33-28 40-45 3.26-17 04-15 4.17-06 15-29 5.41-47 29-07 6.47-38 07-12 7.38-20 12-08 8.20-03 08-35 9.03-21 35-49 10.21-08 49-35 11.08-02 35-40 12.02-30 40-07 13.30-43 07-12 14.43-25 12-21 15.25-03 21-16 16.36-13 16-07 17.13-02 07-18 18.02-16 18-01 19.03-17 01-29 20.16-02 29-18 21.02-24 18-36 22.24-47 36-18 23.17-21 18-09 24.21-26 09-18 25.47-33 18-04 26.33-50 04-18 27.26-21 18-04

25 moves without any conversion => draw.

My view is that this 25 moves rule should not be applicable to computer but who has the authority for writing draugths rules for computers ?

Should we keep this rule then, for a theoritical point of view, we should recalculate all our endgame databases because we cannot evaluate the propagation effect of the concerned positions.

Gérard

[Ed Gilbert]

Hi Gerard,

While I understand why you don't like this 25-move rule for computer draughts, I think the programs should play by the same rules that people use, else they're not really playing the exact same type of game. As a practical matter I think we can probably ignore this rule. What do we use draughts programs for? I see the main uses as:

1. We enter them in computer-computer competitions.
2. Tournament players probably use them to review their games to see where they missed a win, where they went wrong if they lost, etc.

For application 1, we never get to the point of invoking the 25-move rule. As soon as both programs can see a database win/loss, then the losing operator resigns the game. At least this is what I observed at Culemborg last year, and it was the same when I participated in a computers checkers tournament at Las Vegas in 2002. We do this because we have a lot of games to play in a few hours time and we don't want any one game to drag on and on.

For application 2, I don't think the players are concerned about the 25 move rule.

The rule seems to be needed to prevent human tournament games from dragging on for a very long time from king moves. But I think programs can safely ignore it. Has this rule ever been invoked in a computer-computer tournament game?

When Damage and Kingsrow play 158-game tournaments on the internet (we just had another one a few weeks ago) we terminate games as soon as one program sees a database win/loss.

-- Ed

[TAILLE]

For application 1, we never get to the point of invoking the 25-move rule. As soon as both programs can see a database win/loss, then the losing operator resigns the game.-- Ed

This statement seems not correct because the all known generated databases do not take into account the 25-move rule. As a consequence both concerned programs will give the same result.

Let us suppose (it is not really my intention!) that I regenerate Damy database in order to take into account this 25-move rule. As a consequence the position I mentionned is marked as a draw (we have always to assume that the opponent will be able to make the best moves) and some other positions will be also marked as a draw.

It may now happen that we reach a position where the result of our databases may differ due to this 25-move rule. Suppose now that this position is reached at the 60th move of the game. In a computer tournament I suppose that the game will continue until the 75th move of the game is reached. What will be now the decision of the referee seing a difference between the two databases ?

Let'us take another example.
Suppose that a 5 kings vs 2 kings endgame appears at the 60th move of a game and suppose that the program with the 5 kings has not the corresponding DTC database (it only have an algorithm in order to win but this algorithm is not very optimised). The 2 databases agree to the win but you cannot prevent the game to reach the 75th move (our experience in tournment tells us that the losing side wish always to continue the game, hoping a bug in the opponent program). After 15 other moves the 75th move of the game is reached. Suppose at this point that the program wtih the DTC database claims for a draw because the DTC of the final position is 15 moves (30 plies). What will be the decision of the referee ?

Gérard

[Ed Gilbert]

Let us suppose (it is not really my intention!) that I regenerate Damy database in order to take into account this 25-move rule. As a consequence the position I mentionned is marked as a draw (we have always to assume that the opponent will be able to make the best moves) and some other positions will be also marked as a draw.

It may now happen that we reach a position where the result of our databases may differ due to this 25-move rule. Suppose now that this position is reached at the 60th move of the game. In a computer tournament I suppose that the game will continue until the 75th move of the game is reached. What will be now the decision of the referee seing a difference between the two databases ?

I am not going to worry about this because it is very unlikely that anyone will generate their WLD dbs in this manner. It is a lot of extra work for a very questionable benefit.

Let'us take another example.
Suppose that a 5 kings vs 2 kings endgame appears at the 60th move of a game and suppose that the program with the 5 kings has not the corresponding DTC database (it only have an algorithm in order to win but this algorithm is not very optimised). The 2 databases agree to the win but you cannot prevent the game to reach the 75th move (our experience in tournment tells us that the losing side wish always to continue the game, hoping a bug in the opponent program). After 15 other moves the 75th move of the game is reached. Suppose at this point that the program wtih the DTC database claims for a draw because the DTC of the final position is 15 moves (30 plies). What will be the decision of the referee ?

Should this happen, then the decision should be draw, and the referee can let the game continue for another 15 moves just to make it a certainty. But my point is that the probability of this happening is very low. These positions with high DTC values only occur when most of the remaining pieces are kings, that usually takes more than 75 moves. Also, my experience during tournaments is different than yours -- I think in all cases when kingsrow was in a win the opponent resigned soon after his program saw database loss and did not try to extend the game to the full 75 moves. AFAIK these situations for 25-move rule and 16-move rule have never been reached in a computer tournament, and that includes hundreds of games.

However, I see your point, and though I said earlier that I think we should play by the same rules as humans, I would not object to discarding these 25 and 16 move rules for computer tournaments.

-- Ed