25,161
edits
Changes
Created page with "'''Home * Evaluation * Endgame * KBNK Endgame''' A checkmate with a bishop and a knight against a lone king..."
'''[[Main Page|Home]] * [[Evaluation]] * [[Endgame]] * KBNK Endgame'''
A [[Checkmate|checkmate]] with a [[Bishop|bishop]] and a [[Knight|knight]] against a lone [[King|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 Tables|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 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=45009&start=5 Re: Search with bitbase] by [[Joona Kiiski]], [[CCC]], September 05, 2012</ref> or the [[Stalemate|stalemate]] trap are left to the [[Search|search]] routine.
<span id="CornerDistance"></span>
=Corner-Distance=
Alternatively, following [[Bit-Twiddling|Bit-twiddling]] determines the [[Manhattan-Distance]] to the closest corner square of the bishop [[Color of a Square|square color]], which might be used as a bonus for the lonesome king. First, the [[Color of a Square|color of the bishop square]] is determined by a multiplication based on 9, to find whether its [[Files|file]] and [[Ranks|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 [[Flipping Mirroring and Rotating#MirrorHorizontally|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 [[Ranks|rank]] and [[Files|file]] indices, if it exceeds 7 the difference to 14 is taken to force the symmetry, mirrored along the [[Diagonals|diagonal]] or [[Anti-Diagonals|anti-diagonal]].
<pre>
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
</pre>
<pre>
/**
* 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;
}
</pre>
which results in following [[x86]] [[Assembly]]:
<pre>
?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
</pre>
=See also=
* [[Avoiding Branches]]
* [[Center Manhattan-Distance]]
* [[Color of a Square]]
* [[Huberman|Huberman's program]]
* [[Manhattan-Distance]]
* [[Mop-up Evaluation]]
* [[Piece-Square Tables]]
=Publications=
* [[Hans Zellner]], [[Jaap van den Herik]], [[Bob Herschberg]] ('''1987'''). ''Corrections and Substantiations to KBNK''. [[ICGA Journal#10_3|ICCA Journal, Vol. 10, No. 3]]
* [[Matej Guid]], [[Martin Možina]], [[Aleksander Sadikov]], [[Ivan Bratko]] ('''2010'''). ''[http://www.springerlink.com/content/um0l155681087p7h Deriving Concepts and Strategies from Chess Tablebases]''. [[Advances in Computer Games 12]], [http://www.ailab.si/matej/doc/Deriving_Concepts_and_Strategies_from_Chess_Tablebases.pdf pdf]
=Forum Posts=
* [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://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=351153 Symbolic: KBNK merit sample code] by [[Steven Edwards]], [[CCC]], February 24, 2004
* [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=51133 Scorpio & egbb issue (OSX)] by Max May, [[CCC]], February 01, 2014 » [[Scorpio Bitbases]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54023 KBNK] by [[Harm Geert Muller]], [[CCC]], October 11, 2014
* [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]]
=External links=
* [http://www.gilith.com/chess/endgames/kbn_k.html Longest mate in King, Bishop and Knight versus King endgame] by [[Joe Leslie-Hurd]], February 16, 2005
* [https://en.wikipedia.org/wiki/Bishop_and_knight_checkmate Bishop and knight checkmate from Wikipedia]
=References=
<references />
'''[[Endgame|Up one Level]]'''
A [[Checkmate|checkmate]] with a [[Bishop|bishop]] and a [[Knight|knight]] against a lone [[King|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 Tables|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 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=45009&start=5 Re: Search with bitbase] by [[Joona Kiiski]], [[CCC]], September 05, 2012</ref> or the [[Stalemate|stalemate]] trap are left to the [[Search|search]] routine.
<span id="CornerDistance"></span>
=Corner-Distance=
Alternatively, following [[Bit-Twiddling|Bit-twiddling]] determines the [[Manhattan-Distance]] to the closest corner square of the bishop [[Color of a Square|square color]], which might be used as a bonus for the lonesome king. First, the [[Color of a Square|color of the bishop square]] is determined by a multiplication based on 9, to find whether its [[Files|file]] and [[Ranks|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 [[Flipping Mirroring and Rotating#MirrorHorizontally|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 [[Ranks|rank]] and [[Files|file]] indices, if it exceeds 7 the difference to 14 is taken to force the symmetry, mirrored along the [[Diagonals|diagonal]] or [[Anti-Diagonals|anti-diagonal]].
<pre>
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
</pre>
<pre>
/**
* 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;
}
</pre>
which results in following [[x86]] [[Assembly]]:
<pre>
?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
</pre>
=See also=
* [[Avoiding Branches]]
* [[Center Manhattan-Distance]]
* [[Color of a Square]]
* [[Huberman|Huberman's program]]
* [[Manhattan-Distance]]
* [[Mop-up Evaluation]]
* [[Piece-Square Tables]]
=Publications=
* [[Hans Zellner]], [[Jaap van den Herik]], [[Bob Herschberg]] ('''1987'''). ''Corrections and Substantiations to KBNK''. [[ICGA Journal#10_3|ICCA Journal, Vol. 10, No. 3]]
* [[Matej Guid]], [[Martin Možina]], [[Aleksander Sadikov]], [[Ivan Bratko]] ('''2010'''). ''[http://www.springerlink.com/content/um0l155681087p7h Deriving Concepts and Strategies from Chess Tablebases]''. [[Advances in Computer Games 12]], [http://www.ailab.si/matej/doc/Deriving_Concepts_and_Strategies_from_Chess_Tablebases.pdf pdf]
=Forum Posts=
* [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://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=351153 Symbolic: KBNK merit sample code] by [[Steven Edwards]], [[CCC]], February 24, 2004
* [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=51133 Scorpio & egbb issue (OSX)] by Max May, [[CCC]], February 01, 2014 » [[Scorpio Bitbases]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54023 KBNK] by [[Harm Geert Muller]], [[CCC]], October 11, 2014
* [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]]
=External links=
* [http://www.gilith.com/chess/endgames/kbn_k.html Longest mate in King, Bishop and Knight versus King endgame] by [[Joe Leslie-Hurd]], February 16, 2005
* [https://en.wikipedia.org/wiki/Bishop_and_knight_checkmate Bishop and knight checkmate from Wikipedia]
=References=
<references />
'''[[Endgame|Up one Level]]'''
