How to handle the first repetition correctly? (long)

[Sven Schüle]

Geschrieben von:/Posted by: Sven Schüle at 10 August 2004 17:24:56:

Hi,
I am currently thinking about a very basic thing in chess programming, and I am not quite sure if I have done it right in "Surprise". Now I wonder how you are doing this.
First the simple rules again: if a position occurs for the third time in a game (including search tree) with identical board contents, side to move, castle rights, and ep square, then the game is a draw. So far everything is clear, including how to implement the repetition detection in general.
If a position occurs for the second time, i.e. is repeated for the first time, then we have two cases during the search (assuming current depth > 0):
A. The first occurrence was before the current search started and belongs to "game history".
B. The first occurrence belongs to the search tree.
See also Bruce Moreland's page for more details:
http://www.brucemo.com/compchess/progra ... tition.htm
Now I have implemented this stuff in "Surprise" similar to the following pseudo code:

void handleRepetition(int depth, bool & shouldExpand)
{
    if (isRepetition()) {
        int oldRepCount = get_repetition_count_of_repeated_position()&#59;
        int newRepCount = set_repetition_count_of_current_position(oldRepCount + 1)&#59;
        int plyDistance = get_distance_to_repeated_position_in_plies()&#59;
        if (plyDistance > depth) {
            // game history position repeated
            if (newRepCount >= 2) {
                // final position of game
                set_repetition_flag_in_current_position()&#59;
                shouldExpand = false&#59;
            } else {
                // THE CRITICAL CASE:
                // continue search, both sides might want to escape from draw
                shouldExpand = true&#59;
            }
        } else {
            // tree position repeated&#59; will be handled as if it were a
            // final position of game
            set_repetition_flag_in_current_position()&#59;
            shouldExpand = false&#59;
        }
    } else {
        // nothing special
        shouldExpand = true&#59;
    }
}
int treeSearch(int alpha, int beta, int depth, int maxDepth)
{
    // ...
    bool shouldExpand&#59;
    handleRepetition(depth, shouldExpand)&#59;
    if (!shouldExpand) {
        return 0&#59; // draw score
    }
    // ... else ... perhaps call the evaluation function
}


Additionally, the evaluation function (called mainly at leaf nodes of full-width search) gives a bonus of up to 0.6 pawn units if the current position has a repetition count of 1 (THE CRITICAL CASE, see above) and the side to move is down at least 0.01 pawns; but with the bonus the score will not go positive.
Now what I have observed frequently is that "Surprise" likes to repeat a position once before making some progress with a better variation.
Sometimes, even worse, in a clearly won game "Surprise" seems to love the repeated position and wants to see it one more time, loosing a half point. But this might be something very different, most likely a bug.

Long introduction - short question: how to handle the first repetition correctly, especially how to avoid that the engine repeats before making any progress (which might lead to some 50-moves trouble)?
Any helpful comments are welcome!
Bye,
Sven


Surprise

[Will Singleton]

Geschrieben von:/Posted by: Will Singleton at 10 August 2004 18:02:28:
Als Antwort auf:/In reply to: How to handle the first repetition correctly? (long) geschrieben von:/posted by: Sven Schüle at 10 August 2004 17:24:56:

The question is, as you've said, what do you do in the case where the position appears once in the game history and once in the tree? I think most people call this a draw, and don't worry about it. If you, like me, ignore this case, then your engine will occasionally repeat positions. I find this to be slightly beneficial, in that my engine will repeat a position due to seeing a problem deep in the search, and the opponent will (if losing) gladly go back to the original position with a draw score, giving me the opportunity to select a better move. (note, the case when game_rep==0 and tree>1, I score as a draw.)
Your method of scoring draws could cause problems if the sign gets messed up. I had lots of difficulty with that, and eventually decided to always use 0. Try that and note any different behavior.
As far as drawing in a won position, that's clearly a bug and you need to find that before deciding about whether to allow one rep. Might be a hash issue.
Will

[Sven Schüle]

Geschrieben von:/Posted by: Sven Schüle at 10 August 2004 18:55:27:
Als Antwort auf:/In reply to: Re: How to handle the first repetition correctly? (long) geschrieben von:/posted by: Will Singleton at 10 August 2004 18:02:28:

Hi Will,

The question is, as you've said, what do you do in the case where the position appears once in the game history and once in the tree? I think most people call this a draw, and don't worry about it. If you, like me, ignore this case, then your engine will occasionally repeat positions.
[...] (note, the case when game_rep==0 and tree>1, I score as a draw.)
Your method of scoring draws could cause problems if the sign gets messed up. I had lots of difficulty with that, and eventually decided to always use 0. Try that and note any different behavior.
As far as drawing in a won position, that's clearly a bug and you need to find that before deciding about whether to allow one rep. Might be a hash issue.
Will

by "ignore this case" you mean not to cut the search and return with a draw but to continue? That's what I do, and I believe it's good not to cut here for the same reason you mentioned (having the opportunity to select a better move).
Did you mean "game_rep==1 and tree>0"?
At least I hope never to mess up the sign. Furthermore, I only use 0 as draw score, but in case of first repetition of a game history position I don't regard this as a draw. What I tried to describe is what I do in the eval after having done all the positional scoring. I simply give a bonus to push a negative score closer to zero.
Should I replace this by always setting 0 as lower bound for searching a first-repetition position? But what if all moves are losing? Then I clearly return a wrong value of 0. Is this acceptable in this special case? At least there must have been some better alternative for the opponent on his way to the current position, otherwise I may not state that all moves from here (which were also valid at the repeated pos) are losing. But what if such "better alternative" was above the search root? Then the wrong 0 might indeed have an influence on the root value, messing things up really.
Many thanks, Will, I hope to find the bug soon, provided my little daughter will make her moves towards the bed quickly during the next days and will save some thinking time for me (perhaps I can start pondering).
Sven


Surprise

[Will Singleton]

Geschrieben von:/Posted by: Will Singleton at 10 August 2004 23:27:42:
Als Antwort auf:/In reply to: Re: How to handle the first repetition correctly? (long) geschrieben von:/posted by: Sven Schüle at 10 August 2004 18:55:27:

Hi Will,

The question is, as you've said, what do you do in the case where the position appears once in the game history and once in the tree? I think most people call this a draw, and don't worry about it. If you, like me, ignore this case, then your engine will occasionally repeat positions.
[...] (note, the case when game_rep==0 and tree>1, I score as a draw.)
Your method of scoring draws could cause problems if the sign gets messed up. I had lots of difficulty with that, and eventually decided to always use 0. Try that and note any different behavior.

by "ignore this case" you mean not to cut the search and return with a draw but to continue? That's what I do, and I believe it's good not to cut here for the same reason you mentioned (having the opportunity to select a better move).
Did you mean "game_rep==1 and tree>0"?
At least I hope never to mess up the sign. Furthermore, I only use 0 as draw score, but in case of first repetition of a game history position I don't regard this as a draw. What I tried to describe is what I do in the eval after having done all the positional scoring. I simply give a bonus to push a negative score closer to zero.

Yes.
No, I meant when a position does not exist in the game history, but occurs twice in the current search, I score that as a draw.
Oh, I see. That should be ok.
Will