stalemate detection and pruning

[syzygy]

Of course engines make the correction, but my point is that this correction is necessary not because stalemate would somehow violate the premise of alpha-beta, but because you're letting moves get into your search tree that are only legal in a game that is not chess.

[hgm]

Well, if these same moves would occur in pure minimax search, they would not cause any problem. Of course it will always be necessary to explicitly score stalemate as a draw; this is a special rule in Chess, which would never follow from any other rule, (like checkmate could follow from the fact that you will unavoidably have your King captured), no matter how you formulate it. That I called it a 'correction' is just a figure of speech. In an engine which employs legal move generation, there also would have to be a statement inside the "if(legalMoves == 0)" section that says "if(!inCheck) score=0;", and you could also call that a correction on the -INF score you get in all other cases.

So I would say the 'correction' is needed because the rules say that stalemate is a draw.

That the search tree would contain illegal moves would not present any problem in pure minimax. But alpha-beta pruning on such a tree would fail, in the sense that it can alter the root score compared to its minimax value.

[syzygy]

That the search tree would contain illegal moves would not present any problem in pure minimax.

Minimax with king captures needs the same hack/correction/whatever. Pure minimax in a stalemate position would find that all moves would lead to a win for the other side, meaning that the position is a loss.

[hgm]

But the point was that without King captures you need that 'hack' too. Otherwise all positions with zero legal moves would be scored the same.

[zamar]

Some time ago my program lost a game by playing into a stalemate, when it actually had a win. I found this hard to reproduce and never did fix it. But in thinking about it later, a possible cause has occurred to me. Stalemate detection depends on generating all moves and discovering none are legal. But when pruning is done, you don't know that there are no legal moves (I do legal move detection only after the move is made, pruning is done before). So it is possible a position deep enough in the tree so that pruning is happening will not be scored as a draw when in fact it should be.

A fix would be to prune after the move is made and checked for legality but that would slow down the search.

Don't know if other programs have this issue but I suspect some do.

--Jon

AFAIK most top programs only prune moves when depth < 7 or so. So stalemates are detected in higher depths.

Another option is to start pruning moves AFTER engine has played at least one legal move. I think this is the most sensible option especially if you have a good move ordering.

[syzygy]

But the point was that without King captures you need that 'hack' too. Otherwise all positions with zero legal moves would be scored the same.

But then it is just a matter of correctly assigning a value to nodes that have no more children in accordance with the rules of chess. This is an integral part of both the minimax and the alpha-beta algorithm applied to a 2-player game.

Both minimax and alpha-beta are correct algorithms for a whole class of 2-player games and chess belongs to this class. There is nothing in chess that violates any premise of the alpha-beta algorithm. I don't believe we can have any real disagreement here.

Once you start using implementation tricks such as allowing king captures and moving into check as part of the tree being recursively searched, the implementation can no longer be a clean reflection of alpha-beta and you need a hack to ensure that the game-theoretic outcome of all positions remains the same.

[hgm]

Actually assigning a value to nodes is an implementation trick. The rules of Chess, as shown on the FIDE website, defines the score of such nodes recursively, in terms of attacks after making pseudo-legal moves from there, the attacks themselves being again defined as pseudo-legal moves.

Trying to calculate all that by a dedicated shortcut is a speed-enhancing implementation trick. A King-capture engine just litterally follows tthe recipe described in the FIDE rules.

And all I stated was that in that phase alpha-beta pruning is incompatible with the stalemate rule.

[syzygy]

Actually assigning a value to nodes is an implementation trick. The rules of Chess, as shown on the FIDE website, defines the score of such nodes recursively, in terms of attacks after making pseudo-legal moves from there, the attacks themselves being again defined as pseudo-legal moves.

The alpha-beta algorithm is well-defined. It requires you to assign the game-theoretic outcome of positions corresponding to terminal nodes (or a heuristic evaluation if you limit the depth and the game-theoretic outcome is not available). The manner in which the FIDE rules define this outcome is not important.

Trying to calculate all that by a dedicated shortcut is a speed-enhancing implementation trick. A King-capture engine just litterally follows tthe recipe described in the FIDE rules.

The FIDE rules define which moves are legal. Moving into check is not legal. Capturing is not legal either (but anyway impossible if no previous illegal moves were made). Art. 5.2(a) defines the game as drawn if the player to move has no legal move and his king is not in check.

Speed-enhancing tricks are good, but they are not part of the alpha-beta algorithm. If stalemate is to some extent incompatible with a speed-enhancing trick, that does not mean that stalemate violates a premise of alpha-beta.

And all I stated was that in that phase alpha-beta pruning is incompatible with the stalemate rule.

Your statement was "the principle of stalemate violates the basic premise of alpha-beta pruning" written in bold. All I disagree with is that statement. I offered an alternative: relying on King-capture violates the rules of chess. Indeed, according to art. 1.2 leaving one's own king under attack, exposing one's own king to attack and capturing the opponent's king are not allowed.

[syzygy]

No, stalemates remain a draw, because of the rule that when passing would be the only way to not expose your king to check, you can claim a draw.

There is no rule that you can "claim" a draw in a stalemate position. A stalemate position, i.e. a position with no legal moves and without the king of the side to move under attack, is a draw.

Also, for stalemate it does not matter whether there are pseudo-legal moves that would bring the king in check. So also this aspect of the rule you formulate is not present in the FIDE rules.

[hgm]

The alpha-beta algorithm is well-defined. It requires you to assign the game-theoretic outcome of positions corresponding to terminal nodes (or a heuristic evaluation if you limit the depth and the game-theoretic outcome is not available). The manner in which the FIDE rules define this outcome is not important.

Not sure what you are driving at. Perhaps that every Chess program that think ahead is just an 'implementation trick'?

The FIDE rules define which moves are legal. Moving into check is not legal.

But to know what 'check' is, they first let you move there, and then you have to demonstrate that in the new position your king is 'under attack', i.e. the opponent can capture it.

Capturing is not legal either (but anyway impossible if no previous illegal moves were made). Art. 5.2(a) defines the game as drawn if the player to move has no legal move and his king is not in check.

Speed-enhancing tricks are good, but they are not part of the alpha-beta algorithm. If stalemate is to some extent incompatible with a speed-enhancing trick, that does not mean that stalemate violates a premise of alpha-beta.

Which speed-enhancing trick is incompatible with stalemate, then?

And all I stated was that in that phase alpha-beta pruning is incompatible with the stalemate rule.

Your statement was "the principle of stalemate violates the basic premise of alpha-beta pruning" written in bold. All I disagree with is that statement. I offered an alternative: relying on King-capture violates the rules of chess. Indeed, according to art. 1.2 leaving one's own king under attack, exposing one's own king to attack and capturing the opponent's king are not allowed.[/quote]
They would only violate the rules of Chess if you would actually play them in the root. But the rules of Chess force you to think about these moves; the entire concept of check and attack are defined in terms of the possibility to make these moves. If it would be true that it is not allowed to capture the King, then you could never be in check! Check is defined as the possibility to capture a King. In fact the possibility to do so after a null move (which you are also not allowed to play...)

There is no rule that you can "claim" a draw in a stalemate position. A stalemate position, i.e. a position with no legal moves and without the king of the side to move under attack, is a draw.

That is the rule King-capture engines apply. Which is needed to make them play exactly the same game as defined in the FIDE rules (i.e. with the same game-theoretical value for each possible position).

Also, for stalemate it does not matter whether there are pseudo-legal moves that would bring the king in check. So also this aspect of the rule you formulate is not present in the FIDE rules.

I think the formulation is correct: if there are no pseudo-legal moves at all in a stalemate situation, turn passing would still be the only way to not expose your King to check or in fact do anything at all). That something is the only way to achieve X, does not logically imply that there are ways that achieve not-X.