Kurt
Kurt,
a Chess Engine Communication Protocol and UCI compliant open source chess engine under the GNU General Public License, written by Oliver Uwira in C. Able to play Chess960, Kurt participated at the 2nd Livingston Chess960 Computer World Championship 2006 in Mainz.
The last recent Kurt 0.9.2.2 beta is available from Jim Ablett's site.
Contents
Bitboards
Sliding Piece Attacks
Kurt 0.9.2.x beta is a none rotated bitboard engine [2], and uses a three-dimensional pre-initialized array of 128 KByte to lookup sliding piece attacks, indexed by square (0..63), line occupancy index (0..63, considering the outer squares) and finally the four line directions (0..3) for ranks, files, diagonals and anti-diagonals. The six-bit line occupancy index is calculated from the masked line of empty squares, multiplied by a 64-bit De Bruijn Sequence [3] for each square and direction, shifting the product right by 58 .
BitScan
Kurt 0.9.2.x beta uses Matt Taylor's folded BitScan. Returning a byte [4].
static const int LsbDeBruijnMap[64] =
{
63, 30, 3, 32, 59, 14, 11, 33,
60, 24, 50, 9, 55, 19, 21, 34,
61, 29, 2, 53, 51, 23, 41, 18,
56, 28, 1, 43, 46, 27, 0, 35,
62, 31, 58, 4, 5, 49, 54, 6,
15, 52, 12, 40, 7, 42, 45, 16,
25, 57, 48, 13, 10, 39, 8, 44,
20, 47, 38, 22, 17, 37, 36, 26
};
unsigned char LeastSignificantBit(bitboard b)
{
unsigned int fold;
b ^= (b - 1);
fold = ((int) b) ^ ((int)(b>>32));
return LsbDeBruijnMap[(fold * 0x78291acf) >> 26];
}
Collapsing Files and Ranks
Collapsed files and collapsed ranks, as posted by Urban Koistinen in 1997 [5], and Steffan Westcott in 2006 [6] are used in 0.9.2.x for initialization purposes:
/**
* CollapseFiles(bitboard) folds a bitboard vertically into an 8 bit word.
* By or-ing the files of a bitboard, a 8-bit folded bitboard is calculated.
* E.g. by folding a bitboard containing the position of all pawns open files
* can be determined:
*
* abcdefgh
*
* 8 00000000
* 7 10100110
* 6 00010001 abcdefgh
* 5 00000000 => CollapseFiles() => 11110111
* 4 00010000
* 3 00100000 Negating the result yields the open-property of
* 2 11000011 the 8 files => the e-file is open.
* 1 00000000
*
* Pawns
*/
unsigned char CollapseFiles(bitboard src)
{
src |= src >> 32;
src |= src >> 16;
src |= src >> 8;
return (unsigned char)(src & 0xff);
}
/**
* CollapseRanks() folds a bitboard horizontally into an 8 bit word.
* This is similar to CollapseFiles(bitboard).
*/
unsigned char CollapseRanks(bitboard src)
{
src |= src >> 4; // No masking needed
src |= src >> 2; // " "
src |= src >> 1; // " "
return (unsigned char)(((src & 0x0101010101010101) * 0x0102040810204080) >> 56);
}
Search
Kurt's search is PVS with null move pruning and killer heuristic with two slots for mate killers and other killer moves each, kept in its parent's node structure. Further, SEE is used in move ordering and quiescence search pruning.
Evaluation
The evaluation is speeded up by a hash table and considers material and various positional terms such as development, pawn structure, in particular backward pawns and passed pawns, and king safety.
Forum Posts
- One step forward again by Oliver Uwira, CCC, September 22, 2010
- New Version: Kurt 0.9.2 beta by Oliver Uwira, CCC, October 11, 2010
- New Version: Kurt 0.9.2 beta by Oliver Uwira, Winboard Forum, October 11, 2010
External Links
Chess Engine
- Index of /chess/engines/Jim Ablett/KURT compiled by Jim Ablett, hosted by Kirill Kryukov
Misc
- Kurt (disambiguation) from Wikipedia
- Kurt & Rolf Chess Homepage of Kurt Utzinger
- Kurt Richter from Wikipedia
- Kurt Tucholsky from Wikipedia
- Kurt Wallander from Wikipedia
- Kurt Weill from Wikipedia
- Louis Armstrong - Mack the Knife, Hollywood Palace, May 01, 1965, YouTube Video
- Miloš Kopecký - Mackie Messer, YouTube Video
References
- ↑ Original caption (German): Kurt Weill in Wien, Kurt Weill, der bekannte Komponist der "Drei-Groschen-Oper", ist zur Premiere seines neuen Stückes "Aufstieg und Fall der Stadt Mahagonny" nach Wien gekommen, German Federal Archives, Kurt Weill from Wikipedia
- ↑ rotated bitboards obsolete? by Gerd Isenberg, CCC, February 26, 2006
- ↑ De Bruijn sequence factors are not required and work more like random magic factors here. File pattern for a north-fill multiplication, or diagonal pattern for a flip-multiplication, as applied in kindergarten bitboards are more stringent to map the inner six squares of any line to an 6-bit index
- ↑ kurt_0_9_2_beta/src/bitboard.c, New Version: Kurt 0.9.2 beta by Oliver Uwira, Winboard Forum, October 11, 2010
- ↑ Re: Rotated bitboards by Urban Koistinen, rgcc, October 31, 1997
- ↑ Re: Some thoughts on Dann Corbit's rotated alternative by Steffan Westcott, CCC, March 03, 2006
