Alpha-beta search for drawing endgames

[klx]

I'm curious if anyone tried to use alpha-beta search to prove that certain endgames are draws by repetition? How can this be done?

Is there an alternative approach than alpha-beta? I found proof number search and discussion about the GHI problem, but frankly I haven't been successful in making sense of those papers, so was hoping there's an easier way.

[hgm]

Alpha-beta search is very inefficient for this. Usually one uses retrograde analysis for such things.

[klx]

Alpha-beta search is very inefficient for this. Usually one uses retrograde analysis for such things.

Thanks! Just read up on retrograde analysis. I think that will help in many cases, but not if the draw is not in the endgame database. For example:

Let's say I have an endgame database for up to 6 pieces. The current board position has 8 pieces. If white trades a piece, all positions lead to a loss for white. However, with 8 pieces on the board, white can force a draw by repetition.

How can I prove such a draw? You mention alpha-beta is inefficient; I don't see how it can work at all in practice... I suppose I can detect draws by repetition by looking at the parents leading up to the current position, and if there's a repetition I call it a draw, which I can take turn to consider either a win or loss -- but how would that work together with a transposition table?

[Desperado]

Alpha-beta search is very inefficient for this. Usually one uses retrograde analysis for such things.

Thanks! Just read up on retrograde analysis. I think that will help in many cases, but not if the draw is not in the endgame database. For example:

Let's say I have an endgame database for up to 6 pieces. The current board position has 8 pieces. If white trades a piece, all positions lead to a loss for white. However, with 8 pieces on the board, white can force a draw by repetition.

How can I prove such a draw? You mention alpha-beta is inefficient; I don't see how it can work at all in practice... I suppose I can detect draws by repetition by looking at the parents leading up to the current position, and if there's a repetition I call it a draw, which I can take turn to consider either a win or loss -- but how would that work together with a transposition table?

The retrograde analysis are used to create the databases. Of course this knowledge will be retrieved within a search like an alpha beta search.
Basically, if the search hits a 6-men position, the result will be backpropagated to the root like any other value. You can simply think of mate values for example. This way an 8 ply search will report a perfect result based on the endgame database.

There are different database types which include different information. endgame databases

[Jakob Progsch]

Not sure I see the problem with the transposition table. Once the position repeats you evaluate it as a draw. however the repetition appears with less depth than its first occurrence. Once you return from the recursion if the same position has a stronger evaluation it will overwrite the drawn TT entry provided you prefer higher depth entries.

[hgm]

Let's say I have an endgame database for up to 6 pieces. The current board position has 8 pieces. If white trades a piece, all positions lead to a loss for white. However, with 8 pieces on the board, white can force a draw by repetition.

You just generate the relevant part of the 8-piece EGT. Often that is easy enough. At least, if you are mainly interested in end-games with Pawns.

[klx]

Not sure I see the problem with the transposition table. Once the position repeats you evaluate it as a draw. however the repetition appears with less depth than its first occurrence. Once you return from the recursion if the same position has a stronger evaluation it will overwrite the drawn TT entry provided you prefer higher depth entries.

Here's what I think will be a problem: Imagine from a root position R, we have the following two lines of search (A, B, C, D are states):

1. R -> A -> B -> C -> D -> A (repeated; draw)
2. R -> C -> D -> A -> win

In the first line, we repeat state A, so consider it a draw, which is propagated up, so D and C are also set to draws in the TT. Then, in the second (independent) line, we would immediately consider C a draw, even though it would later be a win.

On the contrary, if we visit line 2 first, we might store A, D and C as wins in the TT, and then visiting line 1, we might consider C a win, even though the only possible extension from that position would lead to a draw through repeating A.

Not sure does this make sense?

[klx]

You just generate the relevant part of the 8-piece EGT. Often that is easy enough. At least, if you are mainly interested in end-games with Pawns.

Ah ok. Just to make sure I understand fully: You mean I would generate the EGT only for the specific pieces I'm trying to solve for, and using the fact that pawns can only move forward from their current positions, so I wouldn't need to calculate all positions?

Any other tricks to reduce the number of states I need to calculate?

[hgm]

Ah ok. Just to make sure I understand fully: You mean I would generate the EGT only for the specific pieces I'm trying to solve for, and using the fact that pawns can only move forward from their current positions, so I wouldn't need to calculate all positions?

Exactly. Depending on how many of the pieces are Pawns, and how these block each other, this can give an enormous reduction of the number of relevant positions. Normally an extra piece multiplies the number of positions by 64. If you add a white Pawn on e4 and a black Pawn on e5, you only multiply the number of positions with the Pawns unpromoted by 8 and with one of the Pawns promoted to Queen by 64. So that would be 64 + 64 + 8 = 136 times as many, instead of 64 x 64 = 4096 times as many.

And in most cases you would not even need the positions where one of the Pawns has queened, because you can prove that the defending side can prevent the Queening. I.e. alter the rules to abolish promotion and having a Pawn on the 8th rank when it is your turn to move is a win. If under those rules the position you want to analyse is still a draw, you have proven that it will also be a draw under FIDE rules. It would only be tricky when one of the players can force promotion (so that the position to analyse comes out as a win with the altered rules). Then you would have to figure out whether the promotions that can be forced are really wins under FIDE rules, which would require generation of the EGT with a Queen instead of the Pawn.

[Jakob Progsch]

1. R -> A -> B -> C -> D -> A (repeated; draw)
2. R -> C -> D -> A -> win

So my counter argument is that if there is a win after A then that win is available the first time you encounter A regardless of history. So you should have found that win when encountering A in 1. as well. On the other hand if your opponent has a forced repetition draw that includes A then you can't escape that independently of where or how you encountered A. In which case your search will avoid A after correctly storing it as a draw in the TT (assuming there is a better than draw line available at the root).