25,161
edits
Changes
Created page with "'''Home * Search * Mate Search''' A '''Mate Search''' is used in some engines to find a forced checkmate in a certain number of moves. After f..."
'''[[Main Page|Home]] * [[Search]] * Mate Search'''
A '''Mate Search''' is used in some engines to find a forced [[Checkmate|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|pruning]] methods in [[Minimax|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 <ref>[[George Baylor|George W. Baylor]], [[Herbert Simon|Herbert A. Simon]] ('''1966'''). ''[http://dl.acm.org/citation.cfm?id=1464182.1464233&coll=GUIDE&dl=GUIDE A chess mating combinations program]''. [https://en.wikipedia.org/wiki/American_Federation_of_Information_Processing_Societies AFIPS] [https://en.wikipedia.org/wiki/Joint_Computer_Conference Joint Computer Conferences], reprinted 1988 in [[Computer Chess Compendium]]</ref> .
The mate finding procedure usually works like an ordinary [[Depth-First|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|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 Recognizer|interior node recognizers]] are often used to speed up search. Particularly useful for chess problems are:
* [[Endgame Tablebases]]
* [[Mate at a Glance]]
* [[Blockage Detection]]
* [[Check#Perpetual|Perpetual Check Detection]]
* "Cold Position" Detection (see [[Chest]])
=See also=
* [[Checkmate]]
* [[Chest]]
* [[Mate at a Glance]]
* [[Mate-in-two]]
* [[Mater]]
* [[Popeye]]
* [[Proof-Number Search]]
=Publications=
* [[Dietrich Prinz]] ('''1952'''). ''Robot Chess''. Research, Vol. 6, reprinted 1988 in [[Computer Chess Compendium]] » [[Mate-in-two]]
* [[Gerd Veenker]] ('''1965'''). ''[http://www.degruyter.com/view/j/itit.1965.7.issue-1-6/itit.1965.7.16.25/itit.1965.7.16.25.xml Ein Programm zur Lösung von Schachaufgaben]''. [http://dblp.uni-trier.de/db/journals/it/it7.html Elektronische Rechenanlagen, Vol. 7], No. 1 (German)
* [[George Baylor|George W. Baylor]] ('''1965'''). ''[http://www.dtic.mil/docs/citations/AD0619018 Report on a Mating Combinations Program]''. SDC Paper, No. SP-2150, System Development Corporation, Santa Monica, Calif. » [[Mater]]
* [[George Baylor|George W. Baylor]], [[Herbert Simon|Herbert A. Simon]] ('''1966'''). ''[http://dl.acm.org/citation.cfm?id=1464182.1464233&coll=GUIDE&dl=GUIDE A chess mating combinations program]''. [https://en.wikipedia.org/wiki/American_Federation_of_Information_Processing_Societies AFIPS] [https://en.wikipedia.org/wiki/Joint_Computer_Conference Joint Computer Conferences], reprinted 1988 in [[Computer Chess Compendium]]
* [[George Baylor|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, [https://en.wikipedia.org/wiki/Nauka_%28publisher%29 Nauka], [https://en.wikipedia.org/wiki/Moscow Moscow]
* [[Max Bramer]] ('''1982'''). ''Finding Checkmates''. [https://en.wikipedia.org/wiki/Computer_and_Video_Games Computer & Video Games], [http://www.chesscomputeruk.com/html/publication_archive_1982.html Spring 1982], [http://www.chesscomputeruk.com/Computer___Video_Games_Spring_1982.pdf 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 [http://www.top-5000.nl/ps/Mate%20in%2038-%20applying%20proof%20number%20search%20to%20chess.pdf Mate in 38: Applying Proof-Number Search] from [[Ed Schroder|Ed Schroder's]] [http://www.top-5000.nl/prostuff.htm Programmer's Stuff site]
* [[Vladan Vučković]] ('''2004'''). ''Realization of the Chess Mate Solver Application''. [http://www.doiserbia.nb.rs/issue.aspx?issueid=138 Yugoslav Journal of Operations Research, Volume 14, Number 2], [http://www.doiserbia.nbs.bg.ac.yu/img/doi/0354-0243/2004/0354-02430402273V.pdf pdf]
* [[Ami Hauptman]], [[Moshe Sipper]] ('''2007'''). ''Evolution of an Efficient Search Algorithm for the Mate-In-N Problem in Chess''. [http://www.informatik.uni-trier.de/~%20LEY/db/conf/eurogp/eurogp2007.html EuroGP 2007], [http://www.cs.bgu.ac.il/~sipper/papabs/gpsearch.pdf pdf]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=130376 Questions about Mate Searching] by [[William Bryant]], [[CCC]], September 23, 2000
* [http://www.talkchess.com/forum/viewtopic.php?t=57076 Dedicated mate finders] by [[Steven Edwards]], [[CCC]], July 25, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=61731 Why do engines lack mate solving?] by [[Rasmus Althoff]], [[CCC]], October 15, 2016
=References=
<references />
'''[[Search|Up one level]]'''
A '''Mate Search''' is used in some engines to find a forced [[Checkmate|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|pruning]] methods in [[Minimax|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 <ref>[[George Baylor|George W. Baylor]], [[Herbert Simon|Herbert A. Simon]] ('''1966'''). ''[http://dl.acm.org/citation.cfm?id=1464182.1464233&coll=GUIDE&dl=GUIDE A chess mating combinations program]''. [https://en.wikipedia.org/wiki/American_Federation_of_Information_Processing_Societies AFIPS] [https://en.wikipedia.org/wiki/Joint_Computer_Conference Joint Computer Conferences], reprinted 1988 in [[Computer Chess Compendium]]</ref> .
The mate finding procedure usually works like an ordinary [[Depth-First|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|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 Recognizer|interior node recognizers]] are often used to speed up search. Particularly useful for chess problems are:
* [[Endgame Tablebases]]
* [[Mate at a Glance]]
* [[Blockage Detection]]
* [[Check#Perpetual|Perpetual Check Detection]]
* "Cold Position" Detection (see [[Chest]])
=See also=
* [[Checkmate]]
* [[Chest]]
* [[Mate at a Glance]]
* [[Mate-in-two]]
* [[Mater]]
* [[Popeye]]
* [[Proof-Number Search]]
=Publications=
* [[Dietrich Prinz]] ('''1952'''). ''Robot Chess''. Research, Vol. 6, reprinted 1988 in [[Computer Chess Compendium]] » [[Mate-in-two]]
* [[Gerd Veenker]] ('''1965'''). ''[http://www.degruyter.com/view/j/itit.1965.7.issue-1-6/itit.1965.7.16.25/itit.1965.7.16.25.xml Ein Programm zur Lösung von Schachaufgaben]''. [http://dblp.uni-trier.de/db/journals/it/it7.html Elektronische Rechenanlagen, Vol. 7], No. 1 (German)
* [[George Baylor|George W. Baylor]] ('''1965'''). ''[http://www.dtic.mil/docs/citations/AD0619018 Report on a Mating Combinations Program]''. SDC Paper, No. SP-2150, System Development Corporation, Santa Monica, Calif. » [[Mater]]
* [[George Baylor|George W. Baylor]], [[Herbert Simon|Herbert A. Simon]] ('''1966'''). ''[http://dl.acm.org/citation.cfm?id=1464182.1464233&coll=GUIDE&dl=GUIDE A chess mating combinations program]''. [https://en.wikipedia.org/wiki/American_Federation_of_Information_Processing_Societies AFIPS] [https://en.wikipedia.org/wiki/Joint_Computer_Conference Joint Computer Conferences], reprinted 1988 in [[Computer Chess Compendium]]
* [[George Baylor|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, [https://en.wikipedia.org/wiki/Nauka_%28publisher%29 Nauka], [https://en.wikipedia.org/wiki/Moscow Moscow]
* [[Max Bramer]] ('''1982'''). ''Finding Checkmates''. [https://en.wikipedia.org/wiki/Computer_and_Video_Games Computer & Video Games], [http://www.chesscomputeruk.com/html/publication_archive_1982.html Spring 1982], [http://www.chesscomputeruk.com/Computer___Video_Games_Spring_1982.pdf 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 [http://www.top-5000.nl/ps/Mate%20in%2038-%20applying%20proof%20number%20search%20to%20chess.pdf Mate in 38: Applying Proof-Number Search] from [[Ed Schroder|Ed Schroder's]] [http://www.top-5000.nl/prostuff.htm Programmer's Stuff site]
* [[Vladan Vučković]] ('''2004'''). ''Realization of the Chess Mate Solver Application''. [http://www.doiserbia.nb.rs/issue.aspx?issueid=138 Yugoslav Journal of Operations Research, Volume 14, Number 2], [http://www.doiserbia.nbs.bg.ac.yu/img/doi/0354-0243/2004/0354-02430402273V.pdf pdf]
* [[Ami Hauptman]], [[Moshe Sipper]] ('''2007'''). ''Evolution of an Efficient Search Algorithm for the Mate-In-N Problem in Chess''. [http://www.informatik.uni-trier.de/~%20LEY/db/conf/eurogp/eurogp2007.html EuroGP 2007], [http://www.cs.bgu.ac.il/~sipper/papabs/gpsearch.pdf pdf]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=130376 Questions about Mate Searching] by [[William Bryant]], [[CCC]], September 23, 2000
* [http://www.talkchess.com/forum/viewtopic.php?t=57076 Dedicated mate finders] by [[Steven Edwards]], [[CCC]], July 25, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=61731 Why do engines lack mate solving?] by [[Rasmus Althoff]], [[CCC]], October 15, 2016
=References=
<references />
'''[[Search|Up one level]]'''
