Home * Search * Mate Search

A Mate Search is used in some engines to find a forced checkmate in a certain number of moves. After finding a forced line to a mate, a mate search is used to check for any other forced mates in a lesser number of moves, which might have been cut off by some of the commonly used pruning methods in minimax search. Some programs are built exclusively to find mates, such as Chest. While these programs are similar to normal engines, they are not typically considered engines because they cannot play a full game of chess [1] .
The mate finding procedure usually works like an ordinary depth first search. The main difference lies in the absence of the evaluation function. Mate finders only look for forced mates, but not for any material/positional advances. So any other evaluations than a mate-inspection are useless.

Pruning

Backward Pruning

Pruning techniques that only discard nodes which wouldn't have influenced the final result anyway. Similar to standard chess engines mate searchers also use mate-distance-pruning. In its basic form all moves are pruned once a depth is reached, if another forced line has been found that has given mate at the same depth. Extending on this Heiner Marxen coined the term Fatal-Anti-Check. If in a line the side to move must be mated in the next move, prune if it can check the attacker and so that there is no way to avoid the check and mate the defender at the same time. This idea is comparable to some sound variation of futility pruning.

Forward Pruning

Mate searchers don't rely on probability based forward pruning techniques known from standard chess engines. As mate searchers are often used to solve chess problems that contain sacrifices, moves where these pruning techniques fail. Chest offers the user to search checking-moves only, prune if the defender has more than n moves, prune if the defending king has more than n moves or prune if more than n opponent pieces were able to move. Very stringent parameters can lead to solutions very quickly and can be extended gradually.

Interior Nodes Recognizers

Additionally to pruning technics, interior node recognizers are often used to speed up search. Particularly useful for chess problems are:

See also


Publications


Forum Posts


References

  1. ^ George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences, reprinted 1988 in Computer Chess Compendium

What links here?


Up one level