KBNK Endgame

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 or the stalemate trap are left to the search routine.

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

Up one Level