stalemate detection and pruning

[hgm]

The initial versions of micro-Max had a problem in detecting stale-mate. The reason was that it also did pseaudo-legal move generation, relying on King-capture in the daughter to prove illegality, and that the principle of stalemate violates the basic premise of alpha-beta pruning:

Normally, when you find a move that scores above beta, you know the corresponding move in the parent is refuted, and there is no need to search for better refutations. They can only make the parent worse, and most often they would only make one move in the parent worse, not affecting the parent score at all, because it was not the best move there anyway. But if the 'better' refutation would be a king capture, it would make the move in the parent so much worse that it becomes illegal, and if all other moves were illegal too. the parent becomes a stalemate, which raises its score to 0!

So having a move that scores above beta is not enough to conclude you can take a beta cutoff if beta > 0: you have to search on to see if you have a King capture, because having a King capture in addition to the 'cut move' might actually lower the score to 0. (Although most often it would of course raisethe score to +INF).

The current version of micro-Max therefore temporarily raises beta to +INF in the pre-QS iteration of IID, so that it is guaranteed to detect King capture, and only then continues the QS iteration with the best capture it found in the pre-QS, with the normal beta.

[syzygy]

The initial versions of micro-Max had a problem in detecting stale-mate. The reason was that it also did pseaudo-legal move generation, relying on King-capture in the daughter to prove illegality, and that the principle of stalemate violates the basic premise of alpha-beta pruning:

Isn't it more accurate to say that relying on King-capture violates the rules of chess? This becomes apparent in stalemate situations.

Chess with king captures is a different game. Using an alpha-beta search for a different game to play chess requires hacks, but so does using a minimax search for a different game to play chess.

[hgm]

Isn't it more accurate to say that relying on King-capture violates the rules of chess?

Not really. Stalemate could be defined in the rules as the possibility to claim a draw in a position where turn passing would be the only way to avoid exposing your King, even if exposing your King was legal. And then it would be exactly the same game as orthodox Chess.

A precedent exists for this in the rules of Shogi. Shogi is a King capture game, although custom is to resign when you are checkmated (because having your King captured is seen as humiliating.)

There is a rule, however, that you are not allowed to checkmate the opponent by dropping a Pawn. Despite the fact that checkmate is not the end of the game.

So you have the similar issue there: a move out of the checkmate position there can be refuted by a high-scoring move, but if at the same time King capture is possible, this could turn the parent into a checkmate, and if move leading to that parent was a Pawn drop the checkmate would turn into a win for the mated side, so that your non-King-apturing refutation actually did not refute anything.

[syzygy]

Isn't it more accurate to say that relying on King-capture violates the rules of chess?

Not really.

Why not? Chess with king captures really is a different game.

Stalemate could be defined in the rules as the possibility to claim a draw in a position where turn passing would be the only way to avoid exposing your King, even if exposing your King was legal. And then it would be exactly the same game as orthodox Chess.

Now you're describing yet another game.

[Uri Blass]

Isn't it more accurate to say that relying on King-capture violates the rules of chess?

Not really.

Why not? Chess with king captures really is a different game.

Stalemate could be defined in the rules as the possibility to claim a draw in a position where turn passing would be the only way to avoid exposing your King, even if exposing your King was legal. And then it would be exactly the same game as orthodox Chess.

Now you're describing yet another game.

It is not a different game in the meaning that the result between strong players is practically the same because strong players will never allow their opponent to capture the king and win when they have some alternative and if (when they are not in check) they see that every legal move allow their opponent to capture the king they are going to be smart enough to claim a draw.

[syzygy]

It is not a different game in the meaning that the result between strong players is practically the same (...)

This is a theoretical discussion, not a practical. Allowing king captures changes the game theoretic value of at least one position. It therefore becomes a different game.

[hgm]

I don't think the game-theoretical value of any position changes. Which position are you talking about?

[Uri Blass]

I don't think the game-theoretical value of any position changes. Which position are you talking about?

The only position that I can think about is illegal positions in chess when you can capture the king that has win value in your game and undefined value in chess.

I agree that the theoretical value of every legal position in chess should be the same also in your game.

[syzygy]

I don't think the game-theoretical value of any position changes. Which position are you talking about?

Most if not all stalemate positions stop being a draw. Move the king into check, king gets captured, you lose.

To avoid this while allowing king captures in the search tree, you need to hack alpha-beta (and minimax as well).

Point being: if you allow only legal moves in your search tree (which does not equate to legal move generation, as you can simply make/check/undo), then alpha-beta works just fine.

[hgm]

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.

That is how King-capture engines work. That is how micro-Max works. That is how pseudo-legal move generation works.

Failing to make the stalemate correction is just wrong. No engine I know does it. You would not even be able to win KQK when you did that.