Difference between revisions of "Checkmate"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
(One intermediate revision by the same user not shown) | |||
Line 105: | Line 105: | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=61134 Mate scores from IID] by [[Matthew R. Brades]], [[CCC]], August 16, 2016 » [[Internal Iterative Deepening]] | * [http://www.talkchess.com/forum/viewtopic.php?t=61134 Mate scores from IID] by [[Matthew R. Brades]], [[CCC]], August 16, 2016 » [[Internal Iterative Deepening]] | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=61731 Why do engines lack mate solving?] by [[Rasmus Althoff]], [[CCC]], October 15, 2016 » [[Mate Search]] | * [http://www.talkchess.com/forum/viewtopic.php?t=61731 Why do engines lack mate solving?] by [[Rasmus Althoff]], [[CCC]], October 15, 2016 » [[Mate Search]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=64428 Mate Score] by [[Tamás Kuzmics]], [[CCC]], June 27, 2017 | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=67049 Mate scores in TT (a new?... approach)] by Vince Sempronio, [[CCC]], April 09, 2018 | * [http://www.talkchess.com/forum/viewtopic.php?t=67049 Mate scores in TT (a new?... approach)] by Vince Sempronio, [[CCC]], April 09, 2018 | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=67078 Yet another Mate scores in TT thread] by [[Andrew Grant]], [[CCC]], April 12, 2018 » [[Score]], [[Transposition Table]] | * [http://www.talkchess.com/forum/viewtopic.php?t=67078 Yet another Mate scores in TT thread] by [[Andrew Grant]], [[CCC]], April 12, 2018 » [[Score]], [[Transposition Table]] | ||
Line 110: | Line 111: | ||
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=68146 A mate suite to test multi-pv and new engines] by [[Uri Blass]], [[CCC]], August 06, 2018 | * [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=68146 A mate suite to test multi-pv and new engines] by [[Uri Blass]], [[CCC]], August 06, 2018 | ||
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=71337 Trying to find a weird mate in 1...] by [[Martin Bryant]], [[CCC]], July 22, 2019 » [[#FiebergMateInOne|Fieberg's mate-in-1]] | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=71337 Trying to find a weird mate in 1...] by [[Martin Bryant]], [[CCC]], July 22, 2019 » [[#FiebergMateInOne|Fieberg's mate-in-1]] | ||
+ | ==2020 ...== | ||
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74411 Correct way to store and extract mate scores] by Ian Mitchell, [[CCC]], July 08, 2020 » [[Score]], [[Transposition Table]] | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74411 Correct way to store and extract mate scores] by Ian Mitchell, [[CCC]], July 08, 2020 » [[Score]], [[Transposition Table]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=77834 mate suite for chess engines] by [[Uri Blass]], [[CCC]], July 30, 2021 | ||
<span id="Leonid"></span> | <span id="Leonid"></span> | ||
==Leonid's Positions== | ==Leonid's Positions== |
Latest revision as of 21:27, 5 August 2021
Checkmate (often shortened to mate) occurs if a king is under immediate attack by one (or two) opponent pieces (in check) and has no way to remove it from attack on the next move. Checkmate is the object of the game of chess, it ends with the mate giving player as the winner, and the mated player the loser.
Contents
Mate Score
At the Root
At the root the score of a mated player is the worst score one can get, that is a negative score with the greatest absolute value of the score range. It is quite common and sufficient to use something like this in C, C++:
#include <limits.h> /* (-32768/2 = -16384) */ #define VALUE_MATED (SHRT_MIN/2)
Inside a 16-bit short integer range, assuming centipawn evaluation, it translates to roughly being 16 queens down. Note that using SHRT_MIN instead of SHRT_MIN/2 as mate value has issues in greater/less comparisons of additive expressions, where summands around SHRT_MIN or SHRT_MAX may under- or overflow, which has somehow relaxed with the advent of the usual 32-bit sign-extension.
Down the Tree
Inside a negamax based search, most [4] programs assign VALUE_MATED + ply distance to the root as worst case score if entering a node, which if propagated as mate score along the Principal Variation to the root, translates in mate in odd plies (positive values), or getting mated in even plies. However, those scores need ply-adjustment if stored as exact score inside the transposition table, and re-adjustment if retrieving from TT. An alternative approach, not only related to mate scores was proposed by Harm Geert Muller, The Delay Penalty as implemented in Micro-Max [5] [6] [7] [8].
Detecting Mate
Some programs rely on pseudo-legal move generation, and find Checkmate if all those moves are in fact illegal after making and finding the "refutation" of capturing the king. At the latest, if no legal move was found, programs need the information whether the king is in check to decide about checkmate or stalemate score. Despite, most programs (should be) are aware of check in advance, and use special move generator(s) if in check or even in double check:
- Double check
- Only King moves or captures
- Single check
- Capture the checking piece
- King moves or captures
- In case of distant checks, interposing a piece between the threatening sliding piece and the king
See also
- Check
- Chess Problems, Compositions and Studies
- Mate at a Glance
- Mate Distance Pruning
- Mate-in-two
- Mate Search
- Stalemate
Publications
1952
- Dietrich Prinz (1952). Robot Chess. Research, Vol. 6, reprinted 1988 in Computer Chess Compendium » Mate-in-two
1965 ...
- 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 in Herbert A. Simon (1979). Models of Thought. Yale University Press, pp. 181-200, in David Levy (ed.) (1988). 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
- Vladimir E. Alekseev (1969). Compilation of Chess Problems on a Computer. Technical translation FSTC-HT-23-124-69, US Army, NTIS AD 689470 (Problemy Kibernetiki, 19, 1967)
1980 ...
- John Birmingham, Peter Kent (1980). Mate at a Glance. Advances in Computer Chess 2, reprinted in Computer Chess Compendium
- Max Bramer (1982). Finding Checkmates. Computer & Video Games, Spring 1982, pdf hosted by Mike Watters » Mater
- Don Beal (1984). Mating Sequences in the Quiescence Search. ICCA Journal, Vol. 7, No. 3
1990 ...
- Thomas Mally (1993). Matt in Wieviel? PC Schach 3/93 (German)
2000 ...
- Vladan Vučković (2004). Realization of the Chess Mate Solver Application. Yugoslav Journal of Operations Research, Volume 14, Number 2, pdf
- Fridel Fainshtein (2006). An Orthodox k-Move Problem-Composer for Chess Directmates. M.Sc. thesis, Bar-Ilan University, pdf
- Fridel Fainshtein, Yaakov HaCohen-Kerner (2006). A Chess Composer of Two-Move Mate Problems. ICGA Journal, Vol. 29, No. 1, pdf
- Ami Hauptman, Moshe Sipper (2007). Evolution of an Efficient Search Algorithm for the Mate-In-N Problem in Chess. EuroGP 2007, pdf
2010 ...
- Azlan Iqbal (2010). Aesthetics in Mate-In-3 Combinations. Part I Combinatorics and Weights, ICGA Journal, Vol. 33, No. 3
- Azlan Iqbal (2010). Aesthetics in Mate-In-3 Combinations. Part II Normality, ICGA Journal, Vol. 33, No. 4
- Taichi Ishitobi, Alessandro Cincotti, Hiroyuki Iida (2013). Shape-Keeping Technique and Its Application to Checkmate Problem Composition. 2013 AIIDE Workshop
Forum Posts
1997 ...
- Mate in 4 explanation by Howard Exner, CCC, October 07, 1997
- Mate in 30 testposition for Rebel 9! by Jouni Uski, CCC, November 20, 1997 » Rebel
- Mate in 18 moves? by Ed Schröder, CCC, January 09, 1998
- Using too-shallow mate scores from the hash table by David Eppstein, CCC, July 05, 1998
- Re: Using too-shallow mate scores from the hash table by David Eppstein, CCC, July 06, 1998
- Re: Using too-shallow mate scores from the hash table by Don Dailey, CCC, July 07, 1998
- Solve for Mate by Trefor Deane, CCC, July 11, 1998
- Mate the Royal Couple by Hans Havermann, CCC, November 14, 1998
- Estimated # of checkmate positions? by Jeff Anderson, CCC, July 07, 1999
- Mate solvers... by Dann Corbit, CCC, September 07, 1999
- Interesting mate test for hashing by Robert Hyatt, CCC, September 10, 1999 » Transposition Table
- Is "Interesting mate test..." the longest ever thread.... by Tina Long, CCC, September 11, 1999
2000 ...
- Mate in 1 - but Fritz 6 needs 1 hour!!! by Christoph Fieberg, CCC, August 10, 2000
- What's the fastest mate-finder? by Michel Langeveld, CCC, August 27, 2000
- Questions about Mate Searching by William Bryant, CCC, September 23, 2000 » Mate Search
- Mate in 7 moves - diagram by Eduard Nemeth, CCC, September 27, 2000 » Zugzwang
- Static Mate Detection by Gerd Isenberg, CCC, January 22, 2002 » Mate at a Glance
- First mate in 2, then mate in 3 by Albert Bertilsson, CCC, March 03, 2003
- Easy mate by Frank Phillips, CCC, September 13, 2003 [9]
2005 ...
- Shortest ever mate? by Tord Romstad, CCC, October 30, 2005
- The Code for the Rybka-Mate-Bug by Chrilly Donninger, CCC, December 13, 2005 » Rybka
- Unusual Mate in 3 by Charles Roberson, CCC, March 02, 2006
- Delayed-loss-bonus discussion goes here by Harm Geert Muller, CCC, September 28, 2007
- mate detetion issue by Mike Adams, CCC, October 24, 2008 » Connect Four, Fail-Soft
- How to check for checkmate/stalemate programmatically? by Valentin, Rybka Forum, November 22, 2008 » Stalemate
- Draw by repetition when mate is possible by Mathieu Pagé, CCC, December 30, 2008 » Repetitions
2010 ...
- Puzzle with mate scores in TT by Robert Purves, CCC, December 10, 2010 » Score, Transposition Table
- Yet Another Mate Solving Test by Jouni Uski, CCC, January 14, 2011
- Mate score in TT by Marco Costalba, CCC, December 28, 2011 » Score, Transposition Table
- Checkmate In Zero by Christopher Conkie, CCC, January 02, 2013
- Quiescence Search and Checkmates by CDaley11, OpenChess Forum, January 11, 2013 » Quiescence Search
- To be, or not to be checkmated by Harm Geert Muller, CCC, April 18, 2014
- Mate score from the transposition table by Evert Glebbeek, CCC, October 25, 2014 » Score, Transposition Table
2015 ...
- Remember Leonid Liberman (author of LLCHESS)? by Dann Corbit, CCC, May 23, 2015 » Leonid's Positions
- TT Mate scores by rgoomes, OpenChess Forum, February 10, 2016 » Score, Transposition Table
- Funny mate in 6 by Sergei S. Markoff, CCC, February 17, 2016
- Mate scores from IID by Matthew R. Brades, CCC, August 16, 2016 » Internal Iterative Deepening
- Why do engines lack mate solving? by Rasmus Althoff, CCC, October 15, 2016 » Mate Search
- Mate Score by Tamás Kuzmics, CCC, June 27, 2017
- Mate scores in TT (a new?... approach) by Vince Sempronio, CCC, April 09, 2018
- Yet another Mate scores in TT thread by Andrew Grant, CCC, April 12, 2018 » Score, Transposition Table
- mate test positions by Uri Blass, CCC, July 29, 2018 » Test-Positions
- A mate suite to test multi-pv and new engines by Uri Blass, CCC, August 06, 2018
- Trying to find a weird mate in 1... by Martin Bryant, CCC, July 22, 2019 » Fieberg's mate-in-1
2020 ...
- Correct way to store and extract mate scores by Ian Mitchell, CCC, July 08, 2020 » Score, Transposition Table
- mate suite for chess engines by Uri Blass, CCC, July 30, 2021
Leonid's Positions
- Mate in ...? by Leonid, CCC, February 12, 2000
- Two mate positions to solve by Leonid, CCC, September 02, 2000
- Two mate position to solve by Leonid, CCC, September 06, 2000
- What shortest mate that you can find for this position? by Leonid, CCC, January 17, 2001
- If you like to find a mate... by Leonid, CCC, January 18, 2001
- If you want solve one mate... by Leonid, CCC, January 21, 2001
- One easy mate to solve... by Leonid, CCC, January 22, 2001
- One average mate position... by Leonid, CCC, January 23, 2001
- If you like to solve easy forced mate... by Leonid, CCC, January 24, 2001
- If you like to solve average mate position... by Leonid, CCC, January 25, 2001
- If you like to solve real mate... by Leonid, CCC, January 27, 2001
- If you like to solve mate from real game... by Leonid, CCC, January 28, 2001
- If you like forced mate... by Leonid, CCC, January 30, 2001
- Forced mate position to solve... by Leonid, CCC, January 31, 2001
- If you like to solve a mate... by Leonid, CCC, February 01, 2001
- Forced mate so solve... by Leonid, CCC, February 05, 2001
- If you like to solve easy mate... by Leonid, CCC, February 08, 2001
- If you like to solve a mate... by Leonid, CCC, February 09, 2001
- If you like to crush easy mate... by Leonid, CCC, February 10, 2001
- If you like to solve mate for light position... by Leonid, CCC, February 11, 2001
- If you like to solve mate... by Leonid, CCC, February 14, 2001
- If you like solving forced mate... by Leonid, CCC, February 15, 2001
- If you like to solve one easy mate... by Leonid, CCC, February 16, 2001
- Easy mate to solve... by Leonid, CCC, March 04, 2001
- If you like to sove a mate... by Leonid, CCC, March 10, 2001
- If you are ready to solve one mate... by Leonid, CCC, April 11, 2001
- If you like easy mate... by Leonid, CCC, April 12, 2001
- If you want to solve one mate... by Leonid, CCC, April 14, 2001
- If you enjoy like me solving mates... by Leonid, CCC, April 16, 2001
- Mate that every program will solve... by Leonid, CCC, April 17, 2001
- One mate to solve... by Leonid, CCC, April 22, 2001
- Mate to solve... by Leonid, CCC, April 23, 2001
- Mate that every program will find by Leonid, CCC, April 26, 2001
- Mate to solve for champions... by Leonid, CCC, April 29, 2001
- One mate to solve for fittest programs by Leonid, CCC, May 04, 2001
- Very easy mate to solve by Leonid, CCC, May 05, 2001
- One mate to solve... by Leonid, CCC, May 06, 2001
- Mate to solve in two flavous by Leonid, CCC, May 07, 2001
- One mate to solve... by Leonid, CCC, May 08, 2001
- One mate to solve... by Leonid, CCC, May 15, 2001
- One very easy mate to solve by Leonid, CCC, May 21, 2001
- One mate to solve... by Leonid, CCC, May 30, 2001
- One mate to solve... by Leonid, CCC, June 02, 2001
- Mate to solve for good program by Leonid, CCC, June 07, 2001
- One mate to solve for Champion! by Leonid, CCC, June 16, 2001
- One mate to solve by Leonid, CCC, July 17, 2001
- One mate to sove for Champions! by Leonid, CCC, September 02, 2001
- One mate to solve for Champions! by Leonid, CCC, October 02, 2001
- A mate for Leonid by Sven Reichard, CCC, October 10, 2001
- Try this mate by Leonid, CCC, October 16, 2001
- Try solve this mate by Leonid, CCC, October 21, 2001
- Try this moderate mate by Leonid, CCC, October 27, 2001
- One easy mate by Leonid, CCC, November 04, 2001
- Very easy mate to solve by Leonid, CCC, December 22, 2001
- Find a mate by Leonid, CCC, August 03, 2002
- One mate in 10 to solve by Leonid, CCC, August 10, 2002
- One mate in 11 by Leonid, CCC, September 07, 2002
- Try to solve mate by Leonid, CCC, September 14, 2002
- Mate slightly harder by Leonid, CCC, August 25, 2003
- Mate that should be easy by Leonid, CCC, October 19, 2003
- Heavy mate position but easy to solve by Leonid, CCC, October 20, 2003
- Mate to torture by Leonid, CCC, November 02, 2003
- Try very easy mate by Leonid, CCC, November 04, 2003
- Try to solve very populated mate by Leonid, CCC, November 05, 2003
- Very easy mate by Leonid, CCC, November 06, 2003
External Links
- Checkmate from Wikipedia
- Checkmate pattern from Wikipedia
- Checkmate/Stalemate Scoring from Bruce Moreland's Programming Topics
- Handling Mate Scores from Bruce Moreland's Programming Topics
References
- ↑ Shannon Larratt - Fool's mate (2007) from Tableaux ayant pour sujet les échecs (dead link)
- ↑ In Loving Memory of Shannon Larratt 1:24, YouTube Video
- ↑ Shannon Larratt is Zentastic › Blog archives, February 09, 2007
- ↑ The Code for the Rybka-Mate-Bug by Chrilly Donninger, CCC, December 13, 2005
- ↑ Evaluation: Aging - The Delay Penalty from Micro-Max by Harm Geert Muller
- ↑ Re: Transposition Tables by Harm Geert Muller, CCC, September 26, 2007
- ↑ Delayed-loss-bonus discussion goes here by Harm Geert Muller, CCC, September 28, 2007
- ↑ Seeing a promotion, but not playing it... by Harm Geert Muller, CCC, January 24, 2010
- ↑ Frank Phillips' KNNKP position revisited ... by Guy Haworth, CCC, September 18, 2003 » Endgame Tablebases