Difference between revisions of "KBNK Endgame"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
Line 70: | Line 70: | ||
=Forum Posts= | =Forum Posts= | ||
+ | ==1997 ...== | ||
* [https://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/d25a7b108d1332a5/ How to get chess program to solve KBN mate?] by Paul Pedriana, [[Computer Chess Forums|rgcc]], September 17, 1997 | * [https://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/d25a7b108d1332a5/ How to get chess program to solve KBN mate?] by Paul Pedriana, [[Computer Chess Forums|rgcc]], September 17, 1997 | ||
: [https://groups.google.com/group/rec.games.chess.computer/msg/ba9febc300f8698f Re: How to get chess program to solve KBN mate?] by [[David Blackman|David John Blackman]], [[Computer Chess Forums|rgcc]], September 18, 1997 » [[KnightCap]] | : [https://groups.google.com/group/rec.games.chess.computer/msg/ba9febc300f8698f Re: How to get chess program to solve KBN mate?] by [[David Blackman|David John Blackman]], [[Computer Chess Forums|rgcc]], September 18, 1997 » [[KnightCap]] | ||
+ | ==2000 ...== | ||
* [https://www.stmintz.com/ccc/index.php?id=110681 Caution K v KBN and lazy eval or futility] by [[Brian Richardson]], [[CCC]], May 14, 2000 » [[Lazy Evaluation]], [[Futility Pruning]] | * [https://www.stmintz.com/ccc/index.php?id=110681 Caution K v KBN and lazy eval or futility] by [[Brian Richardson]], [[CCC]], May 14, 2000 » [[Lazy Evaluation]], [[Futility Pruning]] | ||
* [https://www.stmintz.com/ccc/index.php?id=350837 Symbolic: The KBNK recognizer] by [[Steven Edwards]], [[CCC]], February 23, 2004 » [[Symbolic]] | * [https://www.stmintz.com/ccc/index.php?id=350837 Symbolic: The KBNK recognizer] by [[Steven Edwards]], [[CCC]], February 23, 2004 » [[Symbolic]] | ||
* [https://www.stmintz.com/ccc/index.php?id=351153 Symbolic: KBNK merit sample code] by [[Steven Edwards]], [[CCC]], February 24, 2004 | * [https://www.stmintz.com/ccc/index.php?id=351153 Symbolic: KBNK merit sample code] by [[Steven Edwards]], [[CCC]], February 24, 2004 | ||
+ | ==2010 ...== | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=45009&start=5 Re: Search with bitbase] by [[Joona Kiiski]], [[CCC]], September 05, 2012 | * [http://www.talkchess.com/forum/viewtopic.php?t=45009&start=5 Re: Search with bitbase] by [[Joona Kiiski]], [[CCC]], September 05, 2012 | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=48826&start=22 Re: Best was to Recognize Know Endgames?] by [[Harm Geert Muller]], [[CCC]], August 03, 2013 » [[Interior Node Recognizer]] | * [http://www.talkchess.com/forum/viewtopic.php?t=48826&start=22 Re: Best was to Recognize Know Endgames?] by [[Harm Geert Muller]], [[CCC]], August 03, 2013 » [[Interior Node Recognizer]] | ||
Line 81: | Line 84: | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=58965 Improved corner painting] by [[Harm Geert Muller]], [[CCC]], January 18, 2016 » [[Fairy-Max]] | * [http://www.talkchess.com/forum/viewtopic.php?t=58965 Improved corner painting] by [[Harm Geert Muller]], [[CCC]], January 18, 2016 » [[Fairy-Max]] | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=62257 Simple method for simple mates for programs without TBs] by [[J. Wesley Cleveland]], [[CCC]], November 25, 2016 » [[Center Manhattan-Distance]], [[Mop-up Evaluation]] | * [http://www.talkchess.com/forum/viewtopic.php?t=62257 Simple method for simple mates for programs without TBs] by [[J. Wesley Cleveland]], [[CCC]], November 25, 2016 » [[Center Manhattan-Distance]], [[Mop-up Evaluation]] | ||
+ | ==2020 ...== | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77249 knbk DTM] by [[Martin Sedlak]], [[CCC]], May 05, 2021 » [[Endgame Tablebases#DTM|DTM]] | ||
+ | : [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77249&start=4 Re: knbk DTM] by [[Harm Geert Muller]], [[CCC]], May 05, 2021 » [[Marcel van Kervinck|Marcel van Kervinck's]] pretty fast kbnk generator | ||
=External links= | =External links= |
Latest revision as of 09:52, 8 May 2021
Home * Evaluation * Endgame * KBNK
A checkmate with a bishop and a knight against a lone king is delivered in the corner that can be covered by a bishop of the attacking side. For that reason a program ought to use a separate piece-square table for the position of the opponent king in order to drive it to the correct corner. Draw cases due to tactical loss of one of the pieces [1] or the stalemate trap are left to the search routine.
Contents
Corner-Distance
Alternatively, following Bit-twiddling determines the Manhattan-Distance to the closest corner square of the bishop square color, which might be used as a bonus for the lonesome king. First, the color of the bishop square is determined by a multiplication based on 9, to find whether its file and rank sum is odd or even. It is done that way, that an odd sum results in the sign-bit set, to build a mask by shifting arithmetically right and to conditionally flip the file of the king square, so that squares 0 and 63 become the relevant corner squares. The king's Corner Manhattan-distance is then simply the sum of its rank and file indices, if it exceeds 7 the difference to 14 is taken to force the symmetry, mirrored along the diagonal or anti-diagonal.
0 1 2 3 4 5 6 7 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 6 6 7 6 5 4 3 2 1 2 3 4 5 6 7 6 5 5 6 7 6 5 4 3 2 3 4 5 6 7 6 5 4 4 5 6 7 6 5 4 3 4 5 6 7 6 5 4 3 3 4 5 6 7 6 5 4 5 6 7 6 5 4 3 2 2 3 4 5 6 7 6 5 6 7 6 5 4 3 2 1 1 2 3 4 5 6 7 6 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7
/** * manhattanDistance2ClosestCornerOfBishopSquareColor * for KBNK purpose * @author Gerd Isenberg * @param b bishop square (to determine its square color) * @param k opponent king square (0..63) * @return manhattanDistance to the closest corner square * of the bishop square color */ int manhattanDistance2ClosestCornerOfBishopSquareColor(int b, int k) { b = -1879048192*b >> 31; // 0 | -1 to mirror k = (k>>3) + ((k^b) & 7); // rank + (mirrored) file k = (15*(k>>3)^k)-(k>>3); // if (k > 7) k = 14 - k return k; }
which results in following x86 Assembly:
?manhattanDistance2ClosestCornerOfBishopSquareColor PROC NEAR ; _b$ = ecx ; _k$ = edx 00000 69 c9 00 00 00 90 imul ecx, 90000000H 00006 c1 f9 1f sar ecx, 31 00009 33 ca xor ecx, edx 0000b c1 fa 03 sar edx, 3 0000e 83 e1 07 and ecx, 7 00011 03 ca add ecx, edx 00013 8b d1 mov edx, ecx 00015 c1 fa 03 sar edx, 3 00018 8b c2 mov eax, edx 0001a 6b c0 0f imul eax, 15 0001d 33 c1 xor eax, ecx 0001f 2b c2 sub eax, edx 00021 c3 ret 0
See also
- Avoiding Branches
- Center Manhattan-Distance
- Color of a Square
- Huberman's program
- Manhattan-Distance
- Mop-up Evaluation
- Piece-Square Tables
Publications
- Jaap van den Herik (1983). Representation of Experts' Knowledge in a Subdomain of Chess Intelligence. IJCAI 1983
- Hans Zellner, Jaap van den Herik, Bob Herschberg (1987). Corrections and Substantiations to KBNK. ICCA Journal, Vol. 10, No. 3
- Matej Guid, Martin Možina, Aleksander Sadikov, Ivan Bratko (2010). Deriving Concepts and Strategies from Chess Tablebases. Advances in Computer Games 12, pdf
Forum Posts
1997 ...
- How to get chess program to solve KBN mate? by Paul Pedriana, rgcc, September 17, 1997
- Re: How to get chess program to solve KBN mate? by David John Blackman, rgcc, September 18, 1997 » KnightCap
2000 ...
- Caution K v KBN and lazy eval or futility by Brian Richardson, CCC, May 14, 2000 » Lazy Evaluation, Futility Pruning
- Symbolic: The KBNK recognizer by Steven Edwards, CCC, February 23, 2004 » Symbolic
- Symbolic: KBNK merit sample code by Steven Edwards, CCC, February 24, 2004
2010 ...
- Re: Search with bitbase by Joona Kiiski, CCC, September 05, 2012
- Re: Best was to Recognize Know Endgames? by Harm Geert Muller, CCC, August 03, 2013 » Interior Node Recognizer
- Scorpio & egbb issue (OSX) by Max May, CCC, February 01, 2014 » Scorpio Bitbases
- KBNK by Harm Geert Muller, CCC, October 11, 2014
- Improved corner painting by Harm Geert Muller, CCC, January 18, 2016 » Fairy-Max
- Simple method for simple mates for programs without TBs by J. Wesley Cleveland, CCC, November 25, 2016 » Center Manhattan-Distance, Mop-up Evaluation
2020 ...
- knbk DTM by Martin Sedlak, CCC, May 05, 2021 » DTM
- Re: knbk DTM by Harm Geert Muller, CCC, May 05, 2021 » Marcel van Kervinck's pretty fast kbnk generator
External links
- Longest mate in King, Bishop and Knight versus King endgame by Joe Leslie-Hurd, February 16, 2005
- Bishop and knight checkmate from Wikipedia
References
- ↑ Re: Search with bitbase by Joona Kiiski, CCC, September 05, 2012