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.
Contents
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
- Dietrich Prinz (1952). Robot Chess. Research, Vol. 6, reprinted 1988 in Computer Chess Compendium » Mate-in-two
- Gerd Veenker (1965). Ein Programm zur Lösung von Schachaufgaben. Elektronische Rechenanlagen, Vol. 7, No. 1 (German)
- George W. Baylor (1965). Report on a Mating Combinations Program. SDC Paper, No. SP-2150, System Development Corporation, Santa Monica, Calif. » Mater
- George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences, reprinted 1988 in Computer Chess Compendium
- George W. Baylor (1966). A Computer Model of Checkmating Behaviour in Chess. in Adriaan de Groot, Walter R. Reitman (eds.) (1966). Heuristic Processes in Thinking. International Congress of Psychology, Nauka, Moscow
- Max Bramer (1982). Finding Checkmates. Computer & Video Games, Spring 1982, pdf hosted by Mike Watters » Mater
- Dennis Breuker, Victor Allis, Jaap van den Herik (1994). How to Mate: Applying Proof-Number Search. Advances in Computer Chess 7, reprint as Mate in 38: Applying Proof-Number Search from Ed Schroder's Programmer's Stuff site
- Vladan Vučković (2004). Realization of the Chess Mate Solver Application. Yugoslav Journal of Operations Research, Volume 14, Number 2, pdf
- Ami Hauptman, Moshe Sipper (2007). Evolution of an Efficient Search Algorithm for the Mate-In-N Problem in Chess. EuroGP 2007, pdf
Forum Posts
- Questions about Mate Searching by William Bryant, CCC, September 23, 2000
- Dedicated mate finders by Steven Edwards, CCC, July 25, 2015
- Why do engines lack mate solving? by Rasmus Althoff, CCC, October 15, 2016
References
- ↑ George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences, reprinted 1988 in Computer Chess Compendium
