Kurt

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * Kurt

Kurt Weill [1]

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.

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

External Links

Chess Engine

Index of /chess/engines/Jim Ablett/+++ LINUX ENGINES ++/64 BIT/kurt

Misc

References

  1. 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
  2. rotated bitboards obsolete? by Gerd Isenberg, CCC, February 26, 2006
  3. 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
  4. kurt_0_9_2_beta/src/bitboard.c, New Version: Kurt 0.9.2 beta by Oliver Uwira, Winboard Forum, October 11, 2010
  5. Re: Rotated bitboards by Urban Koistinen, rgcc, October 31, 1997
  6. Re: Some thoughts on Dann Corbit's rotated alternative by Steffan Westcott, CCC, March 03, 2006

Up one Level