Minmax algorithm and mate/stalemate
Posted: Sun Jul 26, 2020 8:50 pm
Suppose I was writing an engine for Chess variants, then I would have to implement a minmax algorithm. It would more or less work like this:
It searches the tree of subsequent moves for white/black up to a depth of a given number of plies. At the deepest level it would stop looking into more lines of moves, but just evaluate a position.
In FIDE chess we have the concepts of check, mate and stalemate. To evaluate these concepts in a given position, is not possible in a static way.
- An engine can only know that a King is in check, by looking one ply deeper, and check all potential moves, and see if one player could capture the King on the next move.
- An engine can only know that a King is mated or stalemated, by looking two plies deeper, and find a certainty that one of the Kings ends up off the board.
Piece activity, pawn structure, development, and many more aspects can perhaps be evaluated for a given position, without opening up the next tree of moves. But check, mate and stalemate cannot.
While writing a Chu Shogi engine, this aspect should be easier: a position is absolutely won if one King is off the board. But this does not work for FIDE chess.
I would like to understand how I can approach this, having to deal with check, mate and stalemate.
It searches the tree of subsequent moves for white/black up to a depth of a given number of plies. At the deepest level it would stop looking into more lines of moves, but just evaluate a position.
In FIDE chess we have the concepts of check, mate and stalemate. To evaluate these concepts in a given position, is not possible in a static way.
- An engine can only know that a King is in check, by looking one ply deeper, and check all potential moves, and see if one player could capture the King on the next move.
- An engine can only know that a King is mated or stalemated, by looking two plies deeper, and find a certainty that one of the Kings ends up off the board.
Piece activity, pawn structure, development, and many more aspects can perhaps be evaluated for a given position, without opening up the next tree of moves. But check, mate and stalemate cannot.
While writing a Chu Shogi engine, this aspect should be easier: a position is absolutely won if one King is off the board. But this does not work for FIDE chess.
I would like to understand how I can approach this, having to deal with check, mate and stalemate.