Can someone describe to me the best way to search for Check Mate in a chess engine.
I am currently using an attack board comparing all of the chess board squares being attacked against the moves a king can make. Is there an easier way?
Checking for Mate
Moderator: Ras
-
Desperado
- Posts: 879
- Joined: Mon Dec 15, 2008 11:45 am
Re: Checking for Mate
Hello Adam,
i think you ask for _detecting_ a mate (not searching), or ?!
if so, one possibility is to catch the case where no legal move
is available in a certain node.
(
-loop your movelist
-check if king can be captured (is attacked) after each move
)
Then, when you leave the loop and no legalMove is counted,
test if king is attacked, so to differ between mate/stalemate.
Michael
i think you ask for _detecting_ a mate (not searching), or ?!
if so, one possibility is to catch the case where no legal move
is available in a certain node.
(
-loop your movelist
-check if king can be captured (is attacked) after each move
)
Then, when you leave the loop and no legalMove is counted,
test if king is attacked, so to differ between mate/stalemate.
Michael
-
Sven
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Checking for Mate
Please describe your goal first: are you looking for a way
a) to detect checkmate during normal tree search of your chess engine, or
b) to do a specialized search that is designed to find checkmate in N plies only (which is not necessarily part of a chess engine but may be useful within a special mate searching program)?
Taking into account your previous postings up to now, I would assume a) of course, but we should be sure about it. The following is based on my assumption a).
It is also necessary to know more about your way of checking legality, and about your check detection strategy.
1) May I assume that you generate all pseudo-legal moves, and that you check for legality of each move by making it on the board and then checking whether this leaves or puts the king of the side that made the move in/into check?
2) Are you using check extension, i.e. do you detect whether the king of the moving side is in check at the very beginning of each node, and increment the remaining depth by one in case it is in check?
In case 2) is true it would be useful to maintain a boolean "is in check" flag for each ply which you set according to the result of your check detection function. This is to avoid calling that function several times for the same node. Be sure, though, to only use the value of that flag after having called the check detection function once for the current node.
Under all these assumptions, the algorithm for mate detection works like Michael already described. When all pseudo-legal moves have been tried during full-width search but none of them was legal, you definitely have an end-of-game situation on the board: either the moving side is checkmated (when being in check), or it is a stalemate.
When the moving side is checkmated, you have to return a value that reflects the distance from the root to the current node (e.g. -(MAX_VALUE - distanceFromRoot)). Otherwise you will never find the shortest mate, and also in winning positions your engine will frequently play a move that "mates in three plies" instead of immediately playing the mating move, which effectively means it will often be unable to checkmate the opponent even though it sees a deeper mate. This would happen because a mate in one ply would have the same value as a mate in three, five, ... plies, which would be wrong. (The same would apply to the opposite case, being checkmated. The engine would look quite dumb by allowing immediate mate instead of postponing the mate for some moves, although this is less important than being unable to win.)
There are at least two ways of tracking whether all moves were illegal. One is simple: maintain a local boolean flag "hasLegalMove" which you set to true if a move that has been made is not illegal. The other way is possible if you are using the "fail-soft" variant of the alpha-beta search algorithm, because in that case you initialize your "bestValue" variable to -MAX_VALUE (or -INFINITY) prior to the move loop, and this would allow to test whether "bestValue == -MAX_VALUE" is still valid behind the loop, indicating that there was no legal move made and therefore no move raised "bestValue". (Again: only during full-width search - many engines are not able to detect checkmate during quiescence search.) With the traditional alpha-beta algorithm this is not possible because a legal move can fail low with a value <= alpha and therefore does not raise your "alpha" variable.
Sven
a) to detect checkmate during normal tree search of your chess engine, or
b) to do a specialized search that is designed to find checkmate in N plies only (which is not necessarily part of a chess engine but may be useful within a special mate searching program)?
Taking into account your previous postings up to now, I would assume a) of course, but we should be sure about it. The following is based on my assumption a).
It is also necessary to know more about your way of checking legality, and about your check detection strategy.
1) May I assume that you generate all pseudo-legal moves, and that you check for legality of each move by making it on the board and then checking whether this leaves or puts the king of the side that made the move in/into check?
2) Are you using check extension, i.e. do you detect whether the king of the moving side is in check at the very beginning of each node, and increment the remaining depth by one in case it is in check?
In case 2) is true it would be useful to maintain a boolean "is in check" flag for each ply which you set according to the result of your check detection function. This is to avoid calling that function several times for the same node. Be sure, though, to only use the value of that flag after having called the check detection function once for the current node.
Under all these assumptions, the algorithm for mate detection works like Michael already described. When all pseudo-legal moves have been tried during full-width search but none of them was legal, you definitely have an end-of-game situation on the board: either the moving side is checkmated (when being in check), or it is a stalemate.
When the moving side is checkmated, you have to return a value that reflects the distance from the root to the current node (e.g. -(MAX_VALUE - distanceFromRoot)). Otherwise you will never find the shortest mate, and also in winning positions your engine will frequently play a move that "mates in three plies" instead of immediately playing the mating move, which effectively means it will often be unable to checkmate the opponent even though it sees a deeper mate. This would happen because a mate in one ply would have the same value as a mate in three, five, ... plies, which would be wrong. (The same would apply to the opposite case, being checkmated. The engine would look quite dumb by allowing immediate mate instead of postponing the mate for some moves, although this is less important than being unable to win.)
There are at least two ways of tracking whether all moves were illegal. One is simple: maintain a local boolean flag "hasLegalMove" which you set to true if a move that has been made is not illegal. The other way is possible if you are using the "fail-soft" variant of the alpha-beta search algorithm, because in that case you initialize your "bestValue" variable to -MAX_VALUE (or -INFINITY) prior to the move loop, and this would allow to test whether "bestValue == -MAX_VALUE" is still valid behind the loop, indicating that there was no legal move made and therefore no move raised "bestValue". (Again: only during full-width search - many engines are not able to detect checkmate during quiescence search.) With the traditional alpha-beta algorithm this is not possible because a legal move can fail low with a value <= alpha and therefore does not raise your "alpha" variable.
Sven