Wikispaces : chessprogramming - items matching description

Ant

GerdIsenberg — Mon, 01 Jun 2015 22:07:20 GMT

Home * Engines * Ant

		Ant, a WinBoard compatible chess engine by Tom Vijlbrief, written in C++, at times supported by Hans Secelle ^[1] and Albrecht Heeffer. Ant regularly participates at Dutch Open Computer Chess Championships and International CSVN Tournaments and had its debut at the DOCCC 1995. It further played the Aegon 1996 and Aegon 1997 human machine tournaments, the IPCCC 1998, and the Livingston Chess960 Computer World Championships in 2005 and 2006.
M. C. Escher, Ant, 1943 ^[2]

Photos & Games

Ant beats Tiger

ICT 2002: round 2, Ant - Chess Tiger, Hans Secelle and Hans van der Zijden ^[3] ^[4]

[Event "ICT 2002"]
[Site "Leiden NED"]
[Date "2002.05.31"]
[Round "02"]
[White "Ant"]
[Black "Chess Tiger"]
[Result "1-0"]
 
1.e4 e5 2.Nf3 Nc6 3.c3 Nf6 4.d4 Nxe4 5.d5 Ne7 6.Nxe5 Ng6 7.Nxg6 hxg6
8.Qe2 Qe7 9.Bf4 d6 10.Na3 Bf5 11.f3 Nf6 12.Qxe7+ Bxe7 13.Bb5+ Nd7 14.g4 g5
15.Be3 Bg6 16.O-O a6 17.Bxd7+ Kxd7 18.Rf2 Bf6 19.Rd1 Rae8 20.Bc1 Rh3
21.Nc4 Reh8 22.Ne3 Be5 23.Nf1 f6 24.Be3 Re8 25.Kg2 Rh7 26.c4 b5 27.c5 dxc5
28.Bxc5 Reh8 29.Kg1 Bf7 30.b3 Rh3 31.Rd3 R8h4 32.Rd1 Bg8 33.Kh1 Rh6
34.Rd3 Bf7 35.a4 R6h4 36.axb5 axb5 37.Rg2 Bg6 38.Re3 Kc8 39.b4 Bf7
40.Rd3 c6 41.Ra2 Bxd5 42.Ra8+ Kd7 43.Ra7+ Ke8 44.Re7+ Kd8 45.Kg2 Bb2
46.Rxg7 Rh6 47.Re3 Rh8 48.Ree7 Bxf3+ 49.Kg1 Bxg4 50.Rb7 Be5 51.Ra7 Bd7
52.Raxd7+ Kc8 53.Ra7 Kb8 54.Rgb7+ Kc8 55.Rb6 R8h7 56.Rxc6+ Kb8
57.Ra5 Kb7 58.Rb6+ Kc8 59.Kg2 Kd7 60.Ra7+ Kc8 61.Rc6+ Kb8 62.Ra5 Rb3
63.Rxb5+ Rb7 64.Bd6+ Bxd6 65.Rxb7+ Kxb7 66.Rxd6 Rb2+ 67.Kf3 f5 68.Rd5 Rb3+
69.Ke2 Rb2+ 70.Nd2 Rxb4 71.Rxf5 g4 72.Ke3 Ra4 73.Ne4 Kb6 74.Rf6+ Kc7
75.Nf2 Kd7 76.Rg6 Ra3+ 77.Ke4 Ra4+ 78.Kf5 Ra5+ 79.Kxg4 Ra2 80.Kf3 Ra3+
81.Kf4 Ke7 82.h4 Ra5 83.Rg5 Ra4+ 84.Ne4 Ra2 85.h5 Rh2 86.Rg7+ Kf8
87.Rh7 Kg8 88.Ra7 Rh4+ 89.Kf5 Kf8 90.Kf6 Rf4+ 91.Kg6 Rxe4 92.Ra8+
1-0

Ant draws Shredder

ICT 2005, round 9, Ant - Shredder ^[5]

[Event "ICT 2005"]
[Site "Leiden NED"]
[Date "2005.06.05"]
[Round "9"]
[White "Ant"]
[Black "Shredder"]
[Result "1/2-1/2"]
 
1. d4 d5 2. c4 dxc4 3. e3 Nf6 4. Bxc4 e6 5. Nf3 a6 6. O-O c5 
7. Bd3 Nbd7 8. Re1 b6 9. e4 cxd4 10. e5 Nd5 11. Nxd4 Bb7 12. Nxe6 fxe6 
13. Qh5 Ke7 14. Bxh7 Qc7 15. Bg5 N5f6 16. exf6 gxf6 17. Bd2 Qc5 
18. Qxc5 Nxc5 19. Bc2 Rd8 20. Be3 Bh6 21. f4 Nd3 22. Bxd3 Rxd3 
23. g3 Bg7 24. Nc3 Bf3 25. h4 f5 26. Bxb6 Rb8 27. Bc5 Kf7 28. Rab1 Bxc3
29. bxc3 Rxb1 30. Rxb1 Bd5 31. Bf2 Rxc3 32. Ra1 Ra3 33. Kf1 Kg6 
34. Ke2 a5 35. Kd2 1/2-1/2

When Ants Play Chess

Alexis Drogoul (1993, 1995). When Ants Play Chess (Or Can Strategies Emerge From Tactical Behaviors?) MAAMAW ’93, CiteSeerX pdf

Forum Posts

Ant 4.13 (Dutch-ch 99 Leiden) ! by Frank Quisinsky, CCC, November, 08, 1999
Dutch Championship : Nimzo 8 - Ant by Johan Havegheer, CCC, October, 14, 2000
Trapper Ant by Ulrich Türke, CCC, May 18, 2003

External Links

Chess Engine

Misc

Ant's ICGA Tournaments, Connect6 program
Ant from Wikipedia
Ant (disambiguation) from Wikipedia
Netherlands Antilles from Wikipedia
Apache Ant from Wikipedia
Langton's ant from Wikipedia
Albert Mangelsdorff, Jaco Pastorius, Alphonse Mouzon - Ant Steps On An Elephant's Toe, Trilogue, Berlin Jazz Festival, November 06, 1976, Berliner Philharmonie, YouTube Video

References

^ Some news about H. Secelle (author of Bionic) by Johan Havegheer, Winboard Forum, September 08, 1999
^ Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website
^ A black day for France by Eric van Reem, ChessBase News, June 01, 2002
^ Ant vs Chess Tiger 14.0 48...Bxf3 by K. Burcham, CCC, June 01, 2002
^ Leiden(9) surprise: Ant-Shredder 1/2-1/2 by Theo van der Storm, CCC, June 05, 2005

What links here?

Page	Date Edited
Aegon 1996	Jan 22, 2017
Aegon 1997	Apr 7, 2017
Albrecht Heeffer	Sep 6, 2016
Ant	Jun 1, 2015
Bionic Impakt	Sep 6, 2014
Chess960CWC 2005	Jan 1, 2016
Chess960CWC 2006	Sep 25, 2014
De Bruijn sequence	Feb 20, 2018
DOCCC 1995	Jun 7, 2016
DOCCC 1996	Jun 7, 2016
DOCCC 1997	Aug 15, 2015
DOCCC 1998	Feb 25, 2018
DOCCC 1999	Aug 15, 2015
DOCCC 2000	Aug 15, 2015
DOCCC 2001	Aug 15, 2015
DOCCC 2002	Nov 24, 2017
DOCCC 2003	Aug 17, 2016
DOCCC 2004	Nov 19, 2016
DOCCC 2006	Aug 27, 2016
DOCCC 2007	Aug 15, 2015
Engines	Mar 10, 2018
Hans Secelle	Nov 2, 2012
ICT 2001	Oct 14, 2015
ICT 2002	Nov 19, 2016
ICT 2003	Aug 18, 2016
ICT 2004	Aug 17, 2016
ICT 2005	Oct 14, 2015
ICT 2006	Oct 14, 2015
IPCCC 1998	Feb 25, 2018
Jan Kozak	Mar 17, 2015
Johan Havegheer	Feb 2, 2013
Matant	Aug 14, 2013
Tom Vijlbrief	Mar 6, 2015
XiniX	Jan 7, 2016

Up one Level

Bitboard Serialization

GerdIsenberg — Wed, 24 Dec 2014 12:09:43 GMT

Home * Board Representation * Bitboards * Bitboard Serialization

		Bitboard Serialization refers to the transformation of a bitboard with up to 64 one-bits set into a list of up to 64 bit-indices aka square indices of a 8x8 board - for instance to process move-target sets for move generation. This is done in two phases, isolating none-empty subsets and then transforming those more versatile subsets into lists, either bit by bit, by applying a bisection scheme, where finally words or bytes may act as index of a pre-calculated database, or by perfect hashing of square lists by subsets with a limited maximum popularity, for instance move-target sets of a king or knight even with minimal perfect hashing.
M. C. Escher, Encounter, 1944 ^[1]

Isolating Subsets

Single Bits

Multiple Bits

Converting Sets to Lists

Square Index Serialization

Hashing Multiple Bits

Isolating Subsets

The process of isolating subsets is performed by intersection, for single populated subsets with the two's complement.

Single Bits

This obvious loop approach is similar to Brian Kernighan's way to count the number of one-bits by consecutively isolating and clearing the LS1B:

while ( x ) {
   U64 ls1b = x & -x; // isolate LS1B
   ...
   x &= x-1; // reset LS1B
}

or with likely the same generated assembly:

if ( x ) do {
   U64 ls1b = x & -x; // isolate LS1B
   ...
} while ( x &= x-1 );

Of course we may also reset the LS1B by

   x ^= ls1b; // reset LS1B

but todays processors like to gain more parallelism to calculate independent expressions.

Multiple Bits

Isolating none-empty subsets with possibly multiple one-bits can be applied by divide and conquer, that is to divide the bitboard or quad word recursively into smaller items, two double words, consisting of two words and those again of two bytes. Word and byte-wide isolated subsets may then act as an index of a pre-calculated lookup table to convert those subsets to adequate data-structures, most likely lists with up to sixteen or eight elements.

Converting Sets to Lists

Square Index Serialization

For most applications LS1B-isolation alone is not appropriate, but the conversion from the exponential bitboard centric world to the scalar square centric world, also called bit-scanning.

Scanning Forward

if ( x ) do {
   int idx = bitScanForward(x); // square index from 0..63
   *list++ = foo(idx, ...);
} while (x &= x-1); // reset LS1B

Per definition bitScanForward reveals the index of LS1B.

Scanning Reverse

If - for some reason - we like to traverse the sets in reverse or unknown order anyway, we can not (or don't want to) rely on the independent LS1B reset.

if ( x ) do {
   int idx = bitScanReverse(x); // square index from 0..63
   *list++ = foo(idx, ...);
} while (x ^= powOf2[idx]) ; // or 1ULL << idx -> reset found bit

Scanning with Reset

A win of abstraction is to use a combined bitscan with reset found bit routine. This is fine. But probably harder for compilers to generate optimal code in the if-do-while-sense, where reset last bit already sets the zero-flag. If you don't care on such micro-optimizations, this is the preferred control structure.

while ( x ) {
   int idx = bitScanAndReset(&x); // square index from 0..63
   *list++ = foo(idx, ...);
}

One may even don't care about the order.

Intrinsic Version

If bitscan is able to properly handle empty sets - leaving an value outside the 0..63 range (like leading or trailing zero count), we may think about to skip the leading while condition and to break on bitscan(x) > 63 for instance. That was not recommend - since the reset leaves the condition en-passant, and the computational cost of an additional bitscan or zero count was higher. If you like to play the optimization game, it might be fine for x86-64 Core 2 duo thought - using bitscan and bittestandreset intrinsics or wrappers - if kept all in registers of course.

while (_BitScanForward64(&idx, x)) { // or reverse
   *list++ = foo(idx, ...);
   _bittestandreset64(&x, idx);
}

The loop is intended to look like this in x86-64 assembly:

; input rdx - move target set
;       ecx - move from aspects
;       rdi - pointer to movelist
   std           ; set direction flag
   bsf  rax, rdx ; scan first to-bit
   jz   over     ; jump if no more moves
loop:
   btr  rdx, rax ; reset found bit
   or   eax, ecx ; combine to- with from-square
   stosw         ; store 16-bit move *rdi++ = move
   bsf  rax, rdx ; scan next to-bit
   jnz  loop     ; jump if more moves
over:

Black or White

With bitboard serialization one minor problem is the relative order in move generation considering side to move. Bsf scans the board in a1..h1, a2..h2, a8..h8 order, assuming little-endian rank-file mapping, which might be the desired order for an attacking black player. Traversing white pieces and target squares the same way may result in asymmetries and different search behavior of color flipped positions. Despite other features considered in move ordering, the initial order in generation has more or less influence. Therefore, it is desired to traverse the "white" bitboards with priority for the black back-rank as well ^[2] . This might be done by bitscan reverse, which covers the rank symmetry, but also mirrors the files. Another alternative is to traverse a vertically flipped "white" bitboard, which can be done outside the do-while loop by a "conditional" x86-64 byte swap, and requires one further register and xor per loop cycle, which might be combined with other stuff, f.i. the from square of a move:

if ( x ) {
   U64 m = (U64)color - 1; // e.g. -1 if white, 0 for black
   int o = (int)m & 56;
   x = x ^ ((x ^ flipVertical(x)) & m); // conditional flip
   do {
      int idx = bitScanForward(x) ^ o; // square index from 0..63
      *list++ = foo(idx , ...);
   } while (x &= x-1); // reset LS1B
}

STL Iterator

Rein Halbersma has written a prototype of a generic C++11 bitset template that can be used to traverse a set in STL iterator style, hiding bitscan and reset ^[3] ^[4] ...

typedef bit_set<int64_t, 1> bitset;
 
void testLoop(int* p, const bitset & x) {
  for (auto it = x.begin(); it != x.end(); ++it)
    *p++ = *it;
}
/* or std::copy */
void testCopy(int* p, const bitset & x) {
  std::copy(x.begin(), x.end(), p); 
}

... which yields in following X86-64 assembly, almost identical for the iterator loop and std::copy ^[5]:

; testLoop(int*, bit_set<long, 1ul>):
  test  rsi, rsi
  jne   .L13
.L7:
  ret
.L13:
  bsf   rax, rsi
  mov   DWORD PTR [rdi], eax
  lea   rax, [rsi-1]
  add   rdi, 4
  and   rsi, rax
  jne   .L13
  jmp   .L7

Hashing Multiple Bits

Similar to the idea to hash occupancies in kindergarten bitboards and magic bitboards, one may hash certain move-target subsets of one piece in one run, to lookup tables with pre-calculated moves-lists ^[6] . Sounds like doing up to eight bitscans in parallel. The idea is to muliply-shift-lookup a move-target bitboard, to do an almost branch-less move-generation with pre-calculated moves inside move-lists. For instance king- and knight-moves ^[7] as well as moves of sliding pieces per line:

moveTarget = KingAttacks[sq] & ~(ownPieces | attackedSquares);
idx = (moveTarget * kingMagic[sq]) >> kingShift[sq]);
movelists = kingMoveLists[sq];
movelist  = movelists[idx];
moveCpy(target, movelist, movelist->n);

A king in a corner may have up to three moves. Thus there are 2^3 == 8 possible move-lists.
For instance for a king on a1 (number of moves: vector of moves):

0:{empty}
1:{a1-b1}
1:{a1-a2}
1:{a1-b2}
2:{a1-b1,a1-a2}
2:{a1-b1,a1-b2}
2:{a1-a2,a1-b2}
3:{a1-b1,a1-a2,a1-b2}

Kings on edges have 5 potential target squares, thus there are 32 possible move-lists. All other kings have 8 all the 8 neighbors with up to 256 move-lists. Similar move-list enumeration is possible with knights and others. All possible move-target subsets of kings and knights for all 64 from-squares are perfectly minimal hashtable with a magic factor of four one-bits set. 10016 possible king-move-lists and 5520 knight-move-lists. To reduce memory one may offset the sets to a "normalized" source square per king, knight and sliding piece line, implying some vector arithmetic in the board centric world considering the offset.

The less populated move-target subsets are, the less efficient this hashing technique. This might become a problem since bitboard move-generation is essentially about subsets of moves with certain properties, like most importantly fast winning captures at Cut-nodes.

Forum Posts

Subject: sliding move generation idea with bitboards by Gerd Isenberg, CCC, February 19, 2006
Magic Knight- and King-Move Generation by Gerd Isenberg, Winboard Forum, Januar 11, 2007
Re: C vs ASM by Rein Halbersma, CCC, March 05, 2013
Symmetric move generation using bitboards by Lasse Hansen, CCC, December 20, 2014 » BitScan

External Links

Serialization from Wikipedia

References

^ Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website
^ Re: Alternatives to History Heuristics by Robert Hyatt, CCC, September 02, 2009
^ LiveWorkSpace(IDE online): C++-3.2 (clang++): 41EaZl
^ Re: C vs ASM by Rein Halbersma, CCC, March 05, 2013
^ GCC Explorer with g++ 4.7 compiler, options -std=c++11 -O3 -march=k8-sse3 -fverbose-asm
^ Subject: sliding move generation idea with bitboards by Gerd Isenberg, CCC, February 19, 2006
^ Magic Knight- and King-Move Generation by Gerd Isenberg, Winboard Forum, Januar 11, 2007

What links here?

Page	Date Edited
More Links
Backtracking	Dec 16, 2017
Bison	Sep 29, 2016
Bitboard Serialization	Dec 24, 2014
Bitboards	Nov 14, 2017
BitScan	Sep 10, 2017
Blockers and Beyond	Mar 21, 2014
Brainless	Jun 24, 2017
Checks and Pinned Pieces (Bitboards)	Aug 14, 2013
CHEOPS	Apr 18, 2015
Color Flipping	May 17, 2017
Crafty	Jan 28, 2018
Double and Triple (Bitboards)	May 12, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
General Setwise Operations	Feb 25, 2018
Gibbon	Dec 23, 2014
Gk	Oct 9, 2017
Hash Table	Jan 1, 2018
Iteration	May 5, 2017
Joker IT	Sep 16, 2017
Knight Pattern	Feb 23, 2015
Lasse Hansen	Sep 1, 2015
Linked List	Oct 11, 2016
Move Generation	Jan 29, 2018
NoraGrace	Nov 23, 2014
Open Pawns (Bitboards)	Aug 24, 2017
Passed Pawns (Bitboards)	Aug 23, 2010
Pawn Pushes (Bitboards)	Apr 5, 2013
Piece-Sets	Jun 9, 2017
Pieces versus Directions	Oct 6, 2016
Population Count	Sep 3, 2017
Praetorian	Feb 21, 2015
Rein Halbersma	Dec 22, 2015
Reverse Bitboards	Aug 29, 2015
Ryan Mack	Jan 18, 2011
Rybka	Mar 27, 2017
Sliding Piece Attacks	May 27, 2016
Sliding Pieces	Aug 3, 2017
Spector	Nov 11, 2016
Tinker	Aug 29, 2015
Traversing Subsets of a Set	Oct 14, 2016

Up one Level

BitScan

GerdIsenberg — Sun, 10 Sep 2017 15:44:37 GMT

Home * Board Representation * Bitboards * BitScan

		BitScan, a function that determines the bit-index of the least significant 1 bit (LS1B) or the most significant 1 bit (MS1B) in an integer such as bitboards. If exactly one bit is set in an unsigned integer, representing a numerical value of a power of two, this is equivalent to a base-2 logarithm. Many implementations have been devised since the advent of bitboards, as described on this page, and some implementation samples of concrete open source engines listed for didactic purpose.
M. C. Escher, Eye, 1946 ^[1]

Hardware vs. Software

For recent x86-64 architectures like Core 2 duo and K10, one should use the Processor Instructions for Bitscans via intrinsics or inline assembly, see x86-64 timing. P4 and K8 have rather slow bitscan-instructions. K8 uses so called vector path instructions ^[2] with 9 or 11 cycles latency, even blocking other processor resources. For these processors, specially K8 with already fast multiplication, the De Bruijn Multiplication (64-bit mode) or Matt Taylor's Folded 32-bit Multiplication (32-bit mode) might be the right choice. Other routines mentioned might be advantageous on certain architectures, specially with slow integer multiplications.

Non Empty Sets

Bitscan is most often used in serializing bitboards, and is therefor - due to a leading while-condition - not called with empty sets. Until stated otherwise, most mentioned bitscan-routines in C/C++ have the same prototype and assume none empty sets as actual parameter.

Bitscan forward

A bitscan forward is used to find the index of the least significant 1 bit (LS1B).

Trailing Zero Count

Bitscan forward is identical with a Trailing Zero Count for none empty sets, possibly available as machine instruction on some architectures, for instance the x86-64 bit-manipulation expansion set BMI1.

De Bruijn Multiplication

The De Bruijn bitscan was devised in 1997, according to Donald Knuth ^[3] by Martin Läuter, and independently by Charles Leiserson, Harald Prokop and Keith H. Randall a few month later ^[4] ^[5] , to determine the LS1B index by minimal perfect hashing. De Bruijn sequences were named after the Dutch mathematician Nicolaas de Bruijn. Interestingly sequences with the binary alphabet were already investigated by the French mathematician Camille Flye Sainte-Marie in 1894, but later "forgotten" and re-investigated and generalized by De Bruijn and Tanja van Ardenne-Ehrenfest half a century later ^[6] .

A 64-bit De Bruijn sequence contains 64-overlapped unique 6-bit sequences, thus a circle of 64 bits, where five leading zeros overlap five hidden "trailing" zeros. There are 226 = 67108864 odd sequences with 6 leading binary zeros and 226 even sequences with 5 leading binary zeros, which may be calculated from the odd ones by shifting left one.

With isolated LS1B

A multiplication with a power of two value (the isolated LS1B) acts like a left shift by it's exponent. Thus, if we multiply a 64-bit De Bruijn sequence with the isolated LS1B, we get a unique six bit subsequence inside the most significant bits. To obtain the bit-index we need to extract these upper six bits by shifting right the product, to lookup an array.

const int index64[64] = {
    0,  1, 48,  2, 57, 49, 28,  3,
   61, 58, 50, 42, 38, 29, 17,  4,
   62, 55, 59, 36, 53, 51, 43, 22,
   45, 39, 33, 30, 24, 18, 12,  5,
   63, 47, 56, 27, 60, 41, 37, 16,
   54, 35, 52, 21, 44, 32, 23, 11,
   46, 26, 40, 15, 34, 20, 31, 10,
   25, 14, 19,  9, 13,  8,  7,  6
};
 
/**
 * bitScanForward
 * @author Martin Läuter (1997)
 *         Charles E. Leiserson
 *         Harald Prokop
 *         Keith H. Randall
 * "Using de Bruijn Sequences to Index a 1 in a Computer Word"
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb) {
   const U64 debruijn64 = C64(0x03f79d71b4cb0a89);
   assert (bb != 0);
   return index64[((bb & -bb) * debruijn64) >> 58];
}

See also how to Generate your "private" De Bruijn Bitscan Routine.

With separated LS1B

Instead of the classical LS1B isolation, Kim Walisch proposed the faster xor with the ones' decrement. The separation bb ^ (bb-1) contains all bits set including and below the LS1B. The 222 (4,194,304) upper De Bruijn sequences of the 226 available leave unique 6-bit indices. Using LS1B separation takes advantage of the x86 lea instruction, which saves the move instruction and unlike negate, has no data dependency on the flag register. Kim reported a 10 to 15 percent faster execution (compilers: g++-4.7 -O2, clang++-3.1 -O2, x86_64) than the traditional 64-bit De Bruijn bitscan on Intel Nehalem and Sandy Bridge CPUs.

const int index64[64] = {
    0, 47,  1, 56, 48, 27,  2, 60,
   57, 49, 41, 37, 28, 16,  3, 61,
   54, 58, 35, 52, 50, 42, 21, 44,
   38, 32, 29, 23, 17, 11,  4, 62,
   46, 55, 26, 59, 40, 36, 15, 53,
   34, 51, 20, 43, 31, 22, 10, 45,
   25, 39, 14, 33, 19, 30,  9, 24,
   13, 18,  8, 12,  7,  6,  5, 63
};
 
/**
 * bitScanForward
 * @author Kim Walisch (2012)
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb) {
   const U64 debruijn64 = C64(0x03f79d71b4cb0a89);
   assert (bb != 0);
   return index64[((bb ^ (bb-1)) * debruijn64) >> 58];
}

Matt Taylor's Folding trick

A 32-bit friendly implementation to find the the bit-index of LS1B by Matt Taylor ^[7]. The xor with the ones' decrement, bb ^ (bb-1) contains all bits set including and below the LS1B. The 32-bit xor-difference of both halves yields either the complement of the upper half, or the lower half otherwise. Some samples:

ls1b	bb ^ (bb-1)	folded
63	`0xffffffffffffffff`	`0x00000000`
62	`0x7fffffffffffffff`	`0x80000000`
59	`0x0fffffffffffffff`	`0xf0000000`
32	`0x00000001ffffffff`	`0xfffffffe`
31	`0x00000000ffffffff`	`0xffffffff`
30	`0x000000007fffffff`	`0x7fffffff`
0	`0x0000000000000001`	`0x00000001`

Even if this folded "LS1B" contains multiple consecutive one-bits, the multiplication is De Bruijn like. There are only two magic 32-bit constants with the combined property of 32- and 64-bit De Bruijn sequences to apply this minimal perfect hashing:

const int lsb_64_table[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
};
 
/**
 * bitScanForward
 * @author Matt Taylor (2003)
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb) {
   unsigned int folded;
   assert (bb != 0);
   bb ^= bb - 1;
   folded = (int) bb ^ (bb >> 32);
   return lsb_64_table[folded * 0x78291ACF >> 26];
}

A slightly modified version may take one x86-register less in 32-bit mode, but calculates bb-1 twice:

int bitScanForwardM(BitBoard bb) {
   unsigned int folded;
   assert (bb != 0);
   folded  = (int)((bb ^ (bb-1)) >> 32);
   folded ^= (int)( bb ^ (bb-1)); // lea
   return lsb_64_table[folded * 0x78291ACF >> 26];
}

with this VC6 generated x86 assembly to compare:

bitScanForward PROC NEAR                   bitScanForwardM PROC NEAR
   mov  ecx, DWORD PTR _bb$[esp-4]            mov  eax, DWORD PTR _bb$[esp-4]
   mov  eax, DWORD PTR _bb$[esp]              mov  ecx, eax
   mov  edx, ecx                              add  ecx, -1
   push esi                                   mov  ecx, DWORD PTR _bb$[esp]
   add  edx, -1                               mov  edx, ecx
   mov  esi, eax                              adc  edx, -1
   adc  esi, -1                               xor  edx, ecx
   xor  ecx, edx                              lea  ecx, DWORD PTR [eax-1]
   xor  eax, esi                              xor  edx, ecx
   pop  esi
   xor  eax, ecx                              xor  edx, eax
   imul eax, 78291acfH                        imul edx, 78291acfH
   shr  eax, 26                               shr  edx, 26
   mov  eax, DWORD PTR _lsb_64_table[eax*4]   mov  eax, DWORD PTR _lsb_64_table[edx*4]
   ret  0                                     ret  0
bitScanForward ENDP                        bitScanForward ENDP

Walter Faxon's magic Bitscan

Walter Faxon's 32-bit friendly magic bitscan ^[8] uses a fast none minimal perfect hashing function:

const char LSB_64_table[154] =
{
#define __ 0
   22,__,__,__,30,__,__,38,18,__, 16,15,17,__,46, 9,19, 8, 7,10,
   0, 63, 1,56,55,57, 2,11,__,58, __,__,20,__, 3,__,__,59,__,__,
   __,__,__,12,__,__,__,__,__,__, 4,__,__,60,__,__,__,__,__,__,
   __,__,__,__,21,__,__,__,29,__, __,37,__,__,__,13,__,__,45,__,
   __,__, 5,__,__,61,__,__,__,53, __,__,__,__,__,__,__,__,__,__,
   28,__,__,36,__,__,__,__,__,__, 44,__,__,__,__,__,27,__,__,35,
   __,52,__,__,26,__,43,34,25,23, 24,33,31,32,42,39,40,51,41,14,
   __,49,47,48,__,50, 6,__,__,62, __,__,__,54
#undef __
};
 
/**
 * bitScanForward
 * @author Walter Faxon, slightly modified
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb)
{
   unsigned int t32;
   assert(bb);
   bb  ^= bb - 1;
   t32  = (int)bb ^ (int)(bb >> 32);
   t32 ^= 0x01C5FC81;
   t32 +=  t32 >> 16;
   t32 -= (t32 >> 8) + 51;
   return LSB_64_table [t32 & 255]; // 0..63
}

A slightly modified version may take one x86-register less in 32-bit mode, but calculates bb-1 twice:

int bitScanForward(U64 bb)
{
   int t32 = 0x01C5FC81;
   assert(bb);
   t32 ^= (int)((bb ^ (bb-1)) >> 32);
   t32 ^= (int)( bb ^ (bb-1)); // lea
   t32 += t32 >> 16;
   t32 -=(t32 >>  8) + 51;
   return LSB_64_table [t32 & 255];
}

The initial LS1B separation by bb ^ (bb-1) and folding is equivalent to Matt's,

ls1b	bb ^ (bb-1)	folded
63	`0xffffffffffffffff`	`0x00000000`
62	`0x7fffffffffffffff`	`0x80000000`
59	`0x0fffffffffffffff`	`0xf0000000`
32	`0x00000001ffffffff`	`0xfffffffe`
31	`0x00000000ffffffff`	`0xffffffff`
30	`0x000000007fffffff`	`0x7fffffff`
0	`0x0000000000000001`	`0x00000001`

while Walter originally resets the LS1B, yielding in a cyclic index wrap:

LS1B	(bb & (bb-1)) ^ (bb-1)	folded
0	`0x0000000000000000`	`0x00000000`
63	`0x7fffffffffffffff`	`0x80000000`
60	`0x0fffffffffffffff`	`0xf0000000`
33	`0x00000001ffffffff`	`0xfffffffe`
32	`0x00000000ffffffff`	`0xffffffff`
31	`0x000000007fffffff`	`0x7fffffff`
1	`0x0000000000000001`	`0x00000001`

Bitscan by Modulo

Another idea is to apply a modulo (remainder of a division) operation of the isolated LS1B by the prime number 67 ^[9] ^[10] . The remainder 0..66 can be used to perfectly hash the bit-index table. Three gaps are 0, 17, and 34, so the mod 67 can make a branchless trailing zero count:

Bit-Index	Bitboard	mod 67
-	0x0000000000000000	0
0	0x0000000000000001	1
1	0x0000000000000002	2
2	0x0000000000000004	4
3	0x0000000000000008	8
4	0x0000000000000010	16
5	0x0000000000000020	32
6	0x0000000000000040	64
7	0x0000000000000080	61
8	0x0000000000000100	55
9	0x0000000000000200	43
10	0x0000000000000400	19
11	0x0000000000000800	38
12	0x0000000000001000	9
13	0x0000000000002000	18
14	0x0000000000004000	36
15	0x0000000000008000	5
16	0x0000000000010000	10
17	0x0000000000020000	20
18	0x0000000000040000	40
19	0x0000000000080000	13
20	0x0000000000100000	26
21	0x0000000000200000	52
22	0x0000000000400000	37
23	0x0000000000800000	7
24	0x0000000001000000	14
25	0x0000000002000000	28
26	0x0000000004000000	56
27	0x0000000008000000	45
28	0x0000000010000000	23
29	0x0000000020000000	46
30	0x0000000040000000	25
31	0x0000000080000000	50
32	0x0000000100000000	33
33	0x0000000200000000	66
34	0x0000000400000000	65
35	0x0000000800000000	63
36	0x0000001000000000	59
37	0x0000002000000000	51
38	0x0000004000000000	35
39	0x0000008000000000	3
40	0x0000010000000000	6
41	0x0000020000000000	12
42	0x0000040000000000	24
43	0x0000080000000000	48
44	0x0000100000000000	29
45	0x0000200000000000	58
46	0x0000400000000000	49
47	0x0000800000000000	31
48	0x0001000000000000	62
49	0x0002000000000000	57
50	0x0004000000000000	47
51	0x0008000000000000	27
52	0x0010000000000000	54
53	0x0020000000000000	41
54	0x0040000000000000	15
55	0x0080000000000000	30
56	0x0100000000000000	60
57	0x0200000000000000	53
58	0x0400000000000000	39
59	0x0800000000000000	11
60	0x1000000000000000	22
61	0x2000000000000000	44
62	0x4000000000000000	21
63	0x8000000000000000	42

/**
 * trailingZeroCount
 * @param bb bitboard to scan
 * @return index (0..63) of least significant one bit, 64 if bb is zero
 */
int trailingZeroCount(U64 bb) {
   static const int lookup67[67+1] = {
      64,  0,  1, 39,  2, 15, 40, 23,
       3, 12, 16, 59, 41, 19, 24, 54,
       4, -1, 13, 10, 17, 62, 60, 28,
      42, 30, 20, 51, 25, 44, 55, 47,
       5, 32, -1, 38, 14, 22, 11, 58,
      18, 53, 63,  9, 61, 27, 29, 50,
      43, 46, 31, 37, 21, 57, 52,  8,
      26, 49, 45, 36, 56,  7, 48, 35,
       6, 34, 33, -1 };
   return lookup67[(bb & -bb) % 67];
}

Since div/mod is an expensive instruction, a modulo by a constant is likely replaced by reciprocal fixed point multiplication to get the quotient and a second multiplication and difference to get the remainder. Compared with De Bruijn multiplication it is still too slow.

Divide and Conquer

This is a broad group of bitscans that test in succession, like the trailing zero count based on Reinhard Scharnagl's proposal ^[11] :

/**
 * trailingZeroCount
 *  like bitScanForward for none empty sets
 * @author Reinhard Scharnagl
 * @param bb bitboard to scan
 * @return index (0..64)
 */
unsigned char lsbRS[256] = {
    8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};
 
int trailingZeroCount(U64 b) {
  unsigned buf;
  int acc = 0;
 
  if ((buf = (unsigned)b) == 0) {
    buf = (unsigned)(b >> 32);
    acc = 32;
  }
  if ((unsigned short)buf == 0) {
    buf >>= 16;
    acc += 16;
  }
  if ((unsigned char)buf == 0) {
    buf >>= 8;
    acc += 8;
  }
  return acc + lsbRS[buf & 0xff];
}

What about direct calculation? On x86 this is a chain of test, set and lea instructions:

/**
 * bitScanForward
 * @author Gerd Isenberg
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb) {
   unsigned int lsb;
   assert (bb != 0);
   bb &= -bb; // LS1B-Isolation
   lsb = (unsigned)bb
       | (unsigned)(bb>>32);
   return (((((((((((unsigned)(bb>>32) !=0)  * 2)
                 + ((lsb & 0xffff0000) !=0)) * 2)
                 + ((lsb & 0xff00ff00) !=0)) * 2)
                 + ((lsb & 0xf0f0f0f0) !=0)) * 2)
                 + ((lsb & 0xcccccccc) !=0)) * 2)
                 + ((lsb & 0xaaaaaaaa) !=0);
}

Double conversion of LS1B

Assuming 64-bit doubles and little-endian structure (not portable). We convert the isolated LS1B to a double and interprete the exponent:

/**
 * bitScanForward
 * @author Gerd Isenberg
 * @param bb bitboard to scan
 * @return index (0..63) of least significant one bit
 *         -1023 if passing zero
 */
int bitScanForward(U64 bb)
{
   union {
      double d;
      struct {
         unsigned int mantissal : 32;
         unsigned int mantissah : 20;
         unsigned int exponent : 11;
         unsigned int sign : 1;
      };
   } ud;
   ud.d = (double)(bb & -bb); // isolated LS1B to double
   return ud.exponent - 1023;
}

Index of LS1B by Popcount

If we have a fast population-count instruction, we can count the trailing zeros of LS1B after subtracting one:

// precondition bb != 0
int bitScanForward(U64 bb) {
   assert (bb != 0);
   return popCount( (bb & -bb) - 1 );
}

Bitscan reverse

A bitscan reverse is used to find the index of the most significant 1 bit (MS1B). For non empty sets it is equivalent to floor of the base-2 logarithm. MS1B isolalation or separation is more expensive than LS1B isolalation or separation, due to the LS1B related Two's complement tricks are not applicable. However, beside Divide and Conquer and Double conversion, Bitscan reverse with MS1B separation is mentioned.

Divide and Conquer

As introduced by Eugene Nalimov in 2000, for an IA-64 version of Crafty ^[12] ^[13]

/**
 * bitScanReverse
 * @author Eugene Nalimov
 * @param bb bitboard to scan
 * @return index (0..63) of most significant one bit
 */
int bitScanReverse(U64 bb)
{
   int result = 0;
   if (bb > 0xFFFFFFFF) {
      bb >>= 32;
      result = 32;
   }
   if (bb > 0xFFFF) {
      bb >>= 16;
      result += 16;
   }
   if (bb > 0xFF) {
      bb >>= 8;
      result += 8;
   }
   return result + ms1bTable[bb];
}

Tribute to Frank Zappa

A branchless and little bit obfuscated version of the devide and conquer bitScanReverse with in-register-lookup ^[14] - as tribute to Frank Zappa with identifiers from Freak Out! (1966), Hot Rats (1969), Waka/Jawaka (1972), Sofa (1975), One Size Fits All (1975), Sheik Yerbouti (1979), and Jazz from Hell (1986):

typedef unsigned __int64 OneSizeFits;
typedef unsigned int HotRats;
const HotRats s      =   0;
const HotRats heik   = 457;
const HotRats y      =   1;
const HotRats e      =   2;
const HotRats r      =   3;
const HotRats b      =   4;
const HotRats o      =   5;
const HotRats u      =   8;
const HotRats t      =  16;
const HotRats i      =  32;
const HotRats     ka = (1<< 4)-1;
const HotRats   waka = (1<< 8)-1;
const HotRats jawaka = (1<<16)-1;
const HotRats jazzFromHell = 0-(16*3*heik);
 
HotRats freakOut(OneSizeFits all) {
   HotRats so,fa;
   fa   = (HotRats)(all >> i);
   so   = (fa!=s)       << o;
   fa  ^= (HotRats) all & (fa!=s)-y;
   so  ^= (jawaka < fa) << b;
   fa >>= (jawaka < fa) << b;
   so  ^= (  waka - fa) >> t    & u;
   fa >>= (  waka - fa) >> t    & u;
   so  ^= (    ka - fa) >> u    & b;
   fa >>= (    ka - fa) >> u    & b;
   so  ^=  jazzFromHell >> e*fa & r;
   return so;
}

De Bruijn Multiplication

While the tribute to Frank Zappa is quite 32-bit friendly ^[15], Kim Walisch suggested to use the parallel prefix fill for a MS1B separation with the same De Bruijn multiplication and lookup as in his bitScanForward routine with separated LS1B, with less instructions in 64-bit mode. A log base 2 method was already devised by Eric Cole on January 8, 2006, and shaved off rounded up to one less than the next power of 2 by Mark Dickinson ^[16] on December 10, 2009, as published in Sean Eron Anderson's Bit Twiddling Hacks for 32-bit integers ^[17].

const int index64[64] = {
    0, 47,  1, 56, 48, 27,  2, 60,
   57, 49, 41, 37, 28, 16,  3, 61,
   54, 58, 35, 52, 50, 42, 21, 44,
   38, 32, 29, 23, 17, 11,  4, 62,
   46, 55, 26, 59, 40, 36, 15, 53,
   34, 51, 20, 43, 31, 22, 10, 45,
   25, 39, 14, 33, 19, 30,  9, 24,
   13, 18,  8, 12,  7,  6,  5, 63
};
 
/**
 * bitScanReverse
 * @authors Kim Walisch, Mark Dickinson
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of most significant one bit
 */
int bitScanReverse(U64 bb) {
   const U64 debruijn64 = C64(0x03f79d71b4cb0a89);
   assert (bb != 0);
   bb |= bb >> 1; 
   bb |= bb >> 2;
   bb |= bb >> 4;
   bb |= bb >> 8;
   bb |= bb >> 16;
   bb |= bb >> 32;
   return index64[(bb * debruijn64) >> 58];
}

Double conversion

Assuming 64-bit doubles and little-endian structure (not portable!). Conversion to a double, interpreting the exponent. To avoid possible rounding errors, some lower bits may be cleared.

/**
 * bitScanReverse
 * @author Gerd Isenberg
 * @param bb bitboard to scan
 * @return index (0..63) of most significant one bit
 *         -1023 if passing zero
 */
int bitScanReverse(U64 bb)
{
   union {
      double d;
      struct {
         unsigned int mantissal : 32;
         unsigned int mantissah : 20;
         unsigned int exponent : 11;
         unsigned int sign : 1;
      };
   } ud;
   ud.d = (double)(bb & ~(bb >> 32));  // avoid rounding error
   return ud.exponent - 1023;
}

Leading Zero Count

Some processors have a fast leading zero count instruction. The Motorola 68020 has a bit field find first one instruction (BFFFO), which actually performs an up to 32-bit Leading Zero Count ^[18] . x86-64 AMD K10 has lzcnt as part of the SSE4a extension ^[19] ^[20] , BMI1 has lzcnt as well, while AVX-512CD even features leading zero count on vectors of eight bitbaords.

One can replace bitScanReverse of non empty sets by leadingZeroCount xor 63. Like trailing zero count, it returns 64 for empty sets, and might therefor save the leading condition in some applications.

Bitscan versus Zero Count

While the presented bitscan routines are suited to work only on none empty sets and return a value-range from 0 to 63 as bit-index, leading or trailing zero-count instructions or routines leave 64 for empty sets. Zero-counting has a immanent property of dealing correctly with empty sets - while it likely takes a conditional branch to implement this semantic in bit-scanning.

int trailingZeroCount(U64 bb) {
    if ( bb )
       return bitScanForward(bb);
    return 64;
}
 
int leadingZeroCount(U64 bb) {
    if ( bb )
       return bitScanReverse(bb) ^ 63;
    return 64;
}

Bitscan with Reset

While traversing sets, one may combine bitscanning with reset found bit. That implies passing the bitboard per reference or pointer, and tends to confuse compilers to keep all inside registers inside a typical serialization loop ^[21] .

int bitScanForwardWithReset(U64 &bb) { // also called dropForward
    int idx = bitScanForward(bb);
    bb &= bb - 1; // reset bit outside
    return idx;
}

Generalized Bitscan

This generalized bitscan uses a boolean parameter to scan reverse or forward. It relies on bitScanReverse, but conditionally masks the LS1B in case of scanning forward. It might be used in the classical approach to get positive or negative ray directions with one generalized routine.

 /**
 * generalized bitScan
 * @author Gerd Isenberg
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @param reverse, true bitScanReverse, false bitScanForward
 * @return index (0..63) of least/most significant one bit
 */
 int bitScan(U64 bb, bool reverse) {
    U64 rMask;
    assert (bb != 0);
    rMask = -(U64)reverse;
    bb &= -bb | rMask;
    return bitScanReverse(bb);
 }

Processor Instructions for Bitscans

x86

x86-64 processors have bitscan instructions and can be accessed with compilers today through either inline assembly or compiler intrinsics. For the Microsoft/Intel C compiler, the intrinsics can be accessed by including and using the instructions _BitScanForward64 ^[22] , _BitScanReverse64 ^[23] or _lzcnt64 ^[24] .

unsigned char_BitScanForward64(unsigned long * Index,  unsigned __int64 Mask);
unsigned char _BitScanReverse64(unsigned long * Index,  unsigned __int64 Mask);
unsigned __int64 __lzcnt64(unsigned __int64 value); // AMD K10 only see CPUID

Linux provides library functions ^[25] , find first bit set (ffsll) in a word leaves an index of 1..64, and zero of no bit is set ^[26] . GCC 4.4.5 further has the Built-in Function _builtin_ffsll for finding the least significant one bit, _builtin_ctzll for trailing, and _builtin_clzll for leading zero count ^[27] :

/* Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero */
int __builtin_ffsll (unsigned long long);
 
/* Returns the number of trailing 0-bits in x, starting at the least significant bit position.
   If x is 0, the result is undefined */
int __builtin_ctzll (unsigned long long);
 
/* Returns the number of leading 0-bits in x, starting at the most significant bit position.
   If x is 0, the result is undefined */
int __builtin_clzll (unsigned long long);

Emulating Intrinsics

For the GNU C compiler, the intrinsics can be emulated with inline assembly ^[28] .

//These processor instructions work only for 64-bit processors
#ifdef _MSC_VER
    #include <intrin.h>
    #ifdef _WIN64
        #pragma intrinsic(_BitScanForward64)
        #pragma intrinsic(_BitScanReverse64)
        #define USING_INTRINSICS
    #endif
#elif defined(__GNUC__) && defined(__LP64__)
    static INLINE unsigned char _BitScanForward64(unsigned long* Index, U64 Mask)
    {
        U64 Ret;
        __asm__
        (
            "bsfq %[Mask], %[Ret]"
            :[Ret] "=r" (Ret)
            :[Mask] "mr" (Mask)
        );
        *Index = (unsigned long)Ret;
        return Mask?1:0;
    }
    static INLINE unsigned char _BitScanReverse64(unsigned long* Index, U64 Mask)
    {
        U64 Ret;
        __asm__
        (
            "bsrq %[Mask], %[Ret]"
            :[Ret] "=r" (Ret)
            :[Mask] "mr" (Mask)
        );
        *Index = (unsigned long)Ret;
        return Mask?1:0;
    }
    #define USING_INTRINSICS
#endif

Intrinsics versus asm

Alternatively, rather than to emulate the intrinsics one might use the standard prototype, by using intrinsics or inline assembly for GCC ^[29] :

#ifdef USE_X86INTRINSICS
#include <intrin.h>
#pragma intrinsic(_BitScanForward64)
#pragma intrinsic(_BitScanReverse64)
 
/**
 * bitScanForward
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 x) {
   unsigned long index;
   assert (x != 0);
   _BitScanForward64(&index, x);
   return (int) index;
}
 
/**
 * bitScanReverse
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of most significant one bit
 */
int bitScanReverse(U64 x) {
   unsigned long index;
   assert (x != 0);
   _BitScanReverse64(&index, x);
   return (int) index;
}
#else
 
/**
 * bitScanForward
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 x) {
   assert (x != 0);
   asm ("bsfq %0, %0" : "=r" (x) : "0" (x));
   return (int) x;
}
 
/**
 * bitScanReverse
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of most significant one bit
 */
int bitScanReverse(U64 x) {
   assert (x != 0);
   asm ("bsrl %0, %0" : "=r" (x) : "0" (x));
   return (int) x;
}
#endif

Bsf/Bsr x86-64 Timings

The instruction latency and reciprocal throughput ^[30] heavily differs between various x86-64 architectures:

Architecture Stepping	Instruction(s)	Latency / Cycles	Reciprocal Throughput
AMD
K8 ^[31]	BSF reg16/32/64, mreg16/32/64	Vector Path 8/8/9	8/8/9
K8 ^[31]	BSR reg16/32/64, mreg16/32/64	Vector Path 11	11
K10 ^[32]	BSF reg, reg	Vector Path 4	4
	BSR reg, reg	Vector Path 4	4
	LZCNT reg, reg	Direct Path single 2	1
Intel ^[33]
ATOM	BSF/BSR	16	15
NetBurst 0F_3H	BSF/BSR	16	4
NetBurst 0F_2H	BSF/BSR	8	2
Core 06_0EH	BSF/BSR	2	1
65 nm Intel Core 06_0FH	BSF/BSR	2	1
Enhanced Intel Core 06_17H	BSF/BSR	1	1
Enhanced Intel Core 06_1DH	BSF/BSR	1	1
Nehalem 06_1AH	BSF/BSR	3	1
Sandy Bridge Ivy Bridge Haswell ^[34]	BSF/BSR	3	1
	LZCNT	3	1
	TZCNT	3	1

Bsf/Bsr behavior with zero source

Intel and AMD specify different behavior. In praxis there seems no difference so far. However, as long as Intel docs explicitly state content undefined, it is recommend to don't rely on a pre-initialized content of that target register, if the source is zero.

Intel : If the content of the source operand is 0, the content of the destination operand is undefined. ^[35]
AMD: If the second operand contains 0, the instruction sets ZF to 1 and does not change the contents of the destination register. ^[36]

ARM

ARM has CLZ (Count Leading Zeros) instruction for 32-bit integers. ARM instruction is available in ARMv5 and above, 32-bit Thumb instruction is available in ARMv6T2 and ARMv7 ^[37] , the C-intrinsic is called _builtin_clz ^[38] ^[39] ^[40] .

Engine Samples

Publications

Alan Turing (1949). Alan Turing's Manual for the Ferranti Mk. I. transcribed in 2000 by Robert Thau, pdf from The Computer History Museum, 9.4 The position of the most significant digit » Ferranti Mark 1
Charles E. Leiserson, Harald Prokop and Keith H. Randall (1998). Using de Bruijn Sequences to Index a 1 in a Computer Word, pdf
Pablo San Segundo, Ramón Galán (2005). Bitboards: A New Approach. AIA 2005
Donald Knuth (2009). The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise tricks & techniques, as Pre-Fascicle 1a postscript, p. 10
Andreas Stiller (2013). Spezialkommando - Bits setzen, abfragen, scannen und mehr. c't Magazin für Computertechnik 7/2013, p. 186 (German)

Forum Posts

1996 ...

Bitboards: speeding up FirstOne by Laurent Desnogues, rgcc, April 10, 1996 » Othello
bitboard 2^i mod 67 is unique by Stefan Plenkner, rgcc, August 6, 1996
bitboard 2^i mod 67 is unique by Stefan Plenkner, rgcc, August 7, 1996
bitboard 2^i mod 67 is unique by Joël Rivat, rgcc, September 2, 1996
Question to Bob: Crafty , Alpha and FindBit() by Guido Schimmels, CCC, June 05, 1998
To Nalimov and other programmers about BSF/BSR in VC by Dezhi Zhao, CCC, January 16, 1999

2000 ...

Re: TASM 5.0 versus BSF by Frans Morsch, comp.lang.asm.x86, March 28, 2000
Will the Itanium have a BSF or BSR instruction? by Larry Griffiths, CCC, August 15, 2000
Re: Will the Itanium have a BSF or BSR instruction? by Eugene Nalimov, CCC, August 16, 2000
Binary question by Severi Salminen, CCC, October 19, 2000
Bitboards and Piece Lists by Dann Corbit, CCC, June 14, 2001
FirstBit() in assembler by David Rasmussen, CCC, January 13, 2002
Reply from Intel about BSF/BSR by Severi Salminen, CCC, January 31, 2002
"Using de Bruijn Sequences to Index a 1 in a Computer Word" by Oliver Roese, CCC, February 08, 2002
Another hacky method for bitboard bit extraction by Walter Faxon, CCC, November 17, 2002
Modulo verus BitScan and MMX-PopCount by Gerd Isenberg, CCC, November 29, 2002
Fast 3DNow! BitScan by Gerd Isenberg, CCC, December 01, 2002
Bitscan Conclusions by Matt Taylor, CCC, January 05, 2003
Bitscan by Matt Taylor, CCC, February 11, 2003
FirstOne for Linux by Sune Fischer, CCC, March 29, 2003
Bit magic by Matt Taylor, comp.lang.asm.x86, June 26, 2003
Re: De Bruijn Sequence Generator by Dieter Bürssner, CCC, December 30, 2003 » De Bruijn Sequence Generator
Determining location of LSB/MSB by Renze Steenhuisen, CCC, February 09, 2004
Nalimov: bsf/bsr intrinsics implementation still not optimal by Dezhi Zhao, CCC, September 22, 2004
Re: Nalimov: bsf/bsr intrinsics implementation still not optimal by Eugene Nalimov, CCC, September 23, 2004

2005 ...

A data point for PowerPC bitboard program authors by Steven Edwards, CCC, May 09, 2005 » PowerPC
Best BitBoard LSB funktion? by Reinhard Scharnagl, Winboard Programming Forum, July 20, 2005
Fastest bitboard compress routine when you can't use ASM by mambofish, CCC, May 31, 2007
Bit twiddling question, part 2: arbitrary bitscan order by Zach Wegner, CCC, August 11, 2009
32 bit versions for bitscan64 by Michael Hoffmann, CCC, August 21, 2009
64-bit intrinsic performance by Nathan Thom, CCC, October 27, 2009
Bit Scan (equivalent to ASM instructions bsr and bsf) by Pascal Georges, CCC, December 24, 2009

2010 ...

bitScanReverse32 by Luca Hemmerich, CCC, January 25, 2010
Introduction and (hopefully) contribution - bitboard methods by Alcides Schulz, CCC, June 03, 2011 » Population Count
Leading Zero Count Question by Matthew R. Brades, CCC, September 16, 2012
Optimizing bitboards for ARM by Martin Sedlak, CCC, November 17, 2012
Symmetric move generation using bitboards by Lasse Hansen, CCC, December 20, 2014
Stockfish 32-bit and hardware instructions on MSVC++ by Syed Fahad, CCC, December 30, 2014 » Stockfish, BitScan, Population Count

2015 ...

Fun with De Bruijn by Henk van den Belt, CCC, August 27, 2015
Re: Linux Version of Maverick 1.5 by Michael Dvorkin, CCC, November 12, 2015 » OS X, Maverick
syzygy users (and Ronald) by Robert Hyatt, CCC, September 29, 2016 » Population Count

External Links

Find first set from Wikipedia
The Aggregate Magic Algorithms by Hank Dietz
Bit Twiddling Hacks by Sean Eron Anderson
An Efficient Bit-Reversal Sorting Algorithm for the Fast Fourier Transform by Jennifer Elaan, January 16, 2005
Efficient bit scan mechanism - United States Patent 6172623 from FreePatentsOnline.com
Frank Zappa & the Mothers - King Kong BBC Studio Recording 1968, YouTube Video

References

^ Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website
^ Chip Architect: Detailed Architecture of AMD's Opteron - 1.3 A third class of Instructions by Hans de Vries
^ Donald Knuth (2009). The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise tricks & techniques, as Pre-Fascicle 1a postscript, p 10
^ Charles E. Leiserson, Harald Prokop and Keith H. Randall (1998). Using de Bruijn Sequences to Index a 1 in a Computer Word, pdf
^ "Using de Bruijn Sequences to Index a 1 in a Computer Word" discussion in CCC, February 08, 2002
^ N. G. de Bruijn (1975). Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n zeros and ones that show each n-letter word exactly once. Technical Report, Technische Hogeschool Eindhoven, available as pdf reprint
^ Bit magic by Matt Taylor, comp.lang.asm.x86, June 26, 2003
^ Another hacky method for bitboard bit extraction by Walter Faxon, CCC, November 17, 2002
^ bitboard 2^i mod 67 is unique by Stefan Plenkner, rgcc, August 6, 1996
^ Pablo San Segundo, Ramón Galán (2005). Bitboards: A New Approach. AIA 2005
^ Best BitBoard LSB funktion? by Reinhard Scharnagl, Winboard Programming Forum, July 20, 2005
^ Re: Will the Itanium have a BSF or BSR instruction? by Eugene Nalimov, CCC, August 16, 2000
^ ms1bTable array in Eugene Nalimovs bitScanReverse by Stef Luijten, CCC, April 17, 2011
^ just another reverse bitscan by Gerd Isenberg, CCC, December 22, 2005
^ final version - homage to FZ by Gerd Isenberg, CCC, December 23, 2005
^ EuroPython 2012: Florence, July 2–8 | Mark Dickinson
^ Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup from Bit Twiddling Hacks by Sean Eron Anderson
^ 68020 Bit Field Instructions
^ SSE4a from Wikipedia
^ __lzcnt16, __lzcnt, __lzcnt64 Visual C++ Language Reference
^ Bitscan by Matt Taylor, CCC, February 11, 2003
^ _BitScanForward, _BitScanForward64 Visual C++ Language Reference
^ _BitScanReverse, _BitScanReverse64 Visual C++ Language Reference
^ __lzcnt16, __lzcnt, __lzcnt64 Visual C++ Language Reference
^ Section 3: library functions - Linux man pages
^ ffsll(3): find first bit set in word - Linux man page
^ Other Builtins - Using the GNU Compiler Collection (GCC)
^ Re: Nalimov: bsf/bsr intrinsics implementation still not optimal by Eugene Nalimov, CCC, September 23, 2004
^ Matters Computational - ideas, algorithms, source code (pdf) Ideas and Source Code by Jörg Arndt
^ Instruction tables, Lists of instruction latencies, throughputs and microoperation breakdowns for Intel and AMD CPU's (pdf) by Agner Fog
^ Software Optimization Guide for AMD64 Processors
^ Software Optimization Guide for AMD Family 10h and 12h Processors
^ Intel 64 and IA32 Architectures Optimization Reference Manual
^ Haswell Instructions Latency
^ Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2A: Instruction Set Reference, A-M (pdf) BSF—Bit Scan Forward 3-87
^ AMD64 Architecture Programmer’s Manual Volume 3: General-Purpose and System Instructions (pdf) Bit Scan Forward pg. 111
^ ARM Information Center > General data processing instructions > CLZ
^ ARM Information Center > Instruction intrinsics > __builtin_clz
^ Other Builtins - Using the GNU Compiler Collection (GCC)
^ Bit Scan (equivalent to ASM instructions bsr and bsf) by Pascal Georges, CCC, December 24, 2009

What links here?

Page	Date Edited
68020	Jun 7, 2016
Alcides Schulz	Mar 29, 2018
Algorithms	May 5, 2017
Amundsen	Sep 3, 2013
Array	Dec 1, 2016
Attack and Defend Maps	Nov 5, 2016
AVX-512	Aug 8, 2017
Backtracking	Dec 16, 2017
Beowulf	May 5, 2017
Bison	Sep 29, 2016
Bit	Oct 29, 2012
Bit-Twiddling	Nov 6, 2017
Bitboard Serialization	Dec 24, 2014
Bitboards	Nov 14, 2017
Bitfoot	Sep 8, 2015
BitScan	Sep 10, 2017
Blockage Detection	Oct 19, 2017
BMI1	Mar 24, 2014
BMI2	Mar 6, 2018
Bobcat	Jun 27, 2017
Brainless	Jun 24, 2017
Cassandre	Jul 5, 2013
Charles Leiserson	Oct 12, 2016
CHEOPS	Apr 18, 2015
Chess 0.5	Nov 20, 2016
Chezzz	Jan 20, 2013
Classical Approach	Jan 28, 2018
Congruent Modulo Bitboards	Jun 26, 2013
CookieCat	Nov 15, 2016
Crafty	Jan 28, 2018
Cray-1	Dec 25, 2017
Cupcake	May 19, 2016
Daniel White	Feb 9, 2016
David Rasmussen	Dec 16, 2017
De Bruijn sequence	Feb 20, 2018
De Bruijn Sequence Generator	Dec 1, 2016
DEC Alpha	Aug 15, 2015
Dictionary	Aug 24, 2017
Dieter Bürssner	Dec 1, 2016
Djinn	Feb 8, 2016
Double	May 30, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Encoding Moves	Mar 27, 2016
Eugene Nalimov	Dec 23, 2016
Ferranti Mark 1	Jun 2, 2015
Fizbo	Dec 22, 2017
Float	Nov 11, 2016
Gaviota	Jan 21, 2018
General Setwise Operations	Feb 25, 2018
Gibbon	Dec 23, 2014
Gk	Oct 9, 2017
Guido Schimmels	Apr 23, 2013
Hakkapeliitta	Apr 26, 2016
Harald Prokop	Nov 29, 2017
Hash Table	Jan 1, 2018
HeavyChess	Feb 14, 2014
Ifrit	Feb 7, 2016
Intel	Aug 29, 2015
Itanium	Aug 29, 2015
Jan Renze Steenhuisen	Sep 10, 2017
Java-Bitscan	Mar 15, 2014
Joël Rivat	Jul 21, 2017
Joker IT	Sep 16, 2017
Keith H. Randall	Jun 16, 2015
Kim Walisch	Aug 10, 2017
King of Kings	Sep 4, 2013
King Pattern	Nov 15, 2013
Knight Pattern	Feb 23, 2015
Koundinya Veluri	Feb 2, 2013
Kurt	Apr 20, 2014
Leila	May 8, 2017
Little Wing	Oct 26, 2017
Luca Hemmerich	Jun 19, 2017
Mac OS	Mar 25, 2016
Martin Sedlak	Dec 25, 2017
Mathematician	Apr 9, 2018
Matt Taylor	Feb 17, 2013
Matthew R. Brades	Jun 9, 2017
Michael Dvorkin	Jan 8, 2016
Mikhail R. Shura-Bura	Oct 30, 2013
Murka	Nov 11, 2016
Nathan Thom	Mar 15, 2013
Nicolaas de Bruijn	Feb 3, 2015
NoraGrace	Nov 23, 2014
Obstruction Difference	May 27, 2016
Othello	Jan 4, 2018
Pablo San Segundo	Feb 25, 2015
Paladin	Jan 29, 2017
Pascal Georges	Jun 1, 2014
PIC Microcontroller	Oct 27, 2017
Pieces versus Directions	Oct 6, 2016
Population Count	Sep 3, 2017
PowerPC	Oct 6, 2017
Prophet	Sep 30, 2017
Ramón Galán	Feb 25, 2015
RedQueen	Nov 13, 2017
Reinhard Scharnagl	Apr 9, 2016
Reverse Bitboards	Aug 29, 2015
Robert Hyatt	Dec 25, 2017
Robocide	May 11, 2016
SBAMG	Dec 4, 2016
Scorpio	Mar 28, 2018
Searcher	Sep 26, 2016
Senpai	Nov 10, 2017
Severi Salminen	May 7, 2015
Shifted Bitboards	Jan 9, 2011
Sliding Piece Attacks	May 27, 2016
Space-Time Tradeoff	Jun 17, 2015
Spector	Nov 11, 2016
SSE4	Jun 5, 2016
Stef Luijten	Apr 26, 2015
Stefan Plenkner	Dec 31, 2015
Stockfish	Apr 7, 2018
Sune Fischer	Apr 7, 2014
Sungorus	Apr 11, 2014
Syed Fahad	Jan 1, 2017
Thor's Hammer	Nov 23, 2013
Traversing Subsets of a Set	Oct 14, 2016
Tucano	Dec 16, 2017
Tunguska	Sep 16, 2017
Vadim Demichev	Jul 26, 2013
Vice	Mar 8, 2016
Walter Faxon	Mar 6, 2015
Warrior	Feb 23, 2015
Wasp	Nov 24, 2017
X-ray Attacks (Bitboards)	Mar 31, 2015
x86	Jan 4, 2018
x86-64	Mar 6, 2018
x86-64 Instructions to Include	Feb 12, 2011
Zurichess	Mar 12, 2018

Up one Level

Butterfly Boards

GerdIsenberg — Tue, 27 Jan 2015 19:02:19 GMT

Home * Programming * Data * Butterfly Boards

		Butterfly Boards are two-dimensional arrays (typically of various history counters for each color), indexed by the from- and to-square coordinates of (valid and likely quiet) moves, which appear inside the search. Those counters can then be used for move ordering as mentioned in the history heuristic, or to decide about late move reductions and history leaf pruning. Another application is a kind of killer- or refutation table, to store a refutation of a specific move ^[1], also base of the countermove heuristic ^[2] ^[3].
M. C. Escher, Symmetry ^[4]

Layout

The size of the array is 4K (64 x 64 = 4096) elements for each color, but the density is poor, since most from- and to-square combinations are illegal moves by the rules of chess. Thus, most entries inside the Butterfly boards are not used. Also, as an additional drawback, from-to coordinates, specially those with distance one, are ambiguous and may be legal for several pieces. For instance e2-e3 might be a rook-, queen-, king- or white pawn-move. However, knight-, rook- and bishop moves are disjoint, queen moves are the superset from rook- and bishop-moves, king-moves the one-distance subset of queen moves, and pawn pushes are subset of rook-moves, while pawn captures and en passant (if stored at all) are subset of bishop-moves.

Therefor some programmers omit the origin from-square, but use piece-type instead for denser 12 x 64 tables with only 3/4K entries - or exclude not only captures, but also pawn pushes and/or king moves. Other programmers have abandoned hashing moves for History Heuristic and LMR, and say that given enough search depth, History counters produce just some random noise ^[5] .

This is how butterfly boards may be declared in C or C++:

counterType arrWhiteButterfly[64][64]; // from, to -> 4K
counterType arrBlackButterfly[64][64]; // from, to -> 4K

counterType arrButterfly[2][64][64]; // color, from, to -> 8K

Valid Entries

As mentioned in Influence Quantity of Pieces, there are only 1792 (7/16 of 4K) possible valid moves coordinates, 9/16 of the space in the Butterfly boards is "wasted".

Piece	covers other pieces	#	div 112 (7*16)
Rook	queen, king and pawn pushes	896	8
Bishop	queen, king and pawn captures	560	5
Knight	-	336	3
possible from-to move coordinates		1792	16

The Eponym

The name Butterfly Boards was proposed by Dap Hartmann in 1988, when he introduced the Butterfly Heuristic in the ICCA Journal ^[6], and the application of a Butterfly refutation table at the Advances in Computer Chess 6 conference in 1990 ^[7]. Plotting the illegal move coordinates as black cells # inside a 64*64 sheet, seven butterfly shaped pattern appear along the impossible move diagonal (where squares are equal).

The Butterfly

Single Shape

The thorax of the Butterfly is centered by the wraps from one rank (or dependent on the Square Mapping Considerations, one file) to the next one. With 'a1' as square null mapping, and 'd1' as square 3, 'e2' is square 12, the shape indexed by square coordinates looks as follows, covering two wrapped rank "halfs" including their center files, e.g. d1 - e2:

d e f g h a b c d e        d e f g h a b c d e
1 1 1 1 1 2 2 2 2 2        1 1 1 1 1 2 2 2 2 2
#         #           d1   # - - - - # ~ \ | /
  #       # #         e1   - # - - - # # ~ \ |
    #     # # #       f1   - - # - - # # # ~ \
      #   # # # #     g1   - - - # - # # # # ~
        # # # # # #   h1   - - - - # # # # # #
# # # # # #           a2   # # # # # # - - - -
  # # # #   #         b2   ~ # # # # - # - - -
    # # #     #       c2   \ ~ # # # - - # - -
      # #       #     d2   | \ ~ # # - - - # -
        #         #   e2   / | \ ~ # - - - - #

That is why Dap Hartmann called it Butterfly Boards.

Connected Shapes

one butterfly spans a 10 square range
n butterflies span an 8*n + 2 square range
seven butterflies span 58 square range, from 3 (d1) to 60 (e8)

d e f g h a b c d e f g h a b c d e       d e f g h a b c d e f g h a b c d e
1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3       1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3
#         #                          d1   # - - - - # ~ \ | / ~ # # # \ ~ | ~
  #       # #                        e1   - # - - - # # ~ \ | / ~ # # # \ ~ |
    #     # # #                      f1   - - # - - # # # ~ \ | / ~ # # # \ ~
      #   # # # #                    g1   - - - # - # # # # ~ \ | / # # # # \
        # # # # # #                  h1   - - - - # # # # # # ~ \ | # # # # #
# # # # # #                          a2   # # # # # # - - - - - - - | / ~ # #
  # # # #   #                        b2   ~ # # # # - # - - - - - - \ | / ~ #
    # # #     #                      c2   \ ~ # # # - - # - - - - - ~ \ | / ~
      # #       #         #          d2   | \ ~ # # - - - # - - - - # ~ \ | /
        #         #       # #        e2   / | \ ~ # - - - - # - - - # # ~ \ |
                    #     # # #      f2   ~ / | \ ~ - - - - - # - - # # # ~ \
                      #   # # # #    g2   # ~ / | \ - - - - - - # - # # # # ~
                        # # # # # #  h2   # # ~ / | - - - - - - - # # # # # #
                # # # # # #          a3   # # # # # | \ ~ # # # # # # - - - -
                  # # # #   #        b3   \ # # # # / | \ ~ # # # # - # - - -
                    # # #     #      c3   ~ \ # # # ~ / | \ ~ # # # - - # - -
                      # #       #    d3   | ~ \ # # # ~ / | \ ~ # # - - - # -
                        #         #  e3   ~ | ~ \ # # # ~ / | \ ~ # - - - - #

C-Code

Some arbitrary C-code, to produce the plot:

#include "stdafx.h"
#include <math.h>
 
void butterflyBoard(int from, int to) {
   int sq1, sq2, f1, f2, r1, r2, df, dr;
   int nr = 0, nb = 0, nn = 0;
   for (sq2 = from; sq2 <= to; sq2++)
      printf("%c", (sq2 % 10) ? ' ' : '0' + (sq2/10) );
   printf("\n");
   for (sq2 = from; sq2 <= to; sq2++)
      printf("%1d", sq2 % 10 );
   printf("\n");
   for (sq1 = from; sq1 <= to; sq1++) {
      for (sq2 = from; sq2 <= to; sq2++) {
         if ( sq1 != sq2 ) {
            r1 = sq1 >> 3;
            r2 = sq2 >> 3;
            if (r1 == r2) { // same rank
               nr++;
               printf("-");
               continue;
            }
            f1 = sq1 & 7;
            f2 = sq2 & 7;
            if ( f1 == f2 ) { // same file
               nr++;
               printf("|");
               continue;
            }
            if  (f1 - r1 == f2 - r2) { // same diagonal
               nb++;
               printf("/");
               continue;
            }
            if  (f1 + r1 == f2 + r2) { // same anti-diagonal
               nb++;
               printf("\\");
               continue;
            }
            df = abs (f2 - f1);
            dr = abs (r2 - r1);
            if ( df + dr == 3 )    { // knight distance
               nn++;
               printf("~");
               continue;
            }
         }
         printf("#"); // invalid
      }
      printf(" %2d\n", sq1);
   }
   printf("rook   moves %4d\n", nr);
   printf("bishop moves %4d\n", nb);
   printf("knight moves %4d\n", nn);
   printf("total  moves %4d\n", nr + nb + nn);
}
 
int main(int argc, char* argv[])
{
   butterflyBoard(3, 20); // 0, 63
   return 0;
}

Analogy in Astronomy

Dap Hartmann found a nice analogy in astronomy. Edward Maunders was the first astronomer (1904) to plot the distribution in heliographic latitude of the centers of sunspot groups as a functions of time:

A modern version of the Mauders' sunspot "butterfly diagram" ^[8] .

Publications

Jonathan Schaeffer (1983). The History Heuristic. ICCA Journal, Vol. 6, No. 3
Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3
Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1

External links

AVR Butterfly Board from Asuro Wiki (German)

Wikipedia

Butterflies from Wikipedia ^[9]

Butterfly insect of the order Lepidoptera
Butterfly Game a two-player abstract strategy game from Mozambique
BBN Butterfly a massively parallel computer from the 1980s
Butterfly diagram in the context of fast Fourier transform ^[10] algorithms
Butterfly or Zassenhaus lemma
Schmetterlingsgraph (German)
Butterfly knot
Butterfly theorem in elementary geometry
Butterfly curve (algebraic)
Butterfly curve (transcendental)
Butterfly catastrophe Catastrophe theory
Butterfly options a combination option trade strategy
Iron Butterfly spread
Iron Butterfly (band)
Butterfly ballot
Butterfly effect in the context of Chaos theory
The Butterfly Effect (Film)
The Butterfly Effect (band)

Musicvideo

Herbie Hancock & The Headhunters, Butterfly, 1974, YouTube Video

References

^ Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
^ Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
^ Re: History pruning / move ordering question by Don Dailey, CCC, May 10, 2013
^ Picture gallery "Symmetry" from The Official M.C. Escher Website
^ Re: LMR: history or not? by Robert Hyatt from CCC, December 13, 2007
^ Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3
^ Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
^ Edward Walter Maunder, Solar observations A modern version of the Mauders' sunspot "butterfly diagram". (This version from the solar group at NASA Marshall Space Flight Center.)
^ Butterfly (disambiguation) from Wikipedia
^ Fast Fourier Transform (FFT) from Reliable Software

What links here?

Page	Date Edited
Array	Dec 1, 2016
Bobby	Jan 7, 2016
Butterfly Boards	Jan 27, 2015
Butterfly Heuristic	May 6, 2016
Countermove Heuristic	Oct 1, 2017
Dap Hartmann	Jun 10, 2017
Dappet	Dec 12, 2016
Data	Nov 26, 2017
Dictionary	Aug 24, 2017
Direction	Oct 6, 2016
Encoding Moves	Mar 27, 2016
History Heuristic	Jul 19, 2017
History Leaf Pruning	Apr 15, 2013
ICGA Journal	Dec 21, 2017
Influence Quantity of Pieces	Jul 21, 2017
Last Best Reply	Jul 6, 2013
Mathematician	Apr 9, 2018
Moves	Feb 19, 2018
Neural MoveMap Heuristic	Sep 24, 2015
Relative History Heuristic	Jun 8, 2015
Squares	Feb 15, 2015
Table-driven Move Generation	Feb 19, 2017
Vector Attacks	Dec 15, 2017

Up one Level

Color

GerdIsenberg — Wed, 12 Mar 2014 17:00:31 GMT

Home * Chess * Color

		In Chess, Color refers to the color of the two piece sets, the color each player is assigned to, the side to move and the color of a square. The pieces are divided, into white and black sets, but their colors should not taken literally. The players are referred to as "White" and "Black", they control their associated pieces. The colors of the sixty-four squares alternate and are referred to "light squares" and "dark squares", sometimes also referred to "White" and "Black" squares.
M. C. Escher, Day and Night, 1938 ^[1]

Color Definition

Since there are only two colors, one bit is sufficient to encode them. This is how one may define colors in C++:

enum enumColor {
   ecWhite = 0,
   ecBlack = 1
};

Toggle Color

Since the players alternately move, one need to toggle the side to move color after each move made inside the Chess Position object. This can be done by subtracting color from one (ecBlack), ...

inline enumColor toggleColor(enumColor color) {
   return ecBlack - color;
}

... or a little bit cheaper by xoring with the color with one (ecBlack).

inline enumColor toggleColor(enumColor color) {
   return color ^ ecBlack;
}

External Links

References

^ Picture gallery "Switzerland and Belgium 1935 - 1941" from The Official M.C. Escher Website

What links here?

Page	Date Edited
AlphaZero	Feb 10, 2018
Bishop Pair	Sep 10, 2017
Bit	Oct 29, 2012
Bitboard Board-Definition	Jun 23, 2014
Bitboards	Nov 14, 2017
Checks and Pinned Pieces (Bitboards)	Aug 14, 2013
Chess	Jan 21, 2018
Color	Mar 12, 2014
Color Flipping	May 17, 2017
Color of a Square	May 24, 2015
Color Weakness	Nov 24, 2017
Dictionary	Aug 24, 2017
Doubled Pawn	Mar 27, 2017
Duo Trio Quart (Bitboards)	Aug 18, 2017
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Endgame	Sep 18, 2017
Files	Nov 22, 2015
Generic Programming	Jul 7, 2012
Material	Mar 31, 2018
Open file	Feb 15, 2015
Pawn Pushes (Bitboards)	Apr 5, 2013
Pertti Saariluoma	Jun 13, 2017
Piece-Lists	Feb 13, 2017
Piece-Square Tables	Mar 31, 2018
Promotion Square	Aug 15, 2011
Promotions	Jun 6, 2017
Pseudo-Legal Move	May 23, 2015
Ralph Betza	Mar 12, 2014
Ranks	Dec 15, 2008
Side to move	Oct 29, 2017
Simona Tancig	Nov 7, 2012
Weak Pawns	Dec 19, 2013

Up one Level

De Bruijn sequence

GerdIsenberg — Tue, 20 Feb 2018 10:21:34 GMT

Home * Programming * Data * De Bruijn sequence

		In combinatorial mathematics, a k-ary De Bruijn sequence B(k, n) of order n, named after the Dutch mathematician Nicolaas de Bruijn, is a cyclic sequence of a given alphabet A with size k for which every possible subsequence of length n in A appears as a sequence of consecutive characters exactly once ^[1] . In chess programming there are applications of de Bruijn sequences with the Binary alphabet, in hashing sets like Piece-Sets or Square-sets, also called Bitboards, most notably in Bit scanning ^[2] .
Escher's ants on Moebius Strip ^[3]

Binary alphabet

According to De Bruijn himself ^[4] , the existence of De Bruijn sequences were first proved, for the case of alphabets with two elements, by Camille Flye Sainte-Marie in 1894, whereas the generalization to larger alphabets is originally due to Tanja van Ardenne-Ehrenfest ^[5] and himself.

Binary digits or bits inside a computer word are B(2, n) de Bruijn sequences, with 2n bits length and equal number of ones and zeros, with 2n overlapping unique n-bit subsequences. Since the sequences are cyclic and n-1 subsequences need to wrap, we restrict them to at least n-1 leading zeros, to make them overlap the hidden trailing "zeros".

Odd sequences have n leading zeros. The even ones with n-1 leading zeros are rotated (shifted) left by one. Due to n leading zeros of these odd sequences we further consider, the first subsequence[0] is zero. Due to the overlapping, each subsequence[i+1] is dependent from subsequence[i]. The doubled value incremented by either zero or one. Since subsequence[0] is zero, a second zero subsequence with six consecutive binary zeros is further prohibited, and subsequence[1] must be one. Subsequence index i is counted from most significant bit left to right, and therefor reversed from usual bit-index. A modulo 2n restricts all subsequences to n bits:

$s[i+1] = (2s[i] + (0|1)) \mod (2^n)$

The Cardinality of all distinct B(2, n) de Bruijn sequences is:

$|B(2, n)| = 2 ^ {({2 ^ {n-1}} - n)}$

$n$	${({2 ^ {n-1}} - n)}$	$\|B(2, n)\|$
1	0	1
2	0	1
3	1	2
4	4	16
5	11	2,048
6	26	67,108,864
7	57	144,115,188,075,855,872
8	120	~1.329e+36

B(2, 1)

The two one-bit subsequences obviously do not overlap:

i  01  s[i]
0  0    0
1   1   1

B(2, 2)

B(2, 2) implies 2^2 or 4-bit sequences. There is one odd four-bit de Bruijn sequence with four overlapping unique two-bit subsequences, 0x3.

i  0011|0  s[i]
0  00 . . . 0
1   01      1
2  . 11 . . 3
3     1|0   2

B(2, 3)

B(2, 3) implies 2^3 or 8-bit sequences. There are two odd eight-bit sequences with eight overlapping unique three-bit subsequences, 0x17 and 0x1d. Note that the five relevant bits are reversed.

i  00010111|00 s[i]    i  00011101|00 s[i]
0  000 . . . .  0      0  000 . . . .  0
1   001         1      1   001         1
2  . 010 . . .  2      2  . 011 . . .  3
3     101       5      3     111       7
4  . . 011 . .  3      4  . . 110 . .  6
5       111     7      5       101     5
6  . . . 11|0   6      6  . . . 01|0   2
7         1|00  4      7         1|00  4

B(2, 4)

B(2, 4) implies 2^4 or 16 bit sequences. There are 16 odd 16-bit sequences with 16 overlapping unique four-bit subsequences:

0x09af  0000100110101111
0x09eb  0000100111101011
0x0a6f  0000101001101111
0x0a7b  0000101001111011
0x0b3d  0000101100111101
0x0b4f  0000101101001111
0x0bcd  0000101111001101
0x0bd3  0000101111010011
0x0cbd  0000110010111101
0x0d2f  0000110100101111
0x0d79  0000110101111001
0x0de5  0000110111100101
0x0f2d  0000111100101101
0x0f4b  0000111101001011
0x0f59  0000111101011001
0x0f65  0000111101100101

for instance 0x0d2f:

i  0000110100101111|000 s[i]
 0  0000 . . . . . . . .  0
 1   0001                 1
 2  . 0011 . . . . . . .  3
 3     0110               6
 4  . . 1101 . . . . . . 13
 5       1010            10
 6  . . . 0100 . . . . .  4
 7         1001           9
 8  . . . . 0010 . . . .  2
 9           0101         5
10  . . . . . 1011 . . . 11
11             0111       7
12  . . . . . . 1111 . . 15
13               111|0   14
14  . . . . . . . 11|00  12
15                 1|000  8

B(2, 5)

B(2, 5) implies 2^5 or 32 bit sequences. There are 2^11 or 2,048 odd 32-bit sequences with 32 overlapping unique five-bit subsequences, for instance 0x076be629

 i  00000111011010111110011000101001|0000 s[i]
 0  00000 . . . . . . . . . . . . . . . .  0
 1   00001                                 1
 2  . 00011 . . . . . . . . . . . . . . .  3
 3     00111                               7
 4  . . 01110 . . . . . . . . . . . . . . 14
 5       11101                            29
 6  . . . 11011 . . . . . . . . . . . . . 27
 7         10110                          22
 8  . . . . 01101 . . . . . . . . . . . . 13
 9           11010                        26
10  . . . . . 10101 . . . . . . . . . . . 21
11             01011                      11
12  . . . . . . 10111 . . . . . . . . . . 23
13               01111                    15
14  . . . . . . . 11111 . . . . . . . . . 31
15                 11110                  30
16  . . . . . . . . 11100 . . . . . . . . 28
17                   11001                25
18  . . . . . . . . . 10011 . . . . . . . 19
19                     00110               6
20  . . . . . . . . . . 01100 . . . . . . 12
21                       11000            24
22  . . . . . . . . . . . 10001 . . . . . 17
23                         00010           2
24  . . . . . . . . . . . . 00101 . . . .  5
25                           01010        10
26  . . . . . . . . . . . . . 10100 . . . 20
27                             01001       9
28  . . . . . . . . . . . . . . 1001|0. . 18
29                               001|00    4
30  . . . . . . . . . . . . . . . 01|000   8
31                                 1|0000 16

B(2, 6)

B(2, 6) implies 2^6 or 64 bit sequences. There are 2^26 or 67,108,864 odd 64-bit sequences with 64 overlapping unique six-bit subsequences, for instance 0x022fdd63cc95386d

 i  0000001000101111110111010110001111001100100101010011100001101101|00000 s[i]
 0  000000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  0
 1   000001                                                                 1
 2  . 000010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  2
 3     000100                                                               4
 4  . . 001000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  8
 5       010001                                                            17
 6  . . . 100010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
 7         000101                                                           5
 8  . . . . 001011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
 9           010111                                                        23
10  . . . . . 101111 . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
11             011111                                                      31
12  . . . . . . 111111 . . . . . . . . . . . . . . . . . . . . . . . . . . 63
13               111110                                                    62
14  . . . . . . . 111101 . . . . . . . . . . . . . . . . . . . . . . . . . 61
15                 111011                                                  59
16  . . . . . . . . 110111 . . . . . . . . . . . . . . . . . . . . . . . . 55
17                   101110                                                46
18  . . . . . . . . . 011101 . . . . . . . . . . . . . . . . . . . . . . . 29
19                     111010                                              58
20  . . . . . . . . . . 110101 . . . . . . . . . . . . . . . . . . . . . . 53
21                       101011                                            43
22  . . . . . . . . . . . 010110 . . . . . . . . . . . . . . . . . . . . . 22
23                         101100                                          44
24  . . . . . . . . . . . . 011000 . . . . . . . . . . . . . . . . . . . . 24
25                           110001                                        49
26  . . . . . . . . . . . . . 100011 . . . . . . . . . . . . . . . . . . . 35
27                             000111                                       7
28  . . . . . . . . . . . . . . 001111 . . . . . . . . . . . . . . . . . . 15
29                               011110                                    30
30  . . . . . . . . . . . . . . . 111100 . . . . . . . . . . . . . . . . . 60
31                                 111001                                  57
32  . . . . . . . . . . . . . . . . 110011 . . . . . . . . . . . . . . . . 51
33                                   100110                                38
34  . . . . . . . . . . . . . . . . . 001100 . . . . . . . . . . . . . . . 12
35                                     011001                              25
36  . . . . . . . . . . . . . . . . . . 110010 . . . . . . . . . . . . . . 50
37                                       100100                            36
38  . . . . . . . . . . . . . . . . . . . 001001 . . . . . . . . . . . . .  9
39                                         010010                          18
40  . . . . . . . . . . . . . . . . . . . . 100101 . . . . . . . . . . . . 37
41                                           001010                        10
42  . . . . . . . . . . . . . . . . . . . . . 010101 . . . . . . . . . . . 21
43                                             101010                      42
44  . . . . . . . . . . . . . . . . . . . . . . 010100 . . . . . . . . . . 20
45                                               101001                    41
46  . . . . . . . . . . . . . . . . . . . . . . . 010011 . . . . . . . . . 19
47                                                 100111                  39
48  . . . . . . . . . . . . . . . . . . . . . . . . 001110 . . . . . . . . 14
49                                                   011100                28
50  . . . . . . . . . . . . . . . . . . . . . . . . . 111000 . . . . . . . 56
51                                                     110000              48
52  . . . . . . . . . . . . . . . . . . . . . . . . . . 100001 . . . . . . 33
53                                                       000011             3
54  . . . . . . . . . . . . . . . . . . . . . . . . . . . 000110 . . . . .  6
55                                                         001101          13
56  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 011011 . . . . 27
57                                                           110110        54
58  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101101 . . . 45
59                                                             01101|0     26
60  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1101|00  . 52
61                                                               101|000   40
62  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 01|0000  16
63                                                                 1|00000 32

De Bruijn Graphs

A De Bruijn graph is a directed graph representing overlaps between sequences of symbols ^[6] .

Each vertex has exactly m incoming and m outgoing edges
Each n-dimensional de Bruijn graph is the line digraph of the (n-1)-dimensional de Bruijn graph
Each de Bruijn graph is Eulerian and Hamiltonian. The Euler cycles and Hamiltonian cycles of these graphs are de Bruijn sequences.

The graph construction of the three smallest binary de Bruijn graphs

B(2, 4) Graph

A De Bruijn graph. Every four-digit sequence occurs exactly once if one traverses every edge exactly once and returns to one's starting point.

De Bruijn Graph on a Chess Board

A directed De Bruijn Graph of B(2, 6) sequences with Little-Endian Rank-File Mapping board coordinates (a1 = 0, b1 = 1, h8 = 63). For topology reasons, almost each node (except a1 and h8) of the graph is deconcentrated and appears twice in the form of two reversed binary trees. The leaf outputs join the respective reversed tree. Between c6 and f3 is a direct cycle, since 42 is 2*21 and 21 is (2*42 + 1) % 64, with both six-bit pattern reversed - 010101 (21) versus 101010 (42). The challenge is to traverse the graph in any way to visit each of the 64 nodes aka squares exactly once.

+----------------->---------------a1--------------<-----------------+
|                                 |                                 |
|                                 b1                                |
|                 +--------------/  \-------------+                 |
|                c1                               d1                |
^         +-----/  \-----+                 +-----/  \-----+         |
|        e1              f1               g1              h1        |
|     +-/  \-+        +-/  \-+         +-/  \-+        +-/  \-+     |
|    a2      b2      c2      d2       e2      f2      g2      h2    |
|  a3  b3  c3  d3  e3 |f3| g3  h3   a4  b4  c4  d4  e4  f4  g4  h4  |
+-a5b5c5d5e5f5g5h5a6b6c6d6e6f6g6h6 a7b7c7d7e7f7g7h7a8b8c8d8e8f8  |  |
     ^ ^ ^ ^ ^ ^ ^ ^ ^   ^ ^ ^ ^ ^  ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^  |  |
                                                                 |  |
+----------------->---------------h8--------------<--------------+  ^
|                                  |                                |
|                                 g8                                |
|                 +--------------/  \-------------+                 |
|                f8                               e8                |
^         +-----/  \-----+                 +-----/  \-----+         |
|        d8              c8               b8              a8        |
|     +-/  \-+        +-/  \-+         +-/  \-+        +-/  \-+     |
|    h7      g7      f7      e7       d7      c7      b7      a7    |
|  h6  g6  f6  e6  d6 |c6| b6  a6   h5  g5  f5  e5  d5  c5  b5  a5--+
+-h4g4f4e4d4c4b4a4h3g3f3e3d3c3b3a3 h2g2f2e2d2c2b2a2h1g1f1e1d1c1
     ^ ^ ^ ^ ^ ^ ^ ^ ^   ^ ^ ^ ^ ^  ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

De Bruijn Networks

So called De Bruijn Networks with the topology of De Bruijn Graphs have interesting properties in processor and computer networks, for instance as described by Feldmann et al. to connect Transputer networks ^[7] ^[8] .

Selected Publications

1894

Camille Flye Sainte-Marie (1894). Solution to question nr. 48, L'Intermédiaire des Mathématiciens 1, reproduced in Nicolaas de Bruijn (1975). Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n zeros and ones that show each n-letter word exactly once. Technical Report, Technische Hogeschool Eindhoven, pdf

1946

Nicolaas de Bruijn (1946). A Combinatorial Problem. Koninklijke Nederlandse Akademie v. Wetenschappen 49: 758–764.
Jack Good (1946). Normal Recurring Decimals. Journal of the London Mathematical Society ^[9]

1950 ...

Lester Randolph Ford, Jr. (1957). A Cyclic Arrangement of M-Tuples. Report No. P-1071. Rand Corporation
Solomon W. Golomb (1967, 1982). Shift Register Sequences. Holden-Day Inc., revised 2nd edition, Aegean Park Press
Harold M. Fredricksen (1968). Disjoint Cycles from the de Bruijn Graph. Ph.D. thesis, University of Southern California, advisor Solomon Wolf Golomb

1970 ...

Harold M. Fredricksen (1970). The lexicographically least de Bruijn cycle. Journal of Combinatorial Theory, Vol. 9, No. 1
Abraham Lempel (1970). On a Homomorphism of the De Bruijn Graph and Its Applications to the Design of Feedback Shift Registers. IEEE Transactions on Computers, Vol. 19, No. 12
Harold M. Fredricksen (1972). Generation of the Ford Sequence of Length 2n, n Large. JPL Technical Report 32-1526, Vol. IV, pdf

1990 ...

Yuejiang Huang (1990). A new algorithm for the generation of binary de Bruijn sequences. Journal of Algorithms, Vol. 11, No. 1
Chris J. Mitchell, Tuvi Etzion, Kenneth G. Paterson (1996). A method for constructing decodable de Bruijn Sequences. pdf via CiteSeerX
Fred S. Annexstein (1997). Generating De Bruijn Sequences: An Efficient Implementation. IEEE Transactions on Computers, Vol. 46, No. 2, pdf, Supplement: C-code implementation
Charles E. Leiserson, Harald Prokop, Keith H. Randall (1998). Using de Bruijn Sequences to Index a 1 in a Computer Word. pdf

2000 ...

Vladimir Raphael Rosenfeld (2002). Enumerating De Bruijn Sequences. Institute of Evolution, University of Haifa, pdf
Vladimir Raphael Rosenfeld (2002). Enumerating Kautz Sequences. Institute of Evolution, University of Haifa, pdf
Anwitaman Datta, Sarunas Girdzijauskas, Karl Aberer (2004). On de Bruijn routing in distributed hash tables: There and back again. P2P2004, The 4th IEEE International Conference on Peer-to-Peer Computing, pdf
Pierre Fraigniaud, Philippe Gauron (2005). D2B: a de Bruijn Based Content-Addressable Network. pdf
Drew Armstrong (2006). De Bruijn Sequences. pdf
Jean Berstel, Dominique Perrin (2007). The origins of combinatorics on words. European Journal of Combinatorics 28, pdf

2010 ...

Yaw-Ling Lin, Charles B. Ward, Bharat Jain, Steven Skiena (2011). Constructing Orthogonal de Bruijn Sequences. LNCS 6844, WADS 2011
Zuling Chang, Martianus Frederic Ezerman, San Ling, Huaxiong Wang (2016). On Binary de Bruijn Sequences from LFSRs with Arbitrary Characteristic Polynomials. arXiv:1611.10088 ^[10]
Zuling Chang, Martianus Frederic Ezerman, Adamas Aqsa Fahreza, San Ling, Huaxiong Wang (2017). Large Order Binary de Bruijn Sequences via Zech's Logarithms. arXiv:1705.03150 ^[11]
Joe Sawada, Aaron Williams (2017). Practical Algorithms to Rank Necklaces, Lyndon Words, and de Bruijn Sequences. Journal of Discrete Algorithms, Vol. 43, No. C, pdf

External Links

De Bruijn sequence from Wikipedia
De Bruijn graph from Wikipedia
Kautz graph from Wikipedia
Koorde from Wikipedia
A166315 - OEIS
Lyndon word from Wikipedia
If - Forgotten Roads, Beat-Club #71, September 25, 1971, YouTube Video

References

^ De Bruijn sequence from Wikipedia
^ Charles E. Leiserson, Harald Prokop, Keith H. Randall (1998). Using de Bruijn Sequences to Index a 1 in a Computer Word. pdf
^ Escher's Moebius Strip - Ants, from Escher for Real (C) Copyright 2002-2011 Gershon Elber, Computer Science Department, Technion, based on Moebius Strip II, 1963
^ Nicolaas de Bruijn (1975). Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n zeros and ones that show each n-letter word exactly once. Technical Report, Technische Hogeschool Eindhoven, pdf
^ Nicolaas de Bruijn (1985). In Memoriam T. van Ardenne-Ehrenfest. pdf
^ De Bruijn graph from Wikipedia
^ Rainer Feldmann, Peter Mysliwietz, Burkhard Monien (1991). A Fully Distributed Chess Program. Advances in Computer Chess 6, pdf
^ Rainer Feldmann (1993). Game Tree Search on Massively Parallel Systems Phd-Thesis, pdf
^ Recurring decimal from Wikipedia
^ LFSR from Wikipedia
^ Zech's logarithm from Wikipedia

What links here?

Page	Date Edited
Backtracking	Dec 16, 2017
BitScan	Sep 10, 2017
Charles Leiserson	Oct 12, 2016
Data	Nov 26, 2017
De Bruijn sequence	Feb 20, 2018
De Bruijn Sequence Generator	Dec 1, 2016
General Setwise Operations	Feb 25, 2018
Gibbon	Dec 23, 2014
Harald Prokop	Nov 29, 2017
Hash Table	Jan 1, 2018
Keith H. Randall	Jun 16, 2015
Kim Walisch	Aug 10, 2017
Kurt	Apr 20, 2014
Linked List	Oct 11, 2016
Magic Bitboards	Apr 13, 2018
Mathematician	Apr 9, 2018
Nicolaas de Bruijn	Feb 3, 2015
Shared Hash Table	Sep 11, 2017
Tim Mann	Nov 5, 2016
Transputer	Apr 30, 2015
Tunguska	Sep 16, 2017

Up one Level

Depth

GerdIsenberg — Sun, 25 Feb 2018 19:57:06 GMT

Home * Search * Depth

		Depth is the height or nominal depth in plies between the Root and so called horizon nodes (depth 0), where a heuristic value is assigned to. Thus, depth is the number of half moves the search nominally looks ahead. Despite quiescence search, where usually winning captures and even some checks are tried at or behind the search horizon, until positions become sufficiently quite, selectivity of modern chess programs, caused by extensions, pruning and reductions, notably Check Extensions, Null Move Pruning and Late Move Reductions, leads to bushy, non-uniform trees where some branches are searched deeper than nominal, but others shallower. A depth reduction R of multiple plies is often performed in forward pruning techniques like Null Move Pruning and Multi-Cut.
M. C. Escher, Depth, 1955 ^[1]

Draft versus Ply-Index

Most likely inside the search routine, a ply-index is used to index stacks or arrays with pre-saved search information. This index is initialized with zero at the root, and is then incremented after making a move each time the recursive search is called. This index measures the ply-distance from the current node to the root and would therefor be sufficient to determine the remaining depth to the horizon, also called draft:

draft ::= depth at the root - ply index

However, there are various reasons to decouple the depth to horizon from the ply-index or depth from root, which are often passed as independent parameters to a recursive search routine (see code below). While the ply-index is incremented by one each time, the draft may be independently altered by various extension- or reduction-schemes and may also consider fractional extensions ^[2] ^[3] .

Fractional Plies

Some programs extend or reduce in fractions of one ply. Inside an Iterative Deepening framework, the search depth is incremented, usually by one ply - or by a fraction of one ply, for instance 1/2 ply.

Amir Ban on Junior in rgcc, March 1998 ^[4] :

The brute-force ply depth is indeed half the publicized depth. All the rest are extensions (in conventional terminology, I don't think of them this way). If you set Junior to depth 12, e.g., then you should be able to find a 7-ply combination where it fails. If I am doing a good job, then you should have a hard time finding one.

The question of what this is equivalent to in terms of other programs, e.g. a null-mover with "standard" extensions is interesting, but I don't know the answer. In tournament conditions middlegame Junior typically gets 14-16 depths, and it looks competitive tactically.

Depth Comparison of different programs

Due to different implementations, the reported search depth of chess programs is not comparable in general. Programs like The King (Chessmaster), Junior and Rybka are known for interpreting depth differently for whatever reasons.

Selective Search Depth

Some programs also report a selective search depth beside the nominal search depth, most often much greater than the nominal search depth. Some programs determine the highest distance to the root at any node, others only at the horizon.

int highestDepth;
 
int iterativeDeepening() {
   ...
   highestDepth = 0;
   for (depth = 0; depth <= maxdepth; depth += DEPTH_OF_ONE_PLY) {
      score = abSearch( -oo, +oo, depth, 0 );
      if (timeIsOver (...) )
         break;
   }
   ...
}
 
int abSearch( int alpha, int beta, int depth, int ply ) {
   depth += determineExtensions(...);
   depth -= determineReductions(...);
   if( depth <= 0 ) return quiesce( alpha, beta );
   if ( ply > highestDepth )
      highestDepth = ply;
 
   for ( all moves)  {
      score = -abSearch( -beta, -alpha, depth - DEPTH_OF_ONE_PLY, ply + 1 );
      if( score >= beta )
         return beta;   // beta cutoff
      if( score > alpha )
         alpha = score; // alpha acts like max in MiniMax
   }
   return alpha;
}

Maximum Search Depth

The Maximum Search Depth of a depth-first search is usually determined by a compile time constant in ply units (MAX_PLAY). It is used to statically allocate arrays like a Triangular PV-Table, or search stacks inside the programs data- or bss segment. While 64 was quite common, todays programs tend to use higher values, e.g. 128. A search routine should nevertheless check the upper bound of the search stack to immediate return a lazy evaluation score or material balance when the ply index threatens overflow.

Diminishing Returns

Despite the existence of pathology in searching some trees, where a deeper minimax search results in worse play, it is quite consensus in Chess that deeper search yields in stronger play. Strength improvement from depth d to depth d+1 was first systematically examined by Ken Thompson with Belle in Computer Chess Strength, as introduced at the Advances in Computer Chess 3 conference in 1981 ^[5] . Thompson found Belle (n+1) scored about 80% versus Belle (n), which roughly translates to a 200 Elo improvement playing one ply deeper, while the improvement seemed constant independent from the used depths from 3 to 8, while a second experiment ^[6] indicated a falloff beyond depth 7.

	P4	P5	P6	P7	P8	P9	Ratings	RI
P4	X	5	½	0	0	0	1235	-
P5	15	X	3½	3	½	0	1570	235
P6	19½	16½	X	4	1½	1½	1826	256
P7	20	17	16	X	5	4	2031	205
P8	20	19½	18½	15	X	5½	2208	167
P9	20	20	18½	16	14½	X	2328	120

Also, in other board games such as Othello and Checkers, additional plies of search translated into decreasing benefits, giving rise to Diminishing returns for deeper searching. In their 1997 paper Diminishing Returns for Additional Search in Chess ^[7] , Junghanns, Schaeffer, Brockington, Björnsson and Marsland conclude the existence of Diminishing returns in Chess as well, somehow hidden by the high percentage of errors made by chess programs for lower search depth.

In self-play experiments with Crafty, Robert Hyatt, Monroe Newborn ^[8] and later Ernst A. Heinz with DarkThought ^[9] steadily discovered new best moves while searching deeper. In further experiments ^[10] , Heinz found indications of decreasing returns from increasing search in chess. In his 2001 ICGA Journal paper Self-Play, Deep Search and Diminishing Returns ^[11] he gave following match results (3,000 games each) ^[12] :

12-ply was 84 Elo points better than 11 ply
11-ply was 92 Elo points better than 10 ply
10-ply was 115 Elo points better than 9 ply

Tony van Roon-Werten made following statement on Diminishing Returns ^[13] :

If two programs play with 5 vs 6 ply search, the second engine has a 20% depth advantage. With 10 vs 11 it's only 10%. So of course the difference in wins is smaller. ...

Diminishing returns are only proven (IMO) if 6 vs 5 wins more games than 12 vs 10 because only then are you comparing something linear and you give a linear advantage.

Ed Schröder conducted self-play experiments with ProDeo 1.74 playing different depths. Schröder also suggests that ProDeo has a branching-factor of roughly 2, in other words an additional ply corresponds to a doubling of time. In the following table the values indicate the Elo advantage of ProDeo playing with depth A against itself with depth B. The exact tournament conditions can be studied on his webpage ^[14] .

depth A depth B	7	8	9	10	11
6	180	321	401
7	0	147	281	389
8		0	151	255	386
9			0	129	255
10				0	127

Publications

1978 ...

James Gillogly (1978). Performance Analysis of the Technology Chess Program. Ph.D. Thesis. Tech. Report CMU-CS-78-189, Carnegie Mellon University

1980 ...

Ken Thompson (1982). Computer Chess Strength. Advances in Computer Chess 3
Joe Condon, Ken Thompson (1983). BELLE. Chess Skill in Man and Machine
Dana S. Nau (1983). Decision quality as a function of search depth on game trees. Journal of the ACM, Vol. 30, No. 4
Hermann Kaindl (1983). Searching to Variable Depth in Computer Chess. Proceedings of IJCAI 83, pp. 760-762. Karlsruhe. pdf
Monroe Newborn (1985). A Hypothesis Concerning the Strength of Chess Programs. ICCA Journal, Vol. 8, No. 4
Alexander Szabo, Barbara Szabo (1988). The Technology Curve Revisited. ICCA Journal, Vol. 11, No. 1
David Levy, David Broughton, Mark Taylor (1989). The SEX Algorithm in Computer Chess. ICCA Journal, Vol. 12, No. 1

1990 ...

Robert Hyatt, Monroe Newborn (1997). CRAFTY Goes Deep. ICCA Journal, Vol. 20, No. 2
Andreas Junghanns, Jonathan Schaeffer, Mark Brockington, Yngvi Björnsson, Tony Marsland (1997). Diminishing Returns for Additional Search in Chess. Advances in Computer Chess 8, pdf
Ernst A. Heinz (1998). DarkThought Goes Deep. ICCA Journal, Vol. 21, No. 4

2000 ...

Ernst A. Heinz (2000). A New Self-Play Experiment in Computer Chess. Massachusetts Institute of Technology, Laboratory of Computer Science, Technical Memo No. 608, zipped ps, pdf
Ernst A. Heinz (2000). New Self-Play Results in Computer Chess. CG 2000
Ernst A. Heinz (2001). Self-play Experiments in Computer Chess Revisited. Advances in Computer Games 9
Ernst A. Heinz (2001). Modeling the “Go Deep” Behaviour of CRAFTY and DARK THOUGHT. Advances in Computer Games 9
Ernst A. Heinz (2001). Self-Play, Deep Search and Diminishing Returns. ICGA Journal, Vol. 24, No. 2
David Levy (2002). SOME COMMENTS ON REALIZATION PROBABILITIES AND THE SEX ALGORITHM. ICGA Journal, Vol. 25, No. 3
Ernst A. Heinz (2003). Follow-Up on Self-Play, Deep Search, and Diminishing Returns. ICGA Journal, Vol. 26, No. 2
Jonathan Schaeffer (2004). 8. Search Depth. in AI- and Search, Online Course, slides as pdf
Jan Renze Steenhuisen (2005). New Results in Deep-Search Behaviour. ICGA Journal, Vol. 28, No. 4, pdf
Matej Guid, Ivan Bratko (2007). Factors affecting diminishing returns for searching deeper. CGW 2007 » Crafty, Rybka, Shredder, Diminishing Returns
Matej Guid, Ivan Bratko (2007). Factors affecting diminishing returns for searching deeper. ICGA Journal, Vol. 30, No. 2, pdf

2010 ...

Diogo R. Ferreira (2013). The Impact of the Search Depth on Chess Playing Strength. ICGA Journal, Vol. 36, No. 2
Tamal T. Biswas, Kenneth W. Regan (2015). Quantifying Depth and Complexity of Thinking and Knowledge. ICAART 2015, pdf
Tamal T. Biswas, Kenneth W. Regan (2015). Measuring Level-K Reasoning, Satisficing, and Human Error in Game-Play Data. IEEE ICMLA 2015, pdf preprint
Matej Guid, Ivan Bratko (2017). Influence of Search Depth on Position Evaluation. Advances in Computer Games 15

Forum Posts

1996 ...

Fractional depth increments by S.Read, rgcc, January 18, 1996
Diminishing Returns in Search by Jouni Uski, rgcc, September 6, 1996
HIARCS 5 Maximum Search Depth by Kevin Miller, rgcc, January 7, 1997
Ply depth (was: Deep Blue) by Moritz Berger, rgcc, February 18, 1997
Suggested chess experiment by Henri H. Arsenault, rgcc, February 17, 1999

2000 ...

diminishing returns w/ increased search depth? by Peter Kappler, CCC, January 27, 2000
A New Self-Play Experiment - Diminishing Returns Shown with 95% Conf. by Ernst A. Heinz, CCC, May 24, 2000 » Diminishing Returns
Faster, deeper and more of such... by Ed Schröder, CCC, September 14, 2000 » Search Statistics
ICGA_J (June) self-play information by Guy Haworth, CCC, September 05, 2001 ^[15]
About diminishing returns (Uri) by Jouni Uski, CCC, November 22, 2001
The probability to find better move is simply irrelevant for diminishing returns by Uri Blass, CCC, February 09, 2002
The law of diminishing returns by Ed Schröder, CCC, July 12, 2002
Regarding Qsearch with Fractional ply extensions by Federico Corigliano, CCC, August 11, 2003 » Quiescence Search
In chess we will reach diminishing returns just like in Checkers 1994 by Jorge Pichard, CCC, October 29, 2003 ^[16]
diminishing returns by Duncan Roberts, CCC, January 30, 2004
Shredder 8 secret: search depth? by Jouni Uski, CCC, March 23, 2004
Re: Shredder 8 secret: search depth? by Vasik Rajlich, CCC, March 23, 2004 » Shredder, Junior, Fritz
Diminishing returns by Tony Werten, CCC, April 29, 2004
Diminishing returns of increasing search depth by Jarkko, CCC, July 18, 2009

2010 ...

Node counts at a given depth/iteration in search by BB+, OpenChess Forum, May 23, 2011
Elo versus speed by Peter Österlund, CCC, April 02, 2012
From 5 ply to 6.... by Fernando Villegas, CCC, May 06, 2012
Elo Increase per Doubling by Adam Hair, CCC, May 07, 2012
Diminishing returns in fixed depth testing revisited by Jesús Muñoz, CCC, August 25, 2012
Houdini 3-Houdini 3: Nutzen der Bedenkzeitverlängerung by Patrick Götz, CSS-Forum, December 07, 2012 (German) » Houdini
Elo points gain from doubling time by Kai Laskos, CCC, December 10, 2012 » Komodo
Scaling at 2x nodes (or doubling time control). by Kai Laskos, CCC, July 23, 2013 » Houdini, Knowledge, Diminishing Returns
Time to depth measuring tool by Peter Österlund, CCC, July 28, 2013 » Parallel Search
Stockfish depth vs. others; challenge by Larry Kaufman, CCC, November 24, 2013 » Stockfish
How many plies are searched in a typical chess program? by Stephen Dause, CCC, November 09, 2014

2015 ...

Fractional plies and transposition tables by Alexandru Mosoi, CCC, April 18, 2015 » Depth - Fractional Plies, Transposition Table
Doubling of time control by Andreas Strangmüller, CCC, October 21, 2016 » Doubling TC, Diminishing Returns, Playing Strength, Komodo
Stockfish 8 - Double time control vs. 2 threads by Andreas Strangmüller, CCC, November 15, 2016 » Doubling TC, Diminishing Returns, Playing Strength, Stockfish
Diminishing returns and hyperthreading by Kai Laskos, CCC, December 27, 2016 » Diminishing Returns, Match Statistics, Playing Strength, Thread
Ridiculous QSearch Depth by Jonathan Rosenthal, CCC, March 03, 2017 » Quiescence Search

External Links

References

^ Picture gallery "Recognition and Success 1955 - 1972" from The Official M.C. Escher Website
^ David Levy, David Broughton, Mark Taylor (1989). The SEX Algorithm in Computer Chess. ICCA Journal, Vol. 12, No. 1
^ David Levy (2002). SOME COMMENTS ON REALIZATION PROBABILITIES AND THE SEX ALGORITHM. ICGA Journal, Vol. 25, No. 3
^ Funny Junior Engine in CBLight / Junior Engine ply depth by Wolfgang Krietsch, rgcc, February 27, 1998, post 7 and 16 by Amir Ban
^ Ken Thompson (1982). Computer Chess Strength. Advances in Computer Chess 3
^ Joe Condon, Ken Thompson (1983). BELLE. Chess Skill in Man and Machine
^ Andreas Junghanns, Jonathan Schaeffer, Mark Brockington, Yngvi Björnsson, Tony Marsland (1997). Diminishing Returns for Additional Search in Chess. Advances in Computer Chess 8, pdf
^ Robert Hyatt, Monroe Newborn (1997). CRAFTY Goes Deep. ICCA Journal, Vol. 20, No. 2
^ Ernst A. Heinz (1998). DarkThought Goes Deep. ICCA Journal, Vol. 21, No. 4
^ A New Self-Play Experiment - Diminishing Returns Shown with 95% Conf. by Ernst A. Heinz, CCC, May 24, 2000
^ Ernst A. Heinz (2001). Self-Play, Deep Search and Diminishing Returns. ICGA Journal, Vol. 24, No. 2
^ ICGA_J (June) self-play information by Guy Haworth, CCC, September 05, 2001
^ Re: In chess we will reach diminishing returns just like in Checkers 1994 by Tony Werten, CCC, October 30, 2003
^ Experiments in computer chess: The value of depth and diminishing return effects by Ed Schröder, June 2012
^ Ernst A. Heinz (2001). Self-Play, Deep Search and Diminishing Returns. ICGA Journal, Vol. 24, No. 2
^ Perfection in checkers, ChessBase News, October 29, 2003
^ Regan's latest: Depth of Satisficing by Carl Lumma, CCC, October 09, 2015

Up one Level

Fill Algorithms

GerdIsenberg — Wed, 06 Nov 2013 20:14:44 GMT

Home * Board Representation * Bitboards * Fill Algorithms

		Fill algorithms perform the union of a set with their consecutive direction-wise shifts. The shifted intermediate sets are likely intersected with some mask to avoid board wraps of certain directions, and/or also to consider the occupancy or any reasonable taboo set (i.e. pawn attacks) as flood stopping obstruction. For the non sliding pieces, pawn, knight and king, one fill cycle covers all potential moves in one certain direction, or even all moves in different directions. However, for the sliding pieces, bishop, rook and queen, one fill cycle covers a direction-wise move step for a union set of attacked squares reachable in one move. Often, the up to seven direction wise fill cycles may be performed in three parallel prefix steps. Applications of fill algorithms are related to all kinds of pawn properties, progressive mobility and path finding algorithms, f.i. to find so called Trajectories ^[1] ^[2] .
M. C. Escher, Plane Filling II, 1957 ^[3]

Pawn

Pawn fills are performed by north- or south steps, for span determination on the otherwise empty board. If it is about to consider obstructions, the north- or south Dumb7- or Kogge-Stone occluded fill might be applied.

Knight

King

Sliding Pieces

Albeit intended as direction-wise attack generators, a surrounding loop may determine target in at least N moves sets of sliding pieces as well. One may pass not only pieces as argument, but their attacks repetitively, likely with alternating disjoint directions, i.e. file- versus ranks-attacks for rooks and diagonal versus anti-diagonal attacks for bishops.

Forum Posts

Re: Hyperbola Quiesscene: hardly any improvement by Karlo Bala Jr., CCC, January 14, 2009 » Hyperbola Quintessence

External Links

References

^ Boris Stilman (1994). A Linguistic Geometry of the Chess Model. Advances in Computer Chess 7, pdf draft
^ Boris Stilman (2000). Linguistic Geometry - From Search to Construction (Operations Research/Computer Science Interfaces Series). amazon.com
^ Picture gallery "Recognition and Success 1955 - 1972" from The Official M.C. Escher Website

What links here?

Page	Date Edited
Alen Shapiro	May 3, 2015
Algorithms	May 5, 2017
AltiVec	Jun 7, 2016
Bitboards	Nov 14, 2017
Blockage Detection	Oct 19, 2017
Control of Stop and Telestop	Feb 26, 2013
DirGolem	Jun 5, 2016
Distance	Sep 25, 2015
Dumb7Fill	May 27, 2016
Fill Algorithms	Nov 6, 2013
Fill by Subtraction	Mar 5, 2010
HansDamf	Jun 27, 2012
IsiChess	Jan 7, 2016
Iteration	May 5, 2017
Ivan Bratko	Aug 16, 2017
John L. Jerz	Jul 15, 2013
Karlo Bala Jr.	Feb 19, 2017
King Pattern	Nov 15, 2013
Knight Pattern	Feb 23, 2015
Knight-Distance	Oct 20, 2013
Kogge-Stone Algorithm	Sep 17, 2016
Lachex	Jan 7, 2016
Mobility	Jan 17, 2018
Othello	Jan 4, 2018
Pawn Fills	Jul 18, 2014
Pawn Spans	Jul 22, 2010
Shifted Bitboards	Jan 9, 2011
SIMD and SWAR Techniques	Jun 27, 2017
Sliding Piece Attacks	May 27, 2016
Tarrasch Rule	Jun 2, 2014
Trajectory	Jan 3, 2015
Unstoppable Passer	Jun 21, 2016
Zdenek Zdrahal	Apr 4, 2013

Up one Level

Fortress

GerdIsenberg — Thu, 01 Feb 2018 20:40:01 GMT

Home * Chess * Fortress

		Fortress, an endgame drawing technique where a side usually behind in material sets up a zone of protection that the opponent cannot penetrate ^[1]. While fortresses are quite common in (late) endgames, f.i. in Wrong color Bishop and rook pawn, fortresses may rarely occur in the (late) middlegame, characterized by long fixed pawn chains with up to one or two open files but all points of penetration well defended by the weaker side. Chess programs without the implemetation of special knowledge typically fail to recognize fortresses and seem to claim a winning advantage, although they are not able to achieve the win against adequate defence ^[2].
M. C. Escher, Tropea, Calabria ^[3]

Selected Publications

Fortress Detection

Evaluation

Fortress detection might be triggered in evaluation or interior node recognizers if certain material configurations along with the winning advantage, and pawn structure properties occur. Further pattern matching considering relevant features of fortress positions or fuzzier pattern recognition is then used to scale the winning advantage towards the draw score zero - the fuzzier and possibly more error-prone the heuristics, the less the draw scaling. However, due to search versus knowledge trade-off, and all that generalization and tuning problems involved with adding knowledge and noise, practical playing strength versus usefulness in analysis is an issue.

Sample

A pattern of rook vs queen fortress in the endgame was given by Lyudmil Tsvetkov in his 2017 The Secret of Chess ^[4]:

One side having just one queen, and at most a single pawn, with the other having just one rook, and at least one pawn, if the queen side has no passers, the rook is protected by a pawn on the g or b files on its 2nd rank, the king of the rook side is adjacent to that pawn, the pawn of the queen side is on files h,f,a or c, and the king of the queen side is not past its 5th rank.

Search

Another technique of fortress detection as proposed by Matej Guid and Ivan Bratko in 2012 ^[5] is related to search, in particular iterative deepening along with "no progress" indication - that is the root evaluation or low search depths already indicate a winning score, which is not increasing in consecutive iterations. A few programs start scaling scores toward zero if the halfmove clock already exceeds values far below enforcing the 50 move rule, often triggered by conditions mentioned above. Matej Guid and Ivan Bratko further mention the possibility of Monte-Carlo Tree Search to detect fortresses.

Selected Publications

Karsten Müller, Wolfgang Pajeken (2008). How to Play Chess Endings. Gambit Publications, amazon, Chapter 11
Lyudmil Tsvetkov (2010). Little Chess Evaluation Compendium. 2010 pdf
Matej Guid, Ivan Bratko (2012). Detecting Fortresses in Chess. Elektrotehniški vestnik, Vol. 79, Nos. 1-2, pdf » Rybka, Houdini ^[6]
Lyudmil Tsvetkov (2017). The Secret of Chess. amazon

Forum Posts

2000 ...

Thanks -- and a question about "fortress" recognition in programs by Steve, CCC, March 21, 2002
The Bahrain Fortress by Mike Scheidl, December 10, 2002 » Kramnik versus Deep Fritz 2002 - Game 6
missing a win or fortress? by Uri Blass, CCC, July 21, 2004

2005 ...

Fortress: is there an engine that can solve this? by Peter Kasinski, CCC, December 18, 2005
Is this positions drawn ? by M. Ansari, CCC, May 18, 2007
Fortress detection program by Anil, CCC, August 19, 2008
Fortress Draws by Ted Summers, CCC, May 31, 2009

2010 ...

Funny fortress position by Joona Kiiski, CCC, January 25, 2010
"No progress" and Graph History Interaction by BB+, OpenChess Forum, January 23, 2011 » Graph History Interaction
Another fortress position by Robert Flesher, CCC, March 13, 2011
Simple fortress detection, engines fail by Vincent Lejeune, CCC, July 04, 2012
test position: fortress by Jon Dart, CCC, December 02, 2012
Idea for recognizing fortress/encouraging progress by Piotr Lopusiewicz, CCC, May 03, 2013
Re: Chessprogams with the most chessknowing by Ferdinand Mosca, CCC, December 20, 2014

2015 ...

Endgame fortress handling by Lyudmil Tsvetkov, CCC, March 25, 2015
A very subtle fortress destruction by Árpád Rusz, CCC, January 23, 2016
Fortresses by Jon Fredrik Åsvang, CCC, February 15, 2016
Fortresses by Jon Fredrik Åsvang, CCC, January 30, 2017
What does semi-fortress mean? by Jon Fredrik Åsvang, CCC, September 22, 2017
replace the evaluation by playing against yourself by Uri Blass, CCC, January 25, 2018 » Evaluation

External Links

On Topic

Misc

References

^ Fortress (chess) from Wikipedia
^ Matej Guid, Ivan Bratko (2012). Detecting Fortresses in Chess. Elektrotehniški vestnik, Vol. 79, Nos. 1-2, pdf
^ M. C. Escher, Tropea, Calabria, 1931, Picture gallery "Italian Period" from The Official M.C. Escher Website
^ Lyudmil Tsvetkov (2017). The Secret of Chess. amazon - Rook vs queen fortress in the endgame, pp. 273
^ Matej Guid, Ivan Bratko (2012). Detecting Fortresses in Chess. Elektrotehniški vestnik, Vol. 79, Nos. 1-2, pdf
^ Re: Tony's positional test suite by Louis Zulli, CCC, August 01, 2017

What links here?

Page	Date Edited
Blockage Detection	Oct 19, 2017
Chess	Jan 21, 2018
Design Principles	Jan 17, 2018
Draw Evaluation	Mar 12, 2018
Evaluation	Feb 1, 2018
Fortress	Feb 1, 2018
Fortress (Engine)	Oct 19, 2017
Graph History Interaction	Oct 16, 2017
Kramnik versus Deep Fritz 2002	Oct 16, 2017
Marek Kwiatkowski	Oct 22, 2017
Sting	Mar 16, 2018
SugaR	Oct 9, 2017
Texel	Oct 9, 2017
Uri Blass	Feb 26, 2018
Wrong color Bishop and rook pawn	Oct 19, 2017

Up one Level

Futility Pruning

GerdIsenberg — Wed, 30 Aug 2017 18:51:59 GMT

Home * Search * Selectivity * Pruning * Futility Pruning

		Futility Pruning, in its pure form implemented at the frontier nodes (depth == 1) with one ply left to the horizon. It discards the moves that have no potential of raising alpha, which in turn requires some estimate of a potential value of a move. This is calculated by adding a futility margin (representing the largest conceivable positional gain) to the evaluation of the current position. If this does not exceed alpha then the futility pruning is triggered to skip this move (which further means setting a flag like f_prune = 1 to indicate not all moves were tried).
M. C. Escher, Relativity, 1953 ^[1]

Conditions

Extended Futility Pruning

Move Count Based Pruning

Deep Futility Pruning

Conditions

For tactical stability, even in such a node we ought to search the following moves:

captures (either all or less typically only those that are capable of raising the score above alpha + margin)
moves that give check

Futility pruning is not used when the side to move is in check , or when either alpha or beta are close to the mate value, since it would leave the program blind to certain checkmates. Tord Romstad reported that in his early program Gothmog one more condition was necessary - namely that futility pruning requires checking for the existence of at least one legal move ^[2] ^[3] to avoid returning erroneous stalemate scores. As replied by Omid David: then simply return alpha (to fail low but hard).

Extended Futility Pruning

Ernst A. Heinz advocated using so-called extended futility pruning ^[4]. It means employing similar algorithm at pre frontier nodes at depth == 2, only with the greater margin. If at depth 1 the margin does not exceed the value of a minor piece, at depth 2 it should be more like the value of a rook.

Move Count Based Pruning

A further variation of Extended Futility Pruning combining the ideas of Fruit's History Leaf Pruning and Late Move Reductions is called Move Count Based Pruning or Late Move Pruning (LMP) as implemented in Stockfish ^[5].

Deep Futility Pruning

Deep Futility Pruning was proposed by Harm Geert Muller ^[6]. It is applied at depths of 1<d<=3+R, i.e. with two moves to go:

if ( CurEval <= Alpha - PVal[FirstPiece(Opponent)] - PVal[SecondPiece(Opponent)] - 2*PosMargin )
   prune

Publications

Jonathan Schaeffer (1986). Experiments in Search and Knowledge. Ph.D. Thesis, University of Waterloo. Reprinted as Technical Report TR 86-12, Department of Computing Science, University of Alberta
Chun Ye, Tony Marsland (1992). Experiments in Forward Pruning with Limited Extensions. ICCA Journal, Vol. 15, No. 2
Ernst A. Heinz (1998). Extended Futility Pruning. ICCA Journal, Vol. 21, No. 2.

Forum Posts

1995 ...

futility cut-offs by Alessandro Damiani, rgcc, November 14, 1997
Extended Futility Pruning - anyone tried it? by Tom King, rgcc, August 16, 1998
Extensions and Futility Pruning by James Robertson, CCC, May 04, 1999 » Extensions
Extended futility pruning and hashtables by Gian-Carlo Pascutto, CCC, December 30, 1999 » Transposition Table

2000 ...

Futility Pruning (I think) Question by Brian Richardson, CCC, April 02, 2000
Caution K v KBN and lazy eval or futility by Brian Richardson, CCC, May 14, 2000 » KBNK Endgame, Lazy Evaluation
Something wrong with my futility pruning? by Severi Salminen, CCC, December 05, 2000
About history heuristics, killers and my futil. pruning code by Severi Salminen, CCC, December 06, 2000 » History Heuristic, Killer Heuristic
question about futility pruning and positional evaluation by Bert van den Akker, CCC, December 07, 2000 » Evaluation
Futility Cutoff futile? by Stuart Cracraft, CCC, August 29, 2001
Re: Futility Pruning by Vincent Diepeveen, CCC, December 20, 2002
To Stefan Knappe by Rahman Paidar, Winboard Forum, June 21, 2003 » Stefan Knappe
futility pruning? by Daniel Shawul, CCC, November 09, 2003
Unexpected problem with futility pruning ? by Geoff, CCC, December 29, 2003
Extended futility pruning not working by Cesar Contreras, CCC, August 03, 2004
Futility by Stuart Cracraft, CCC, October 14, 2004
Futility Prune question by Stuart Cracraft, CCC, October 17, 2004
Futility @ 1/Extended Futility @ 2/Limited Razoring @ 3 = % node reduce? by Stuart Cracraft, CCC, October 19, 2004

2005 ...

Does simple futility prune work by Rasjid Chan, Winboard Forum, March 27, 2005
Selective Futlity Condition at Quiescence Nodes by Pradu, Winboard Forum, October 26, 2005
Null move, futility and LMR by Harm Geert Muller, Winboard Forum, September 26, 2006 » Null Move Pruning, LMR
Hash Table handling with LMR/Futility pruning by Pradu, Winboard Forum, October 21, 2006
Extended futility reduction by Michael Sherwin, Winboard Forum, November 18, 2006
How much elo from futility? by Alessandro Scotti, CCC, September 05, 2007
LMR and futility by Pawel Koziol, CCC, October 28, 2007
Draw recognizers, futility... mess by Pawel Koziol, CCC, October 14, 2008
futility pruning - razoring by Don Dailey, CCC, September 16, 2009 » Razoring
Futility pruning, Ext futility pruning and Limited Razoring by Jesper Nielsen, CCC, November 26, 2009

2010 ...

Futility Idea based on total score by Mark Lefler, CCC, February 06, 2010
Confused by futility pruning by Michel Van den Bergh, CCC, March 03, 2010
move count based pruning by Tom King, CCC, September 02, 2010
LMR, Razoring, Futility.... with chess variant with drops? by Justin Madru, CCC, December 30, 2010
Futility Methods by kenny stanley, CCC, January 21, 2011
futility pruning in stockfish by Engin Üstün, CCC, May 25, 2011 » Stockfish
Reverse Futility Pruning by Matthew R. Brades, CCC, December 02, 2011 » Reverse Futility Pruning
How to get futility pruning to work? by Robert Purves, CCC, March 05, 2012
futility pruning, razoring question by Marco Belli, CCC, April 04, 2012 » Razoring
A search enhancement? by Daniel Homan, CCC, April 30, 2012 » Move Count Based Pruning
LMP in PV nodes by Peter Österlund, CCC, December 27, 2014 » PV-Node, Texel

2015 ...

Problem understanding futility pruning by Nicu Ionita, CCC, May 11, 2015
Razoring vs Futility pruning by Shawn Chidester, CCC, August 16, 2015 » Razoring

2016

futility pruning by Folkert van Heusden, CCC, February 20, 2016
Futile attempts at futility pruning by Martin Fierz, CCC, March 27, 2016 » Reverse Futility Pruning
Futility prunning by Daniel Anulliero, CCC, August 11, 2016 » Reverse Futility Pruning
Futility Pruning by David Cimbalista, CCC, October 11, 2016

2017

Futility pruning ? by Mahmoud Uthman, CCC, March 04, 2017 » Reverse Futility Pruning
futile futility pruning attempt by Folkert van Heusden, CCC, March 07, 2017
Futility pruning... by thevinenator, OpenChess Forum, April 07, 2017
increasing futility prunning depth by Alexandru Mosoi, CCC, April 28, 2017

External Links

Pruning

Misc

futility - Wiktionary
futile - Wiktionary
Futility from Wikipedia
The Wreck of the Titan: Or, Futility - Wikipedia
Porcupine Tree - Futile, Zeche Bochum, November 18, 2003, YouTube Video

References

^ Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website
^ Serious bug in Gothmog 0.2.6! by Tord Romstad, Winboard Forum, August 04, 2003
^ Re: Unexpected problem with futility pruning? by Tord Romstad, CCC, December 29, 2003
^ Ernst A. Heinz (1998). Extended Futility Pruning. ICCA Journal, Vol. 21, No. 2
^ move count based pruning by Tom King, CCC, September 02, 2010
^ Deep Futility Pruning by Harm Geert Muller

What links here?

Page	Date Edited
Abyss	Aug 5, 2017
AEL-Pruning	Jun 22, 2013
Amy	May 9, 2017
Amyan	Dec 10, 2013
Andscacs	Jan 16, 2018
Arion	Nov 28, 2014
Atlas (ESP)	Jan 28, 2018
Betsabe	Jul 23, 2017
Bison	Sep 29, 2016
BlackBishop	Nov 7, 2014
Carballo	Oct 2, 2016
Cheese	Feb 17, 2018
Cheng	Jul 30, 2017
ChessBrainVB	Jun 24, 2017
ChessV	Jan 21, 2018
Cinnamon	Sep 23, 2017
Coiled	Mar 12, 2017
Counter	Nov 13, 2017
CPW-Engine	Dec 31, 2014
Crafty	Jan 28, 2018
CuckooChess	Jan 17, 2017
Cyclone	Nov 24, 2013
Dan Homan	Oct 19, 2016
Daniel Anulliero	Oct 3, 2017
DarkThought	Jul 3, 2018
DayDreamer	Aug 22, 2016
Defenchess	Mar 18, 2018
Delfi	Jan 7, 2016
Delta Pruning	Dec 2, 2014
Deuterium	Jun 23, 2014
Diablo	May 17, 2016
Dictionary	Aug 24, 2017
Dimitri	Aug 22, 2017
Donna	Aug 17, 2017
Dorky	Oct 10, 2016
DrunkenMaster	Nov 1, 2016
Elephant	Sep 19, 2016
Engine Testing	Feb 1, 2018
Ernst A. Heinz	Mar 6, 2017
ESC	Aug 14, 2013
Ethereal	Mar 20, 2018
Exacto	Oct 3, 2015
EXchess	Jan 21, 2018
Extensions	Apr 19, 2018
Falcon	Sep 2, 2016
Fischerle	Aug 21, 2017
Flux	Jan 12, 2016
Fridolin	Jun 27, 2017
Frontier Nodes	Dec 29, 2013
Futility Pruning	Aug 30, 2017
Galjoen	Mar 19, 2018
Garbochess	Sep 23, 2017
Gaviota	Jan 21, 2018
Ghost	Feb 2, 2018
Gian-Carlo Pascutto	Jan 16, 2018
Gibbon	Dec 23, 2014
Glass	May 24, 2017
Gogobello	Jul 30, 2017
GopherCheck	Feb 3, 2017
Hagrid	Apr 12, 2016
Hakkapeliitta	Apr 26, 2016
History Leaf Pruning	Apr 15, 2013
Ifrit	Feb 7, 2016
ISA	Apr 2, 2018
Jeroen Carolus	Jun 2, 2016
JFresh	Mar 2, 2016
JikChess	Nov 29, 2015
Joker NL	Sep 15, 2017
KBNK Endgame	Nov 26, 2016
KingSlayer	Oct 17, 2016
Koundinya Veluri	Feb 2, 2013
Laser	Dec 27, 2017
Late Move Reduction Test Results	Sep 25, 2017
Late Move Reductions	Sep 25, 2017
Lazy Evaluation	Sep 1, 2017
Little Wing	Oct 26, 2017
Marco Belli	Jan 6, 2018
Mark Lefler	Nov 23, 2017
Martin Fierz	Apr 26, 2018
Marvin	Feb 10, 2018
Matador	Oct 30, 2015
Mate Search	Oct 22, 2016
Matthew R. Brades	Jun 9, 2017
Michel Van den Bergh	Mar 10, 2018
Napoleon	Jun 25, 2017
Natwarlal	Aug 26, 2013
Nebula	Feb 7, 2015
Nemorino	Dec 21, 2017
Nicu Ionita	May 3, 2017
Nirvanachess	Sep 30, 2017
Node Types	Oct 22, 2017
NoraGrace	Nov 23, 2014
Octochess	Aug 15, 2017
Orion	Oct 15, 2017
Ostrich	Dec 28, 2017
Parity Pruning	Jan 14, 2013
Pawny	Jun 17, 2015
Phalanx	May 2, 2016
Plisk	Dec 31, 2014
PostModernist	Jan 7, 2016
Pre Frontier Node	Mar 10, 2012
Prédateur	Nov 11, 2016
ProbCut	Mar 25, 2016
ProChess IT	Sep 30, 2015
Prophet	Sep 30, 2017
Protector	Oct 12, 2017
Pruning	Jan 1, 2018
Purple Haze	Oct 26, 2017
Ramjet	Sep 27, 2017
Rasjid Chan	Nov 26, 2014
RattateChess	Dec 2, 2014
Razoring	Oct 5, 2015
Rebel	Feb 25, 2018
RedQueen	Nov 13, 2017
Requiem	Feb 5, 2018
Reverse Futility Pruning	Jun 2, 2017
Rhetoric	Nov 15, 2017
Rodent	Jan 11, 2018
Sayuri	Oct 1, 2017
Scidlet	May 31, 2014
Search Instability	May 5, 2017
Selectivity	Jan 12, 2018
Senpai	Nov 10, 2017
Severi Salminen	May 7, 2015
Shawn Chidester	Aug 9, 2016
Shield	May 17, 2017
Simplex	Mar 6, 2016
Sinobyl	Jul 3, 2014
Sjeng	Aug 17, 2017
Sloppy	Sep 17, 2016
Smash	May 11, 2016
Snitch	Apr 7, 2016
Spike	Jan 7, 2016
Static Exchange Evaluation	Dec 14, 2017
Stefan Knappe	Jan 22, 2013
Stockfish	Apr 7, 2018
Sunsetter	Jun 1, 2017
Teki	Mar 29, 2018
Texel	Oct 9, 2017
The Baron	Jan 8, 2018
tomitankChess	Dec 8, 2017
Tornado	Dec 14, 2017
Tucano	Dec 16, 2017
Tunguska	Sep 16, 2017
Tytan	Nov 3, 2015
Vajolet	Jan 25, 2018
Volker Böhm	Jan 7, 2016
Wasp	Nov 24, 2017
Waxman	Aug 18, 2014
WildCat	Nov 11, 2016
Wing	Oct 26, 2017
Winter	Jan 23, 2018
WyldChess	Mar 10, 2018
Xiphos	Apr 22, 2018
Xpdnt	Sep 13, 2015
Zeus RU	Jun 6, 2015
Zurichess	Mar 12, 2018

Up one Level

Interior Node Recognizer

GerdIsenberg — Mon, 12 Mar 2018 19:17:07 GMT

Home * Knowledge * Interior Node Recognizer

		Interior Node recognizers are evaluation like functions called from within a node in order to avoid unnecessary searches if perfect knowledge is available, either to prune or narrow the bounds at interior nodes. Most of the time result replacing search is obtained from endgame tablebases, generated by retrograde analysis, but this may well be replaced by code detecting certain characteristics of the position. A trivial example of such a heuristic (restricted to detecting draws) may be found on a page devoted to KPK endings. Other examples are positions with known draws, such as lone K vs lone K, K+B vs K or K+N vs K. Implementation of this technique requires a legality check (even in the most basic example, claiming draw when there are only kings on the board, a buggy code may encourage going into this ending by the means of the illegal capture) or a legal move generator. In general, if a recognizer is based on a remaining material, special care must be taken to avoid the possibility of a stalemate and whether hanging pieces may be captured - for instance if the lonesome king in KBNK may capture either the bishop or knight. Score obtained from interior node recognizers may be treated as if it came from the probe of a transposition table, so they ought to be called near to it. In order to make recognizer results compatible with the results of probes from the transposition tables, they are composed from bound and score information.
M. C. Escher, Circle Limit IV, 1960 ^[1]

Score Type

Exact Score
Lower Bound
Upper Bound
Fail Bound for unsuccessful recognition

Publications

David Slate (1984). Interior-node Score Bounds in a Brute-force Chess Program. ICCA Journal, Vol. 7, No. 4
Ernst A. Heinz (1998). Efficient Interior-Node Recognition. ICCA Journal, Vol. 21, No. 3

Forum Posts

Help Finding X by Mark Lefler, CCC, June 08, 2007
Best was to Recognize Know Endgames? by Steve Maughan, CCC, August 03, 2013
Re: Best was to Recognize Know Endgames? by Harm Geert Muller, CCC, August 03, 2013 » KBNK Endgame

References

^ Picture gallery "Recognition and Success 1955 - 1972" from The Official M.C. Escher Website

What links here?

Page	Date Edited
Blockage Detection	Oct 19, 2017
Bobcat	Jun 27, 2017
Coiled	Mar 12, 2017
DarkThought	Jul 3, 2018
Djinn	Feb 8, 2016
Draw	Apr 14, 2018
Draw Evaluation	Mar 12, 2018
Endgame Bitbases	Apr 5, 2017
Endgame Tablebases	Mar 6, 2018
Ernst A. Heinz	Mar 6, 2017
Fischerle	Aug 21, 2017
Fortress	Feb 1, 2018
Gibbon	Dec 23, 2014
Interior Node	Aug 6, 2012
Interior Node Recognizer	Mar 12, 2018
KBNK Endgame	Nov 26, 2016
Knowledge	Jul 22, 2017
KPK	May 12, 2016
KRK	Nov 26, 2016
Leon Piasetski	Nov 13, 2014
Mate Search	Oct 22, 2016
Material	Mar 31, 2018
Material Hash Table	Apr 3, 2014
Monsoon	Feb 8, 2015
Mop-up Evaluation	Nov 26, 2016
Nuchess	Apr 3, 2017
Oracle	Sep 4, 2016
Pattern Recognition	Sep 8, 2017
Robocide	May 11, 2016
Score	Apr 14, 2018
Space-Time Tradeoff	Jun 17, 2015
Stalemate	Feb 21, 2018
Terminal Node	Nov 17, 2012
Transposition Table	Apr 19, 2018
Typhoon	Apr 18, 2016
Witz	Nov 14, 2017

Up one Level

Intersection Squares

GerdIsenberg — Sat, 04 Oct 2014 21:14:36 GMT

Home * Chess * Squares * Intersection Squares

		Intersection squares are the result of the intersection of two lines from two different squares with two disjoint directions, either rank, file, diagonal or anti-diagonal, in total 2*(3+2+1) = 12 possible combinations. Those lines (may) have up to one square, where both lines intersect - a square where two appropriate sliding pieces were able to move to in one step (assuming no obstructions). In the set-wise world of bitboards one usually relies on set-wise intersection of sliding piece attacks, but square-centric board representations may either use two-dimensional lookup tables, or rely on some algebra based on discrete linear equations and pure register computation. Programs may use these routines as a precondition whether an intersection point exist, for instance to determine a square where a sliding piece may check the opponent king.
M. C. Escher, Two Intersecting Planes, 1952 ^[1]

Rank and File

or vice versa File and Rank

Two squares a and b have always two orthogonal intersection squares s1 and s2.

. | . . . | . .
--1-------b----
. | . . . | . .
. | . . . | . .
. | . . . | . .
. | . . . | . .
--a-------2----
. | . . . | . .

s1 := 8*rankIndex(b) + fileIndex(a);
s2 := 8*rankIndex(a) + fileIndex(b);

s1 := (b & 56) + (a & 7);
s2 := (a & 56) + (b & 7);

Empty Intersection with 0x88 Math

If diagonals or anti-diagonals are involved, the intersection square may off the board. Beside that, the intersection of a diagonal with an anti-diagonal becomes empty, if both lines are of different square color. Considering 0x88-square coordinates for the calculation, covers off the board intersection, and the different color issues en passant. Following C-routines work branchless, and return -1 if no intersection is possible by oring with following {0,-1} integer expression relying on arithmetical shift right:

 -(s88 & 0x88) >> (sizeof(int)-1)

Feel free to use branches instead in a broader scope, since one need to branch on valid intersecion square anyway.

Rank and Diagonal

or vice versa Diagonal and Rank

. . . . . . / .
. . . . . b . .
. . . . / . . .
. . . / . . . .
. . / . . . . .
. / . . . . . .
s-----a--------
. . . . . . . .

with

diagonalIndex := rankIndex - fileIndex;
\f  0  1  2  3  4  5  6  7
r_________________________
7 | 7  6  5  4  3  2  1  0
6 | 6  5  4  3  2  1  0 -1
5 | 5  4  3  2  1  0 -1 -2
4 | 4  3  2  1  0 -1 -2 -3
3 | 3  2  1  0 -1 -2 -3 -4
2 | 2  1  0 -1 -2 -3 -4 -5
1 | 1  0 -1 -2 -3 -4 -5 -6
0 | 0 -1 -2 -3 -4 -5 -6 -7

0x88 Math

rankIndex(s) := rankIndex(a);
fileIndex(s) := rankIndex(s) - diagonalIndex(s);
fileIndex(s) := rankIndex(a) - rankIndex(b) + fileIndex(b);

Because the intersection of any rank with any diagonal may off the board, we rely on 0x88 math for a quick test:

s88 := 16*rankIndex(s) + fileIndex(s);
s88 := 16*rankIndex(a) + (rankIndex(a) - rankIndex(b) + fileIndex(b));
s88 := 17*rankIndex(a) -  rankIndex(b) + fileIndex(b);
if ( s88 & 0x88)
   intersection off board;
else
   sq := ((sq88 >> 1) & 56) + (sq88 & 7);

C-Source

/****************************************
 * return: intersection square (if any)
 *          of rank of square a
 *          with diagonal of square b
 *         -1 if no intersection exists
 ****************************************/
int intersectRankDia(int a, int b) {
   int s88 = 17*(a>>3) - (b >> 3) + (b & 7);
   return (((s88 >> 1) & 56) + (s88 & 7)) | ( -(s88 & 0x88) >> 31);
}

File and Diagonal

or vice versa Diagonal and File

. . . | . . / .
. . . | . b . .
. . . | / . . .
. . . s . . . .
. . / | . . . .
. / . | . . . .
/ . . a . . . .

with

diagonalIndex := rankIndex - fileIndex;
\f  0  1  2  3  4  5  6  7
r_________________________
7 | 7  6  5  4  3  2  1  0
6 | 6  5  4  3  2  1  0 -1
5 | 5  4  3  2  1  0 -1 -2
4 | 4  3  2  1  0 -1 -2 -3
3 | 3  2  1  0 -1 -2 -3 -4
2 | 2  1  0 -1 -2 -3 -4 -5
1 | 1  0 -1 -2 -3 -4 -5 -6
0 | 0 -1 -2 -3 -4 -5 -6 -7

0x88 Math

fileIndex(s) := fileIndex(a);
rankIndex(s) := fileIndex(s) + diagonalIndex(s);
rankIndex(s) := fileIndex(a) + rankIndex(b) - fileIndex(b);

Because the intersection of any file with any diagonal may off the board, we rely on 0x88 math for a quick test:

s88 := 16*rankIndex(s) + fileIndex(s);
s88 := 16*(fileIndex(a) + rankIndex(b) - fileIndex(b)) + fileIndex(a);
s88 := 17*fileIndex(a) + 16*rankIndex(b) - 16*fileIndex(b);
if ( s88 & 0x88)
   intersection off board;
else
   sq := ((sq88 >> 1) & 56) + (sq88 & 7);

C-Source

/****************************************
 * return: intersection square (if any)
 *          of file of square a
 *          with diagonal of square b
 *         -1 if no intersection exists
 ****************************************/
int intersectFileDia(int a, int b) {
   int s88 = 17*(a & 7) + 2*(b & 56) - 16*(b & 7);
   return (((s88 >> 1) & 56) + (s88 & 7)) | ( -(s88 & 0x88) >> 31);
}

Rank and Anti-Diagonal

or vice versa Anti-Diagonal and Rank

. . . . . . . .
. . . . . . . .
\ . . . . . . .
. b . . . . . .
. . \ . . . . .
. . . \ . . . .
------a-s------
. . . . . \ . .

with

antidiagIndex := rankIndex + fileIndex;
\f  0  1  2  3  4  5  6  7
r_________________________
7 | 7  8  9 10 11 12 13 14
6 | 6  7  8  9 10 11 12 13
5 | 5  6  7  8  9 10 11 12
4 | 4  5  6  7  8  9 10 11
3 | 3  4  5  6  7  8  9 10
2 | 2  3  4  5  6  7  8  9
1 | 1  2  3  4  5  6  7  8
0 | 0  1  2  3  4  5  6  7

0x88 Math

rankIndex(s) := rankIndex(a);
fileIndex(s) := antidiagIndex(s) - rankIndex(s);
fileIndex(s) := rankIndex(a) -  rankIndex(b) + fileIndex(b);

Because the intersection of any rank with any anti-diagonal may off the board, we rely on 0x88 math for a quick test:

s88 := 16*rankIndex(s) + fileIndex(s);
s88 := 16*rankIndex(a) + rankIndex(a) -  rankIndex(b) + fileIndex(b);
s88 := 17*rankIndex(a) - rankIndex(b) + fileIndex(b);
if ( s88 & 0x88)
   intersection off board;
else
   sq := ((sq88 >> 1) & 56) + (sq88 & 7);

C-Source

/****************************************
 * return: intersection square (if any)
 *          of rank of square a
 *          with anti-diagonal of square b
 *         -1 if no intersection exists
 ****************************************/
int intersectRankAnt(int a, int b) {
   int s88 = 17*(a >> 3) - (b >> 3) + (b & 7);
   return (((s88 >> 1) & 56) + (s88 & 7)) | ( -(s88 & 0x88) >> 31);
}

File and Anti-Diagonal

or vice versa Anti-Diagonal and File

. . . | . . . .
. . . | . . . .
\ . . | . . . .
. b . | . . . .
. . \ | . . . .
. . . s . . . .
. . . a \ . . .
. . . | . \ . .

with

antidiagIndex := rankIndex + fileIndex;
\f  0  1  2  3  4  5  6  7
r_________________________
7 | 7  8  9 10 11 12 13 14
6 | 6  7  8  9 10 11 12 13
5 | 5  6  7  8  9 10 11 12
4 | 4  5  6  7  8  9 10 11
3 | 3  4  5  6  7  8  9 10
2 | 2  3  4  5  6  7  8  9
1 | 1  2  3  4  5  6  7  8
0 | 0  1  2  3  4  5  6  7

0x88 Math

fileIndex(s) := fileIndex(a);
rankIndex(s) := antidiagIndex(s) - fileIndex(s);
rankIndex(s) := rankIndex(b) + fileIndex(b) - fileIndex(a);

Because the intersection of any rank with any anti-diagonal may off the board, we rely on 0x88 math for a quick test:

s88 := 16*rankIndex(s) + fileIndex(s);
s88 := 16*(rankIndex(b) + fileIndex(b) - fileIndex(a)) + fileIndex(a);
s88 := 16*rankIndex(b) + 16*fileIndex(b) - 15*fileIndex(a);
if ( s88 & 0x88)
   intersection off board;
else
   sq := ((sq88 >> 1) & 56) + (sq88 & 7);

C-Source

/****************************************
 * return: intersection square (if any)
 *          of file of square a
 *          with anti-diagonal of square b
 *         -1 if no intersection exists
 ****************************************/
int intersectFileAnt(int a, int b) {
   int s88 = 2*(b & 56) + 16*(b & 7) - 15*(a & 7);
   return (((s88 >> 1) & 56) + (s88 & 7)) | ( -(s88 & 0x88) >> 31);
}

Diagonal and Anti-Diagonal

or vice versa Anti-Diagonal and Diagonal

. . . . . . . .
. . . . . . . /
\ . . . . . / .
. b . . . / . .
. . \ . / . . .
. . . s . . . .
. . a . \ . . .
. / . . . \ . .

with

diagonalIndex := rankIndex - fileIndex;
\f  0  1  2  3  4  5  6  7
r_________________________
7 | 7  6  5  4  3  2  1  0
6 | 6  5  4  3  2  1  0 -1
5 | 5  4  3  2  1  0 -1 -2
4 | 4  3  2  1  0 -1 -2 -3
3 | 3  2  1  0 -1 -2 -3 -4
2 | 2  1  0 -1 -2 -3 -4 -5
1 | 1  0 -1 -2 -3 -4 -5 -6
0 | 0 -1 -2 -3 -4 -5 -6 -7

and

antidiagIndex := rankIndex + fileIndex;
\f  0  1  2  3  4  5  6  7
r_________________________
7 | 7  8  9 10 11 12 13 14
6 | 6  7  8  9 10 11 12 13
5 | 5  6  7  8  9 10 11 12
4 | 4  5  6  7  8  9 10 11
3 | 3  4  5  6  7  8  9 10
2 | 2  3  4  5  6  7  8  9
1 | 1  2  3  4  5  6  7  8
0 | 0  1  2  3  4  5  6  7

0x88 Math

For same file and rank of intersection-point s:

rankIndex(s) - diagonalIndex(a) ==  antidiagIndex(b) - rankIndex(s);
fileIndex(s) + diagonalIndex(a) ==  antidiagIndex(b) - fileIndex(s);

and therefor

2*rankIndex(s) == antidiagIndex(b) + diagonalIndex(a);
2*fileIndex(s) == antidiagIndex(b) - diagonalIndex(a);

Because the intersection of any rank with any anti-diagonal may off the board, we rely on 0x88 math for a quick test:

s88   = 16*rankIndex(s) + fileIndex(s);

equation times two:

s88x2 = 16*2*rankIndex(s) + 2*fileIndex(s);
s88x2 = 16*(antidiagIndex(b) + diagonalIndex(a)) + (antidiagIndex(b) - diagonalIndex(a) );
s88x2 = 17*antidiagIndex(b) + 15*diagonalIndex(a);
if ( s88x2 & 0x111)
   intersection off board or empty;
else
   sq := ((sq882 >> 2) & 56) + ((sq88>>1) & 7);

Additionally, s88x2 becomes odd if a and b have different square colors, if s88x2 & 0x110 is true, the square is off the board. In both cases there is no intersection square, which can be combined by one test with 0x111. If AND 0x111 is false, we convert 0x88 coordinates to ordinary square coordinates, which might be done "speculative".

C-Source

/****************************************
 * return: intersection square (if any)
 *          of diagonal of square a
 *          with antidiagonal of square b
 *         -1 if no intersection exists
 ****************************************/
int intersectDiaAnt(int a, int b) {
   int s88x2 = 17*((b>>3) + (b & 7)) + 15*((a>>3) - (a & 7));
   return (((s88x2>>2)&56) + ((s88x2>>1)&7)) | ( -(s88x2&0x0111) >> 31);
}

External Links

Line-Line Intersection from Wolfram MathWorld
Line-line intersection from Wikipedia
Line (geometry) from Wikipedia
Linear equations from Wikipedia
Crossroads (culture) from Wikipedia
Sun Ra - Where Pathways Meet, from Lanquidity (1978), YouTube Video

References

^ Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website

What links here?

Page	Date Edited
0x88	Nov 28, 2016
Anti-Diagonals	Sep 2, 2012
Diagonals	Jan 16, 2013
Direction	Oct 6, 2016
Double Attack	Oct 22, 2014
Files	Nov 22, 2015
Intersection Squares	Oct 4, 2014
Move Generation	Jan 29, 2018
Ranks	Dec 15, 2008
Rays	Oct 20, 2016
Squares	Feb 15, 2015
Tactics	Jan 12, 2018
Vector Attacks	Dec 15, 2017

Up one Level

Knight Pattern

GerdIsenberg — Mon, 23 Feb 2015 19:45:51 GMT

Home * Board Representation * Bitboards * Knight Pattern

		Knight Pattern with Bitboards covers knight attacks of single or multiple knights, either by indexed pre-calculated tables or direct bitboard calculation, and the set wise determination of Knight fork target squares.
M. C. Escher, Horseman ^[1]

Knight Attacks

by Lookup

by Calculation

Multiple Knight Attacks

Knight Fill

Knight Forks

See also

Selected Publications

Knight Attacks

The Knight attacks the target squares independently from other pieces around. The compass rose of all eight attacking directions associated with the to - from square differences from an 8x8 board:

        noNoWe    noNoEa
            +15  +17
             |     |
noWeWe  +6 __|     |__+10  noEaEa
              \   /
               >0<
           __ /   \ __
soWeWe -10   |     |   -6  soEaEa
             |     |
            -17  -15
        soSoWe    soSoEa

by Lookup

The knight is specified by square index, likely from a bitscan of a piece-wise bitboard serialization of a knight bitboard from a standard board-definition, to index a table of pre-calculated knight-attacks:

U64 arrKnightAttacks[64];
 
U64 knightAttacks(enumSquare sq) {return arrKnightAttacks[sq];}

For instance a knight on d4

arrKnightAttacks[d4]
 . . . . . . . .
 . . . . . . . .
 . . 1 . 1 . . .
 . 1 . . . 1 . .
 . . . . . . . .
 . 1 . . . 1 . .
 . . 1 . 1 . . .
 . . . . . . . .

by Calculation

Similar to one step only of the four orthogonal and four diagonal directions,each of the eight knight directions is calculated by left or right shift with appropriate pre- or post shift mask, to avoid A- H-file wraps or vice versa. See also AVX2 Knight Attacks.

U64 noNoEa(U64 b) {return (b << 17) & notAFile ;}
U64 noEaEa(U64 b) {return (b << 10) & notABFile;}
U64 soEaEa(U64 b) {return (b >>  6) & notABFile;}
U64 soSoEa(U64 b) {return (b >> 15) & notAFile ;}
U64 noNoWe(U64 b) {return (b << 15) & notHFile ;}
U64 noWeWe(U64 b) {return (b <<  6) & notGHFile;}
U64 soWeWe(U64 b) {return (b >> 10) & notGHFile;}
U64 soSoWe(U64 b) {return (b >> 17) & notHFile ;}
 
U64 noNoEa(U64 b) {return (b & notHFile ) << 17;}
U64 noEaEa(U64 b) {return (b & notGHFile) << 10;}
U64 soEaEa(U64 b) {return (b & notGHFile) >>  6;}
U64 soSoEa(U64 b) {return (b & notHFile ) >> 15;}
U64 noNoWe(U64 b) {return (b & notAFile ) << 15;}
U64 noWeWe(U64 b) {return (b & notABFile) <<  6;}
U64 soWeWe(U64 b) {return (b & notABFile) >> 10;}
U64 soSoWe(U64 b) {return (b & notAFile ) >> 17;}

In almost the same manner as the three pawn directions, there is a unique source-target relationship. The difference is - we have up to eight pawns, but likely not more than two knights per side. Keeping eight disjoint knight directions is consistent to direction-wise fill approaches of other pieces with unique target-source relationship - but disjoint direction-wise knight targets are sparse populated and usually contain only up to two bits.

Multiple Knight Attacks

To initialize the KnightAttacks array one may use a routine with some kind of parallel prefix calculations, rather than the union of all eight directions:

U64 knightAttacks(U64 knights) {
   U64 west, east, attacks;
   east     = eastOne (knights);
   west     = westOne (knights);
   attacks  = (east|west) << 16;
   attacks |= (east|west) >> 16;
   east     = eastOne (east);
   west     = westOne (west);
   attacks |= (east|west) <<  8;
   attacks |= (east|west) >>  8;
   return attacks;
}

or to possibly gain some more parallelism:

U64 knightAttacks(U64 knights) {
   U64 l1 = (knights >> 1) & C64(0x7f7f7f7f7f7f7f7f);
   U64 l2 = (knights >> 2) & C64(0x3f3f3f3f3f3f3f3f);
   U64 r1 = (knights << 1) & C64(0xfefefefefefefefe);
   U64 r2 = (knights << 2) & C64(0xfcfcfcfcfcfcfcfc);
   U64 h1 = l1 | r1;
   U64 h2 = l2 | r2;
   return (h1<<16) | (h1>>16) | (h2<<8) | (h2>>8);
}

If we pass multiple knights set-wise, attacks of some squares may be caused by different knights. Feeding back (safe) target sets, the routine may used to get sets of squares, knights may reach in two or more moves. For instance in late pawn-knight endings whether a knight may catch a passer.

Knight Fill

A fill cycle for a fill algorithm is the union of the attack set with the knights itself:

U64 knightFill(U64 knights) {return knightAttacks(knights) | knights;}

for instance applied six times on the otherwise empty board:

                  1. Fill            2. Fill            3. Fill
. . . . . . . .   . . . . . . . .   . . . . . . . .   . . . . . . . .
. . . . . . . .   . . . . . . . .   . . . . . . . .   . 1 . 1 . . . .
. . . . . . . .   . . . . . . . .   . . . . . . . .   1 . 1 . 1 . . .
. . . . . . . .   . . . . . . . .   1 . 1 . . . . .   1 1 1 1 . 1 . .
. . . . . . . .   . . . . . . . .   . 1 . 1 . . . .   1 1 1 1 1 . 1 .
. . . . . . . .   . 1 . . . . . .   1 1 . . 1 . . .   1 1 . 1 1 1 . .
. . . . . . . .   . . 1 . . . . .   . . 1 1 . . . .   1 . 1 1 1 . 1 .
1 . . . . . . .   1 . . . . . . .   1 . 1 . 1 . . .   1 1 1 1 1 1 . .
 
                  4. Fill            5. Fill            6. Fill
                  . 1 . 1 . 1 . .   1 1 1 1 1 1 1 .   1 1 1 1 1 1 1 1
                  1 1 1 1 1 . 1 .   1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 . 1   1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 .   1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 .   1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 .   1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1

Knight Forks

A common knight pattern is the knight fork. Targets are heavy pieces - king, queen and rooks, hanging pieces, or even undefended pawns. A royal knight fork or "family" check, winning the queen is most important. Otherwise one may loop over all possible pieces, to get the knight-attacks by lookup and to intersect all combinations of attack-squares. A loop- and branch-less solution to get potential fork-attack squares is to union all intersections of all direction attacks, as explained in greater one sets:

U64 forkTargetSquare(U64 targets) {
   U64 west, east, attak, forks;
   east   = eastOne (targets);
   west   = westOne (targets);
   attak  =  east << 16;
   forks  = (west << 16) & attak;
   attak |=  west << 16;
   forks |= (east >> 16) & attak;
   attak |=  east >> 16;
   forks |= (west >> 16) & attak;
   attak |=  west >> 16;
   east   = eastOne (east);
   west   = westOne (west);
   forks |= (east <<  8) & attak;
   attak |=  east <<  8;
   forks |= (west <<  8) & attak;
   attak |=  west <<  8;
   forks |= (east >>  8) & attak;
   attak |=  east >>  8;
   forks |= (west >>  8) & attak;
   return forks;
}

The intersection of those targets with squares not occupied by own pieces or attacked by opponent pawns and knights, but attacked by own knight(s) leaves a move target set with some forced properties.

Selected Publications

Martin Gardner (1967). Problems that are Built on the Knight's Tour in Chess. Scientific American, Vol. 130
Noam D. Elkies, Richard P. Stanley (2003). The Mathematical Knight. The Mathematical Intelligencer, Vol. 25, No. 1, pdf
Ben Hill (2004). Knight’s Tours. pdf
Philip Hingston, Graham Kendall (2005). Ant Colonies Discover Knight's Tours. AI 2004, Lecture Notes in Computer Science 3339
Philip Hingston, Graham Kendall (2005). Enumerating knight's tours using an ant colony algorithm. CEC 2005

Forum Posts

Symbolic: From bitboards to ideas by Steven Edwards, CCC, March 13, 2004 » Symbolic
knight's multiple atacks by Daniel Anulliero, CCC, January 27, 2015

External Links

Knight's tour from Wikipedia
Knight's Tour Notes compiled by George Jelliss
Knight's Tour - from Wolfram MathWorld
Longest uncrossed knight's path from Wikipedia
László Lindner's knight wheel by Frederic Friedel from ChessBase Puzzle
Knight's Tour from Research Reflections by Graham Kendall, January 18, 2014
Knight's Tour - Numberphile, YouTube Video

References

^ View facsimile print from M.C. Escher - 16 Facsimile Prints

What links here?

Page	Date Edited
AVX2	Aug 8, 2017
Bitboards	Nov 14, 2017
Blockers and Beyond	Mar 21, 2014
Chunking	Jun 12, 2017
Combination	Oct 25, 2016
Decoying	Jan 12, 2015
DirGolem	Jun 5, 2016
Double Attack	Oct 22, 2014
Fill Algorithms	Nov 6, 2013
General Setwise Operations	Feb 25, 2018
Graham Kendall	May 26, 2015
Hanging Piece	Jan 14, 2017
Jonathan Warkentin	Jun 29, 2014
Killer (NL)	Dec 15, 2017
Knight Pattern	Feb 23, 2015
Knight-Distance	Oct 20, 2013
Knowledge	Jul 22, 2017
Loose Piece	Jan 10, 2015
Mathematician	Apr 9, 2018
Pattern Recognition	Sep 8, 2017
Pieces versus Directions	Oct 6, 2016
Square Attacked By	Jan 20, 2018
Symbolic	May 8, 2017
Tactics	Jan 12, 2018
Zillions of Games	May 29, 2017

Up one Level

Leaf Node

GerdIsenberg — Sat, 04 Mar 2017 21:33:42 GMT

Home * Search * Node * Leaf Node

		Leaf nodes are nodes with no further successors. They are either terminal nodes or nodes where the desired depth from the root is accomplished and which has been assigned a heuristic value as an "educated guess" to an approximate of a terminal value. Each search tree has at least one leaf node.
M. C. Escher, Dewdrop, 1948 ^[1]

External Links

Leaf node from Wikipedia
Klaus Schulze - The Wisdom of the Leaves, Contemporary Works II (2002), YouTube Video

References

^ Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website

What links here?

Page	Date Edited
Alexander Szabo	Nov 10, 2012
Alpha-Beta	Jan 28, 2018
APHID	Jun 26, 2017
Blockage Detection	Oct 19, 2017
Branching Factor	Jun 28, 2017
ChessBrain	Jun 28, 2017
Conspiracy Numbers	Dec 29, 2017
Constellation	Oct 2, 2016
Daniel Edwards	Jan 19, 2018
Depth-First	Jun 25, 2016
Dictionary	Aug 24, 2017
Enhanced Transposition Cutoff	May 19, 2017
Falcon	Sep 2, 2016
Fixafan	Oct 2, 2015
Francesca	Jan 7, 2016
Frontier Nodes	Dec 29, 2013
Gerhard Trippen	Jun 8, 2015
Gromit	Apr 5, 2017
Horizon Node	Sep 13, 2016
Interior Node	Aug 6, 2012
Kaissa	Apr 9, 2018
Lachex	Jan 7, 2016
Leaf Node	Mar 4, 2017
Leftmost Node	May 28, 2011
MCαβ	Jan 28, 2018
Michael Levin	Sep 10, 2013
Monte-Carlo Tree Search	Apr 26, 2018
Movei	Jan 7, 2016
Node	Jul 20, 2015
Node Types	Oct 22, 2017
Nodes per second	Feb 28, 2018
Nuchess	Apr 3, 2017
Odd-Even Effect	May 19, 2017
Oracle	Sep 4, 2016
Ostrich	Dec 28, 2017
Perft	Sep 26, 2017
Perft Results	Feb 10, 2018
Playing Strength	Mar 31, 2018
Point Value by Regression Analysis	Aug 26, 2017
Quiescent Node	Feb 10, 2017
Richard P. Cochran	Mar 28, 2015
Score	Apr 14, 2018
Search Tree	Dec 23, 2016
Search with Random Leaf Values	Apr 23, 2018
Shu Yokoyama	Oct 25, 2017
Singular Extensions	Jan 9, 2018
SOMA	Mar 25, 2015
Super Constellation	Oct 1, 2016
TechMate	Aug 23, 2014
Temporal Difference Learning	Feb 20, 2018
Terminal Node	Nov 17, 2012
Timothy Hart	Aug 22, 2014
Ulysses	Nov 1, 2016

Up one Level

MTD(f)

GerdIsenberg — Mon, 17 Jul 2017 20:27:13 GMT

Home * Search * MTD(f)

		MTD(f), a search algorithm created by Aske Plaat and the short name for MTD(n, f), which stands for something like Memory-enhanced Test Driver with node n and value f. MTD is the name of a group of driver-algorithms that search minimax trees using null window alpha-beta with transposition table calls. In order to work, MTD(f) needs a first guess as to where the minimax value will turn out to be. The better than first guess is, the more efficient the algorithm will be, on average, since the better it is, the less passes the repeat-until loop will have to do to converge on the minimax value. If you feed MTD(f) the minimax value to start with, it will only do two passes, the bare minimum: one to find an upper bound of value x, and one to find a lower bound of the same value ^[1].
M. C. Escher, Ascending and Descending, 1960 ^[2]

Pascal Pseudo Code

C Pseudo Code

Pascal Pseudo Code

Original Pascal pseudo code by Aske Plaat:

function MTDF(root : node_type; f : integer; d : integer) : integer;
      g := f;
      upperbound := +INFINITY;
      lowerbound := -INFINITY;
      repeat
            if g == lowerbound then beta := g + 1 else beta := g;
            g := AlphaBetaWithMemory(root, beta - 1, beta, d);
            if g < beta then upperbound := g else lowerbound := g;
      until lowerbound >= upperbound;
      return g;

Typically, one would call MTD(f) in an iterative deepening framework, the first guess the value of the previous iteration:

function iterative_deepening(root : node_type) : integer;
 
      firstguess := 0;
      for d = 1 to MAX_SEARCH_DEPTH do
            firstguess := MTDF(root, firstguess, d);
            if times_up() then break;
      return firstguess;

C Pseudo Code

Slightly modified pseudo code in C:

int mtdf(int f, int depth) {
   int bound[2] = {-oo, +oo}; // lower, upper
   do {
      beta = f + (f == bound[0]);
      f = alphaBetaWithMemory(beta - 1, beta, depth);
      bound[f < beta] = f;
   } while (bound[0] < bound[1]);
   return f;
}

Publications

1994 ...

Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1994). A New Paradigm for Minimax Search. TR 94-18
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1996). Best-First Fixed-Depth Minimax Algorithms. pdf
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1996). An Algorithm Faster than NegaScout and SSS* in Practice. pdf from CiteSeerX
Aske Plaat (1997). MTD(f), A Minimax Algorithm Faster Than NegaScout. Internal Report, Erasmus University Rotterdam

2000 ...

Jacek Mańdziuk, Daniel Osman (2004). Alpha-Beta Search Enhancements with a Real-Value Game-State Evaluation Function. ICGA Journal, Vol. 27, No. 1, pdf
Kazutomo Shibahara, Nobuo Inui, Yoshiyuki Kotani (2005). Adaptive Strategies of MTD-f for Actual Games. CIG 2005, pdf

2010 ...

Jr-Chang Chen, I-Chen Wu, Wen-Jie Tseng, Bo-Han Lin, Chia-Hui Chang (2015). Job-Level Alpha-Beta Search. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 7, No. 1

Forum Posts

1997 ...

Tree search issues! by Magnus Heldestad, rgcc, May 26, 1997 » Enhanced Transposition Cutoff
Re: Tree search issues! by Robert Hyatt, rgcc, May 26, 1997
Re: Tree search issues! by Aske Plaat, rgcc, May 27, 1997

1998

New(?) search idea by Andrew Walker, CCC, January 21, 1998
Re: New(?) search idea by Don Dailey, CCC, January 22, 1998
MTD(f) (was Re: New(?) search idea.) by Stuart Cracraft, CCC, January 22, 1998
Re: New(?) search idea by Robert Hyatt, CCC, January 22, 1998 » Minimax Wall

1999

Re: CilkChess by Don Dailey, CCC, February 14, 1999 » CilkChess
Building the Principal Variation in MTD(f) searches by Andrew Williams, CCC, July 18, 1999 » Principal variation
MTD is a big win by Don Dailey, CCC, July 19, 1999
MTD(f) by Nicolas Carrasco, CCC, September 28, 1999

2000 ...

Getting a PV using MTD(f) by Tijs van Dam, CCC, February 08, 2000 » Principal variation
MTD(f) and PV by David Rasmussen, rgcc, March 09, 2000 » Principal variation

2001

MTD(f) and the PV by Adrian Jackson, rgcc, March 16, 2001 » Principal variation
Beating MTD(n,f) by Gian-Carlo Pascutto, CCC, June 05, 2001
MTD(f) and killer heuristics by Marcus Heidkamp, CCC, July 12, 2001 » Killer Heuristic
Performance of MTD(f) versus eval granularity? by Werner Mühlpfordt, CCC, November 01, 2001

2002

MTD(f) Problems by Oren Avraham, CCC, April 10, 2002
Re: MTD(f) Problems by Rudolf Huber, CCC, April 11, 2002
About False Fail Highs, professionals, and MTD searches by Gian-Carlo Pascutto, CCC, April 12, 2002 » Fail-High
Couple of chess programming questions by Eli Liang, CCC, September 10, 2002 » ProbCut, Evaluation, Bitboards, 0x88, Fractional Plies, Transposition Table
Re: Couple of chess programming questions - MDT and parallel by Scott Farrell, CCC, September 10, 2002 » Parallel Search
calculating the PV using MTD by Fabien Letouzey, CCC, September 11, 2002 » Principal variation
MTD: an observation and a question by Martin Fierz, CCC, September 11, 2002

2003

MTD(f), Quiscient Search, and hashing Quiscient nodes by Joel, CCC, January 19, 2003
MTD(f) and storing the PV by Tord Romstad, CCC, July 29, 2003
MTD, IID, fail-low, root-research by Juergen Wolf, CCC, August 14, 2003 » Internal Iterative Deepening, Fail-Low, Root
Re: MTD, IID, fail-low, root-research by Rudolf Huber, CCC, August 14, 2003
MTD(f) and hash table size by Tord Romstad, CCC, August 16, 2003
MTD(F) results by Anthony Cozzie, CCC, December 16, 2003
Re: MTD(F) results by Rudolf Huber, CCC, December 17, 2003

2004

QSearch() as PVS() ? by Matthias Gemuh, CCC, January 14, 2004
MTD(f) by Tord Romstad, CCC, January 14, 2004
Search behavior in a case of root fail high/low by Sergei S. Markoff, CCC, March 10, 2004 » Fail-High, Fail-Low, Root
mtd(f) and null move by Peter Alloysius, CCC March 11, 2004
Question for the MTD(f) experts by Dann Corbit, CCC, April 14, 2004
An MTD(f) question about NULL MOVE searching by Dann Corbit, CCC, July 16, 2004
MTD(f) by Stuart Cracraft, CCC, July 26, 2004
MTD Drivers by Tor Lattimore, CCC, August 10, 2004

2005 ...

MTD(f) by Tor Alexander Lattimore, CCC, June 15, 2005
Rybka uses PVS and not MTD(f). Its no Fruit-Clone by Chrilly Donninger, CCC December 12, 2005
MTD(f) versus Alpha-Beta by Harm Geert Muller, Winboard Forum, December 13, 2005
MTD(f) by Engin Üstün, CCC, December 17, 2005
MTD(f) and Wikipedia by Joachim Rang, CCC, January 19, 2006
MTD(f) experiences by Don Dailey, CCC, May 25, 2008

2010 ...

An Idea Of speeding up MTD-f by Pio Korinth, CCC, August 22, 2014
MTD-f: Extracting PV ? by Henk van den Belt, CCC, June 24, 2016
mtd(f) by stefano.c, FishCooking, August 7, 2016 » Stockfish

External Links

MTD(f) - A Minimax Algorithm faster than NegaScout by Aske Plaat
MTD(f) from Wikipedia
Jan Garbarek, Keith Jarrett, Palle Danielsson, Jon Christensen - Spiral Dance, 1974, YouTube Video

References

What links here?

Page	Date Edited
Algorithms	May 5, 2017
Alpha-Beta	Jan 28, 2018
Andrea Zinno	May 19, 2017
Andrew Williams	Jan 7, 2016
AnMon	Nov 17, 2017
Arie de Bruin	May 23, 2016
Aske Plaat	Jun 26, 2017
Bagatur	Sep 10, 2016
BBchess	Oct 30, 2011
Bernard Brioit	Jan 10, 2015
Best-First	Dec 29, 2017
Branching Factor	Jun 28, 2017
Centipawns	Aug 9, 2016
Chao Ma	Feb 6, 2017
Chia-Hui Chang	Jul 21, 2017
Christian Barreteau	Jan 8, 2016
Cilkchess	Jan 21, 2016
Cmcchess	Jun 19, 2015
Connect6	Jul 22, 2017
Daniel Osman	Nov 8, 2013
David Rasmussen	Dec 16, 2017
Debugging	Jan 20, 2018
Dictionary	Aug 24, 2017
Don Dailey	Dec 7, 2016
Enhanced Transposition Cutoff	May 19, 2017
Fabien Letouzey	Feb 5, 2018
Fail-High	Oct 22, 2017
Fail-Low	Jun 23, 2017
Fail-Soft	Jun 2, 2017
Ghost	Feb 2, 2018
Gian-Carlo Pascutto	Jan 16, 2018
Gothmog	Nov 28, 2013
Harm Geert Muller	Mar 31, 2018
Internal Iterative Deepening	Feb 5, 2018
Iterative Deepening	Jun 23, 2017
Joachim Rang	Mar 19, 2014
Joker IT	Sep 16, 2017
Judea Pearl	Jan 18, 2018
Killer Heuristic	Sep 14, 2017
Kiwi	Sep 2, 2016
KnightCap	Nov 6, 2016
Leftmost Node	May 28, 2011
Martin Fierz	Apr 26, 2018
Mathematician	Apr 9, 2018
Memory	Dec 8, 2017
MTD(f)	Jul 17, 2017
NegaC*	Dec 17, 2016
NegaScout	Jul 6, 2016
Null Move Pruning	Dec 2, 2017
Null Window	Nov 8, 2016
Occam	Jan 21, 2016
Parallel Search	Dec 30, 2017
ParSOS	Jan 7, 2016
Peter Aloysius Harjanto	Jul 21, 2015
PostModernist	Jan 7, 2016
Principal variation	Dec 4, 2017
Principal Variation Search	Oct 22, 2017
Rudolf Huber	Jan 7, 2016
Russell Reagan	Aug 31, 2013
Score	Apr 14, 2018
Scout	Jan 28, 2018
Search	Feb 1, 2018
SEE	Jan 14, 2013
Sergei Markoff	Mar 12, 2018
Small Potato	Feb 14, 2014
Smash	May 11, 2016
SOS	Apr 5, 2017
SSS* and Dual*	Jan 22, 2018
Stuart Cracraft	May 19, 2017
Sunfish	Jan 11, 2018
Tijs van Dam	Feb 27, 2017
Tor Lattimore	Jan 13, 2013
Transposition Table	Apr 19, 2018
Wim Pijls	May 23, 2016
Window	Jun 7, 2017

Up one level

Repetitions

GerdIsenberg — Tue, 16 Jan 2018 08:33:09 GMT

Home * Search * Repetitions

		Repetitions of positions may happen during game play and inside the search of a chess program due to reversible moves played from both sides, which might be nullified in one or multiple further reversible moves. The player to move may claim a draw if the same position occurs three times, or will occur after an intended move, in any order, with the same player to move. Two positions are considered same or equal, if all occupied squares and kind of pieces (not necessarily the same piece) they occupy are the same, the castling rights for both sides did not change, and no en passant capture was possible during the first occurrence, even if obviously not played.
M. C. Escher, Reptiles, 1943 ^[1]

Assigning Draw Score

Threefold repetition implies a position occurred thrice, that is repeated twice. When to score the position as a draw, however, is an entirely different matter. Most programs do this on the first repetition, no matter whether the first occurrence of the repeated position appears in the current search space, or not. Other programs consider that fact, they avoid cycles inside the current search tree to make it a directed acyclic graph (DAG), but allow a one-fold repetition, if the first occurrence appears in the game history before the current root. Anyway, to wait for the second repetition one has its pros and cons. The Repetition score is either zero or the contempt factor.

Rules

The rules of chess state a threefold repetition of a position gives the player to move the option to claim a draw, no matter whether the threefold repetition already occurred yet, or is about to occur after declaring the intended move in conjunction with the draw claim. The latter case is a bit tricky for computers, and is/was likely not strictly implemented in most programs or their user interfaces, since a draw message text or box appeared after the repetition occurs but no claim before. Since July 2014 a fivefold repetition is sufficient without any claim ^[2].

Fide Rule

^[3]

9.2 The game is drawn, upon a correct claim by the player having the move, when the same position, for at least the third time (not necessarily by a repetition of moves)

a) is about to appear, if he first writes his move on his scoresheet and declares to the arbiter his intention to make this move, or
b) has just appeared, and the player claiming the draw has the move.

Positions as in (a) and (b) are considered the same, if the same player has the move, pieces of the same kind and color occupy the same squares, and the possible moves of all the pieces of both players are the same. Positions are not the same if a pawn that could have been captured en passant can no longer in this manner be captured or if the right to castle has been changed temporarily or permanently.

Since July 01, 2014

9.6 If one or both of the following occur(s) then the game is drawn:

a) the same position has appeared, as in 9.2b, for at least five consecutive alternate moves by each player.
b) any consecutive series of 75 moves have been completed by each player without the movement of any pawn and without any capture. If the last move resulted in checkmate, that shall take precedence.

Former Rule

A former (German) rule, was believed to be sufficient to make the game of chess finite ^[4] :

A chess game ends with a draw if a sequence of moves - with all pieces in exactly the same positions - is played three times successively.

was proved not sufficient by Max Euwe in 1929 by applying the Prouhet–Thue–Morse Sequence ^[5] , i. e. with following move indices ^[6] :

0:   Nb1-c3   Nb8-c6   Nc3-b1   Nc6-b8
1:   Ng1-f3   Ng8-f6   Nf3-g1   Nf6-g8

Euwe's prove was the reason, two other rules in force each of which guarantees chess to be a finite game, threefold repetition of positions and the fifty-move rule.

Repetition of Positions

By position we mean the location of all the pieces on the Chessboard as well as castling rights and en passant status. Since the rule speaks about the piece position, and not their identity (i.e. artificially constructed repeated position where the rooks of one player changed places still would be a draw), repetition may be detected by using the Zobrist- or BCH signatures of the position.

Transposition Table

One possible implementation was used by Ken Thompson in Belle, who told Bruce Moreland that he detected repetitions by using the transposition hash table, as follows ^[7] :

The idea is to set an "open" flag in the position's transposition table element when the hash table is probed. This flag stays set until the position is no longer being searched, meaning when the search function returns a value for that position.

At any given time, the only nodes that are "open" are nodes that are in the game history, or are in the current line in the tree search, so if the hash table probe encounters an open node, it must be because the current position has occurred somewhere before

This has the advantage that it uses data structures that are already present in the typical chess program, but there are a few problems with this idea. The hash table element must be written when a node is entered, so an "always replace" scheme must be used. This isn't a problem for Thompson, since his scheme involves using an "always replace" table, but other implementations might not use this kind of replacement scheme. Another problem is that there can be hash table entry collisions, and they must be dealt with. I am not talking about hash key collisions which occur when two positions map to the same 64-bit key, I'm talking about when two particular positions want to share the same hash table element, which should be pretty common. If two open nodes that want to share the same hash element, it's not immediately obvious what to do, other than not detect repetitions on the second one. Perhaps this problem could be dealt with via a re-hashing scheme, but this seems like an annoying thing to add in order to support functionality that isn't central to what the transposition table should be doing. A final problem is that it is hard to figure out how to adapt this to a multiprocessor search where there might be several search threads accessing the same hash table. When an open node is encountered, it might not indicate a repetition at all, since it could belong to a line being searched by another processor. This problem sounds complicated to solve.

List of Keys

Most programs use an array or list of Zobrist- or BCH-keys and compare the current signature with keys 4, 6, 8 and so on plies along the actual variation. This is usually quite cheap, since testing often does not require looking through the entire list, since captures and pawn moves, that reset the halfmove clock for the purpose of enforcing fifty-move rule are known to make a repetition impossible. Since each thread or process may own its own copy of the game-record, this approach has also some merits in parallel search implementations.

John Stanback about his implementation in Zarkov ^[8]:

In Zarkov I simply keep 32 bits of hash for each move in the game history, whether it has actually occurred on the board or during the current search. I also have a variable that contains the ply at which the last irreversible move occurred. At each node in the search, including quiescence, if the current ply is at least 4 plies beyond the last irreversible move I test the current hash value against those for each position in the game history (for the current side to move only) back to the last irreversible move and count the number of matches (repetitions). If the count is 2, then this is the third repetition and a draw score is returned. If the count is 1 and the current_ply > root_ply+2 then a draw score is also returned. This avoids problems that can occur if the program thinks that a move at the root leads to a draw (due to a single repetition) when the opponent may vary, but it also lets the program treat repeated positions in the search as draws which helps a lot. Since most positions in a search are less than 4 plies beyond the last irreversible move the repetition() function is rarely called and the performance hit for detecting repetitions is negligible.

Dedicated Hash Table

Some programs, like Gerbil or Rookie use a separate small hash table, actually an implementation of a Bloom filter revealed by Ronald de Man as mentioned by Marcel van Kervinck in his thesis The design and implementation of the Rookie 2.0 Chess Playing Program ^[9]:

It is tempting to use the transposition table to help detecting repeated positions. However, overloaded transposition tables can lose entries. So we choose something else ^[10]^[11] : a dedicated, small, repetition hash table. This tables has 2^14 one-byte entries that are initially zero (totaling 16KB). When entering a new position, the low 14 bits of the hash-key are used to index the table and bump up its value by one. The value is restored after unmaking the move. When entering a node and its value is found to be non-zero already, we know there could be a cycle, which we verify by tracing back the actual variation. The repetition table is large enough to sufficiently reduce the number of false hits and this vaporizes the costs of futile back-traces.

Repetition of Moves

An alternative, pragmatical approach based on repetitions of moves was proposed by Vladan Vučković and Đorđe Vidanović in 2004, as implemented in Axon ^[12] and discussed in CCC ^[13] ^[14].

The algorithm needs a move list containing the game record including the variation actually searched, 16-bit entries with origin and target square, and a flag whether a move is irreversible, as only information required. Starting with the last move made, the list is scanned backwards as long there are reversible moves. A local concatenating list of up to 24 entries (one entry for each piece able to make reversible moves) is used to determine cycles per piece, where consecutive moves on their target squares are merged to one "pseudo" move, using the earliest origin and the latest target square. If all distinct white and black moving pieces in the chain list contain equal from- and to coordinates, all cycles of moves are closed and a move repetition is detected. This is how the algorithm as given in the paper in 8086 assembly looks in pseudo C++, square coordinates are offset from a 12*12 mailbox approach, so that empty entries have no valid square index.

bool repetition(SMove *pVariant) {
   SMove chainList[24], m;
   short c = 0, i;
 
   for (i=0; i < 24; ++i) {
      chainList[i].setEmpty();
   }
 
l: m = *pVariant--; /* fetch move and decrement move list pointer */
   if ( m.isReversible() ) { 
      /* lookup chain list for from-coordinate that match current to coordinate */
      for (i=0; i < 24; ++i) {
         if ( m.to == chainList[i].from ) {
            if ( m.from == chainList[i].to ) {
              if ( --c == 0 )
                  return true; /* repetition detected */
               chainList[i].setEmpty();
               goto l;
            } 
            chainList[i].from = m.from; /* concatenate moves */
            goto l;
         }
      }
      /* lookup for next empty slot, to add the current move in the chain list */
      for (i=0; i < 24; ++i) {
         if ( chainList[i].isEmpty() ) {
            chainList[i] = m;
            ++c;
            goto l;
         }
      }
   }
   return false;
}

Publications

1929

Max Euwe (1929). Mengentheoretische Betrachtungen über das Schachspiel. Proc. Konin. Akad. Wetenschappen (Amsterdam)

1980 ...

Murray Campbell (1985). The graph-history interaction: on ignoring position history. Computer Science Department, Carnegie Mellon University, Proceedings of the 1985 ACM annual conference, pdf
Harry Nelson, Robert Hyatt (1988). The Draw Heuristic of Cray Blitz. ICCA Journal, Vol. 11, No. 1 » Cray Blitz

1990 ...

Dennis Breuker, Jaap van den Herik, Jos Uiterwijk, Victor Allis (1999). A Solution to the GHI Problem for Best-First Search. CG 1998 » Graph History Interaction, Best-First

2000 ...

Thomas Lincke (2002). Exploring the Computational Limits of Large Exhaustive Search Problems. Ph.D thesis, ETH Zurich, pdf, ^[15] Chapter 4.3 Cycles
Vladan Vučković, Đorđe Vidanović (2004). A New Approach to Draw Detection by Move Repetition in Computer Chess Programming. CoRR arXiv:cs/0406038 ^[16] ^[17]
Akihiro Kishimoto, Martin Müller (2004). A General Solution to the Graph History Interaction Problem. AAAI National Conference, pdf
Akihiro Kishimoto (2005). Correct and Efficient Search Algorithms in the Presence of Repetitions. Ph.D. thesis, University of Alberta, Received the 2005 ChessBase Best-Publication Award, pdf » Proof-Number Search
Akihiro Kishimoto, Martin Müller (2005). A Solution to the GHI Problem for Depth-First Proof-Number Search. 7th Joint Conference on Information Sciences (JCIS2003), pp. 489 - 492, pdf » Graph History Interaction
Daniel Andersson (2009). Perfect-Information Games with Cycles. Ph.D. thesis, Aarhus University, advisor Peter Bro Miltersen, pdf

2010 ...

Marcel van Kervinck (2013). A fast software-based method for upcoming cycle detection in search trees. pdf preview ^[18]

Forum Posts

1990 ...

Repetition detection w/hash tables by Bruce Moreland, rec.games.chess, August 14, 1993

1995 ...

Draw by Repetition Code by cmayer, rgcc, December 31, 1996
Repetitions in Crafty by Martin Borriss, rgcc, January 30, 1997 » Crafty
Perpetual check by Ian Kennedy, rgcc, May 19, 1997
Handling of repetition (draw) in transposition table by Bjarke Dahl Ebert, rgcc, June 9, 1997
triple repetition by Daniel Kang, rgcc, October 26, 1997
draw by repetition and hash tables by Werner Inmann, CCC, July 24, 1998
Problem with draws by rep and hash table by James Robertson, CCC, October 07, 1999

2000 ...

Detecting three-fold repetition? by Tom Kerrigan, CCC, July 17, 2000
Re: Detecting three-fold repetition? by John Stanback, CCC, July 17, 2000 » SCP Repetition detection

2001

The Old way to detect 3fold repetition (help needed) by Gianluigi Masciulli, CCC, March 26, 2001
"Don't trust draw score" <=Is it true? by Teerapong Tovirat, CCC, August 08, 2001 » Transposition Table, Path-Dependency

2002

Detecting Draws using a Small Hash Table? by Steve Maughan, CCC, February 20, 2002
3 fold repetiton (Seacher v Postmodernist) by Frank Phillips, CCC, March 02, 2002
A new(?) technique to recognize draws by Heiner Marxen, CCC, June 01, 2002 » Perpetual Check, Corresponding Squares
Repetitions: is this code correct? by Vladimir Medvedev, CCC, July 12, 2002

2003

Draw claims by Thomas Mayer, CCC, June 17, 2003
In computer games 3-fold repetition should be AUTOMATICALLY draw! by Jouni Uski, CCC, November 30, 2003

2004

perpetual check recognition by Andreas Herrmann, CCC, January 30, 2004
A New Approach to Draw Detection by Move Repetition by Gian-Carlo Pascutto, CCC, July 29, 2004
Draw Detection by Move Repetition Procedure - Comments by Đorđe Vidanović, CCC, August 01, 2004
How to handle the first repetition correctly? (long) by Sven Schüle, Winboard Forum, August 10, 2004
Repetition Detection by Renze Steenhuisen, CCC, December 01, 2004
Perpetual check by Alessandro Scotti, Winboard Forum, December 03, 2004

2005 ...

When to claim repetition and 50 move draws? by Peter Hughes, Winboard Forum, March 26, 2005
draw by repetition by Harm Geert Muller, Winboard Forum, November 21, 2005

2007

Handling 3-rep/50-move in hash tables by Pradu Kannan, Winboard Forum, February 19, 2007
avoidrep-pruning by Gerd Isenberg, CCC, May 15, 2007 » Pruning

2008

Problem with Transposition Table and Repitition-Draw by Oliver Brausch, CCC, January 11, 2008 » Transposition Table
Again, rep-draws (and score aging) by Harm Geert Muller, Winboard Forum, January 28, 2008
Repetition detection question by Robert Hyatt, CCC, January 28, 2008
Repetition detection structure by Mathieu Pagé, CCC, February 23, 2008
Semi-Path Dependent Hashing: a semi-useless idea by Zach Wegner, CCC, May 24, 2008
Repetition Detection by Colin, CCC, August 13, 2008
When and how to return a draw evaluation? by Mathieu Pagé, CCC, August 26, 2008 » Draw
Draw by repetition when mate is possible by Mathieu Pagé, CCC, December 30, 2008 » Checkmate

2009

wrong draw claim or right? by Will Singleton, CCC, December 03, 2009
Stupid Extension Problem/Question by John Merlino, CCC, December 23, 2009 » Extensions

2010 ...

Repetition Detection Without Hashing by Levi Aho, CCC, February 13, 2010
nullmove and repetitive draw detection by Edward Yu, CCC, June 20, 2010 » Null Move Pruning
bizarre repetition detection issue by Robert Hyatt, CCC, November 04, 2010

2011

Repetitions/50 moves and TT by Sergei Markoff, CCC, September 13, 2011
repetition detection by Edmund Moshammer, CCC, October 29, 2011

2012

Draw by 3-fold repetition? by Andy Duplain, CCC, January 06, 2012
Aquarium IDEA, repetitions, and minimax over cycles by kevinfat, OpenChess Forum, September 17, 2012 » Aquarium
Why is this game not a draw? by Carlos Pagador, CCC, October 29, 2012
Re: Move Tables - explain as if I'm five by Karlo Bala Jr., CCC, November 05, 2012 » Repetitions in Belzebub
FIDE Rules by crystalclear, Winboard Forum, December 11, 2012

2013

Half Move Clock Confusion by HumbleProgrammer, OpenChess Forum, January 10, 2013 » Fifty-move Rule, Halfmove Clock
Repetition check by Harm Geert Muller, CCC, March 29, 2013
Upcoming repetition detection by Marcel van Kervinck, OpenChess Forum, April 06, 2013
Stockfish bug by Steven Atkinson, CCC, May 30, 2013 » Stockfish
Repetition check by Harm Geert Muller, CCC, July 20, 2013
UCI protocol issue by Jon Dart, CCC, July 27, 2013 » UCI
ep and castle rights hashing by Natale Galioto, CCC, September 15, 2013 » Castling rights, En passant, Transposition Table

2014

Two fold repetition rule by Michel Van den Bergh, CCC, January 22, 2014
FIDE's new rules for chess by Mark Lefler, CCC, July 20, 2014

2015 ...

Using TT for detecting repetitions by thevinenator, OpenChess Forum, August 18, 2015

2016

Simple triple repetition handler by Stefano Gemma, CCC, February 21, 2016
How to test 3rd repetition rule? by Luis Babboni, CCC, April 12, 2016
This should be in the wiki by Steven Edwards, CCC, April 13, 2016
3rd repetition, a case where not cause castle rights... but by Luis Babboni, CCC, April 14, 2016 » Castling rights
Triple Repitition: Is this considered a repitition or not? by Jayakiran Akurathi, CCC, May 07, 2016 » En passant
Repetitions in the Search Tree by Jayakiran Akurathi, CCC, May 29, 2016
Syzygy and draw by repetition by Jon Dart, CCC, July 22, 2016 » Syzygy Bases
perpetual check position by Erin Dame, CCC, August 16, 2016 » Perpetual Check
Hashed repetition table by J. Wesley Cleveland, CCC, September 04, 2016 » Repetition Hash Table
transposition tables and three-fold repetition by Erin Dame, CCC, September 10, 2016 » Transposition Table
The new chess rules (5-fold repetition and 75-move draw) by Lyudmil Antonov, FishCooking, November 29, 2016 » Stockfish, Fifty-move Rule

2017

Have engines updated for fide 2014 draw rules? by Norm Pollock, CCC, January 28, 2017
Reporting a draw in UCI by Vince Sempronio, CCC, May 05, 2017 » Draw, UCI

2018

3-fold repetition and cutechess-cli by Lars Mathiesen, CCC, January 14, 2018 » En passant

External Links

Cycle detection (graph theory) from Wikipedia
Cycle detection from Wikipedia
Repetition Detection from Bruce Moreland's Programming Topics
Threefold repetition from Wikipedia
Perpetual check from Wikipedia
Fide Handbook - E.I.01A. Laws of Chess
A Chess Firewall at Zero? by Ken Regan, Gödel's Lost Letter and P=NP, January 21, 2016
Agnes Obel - It's Happening Again (2016), BBC 6 Music Live Room, YouTube Video
featuring Kristina Koropecki, Charlotte Danhier, Catherine De Biasio

References

^ Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website
^ FIDE's new rules for chess by Mark Lefler, CCC, July 20, 2014
^ Fide Handbook - E.I.01A. Laws of Chess
^ Mathematical Problems - Max Euwe's sequence by Manfred Börgens
^ Max Euwe (1929). Mengentheoretische Betrachtungen über das Schachspiel, Proc. Konin. Akad. Wetenschappen (Amsterdam)
^ Mathematical Problems - Max Euwe's sequence - Solution by Manfred Börgens
^ Repetition Detection from Bruce Moreland's Programming Topics
^ Draw by Repetition Code, post 4 by John Stanback, rgcc, December 31, 1996
^ Marcel van Kervinck (2002). The design and implementation of the Rookie 2.0 Chess Playing Program. Masters Thesis, pdf
^ Courtesy Ronald de Man for revealing this implementation trick
^ Re: triple repetition by Ronald de Man, rgcc, October 27, 1997
^ Vladan Vučković, Đorđe Vidanović (2004). A New Approach to Draw Detection by Move Repetition in Computer Chess Programming. CoRR arXiv:cs/0406038
^ A New Approach to Draw Detection by Move Repetition by Gian-Carlo Pascutto, CCC, July 29, 2004
^ Draw Detection by Move Repetition Procedure - Comments by Đorđe Vidanović, CCC, August 01, 2004
^ Re: Aquarium IDEA, repetitions, and minimax over cycles by syzygy, OpenChess Forum, September 22, 2012
^ A New Approach to Draw Detection by Move Repetition by Gian-Carlo Pascutto, CCC, July 29, 2004
^ Draw Detection by Move Repetition Procedure - Comments by Đorđe Vidanović, CCC, August 01, 2004
^ Upcoming repetition detection by Marcel van Kervinck, OpenChess Forum, April 06, 2013

What links here?

Page	Date Edited
Abyss	Aug 5, 2017
ACM 1973	Jan 19, 2018
Alessandro Scotti	Feb 27, 2014
AlphaZero	Feb 10, 2018
Andreas Herrmann	Nov 7, 2014
Aquarium	Dec 4, 2016
Asterisk	Mar 24, 2016
Awari	Feb 14, 2017
Axon	Jul 14, 2013
Belzebub	Oct 20, 2015
BlackBishop	Nov 7, 2014
Bruce Moreland	Jan 20, 2016
Buzz	Jun 22, 2016
Castling rights	Jan 7, 2017
Charly	Jan 10, 2013
Check	Feb 1, 2018
Checkmate	Apr 13, 2018
Chess for Android	Mar 1, 2018
Chess Game	Mar 28, 2017
Chess Position	Sep 10, 2017
ChessV	Jan 21, 2018
Chest	Mar 3, 2015
Chinese Chess	Jan 16, 2018
Coiled	Mar 12, 2017
Contempt Factor	Mar 10, 2018
Crafty	Jan 28, 2018
Dartmouth CP	Jan 19, 2018
DelphiMax	Apr 3, 2013
Djinn	Feb 8, 2016
Donna	Aug 17, 2017
Dragon FR	Sep 9, 2016
Draw	Apr 14, 2018
Draw Evaluation	Mar 12, 2018
Dynamic Tree Splitting	Apr 10, 2017
Edmund Moshammer	Sep 23, 2017
En passant	Jan 16, 2018
Endgame Tablebases	Mar 6, 2018
Enhanced Transposition Cutoff	May 19, 2017
Erin Dame	Dec 2, 2017
Evaluation Overlap	Jul 19, 2016
Extensions	Apr 19, 2018
Ferret	Jan 7, 2016
Fidelity	Jan 7, 2016
Fifty-move Rule	Aug 9, 2017
Fischer-Schneider	Nov 23, 2016
Fortress	Feb 1, 2018
Frank Phillips	Sep 26, 2016
Getting Started	Jan 20, 2014
Gianluigi Masciulli	May 18, 2017
Graph History Interaction	Oct 16, 2017
Halfmove Clock	Aug 9, 2017
Harm Geert Muller	Mar 31, 2018
Hash Table	Jan 1, 2018
Heiner Marxen	Apr 19, 2014
Ian Kennedy	Nov 7, 2016
Incremental Updates	Sep 6, 2017
Irreversible Moves	Jan 25, 2014
Iteration	May 5, 2017
Jan Renze Steenhuisen	Sep 10, 2017
Johannes Zwanzger	Jan 7, 2016
John Stanback	Dec 7, 2016
Jon Dart	Dec 17, 2017
Jouni Uski	Sep 28, 2017
Kaissa	Apr 9, 2018
Knowledge	Jul 22, 2017
Little Rook Chess	Sep 1, 2015
Lyudmil Antonov	Aug 31, 2017
Marcel van Kervinck	Dec 6, 2017
Mathieu Pagé	Feb 14, 2018
Max Euwe	Oct 10, 2015
Michael Gherrity	May 8, 2015
Michel Van den Bergh	Mar 10, 2018
Move List	Jul 19, 2017
Noah Weninger	Aug 13, 2017
Null Move Pruning	Dec 2, 2017
OliThink	May 19, 2017
Oliver Brausch	May 19, 2017
Path-Dependency	Oct 16, 2017
Pawn Push	Mar 27, 2010
Peasant	May 21, 2015
Perft	Sep 26, 2017
Pradu Kannan	Aug 3, 2015
Proof-number search	Jan 22, 2018
Pruning	Jan 1, 2018
Psi Chess	Aug 1, 2016
python-chess	Nov 4, 2017
Repetitions	Jan 16, 2018
Requiem	Feb 5, 2018
Reversible Moves	Mar 13, 2010
Rex	Jan 7, 2016
Ronald de Man	Nov 20, 2017
Rookie	Jan 7, 2016
Score	Apr 14, 2018
SCP	Jun 16, 2016
Search	Feb 1, 2018
Search Tree	Dec 23, 2016
Search with Random Leaf Values	Apr 23, 2018
Searcher	Sep 26, 2016
Sergei Markoff	Mar 12, 2018
Sierżant	Apr 15, 2014
SPOC	Jun 21, 2017
Stalemate	Feb 21, 2018
Stockfish	Apr 7, 2018
Supra	Jul 24, 2016
Surprise	Sep 20, 2016
Sven Schüle	Sep 20, 2016
Syzygy Bases	Apr 19, 2018
Teerapong Tovirat	Oct 21, 2014
Tell	Jan 12, 2018
Terminal Node	Nov 17, 2012
Test-Positions	Feb 25, 2018
Transposition	Jun 8, 2015
Transposition Table	Apr 19, 2018
TSCP	Feb 5, 2016
UCI	Mar 4, 2018
Vice	Mar 8, 2016
Vladimir Medvedev	Jul 22, 2016
WCCC 2003	Apr 2, 2017
WCCC 2017	Dec 31, 2017
Will Singleton	Mar 6, 2015
Winglet to include	Apr 25, 2015
Witz	Nov 14, 2017
WMCCC 1990	Oct 27, 2016
Y!	Sep 10, 2017
Zach Wegner	Jan 7, 2016
Zarkov	Feb 26, 2018
Zurichess	Mar 12, 2018
Đorđe Vidanović	Feb 20, 2017

Up one Level

Rotated Bitboards

GerdIsenberg — Tue, 07 Mar 2017 20:56:09 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Rotated Bitboards

		Rotated Bitboards, a bitboard move generation technique coined by Robert Hyatt ^[1], and later by Ernst A. Heinz ^[2] and Peter Gillgasch from the DarkThought team. This variation uses rotated copies of the occupancy in order to place bits along a file, diagonal or anti-diagonal in adjacent bits. Because of this, these bits can be easily extracted to obtain a dense occupancy map for a rank, file, diagonal, and anti-diagonal. These are used, along with the square of the sliding piece, to lookup a bitboard, containing attacks, in an array. While the attack generation per line is more or less only one memory lookup, the incremental update of the occupancy during make and unmake move becomes more expensive, since beside the usual occupied bitboard there are three more rotated bitboards to update, including additional mapping from square coordinates to the rotated indices.
M. C. Escher, Curl-up, 1951 ^[3]

An Example

Square Mapping

by Hyatt

by Gillgasch and Heinz

An Example

As example file-attacks of rook a5 with occupancy along the a-file. The 90-degree rotated bitboard has consecutive bits of that file along its 8th rank, which serves as an index to lookup the pre-calculated file-attacks:

  non-rotated           rotated             file_attacks[a5][rotated]
 ┌─┐                 ┌───────────────┐     ┌─┐
 │1│0 0 0 0 0 0 0    │1_0_0_1_R_0_1_1│════>│0│0 0 0 0 0 0 0
 │1│0 0 0 0 0 0 0     0 0 0 0 0 0 0 0      │1│0 0 0 0 0 0 0
 │0│0 0 0 0 0 0 0     0 0 0 0 0 0 0 0      │1│0 0 0 0 0 0 0
 │R│0 0 0 0 0 0 0     0 0 0 0 0 0 0 0      │0│0 0 0 0 0 0 0
 │1│0 0 0 0 0 0 0     0 0 0 0 0 0 0 0      │1│0 0 0 0 0 0 0
 │0│0 0 0 0 0 0 0     0 0 0 0 0 0 0 0      │0│0 0 0 0 0 0 0
 │0│0 0 0 0 0 0 0     0 0 0 0 0 0 0 0      │0│0 0 0 0 0 0 0
 │1│0 0 0 0 0 0 0     0 0 0 0 0 0 0 0      │0│0 0 0 0 0 0 0
 └─┘                                       └─┘

With a rook on the square marked 'R', an attack bitboard can be obtained with the array lookup file_attacks[R][10011011].

Square Mapping

Interesting is the different mapping of both approaches. Crafty seemed to use little endian square mapping but bit 0 (A1) is mentioned as MSB, while bit 63 (H8) is LSB. DarkThought uses big-endian file-mapping (H1 = 0).

by Hyatt

Crafty didn't use byte aligned diagonals, but visual rotation.

  normal chess board bitmap            occupied_squares 90 degrees
 
  A8 B8 C8 D8 E8 F8 G8 H8              H8 H7 H6 H5 H4 H3 H2 H1
  A7 B7 C7 D7 E7 F7 G7 H7              G8 G7 G6 G5 G4 G3 G2 G1
  A6 B6 C6 D6 E6 F6 G6 H6              F8 F7 F6 F5 F4 F3 F2 F1
  A5 B5 C5 D5 E5 F5 G5 H5              E8 E7 E6 E5 E4 E3 E2 E1
  A4 B4 C4 D4 E4 F4 G4 H4              D8 D7 D6 D5 D4 D3 D2 D1
  A3 B3 C3 D3 E3 F3 G3 H3              C8 C7 C6 C5 C4 C3 C2 C1
  A2 B2 C2 D2 E2 F2 G2 H2              B8 B7 B6 B5 B4 B3 B2 B1
  A1 B1 C1 D1 E1 F1 G1 H1              A8 A7 A6 A5 A4 A3 A2 A1
 
  original left 45                     original right 45
 
              H8                                 A8
            G8  H7                             A7  B8
          F8  G7  H6                         A6  B7  C8
        E8  F7  G6  H5                     A5  B6  C7  D8
      D8  E7  F6  G5  H4                 A4  B5  C6  D7  E8
    C8  D7  E6  F5  G4  H3             A3  B4  C5  D6  E7  F8
  B8  C7  D6  E5  F4  G3  H2         A2  B3  C4  D5  E6  F7  G8
A8  B7  C6  D5  E4  F3  G2  H1     A1  B2  C3  D4  E5  F6  G7  H8
  A7  B6  C5  D4  E3  F2  G1         B1  C2  D3  E4  F5  G6  H7
    A6  B5  C4  D3  E2  F1             C1  D2  E3  F4  G5  H6
      A5  B4  C3  D2  E1                 D1  E2  F3  G4  H5
        A4  B3  C2  D1                     E1  F2  G3  H4
          A3  B2  C1                         F1  G2  H3
            A2  B1                             G1  H2
              A1                                 H1
 
  original left 45                     original right 45
 
   G6 H5|F8 G7 H6|G8 H7|H8|            C7 D8|A6 B7 C8|A7 B8|A8|
   H3|D8 E7 F6 G5 H4|E8 F7             F8|A4 B5 C6 D7 E8|A5 B6
   F4 G3 H2|C8 D7 E6 F5 G4             E6 F7 G8|A3 B4 C5 D6 E7
   E4 F3 G2 H1|B8 C7 D6 E5             E5 F6 G7 H8|A2 B3 C4 D5
   D4 E3 F2 G1|A8 B7 C6 D5             E4 F5 G6 H7|A1 B2 C3 D4
   B5 C4 D3 E2 F1|A7 B6 C5             D2 E3 F4 G5 H6|B1 C2 D3
   C2 D1|A5 B4 C3 D2 E1|A6             G3 H4|D1 E2 F3 G4 H5|C1
  |A1|A2 B1|A3 B2 C1|A4 B3            |H1|G1 H2|F1 G2 H3|E1 F2

by Gillgasch and Heinz

DarkThought used a similar mapping as proposed in Pseudo Rotation by 45 degrees from Flipping Mirroring and Rotating, all diagonals are packed in file-aligned bytes.

Normal Bitboard.                       Flipped Bitboard.
#7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte       #7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte
a8 b8 c8 d8 e8 f8 g8 h8 #7             a8 a7 a6 a5 a4 a3 a2 a1 #7
a7 b7 c7 d7 e7 f7 g7 h7 #6             b8 b7 b6 b5 b4 b3 b2 b1 #6
a6 b6 c6 d6 e6 f6 g6 h6 #5             c8 c7 c6 c5 c4 c3 c2 c1 #5
a5 b5 c5 d5 e5 f5 g5 h5 #4             d8 d7 d6 d5 d4 d3 d2 d1 #4
a4 b4 c4 d4 e4 f4 g4 h4 #3             e8 e7 e6 e5 e4 e3 e2 e1 #3
a3 b3 c3 d3 e3 f3 g3 h3 #2             f8 f7 f6 f5 f4 f3 f2 f1 #2
a2 b2 c2 d2 e2 f2 g2 h2 #1             g8 g7 g6 g5 g4 g3 g2 g1 #1
a1 b1 c1 d1 e1 f1 g1 h1 #0             h8 h7 h6 h5 h4 h3 h2 h1 #0
 
 
A1-H8 Bitboard.                        A8-H1 Bitboard.
#7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte       #7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte
a8|b1 c2 d3 e4 f5 g6 h7 #7             a8 b7 c6 d5 e4 f3 g2 h1 #7
a7 b8|c1 d2 e3 f4 g5 h6 #6             a7 b6 c5 d4 e3 f2 g1|h8 #6
a6 b7 c8|d1 e2 f3 g4 h5 #5             a6 b5 c4 d3 e2 f1|g8 h7 #5
a5 b6 c7 d8|e1 f2 g3 h4 #4             a5 b4 c3 d2 e1|f8 g7 h6 #4
a4 b5 c6 d7 e8|f1 g2 h3 #3             a4 b3 c2 d1|e8 f7 g6 h5 #3
a3 b4 c5 d6 e7 f8|g1 h2 #2             a3 b2 c1|d8 e7 f6 g5 h4 #2
a2 b3 c4 d5 e6 f7 g8|h1 #1             a2 b1|c8 d7 e6 f5 g4 h3 #1
a1 b2 c3 d4 e5 f6 g7 h8|#0             a1|b8 c7 d6 e5 f4 g3 h2 #0

Quotes

From Robert Hyatt as repost to Urban Koistinen from 1997 ^[4] :

When I first thought about doing the rotated bitmap idea, I discussed it with Peter G. of the DarkThought team. He thought (as I did) that the idea was pretty neat and worth trying. I (from the first thought) had always planned on updating the rotated bitmaps by the following approach: I have a set of 64 bitmaps callet set_mask[n]. To set bit 32, I simply AND(bit-map,set_mask[32]). If I have a rotated-90 bitmap, then I also create a rotated-90 set_mask, and do this: AND(bit-map-R90,set_mask_R90[32]) and I am done. Peter didn't like this, and wanted to get rid of the extra memory load for the rotated set_mask variable. (note there are actually 4 of these loads needed, for each of the rotated bitmaps). So he thought about it a bit and found a cute mathematical transformation based on shifts, AND's and OR's (I won't give it here since it is his idea) that avoide needing the set_mask_Rxx masks (note that on some machines, even the set_mask itself is not needed. to set bit 32 you just start with "1" and shift it to the right position avoiding the memory load altogether. However, the effect of Peter's approach is to map diagonal bits on the real bitmap to adjacent bits in a "psuedo-rotated" bitmap, without needing the set_mask_R90 stuff at all. Is it better? I'm not sure. My tests on the P6 said NO. My tests on the alpha with big cache also said NO. Peter's tests on the machine he used said YES. It definitely takes more instructions to do what Peter is doing. On a machine with a huge memory latency, like the PC, my memory loading can be slow. But with a decent sized cache, the 64 words X 8 bytes per word (512 bytes) really tucks into a corner in cache and doesn't hurt at all, particularly since a cache hit on the P6 operates at CPU speed. The PII is a different case since the cache operates at 1/2 CPU speed, which might swing things in his favor. For the record, they are *close* under all cases. We are not talking 10% here...one might be 2% faster on one machine, the other 3% faster on another machine... But the "mapping" is really odd and would not let us just simply swap the L45 and R45 maps...

Table size

The initial implementations of rotated bitboards missed the outer square optimization and used the 8-bit occupied state with four lookup tables of 256*64*8 or 128-Kbyte each, thus 1/2 MByte in total. Roberto Waldteufel seemed first time mentioned the optimization trick 1998 ^[5], masking off the redundant outer occupancies for a four fold table reduction.

Of course one may use calculations similar to kindergarten bitboards to further shrink the tables. In fact, getting the occupancy state and pre-calculated information based on that are two different steps.

Publications

Ernst A. Heinz (1997). How DarkThought Plays Chess. ICCA Journal, Vol. 20, No. 3
Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4 ^[6] ^[7]
Borko Bošković, Sašo Greiner, Janez Brest, Viljem Žumer (2005). The Representation of Chess Game. Proceedings of the 27th International Conference on Information Technology Interfaces
Johannes Buchner (2005). Rotated bitboards in FUSc#. Free University of Berlin, pdf » FUSc#

Forum Posts

1995 ...

bitmaps of rotated boards by Urban Koistinen, gnu.chess, March 2, 1995
Re: Speed of Move Generator by Robert Hyatt, rgcc, August 17, 1995
Rotated bitboards - experiment and result by Robert Hyatt, rgcc, February 28, 1996
bitboard move generation question by Stuart Cracraft, rgcc, September 05, 1997
Bitboard Representation by Carl Tillotson, rgcc, September 18, 1997
Rotated bitboards by Mats Forsén, rgcc, October 29, 1997
Rotated bitboards by Peter Fendrich, CCC, April 22, 1998
Efficient Rotated Bitboard Representations by Roberto Waldteufel, CCC, October 28, 1998
Extracting information from rotated Bitboards by John Stoneham, CCC, November 02, 1998
Bitboard user's information request by Robert Hyatt, CCC, October 05, 1999

2000 ...

Nice Rotated-bitmaps Article by Hyatt in ICCA by Tom Likens, CCC, February 07, 2000 ^[8]
Rotated Bitboards? by Mauricio Castro, rgcc, October 07, 2001
Attack Bitboards by Sune Fischer, CCC, October 30, 2001
Resources about rotated bitboards by Federico Corigliano, CCC, January 02, 2004

2005 ...

Generating "through" attacks with rotated bitboard by Vlad Stamate, CCC, August 28, 2009 » X-ray Attacks (Bitboards)

2010 ...

A question on rotated bitboard by n_ven, OpenChess Forum, May 04, 2011

External Links

Rotated Bitboards by Ernst A. Heinz
Rotated bitmaps, a new twist on an old idea by Robert Hyatt, revisited version of the ICCA Journal paper ^[9]
Computer Chess Programming Theory - Bitboards by Colin Frayn
Herb Alpert - Rotation (1979), YouTube Video

References

^ Speed of Move Generator by Valavan Manohararajah, rgcc, August 15, 1995, post 5 by Robert Hyatt where he mentions on the fly generation with rotated bitboards
^ Rotated Bitboards in Ernst A. Heinz (1997). How DarkThought Plays Chess. ICCA Journal, Vol. 20, No. 3
^ Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website
^ Bitboard Representation by Carl Tillotson, rgcc, September 18, 1997, post 23 by Robert Hyatt
^ Re: Extracting information from rotated Bitboards by Roberto Waldteufel, CCC, November 02, 1998
^ Bitboard user's information request by Robert Hyatt, CCC, October 05, 1999
^ Nice Rotated-bitmaps Article by Hyatt in ICCA by Tom Likens, CCC, February 07, 2000
^ Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4
^ The ICCA Journal paper does not mention the outer square optimization with the four fold table reduction

What links here?

Page	Date Edited
More Links
Alarm	Jun 7, 2017
Alessandro Damiani	Oct 9, 2017
Alice	May 20, 2015
Amundsen	Sep 3, 2013
Android-Chess	Jun 2, 2016
Arasan	Apr 8, 2018
Aristarch	May 8, 2014
Array	Dec 1, 2016
Attack and Defend Maps	Nov 5, 2016
Beaches	Jun 10, 2017
Beowulf	May 5, 2017
Betsy	Jul 28, 2014
BigLion	Sep 28, 2016
Bison	Sep 29, 2016
Bitboards	Nov 14, 2017
BMI1	Mar 24, 2014
BMI2	Mar 6, 2018
Booot	Jan 22, 2018
Brainless	Jun 24, 2017
Bruja	Feb 3, 2015
Cassandre	Jul 5, 2013
Cheese	Feb 17, 2018
Chesley	Dec 25, 2012
ChessV	Jan 21, 2018
Chezzz	Jan 20, 2013
Cinnamon	Sep 23, 2017
Congruent Modulo Bitboards	Jun 26, 2013
Crafty	Jan 28, 2018
Cupcake	May 19, 2016
DarkThought	Jul 3, 2018
David Rasmussen	Dec 16, 2017
DiscoCheck	Jun 23, 2017
Djinn	Feb 8, 2016
Dorky	Oct 10, 2016
Edsel Apostol	Nov 2, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Ernst A. Heinz	Mar 6, 2017
Federico Andrés Corigliano	Feb 13, 2014
First Rank Attacks	Aug 28, 2010
Fischerle	Aug 21, 2017
Flipping Mirroring and Rotating	Oct 14, 2016
Fortress (Engine)	Oct 19, 2017
Freyr	Mar 6, 2014
FUSCsharp	Jun 7, 2013
Gk	Oct 9, 2017
Hagrid	Apr 12, 2016
Hashing Dictionaries	Mar 1, 2014
HeavyChess	Feb 14, 2014
IsiChess	Jan 7, 2016
Jazz	Oct 4, 2017
Johannes Buchner	May 26, 2013
Kindergarten Bitboards	Aug 1, 2017
Kiwi	Sep 2, 2016
Kurt	Apr 20, 2014
La Dame Blanche	Oct 15, 2015
LittleThought	Nov 7, 2016
Loop (Program)	Mar 14, 2017
Magic Bitboards	Apr 13, 2018
Mark Levene	Jun 2, 2015
Mathematician	Apr 9, 2018
Murka	Nov 11, 2016
Nesik	Jan 24, 2014
Occupancy	Sep 19, 2016
Occupancy of any Line	Sep 16, 2016
OliThink	May 19, 2017
Parrot	Dec 31, 2014
Pepito	Nov 27, 2014
Peter Fendrich	May 19, 2017
Peter Gillgasch	May 15, 2016
Pharaon	Sep 2, 2017
Plisk	Dec 31, 2014
Prophet	Sep 30, 2017
Protej	Jul 27, 2014
PsycoChess	Sep 17, 2016
Rabbit	Oct 5, 2014
Requiem	Feb 5, 2018
Robert Hyatt	Dec 25, 2017
Roberto Waldteufel	Jun 5, 2013
Rotated Bitboards	Mar 7, 2017
Rotated Indices	Oct 9, 2017
Rybka	Mar 27, 2017
Sayuri	Oct 1, 2017
Searcher	Sep 26, 2016
SIMD techniques	Nov 26, 2017
Simon	Mar 15, 2014
Sinobyl	Jul 3, 2014
Sliding Piece Attacks	May 27, 2016
Sloppy	Sep 17, 2016
Smash	May 11, 2016
SnailChess	Nov 26, 2014
Snitch	Apr 7, 2016
Space-Time Tradeoff	Jun 17, 2015
Sune Fischer	Apr 7, 2014
Sunsetter	Jun 1, 2017
Terra	Feb 11, 2015
Tom Likens	Mar 7, 2017
Trevor Fenner	Jun 2, 2015
Urban Koistinen	Apr 20, 2014
Vlad Stamate	Dec 31, 2014
Warrior	Feb 23, 2015

Up one Level

SSS* and Dual*

GerdIsenberg — Mon, 22 Jan 2018 12:24:33 GMT

Home * Search * SSS* and Dual*

		SSS* is a best-first state space search developed in 1977 by George C. Stockman for the linguistic analysis of waveforms ^[1] . In a later paper Stockman (1979) ^[2] showed how to use this algorithm to determine the minimax value of game trees. SSS* and it counterpart Dual* are non-directional algorithms for searching AND/OR graphs in a best-first manner similar to A. They expand multiple paths of the search graph and retain global information about the search space, and search fewer nodes than Alpha-Beta in fixed-depth minimax tree search. The algorithm was examined and improved by various researchers: Igor Roizen and Judea Pearl ^[3] , Toshihide Ibaraki ^[4] , Tony Marsland et al., Subir Bhattacharya and Amitava Bagchi, Alexander Reinefeld, Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin. In 1988 Burkhard Monien and Oliver Vornberger compared parallel Alpha-Beta with parallel SSS ^[5] and in 1990, Hans-Joachim Kraas wrote his Ph.D thesis about how to parallelize SSS* ^[6] . However, it turned out the algorithmic overhead was too big to pay off the saved nodes. Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin pointed out, that SSS* can be reformulated as a sequence of alpha-beta null window calls with a Transposition Table.
M. C. Escher, Stars, 1948 ^[7]

SSS*

Aske Plaat et al. about SSS*:

In 1979 Stockman introduced SSS*, which looked like a radically different approach from Alpha-Beta for searching fixed-depth minimax trees. It builds a tree in a so-called best-first fashion by visiting the most promising nodes first. Alpha-Beta, in contrast, uses a depth-first, left-to-right traversal of the tree. Intuitively, it would seem that a best-first strategy should prevail over a rigidly ordered depth-first one. Stockman proved that SSS* dominated Alpha-Beta; it would never evaluate more leaf nodes than Alpha-Beta. Numerous simulations have shown that on average SSS* evaluates considerably fewer leaf nodes. Why, then, has the algorithm been shunned by practitioners?

Alexander Reinefeld has a good answer, and explanation of SSS* in his Lecture ^[8]:

SSS* maintains an OPEN list with descriptors of the active nodes. Descriptors are sorted in decreasing order of their merit (h values). A descriptor (n, s, h) consists of

a node identifier n
a status s {LIVE, SOLVED}
- LIVE: n is still unexpanded and h is an upper bound on the true value
- SOLVED: h is the true value
a merit h

SSS*'s two search phases:

Node Expansion Phase: Top down expansion of a MIN strategy.
Solution Phase: Bottom up search for the best MAX strategy.

Pseudo C-Code

int SSS* (node n; int bound)
{
   push (n, LIVE, bound);
   while ( true ) {
      pop (node);
      switch ( node.status ) {
      case LIVE:
          if (node == LEAF)
             insert (node, SOLVED, min(eval(node),h));
          if (node == MIN_NODE)
             push (node.1, LIVE, h);
          if (node == MAX_NODE)
             for (j=w; j; j--)
                push (node.j, LIVE, h);
          break;
      case SOLVED:
          if (node == ROOT_NODE)
             return (h);
          if (node == MIN_NODE) {
              purge (parent(node));
              push (parent(node), SOLVED, h);
          }
          if (node == MAX_NODE) {
             if (node has an unexamined brother)
                push (brother(node), LIVE, h);
             else
                push (parent(node), SOLVED, h);
          }
          break;
      }
   }
}

SSS* is too complex and too slow!

In each step, the node with the maximum h-value is removed from OPEN.
Whenever an interior MAX-node gets SOLVED, all direct and indirect descendants must be purged from OPEN

These two steps alone take 90% of the CPU time!

Aske Plaat et al. continue:

SSS*, as formulated by Stockman, has several problems. First, it takes considerable effort to understand how the algorithm works, and still more to understand its relation to Alpha-Beta. Second, SSS* maintains a data structure known as the OPEN list, similar to that found in single-agent search algorithms like A*. The size of this list grows exponentially with the depth of the search tree. This has led many authors to conclude that SSS* is effectively disqualified from being useful for real applications like game-playing programs. Third, the OPEN list must be kept in sorted order. Insert and (in particular) delete/purge operations on the OPEN list can dominate the execution time of any program using SSS*. Despite the promise of expanding fewer nodes, the disadvantages of SSS* have proven a significant deterrent in practice.

Quote by Judea Pearl 1984 ^[9] :

The meager improvement in the pruning power of SSS* is more than offset by the increased storage space and bookkeeping (e.g. sorting OPEN) that it requires. One can safely speculate therefore that alphabeta will continue to monopolize the practice of computerized game playing.

Dual*

Dual* is the dual counterpart of SSS* by Tony Marsland et al ^[10] . The dual version of SSS* can be created by inverting SSS*’s operations: use an ascendingly sorted list instead of descending, swap max and min operations, and start at -oo instead of +oo.

RecSSS* and RecDual*

The development of recursive variants was driven by the need for a better understanding of SSS*'s node expansion process and by the demand for more efficient implementations. Two recursive variants were proposed 1990: RecSSS* ^[11] by Subir Bhattacharya and Amitava Bagchi and SSS-2 ^[12] by Wim Pijls and Arie de Bruin. In 1993 Alexander Reinefeld improved RecSSS*, making it both faster and more space efficient, using an OPEN-array rather than dynamic list structures ^[13] .

Pseudo C-Code

based on Alexander Reinefeld's Pascal pseudo code:

int RecSS*(nodeType n)
{
   if (n is leaf) {
      s(n) = SOLVED;
      return min (evaluate(n), h(n));                                            /* evaluate leaf */
   }
   if ( s(n) == UNEXPANDED ) {                                                  /* first descend? */
      s(n) = LIVE;                                                                    /* expand n */
      for (i = 1 to width)
         if ( n.i is leaf )
            insert (n.i, UNEXPANDED, h(n));                    /* insert sons (= MIN leaves) of n */
         else
            insert (n.i.1, UNEXPANDED, h(n));                       /* insert left grandsons of n */
   }
   g = highest h-valued grandson (or son) of n in OPEN;
   while ( h(g) == h(n) && status(g) != SOLVED ) {
      h(g) = RecSS*(g);                                                    /* get new upper bound */
      if ( s(g) == SOLVED && g has a right brother )
          replace g by (brother(g), UNDEXPANDED, h(g));                      /* next brother of g */
      g = highest h-valued grandson (or son) of n in OPEN; /*resolve ties in lexicographical order*/
   }
   if ( s(g) == SOLVED )
      s(n) = SOLVED;
   return h(g);
}

int main()
{
   insert (root, UNEXPANDED, oo);
   do
      h = RecSSS*(root);
   while ( s(n) != SOLVED );
}

SSS* and Dual* as MT

Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin proved with their Memory Test framework, that both SSS* and Dual* can be reformulated as a sequence of alpha-beta null window calls with a Transposition Table ^[14] :

Pseudo C-Code

int MT-SSS*( n )
{
   g := +oo;
   do {
      G := g;
      g := Alpha-Beta(n, G-1, G );
   } while (g != G);
   return g;
}

int MT-DUAL*(n)
{
   g := -oo;
   do {
      G := g;
      g := Alpha-Beta(n, G, G+1 );
   } while (g != G);
   return g;
}

At the 8th Advances in Computer Chess conference 1996, SSS* was finally declared "dead" by Wim Pijls and Arie de Bruin ^[15] ^[16] .

Publications

1979

George Stockman (1979). A Minimax Algorithm Better than Alpha-Beta? Artificial Intelligence, Vol. 12, No. 2.

1980 ...

Igor Roizen, Judea Pearl (1983). A Minimax Algorithm Better than Alpha-Beta? Yes and No. Artificial Intelligence, Vol. 21
Murray Campbell, Tony Marsland (1983). A Comparison of Minimax Tree Search Algorithms. Artificial Intelligence, Vol. 20, No. 4, pp. 347-367. ISSN 0004-3702, pdf
Nanda Srimani (1985). A New Algorithm (PS*) for Searching Game Trees. Master's thesis, University of Alberta
Daniel B. Leifker, Laveen N. Kanal (1985). A Hybrid SSS*/Alpha-Beta Algorithm for Parallel Search of Game Trees. IJCAI'85
Toshihide Ibaraki (1986). Generalizations of alpha-beta and SSS* search procedures. Artificial Intelligence, 29, 73-117
Tony Marsland, Nanda Srimani (1986). Phased State Search. Fall Joint Computer Conference, pdf
Tony Marsland, Alexander Reinefeld, Jonathan Schaeffer (1987). Low Overhead Alternatives to SSS*. Artificial Intelligence, Vol. 31, No. 2, pp. 185-199. ISSN 0004-3702.
Burkhard Monien, Oliver Vornberger (1988). Parallel Alpha-Beta versus Parallel SSS*. Proc. of the IFIP WG 10.3 Working Conference on Distributed Processing, North Holland

1990 ...

Subir Bhattacharya, Amitava Bagchi (1990). Unified Recursive Schemes for Search in Game Trees. Technical Report WPS-144, Indian Institute of Management, Calcutta
Hans-Joachim Kraas (1990).Zur Parallelisierung des SSS*-Algorithmus. Ph.D thesis, TU Braunschweig (German)
Wim Pijls, Arie de Bruin (1990). Another View on the SSS* Algorithm. International Symposium SIGAL '90 (eds. T. Asano, T. Ibaraki, H. Imai, and T. Nishizeki), pp. 211-220. Tokyo, Japan. Lecture Notes in Computer Science, Vol. 450, Springer-Verlag, New York, NY. ISSN 0302-9743.
Claude G. Diderich (1992). Evaluation des performance de l'algorithme SSS* avec phases de synchronisation sur une machine parallèle à mémoires distribées. Technical report LITH-99, Swiss Federal Institute of Technology, Computer Science Theory Laboratory, Lausanne, Switzerland (French)
Alexander Reinefeld (1994). A Minimax Algorithm Faster than Alpha-Beta. Advances in Computer Chess 7
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1994). SSS* = a-b TT. TR-CS-94-17, University of Alberta
Alexander Reinefeld, Peter Ridinger (1994). Time-Efficient State Space Search. Artificial Intelligence, Vol. 71, No. 2, CiteSeerX
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1996). An Algorithm Faster than NegaScout and SSS* in Practice, pdf from CiteSeerX, covers MTD(f)
Arie de Bruin, Wim Pijls (1997). SSS†. Advances in Computer Chess 8
Aske Plaat, Arie de Bruin, Jonathan Schaeffer, Wim Pijls (1999). A Minimax Algorithm better than SSS*. Artificial Intelligence, Vol. 87

2010 ...

Bojun Huang (2015). Pruning Game Tree by Rollouts. AAAI » MT-SSS*, MCTS ^[17]

External Links

SSS* From Wikipedia
State space search From Wikipedia
State Space Search from Murray's Web Pages
Aziza Mustafa Zadeh - Stars Dance, Leverkusener Jazztage, November 7, 2006, 3sat, YouTube Video

References

^ George Stockman, Laveen Kanal (1983). Problem Reduction Representation for the Linguistic Analysis of Waveforms. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 5, No 3
^ George Stockman (1979). A Minimax Algorithm Better than Alpha-Beta? Artificial Intelligence, Vol. 12, No. 2
^ Igor Roizen, Judea Pearl (1983). A Minimax Algorithm Better than Alpha-Beta? Yes and No. Artificial Intelligence, Vol. 21, pp. 199-230. ISSN 0004-3702
^ Toshihide Ibaraki, (1986). Generalizations of alpha-beta and SSS* search procedures.Artificial Intelligence, 29, 73-117
^ Burkhard Monien, Oliver Vornberger (1988). Parallel Alpha-Beta versus Parallel SSS*. Proc. of the IFIP WG 10.3 Working Conference on Distributed Processing, North Holland
^ Hans-Joachim Kraas (1990). Zur Parallelisierung des SSS*-Algorithmus. Ph.D thesis, TU Braunschweig (German)
^ Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website
^ Alexander Reinefeld (2005). Die Entwicklung der Spielprogrammierung: Von John von Neumann bis zu den hochparallelen Schachmaschinen. slides as pdf, Themen der Informatik im historischen Kontext Ringvorlesung an der HU Berlin, 02.06.2005 (English paper, German title)
^ Judea Pearl (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Publishers Co., Reading, MA. ISBN 0-201-05594-5.
^ Tony Marsland, Alexander Reinefeld, Jonathan Schaeffer (1987). Low Overhead Alternatives to SSS*. Artificial Intelligence, Vol. 31, No. 2, pp. 185-199. ISSN 0004-3702.
^ Subir Bhattacharya, Amitava Bagchi (1990). Unified Recursive Schemes for Search in Game Trees. Technical Report WPS-144, Indian Institute of Management, Calcutta
^ Wim Pijls, Arie de Bruin (1990). Another View on the SSS* Algorithm. International Symposium SIGAL '90 (eds. T. Asano, T. Ibaraki, H. Imai, and T. Nishizeki), pp. 211-220. Tokyo, Japan. Lecture Notes in Computer Science, Vol. 450, Springer-Verlag, New York, NY. ISSN 0302-9743.
^ Alexander Reinefeld (1994). A Minimax Algorithm Faster than Alpha-Beta. Advances in Computer Chess 7
^ Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1995). SSS* = Alpha-Beta + TT Technical Report EUR-CS-95-02, pdf
^ Arie de Bruin, Wim Pijls (1997). SSS†. Advances in Computer Chess 8
^ Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin(1996). Best-First Fixed-Depth Minimax Algorithms. Artificial Intelligence, Vol. 87, Nos. 1-2, pdf
^ Re: Announcing lczero by Daniel Shawul, CCC, January 21, 2018 » LCZero

What links here?

Page	Date Edited
Advances in Computer Chess 8	Jun 26, 2017
Alexander Reinefeld	Jul 4, 2016
Algorithms	May 5, 2017
Alpha-Beta	Jan 28, 2018
Amitava Bagchi	May 23, 2016
Arachne	May 22, 2016
Arie de Bruin	May 23, 2016
Aske Plaat	Jun 26, 2017
Asterisk	Mar 24, 2016
B*	Nov 27, 2017
Best-First	Dec 29, 2017
Bojun Huang	Jan 22, 2018
Dictionary	Aug 24, 2017
Fritz	Feb 26, 2018
Gary Lindstrom	Nov 27, 2015
George Stockman	Jul 19, 2013
Hans-Joachim Kraas	Jan 7, 2016
Igor Roizen	Feb 28, 2015
MCαβ	Jan 28, 2018
Memory	Dec 8, 2017
Monte-Carlo Tree Search	Apr 26, 2018
MTD(f)	Jul 17, 2017
Nanda Srimani	Nov 27, 2014
NegaC*	Dec 17, 2016
Null Window	Nov 8, 2016
Parallel Search	Dec 30, 2017
Search	Feb 1, 2018
SSS* and Dual*	Jan 22, 2018
Subir Bhattacharya	Jul 28, 2014
Toshihide Ibaraki	Sep 18, 2017
Wim Pijls	May 23, 2016

Up one level

Zobrist Hashing

GerdIsenberg — Mon, 22 Jan 2018 16:53:04 GMT

Home * Search * Transposition Table * Zobrist Hashing

		Zobrist Hashing, a technique to transform a board position of arbitrary size into a number of a set length, with an equal distribution over all possible numbers, invented by Albert Zobrist ^[1]. In an early Usenet post in 1982, Tom Truscott mentioned Jim Gillogly's n-bit hashing technique ^[2], who apparently read Zobrist's paper early, and credits Zobrist in a 1997 rgcc post ^[3]. Zobrist Hashing is an instance of tabulation hashing ^[4], a method for constructing universal families of hash functions by combining table lookup with exclusive or operations. Zobrist Hashing was rediscovered by J. Lawrence Carter and Mark N. Wegman in 1977 ^[5] and studied in more detail by Mihai Pătrașcu and Mikkel Thorup in 2011 ^[6] ^[7]. The main purpose of Zobrist hash codes in chess programming is to get an almost unique index number for any chess position, with a very important requirement that two similar positions generate entirely different indices. These index numbers are used for faster and more space efficient Hash tables or databases, e.g. transposition tables and opening books.
King Wen sequence ^[8] ^[9]

Lack a True Integer Type

Metamorphosis

M. C. Escher, Metamorphosis III, 1967-1968 ^[10]

Initialization

At program initialization, we generate an array of pseudorandom numbers ^[11] ^[12]:

One number for each piece at each square
One number to indicate the side to move is black
Four numbers to indicate the castling rights, though usually 16 (2^4) are used for speed
Eight numbers to indicate the file of a valid En passant square, if any

This leaves us with an array with 781 (12*64 + 1 + 4 + 8) random numbers. Since pawns don't happen on first and eighth rank, one might be fine with 12*64 though. There are even proposals and implementations to use overlapping keys from unaligned access up to an array of only 12 numbers for every piece and to rotate that number by square ^[13] ^[14] .

Programs usually implement their own Pseudorandom number generator (PRNG), both for better quality random numbers than standard library functions, and also for reproducibility. This means that whatever platform the program is run on, it will use the exact same set of Zobrist keys. This is also useful for things like opening books, where the positions in the book can be stored by hash key and be used portably across machines, considering endianness.

Runtime

If we now want to get the Zobrist hash code of a certain position, we initialize the hash key by xoring all random numbers linked to the given feature.

E.g the starting position:
[Hash for White Rook on a1] xor [White Knight on b1] xor [White Bishop on c1] xor ... ( all pieces )
... xor [White castling short] xor [White castling long] xor ... ( all castling rights )

The fact that xor-operation is own inverse and can be undone by using the same xor-operation again, is often used by chess engines. It allows a fast incremental update of the hash key during make or unmake moves.

E.g., for a White Knight that jumps from b1 to c3 capturing a Black Bishop, these operations are performed:

[Original Hash of position] xor [Hash for White Knight on b1] ... ( removing the knight from b1 )
... xor [Hash for Black Bishop on c3] ( removing the captured bishop from c3 )
... xor [Hash for White Knight on c3] ( placing the knight on the new square )
... xor [Hash for Black to move] ( change sides)

Collisions

Key collisions or type-1 errors are inherent in using Zobrist keys with far less bits than required to encode all reachable chess positions.

Theory

An important issue is the question of what size the hash keys should have. Smaller hash keys are faster and more space efficient, while larger ones reduce the risk of a hash collision. A collision occurs if two positions map the same key ^[15] . The dangers of which were well assessed by Robert Hyatt and Anthony Cozzie in their paper Hash Collisions Effect ^[16]. Usually 64bit are used as a standard size in modern chess programs.

Hash collisions demonstrate the birthday "paradox", which is to say the chance of collisions approaches certainty at around the square root of the number of possible keys, contrary to some people's expectations. You can expect to encounter a collision in a 32 bit hash when you have evaluated sqrt(2 ^ 32) == 2 ^ 16 or around 65 thousand positions. With a 64 bit hash, you can expect a collision after about 2 ^ 32 or 4 billion positions.

Praxis

Post by Jonathan Schaeffer ^[17] :

... I can speak from experience here. In the early versions of my chess program Phoenix, I generated my Zobrist hash numbers using my student id number as a seed, naively thinking the random numbers generated by this seed would be good enough. A few years later I put code in to detect when my 32-bit hash key matched the wrong position. To my surprise, there were lots of errors. I changed my seed to another number and the error rate dropped dramatically. With this better seed, it became very, very rare to see a hash error. All randomly generated numbers are not the same!

Lack a True Integer Type

Some languages (such as JavaScript and Lua) only have a 64-bit floating point "Number" type. In JavaScript, this type breaks down into a 32 bit integer when bitwise operators are used. One way to get a 64 bit hash is to use two 32 bit numbers in parallel, as Garbochess-JS ^[18] does. Another, which p4wn used at one stage, is to use 47 or 48 bit additive hashes. 64 bit floating point numbers are true integers up to 53 bits, so it is possible to sum at least 32 (and on average close to 64) random 48 bit numbers, which was enough for p4wn's purposes. For additive Zobrist hashing, you add the number when placing a piece and subtract it when removing it, rather than using xor both ways. There is no difference in accuracy or speed, and 48 bit hashes give you collisions at around the 2 ^ 24 or 16 million point.

Linear Independence

The minimum and average Hamming Distance over all Zobrist keys was often considered as "quality"-measure of the keys. However, maximizing the minimal hamming distance leads to very poor Zobrist keys. As long the minimum hamming distance is greater zero, linear independence (that is a small subset of all keys doesn't xor to zero), is much more important than hamming distance as explained by Sven Reichard ^[19] :

Assume we associate a bitstring to every piece-square combination. That is what's usually done in chess programs; some codes are added for the side to move, castling rights, e.p. squares, etc. We obtain the code of a position by xor-ing the codes of all the pieces contained in it.

What we want to avoid is collisions at nodes close to the root. For nodes close to the leaves the cost of recomputing the score is smaller. Hence we want to avoid that:

x1^x2^...^xm = y1^y2^...^yn
for codes xi, yi and small number m and n, and xi not equal to yj

To translate that to a language that is more familiar - at least for people of a mathematical background - we consider the field F2 of two elements. The elements are 0 and 1, and we can add and multiply them as usual, with the additional rule that 1 + 1 = 0. This is really a field, just like the real or complex numbers, and we can do calculations as usual. Note that addition is just the exclusive or.

Now the codes or bitstrings become vectors over the field F2, and the bitwise exclusive or becomes componentwise addition, i.e., usual addition of vectors. All these vectors form the vector space F2^k, where k is the length of the vectors. Typically, k = 64.

So, what we want to avoid is an equation

x1 + x2 + ... + xm = y1 + y2 + ... + yn

or

x1 + x2 + ... + xm + y1 + y2 + ... + yn = 0

since in F2, subtraction is the same as addition. Remembering some linear algebra, this just means that we want the set x1,...,xm,y1,...,yn to be linearly independent.

This leads to the following criterion for picking a set of hashcodes: A set of vectors in F2^k is a good set of hash codes if each small subset of non-zero vectors is linearly independent. What is not clear here is the meaning of "small", but we want small to be as big as possible. In other words, we consider sets of size up to a certain size as small, and if we can make that size bigger, it is better, since this leads to unique codes deeper in the tree.

However what is clear is that this quality criterion does not depend on the base of the vector space. I.e., if we have a good set and multiply each vector by an invertible matrix (in other words, if we rotate the vectors), the obtained set will be just as good, since the rotation does not change the linear independence. The Hamming distance, on the other hand, is highly dependent on the vector space base. Take for example the vectors (1,0) and (0,1) in F2^2; they have Hamming distance 2. If we multiply both of them by

(1 1)
(0 1)

we get (1,1) and (0,1), which have Hamming distance 1. Actually we can change any distance to anything else (except for 0) by an appropriate matrix. Thus we try to approximate something that is independent from the base (the quality of our hash codes) by something that depends on it (the Hamming distance). Simple logic tells you that this approximation has to be real bad. An example where it doesn't work: It has been said that the Hamming distance shouldn't be to small or to big. So, vectors at a distance which is half the length should be ok, right? Let the length be 8 (I don't want to type too many 0's and 1's), and consider the vectors

11110000
11001100
00111100

They all have weight 4, their pairwise distance is 4, and yet they add up to 0. Just by looking at Hamming distances, you have no chance of detecting that.

Summarizing I can say that I see no connection between the quality of hash codes and their Hamming distance. Using a good RNG like the one provided in GNU's stdlib will yield good hash codes ( you can actually prove that), and so I will take the codes as they are supplied by rand() or random() without messing with them and thereby most likely make them worse.

Publications

Albert Zobrist (1970). A New Hashing Method with Application for Game Playing. Technical Report #88, Computer Science Department, The University of Wisconsin, Madison, WI, USA. Reprinted (1990) in ICCA Journal, Vol. 13, No. 2, pdf
J. Lawrence Carter, Mark N. Wegman (1977). Universal classes of hash functions. STOC '77
Robert Hyatt, Anthony Cozzie (2005). The Effect of Hash Signature Collisions in a Chess Program. ICGA Journal, Vol. 28., No. 3
Borko Bošković, Sašo Greiner, Janez Brest, Viljem Žumer (2005). The Representation of Chess Game. Proceedings of the 27th International Conference on Information Technology Interfaces
Mihai Pătrașcu, Mikkel Thorup (2011). The Power of Simple Tabulation Hashing. arXiv:1011.5200v2

Forum Posts

1982 ...

compact representation of chess positions by Tom Truscott, net.chess, January 7, 1982

1990 ...

Hash tables - Clash!!! What happens next? by Valavan Manohararajah, rgc, March 15, 1994
Re: Hash tables - Clash!!! What happens next? by Jonathan Schaeffer, March 17, 1994
Collision probability by Dennis Breuker, rgcc, April 15, 1996
Re: Berliner vs. Botvinnik Some interesting points by Bradley C. Kuszmaul, rgcc, November 6, 1996
Re: Hashing function for board positionsby Jim Gillogly, rgcc, May 12, 1997
Fast hash algorithm by John Scalo, CCC, January 08, 1998
Fast hash key method - Revisited! by John Scalo, CCC, January 14, 1998
How to create a set of random integers for hashing? by Ed Schröder, CCC, October 18, 1998

2000 ...

Why Random Number Needed In HashFunction[piece][position] by Cheok Yan Cheng, rgcc, June 12, 2001
About random numbers and hashing by Severi Salminen, CCC, December 04, 2001
Random keys and hamming distance by James Swafford, CCC, August 16, 2002
Hamming distance and lower hash table indexing by Tom Likens, CCC, September 02, 2003
64-Bit random numbers by Martin Schreiber, CCC, October 28, 2003
Is it necessary to include empty fields in the hash key of a position? by Frank Hablizel, rgcc, December 25, 2003
Hashkey collisions (typical numbers) by Renze Steenhuisen, CCC, April 07, 2004

2005 ...

Zobrist key random numbers by Robert Hyatt, CCC, January 21, 2009
Incremental Zobrist - slow? by Vlad Stamate, CCC, June 20, 2009 » Incremental Updates
On Zobrist keys by Lasse Hansen, CCC, June 21, 2009
Overlapped Zobrist keys array by Stefano Gemma, CCC, October 06, 2009

2010 ...

Transposition table random numbers by Justin Madru, CCC, July 13, 2010
TT Key Collisions, Workarounds? by Clemens Pruell, CCC, August 16, 2011
Key collision handling by Jonatan Pettersson, CCC, October 21, 2011
Using a Transposition Table with Zobrist Keys by Miyagi403, OpenChess Forum, February 21, 2012
MT or KISS ? by Dan Honeycutt, CCC, June 02, 2012 ^[20] ^[21] ^[22]
Zobrist alternative? by Harm Geert Muller, CCC, June 12, 2012
Zobrist Number Statistics and WHat to Look For by Andrew Templeton, CCC, October 16, 2012
Question about Zobrist code by Hamfer, OpenChess Forum, December 19, 2012

2015 ...

Zobrist keys - measure of quality? by Martin Sedlak, CCC, February 24, 2015
On-the fly hash key generation? by Evert Glebbeek, CCC, January 12, 2016
Re: On-the fly hash key generation? by Aleks Peshkov, CCC, January 13, 2016
Rotated hash by J. Wesley Cleveland, CCC, September 13, 2016
No Zobrist key by Henk van den Belt, CCC, September 26, 2016
Enpass + Castling for Zorbist hashes by Andrew Grant, CCC, January 06, 2017 » Castling rights, En passant
Zobrist hashing for text by Alvaro Cardoso, CCC, January 20, 2018

External Links

Zobrist hashing from Wikipedia
Tabulation hashing from Wikipedia
Zobrist keys from Bruce Moreland's Programming Topics
Zobrist keys from Mediocre Chess by Jonatan Pettersson
Gödel numbering from Wikipedia
John Cage - Music of Changes, Book 1 (1951), performed by Vicky Chow, DiMenna Center, NYC, June 09, 2012, YouTube Video

References

^ Albert Zobrist (1970). A New Hashing Method with Application for Game Playing. Technical Report #88, Computer Science Department, The University of Wisconsin, Madison, WI, USA. Reprinted (1990) in ICCA Journal, Vol. 13, No. 2, pdf
^ compact representation of chess positions by Tom Truscott, net.chess, January 7, 1982
^ Re: Hashing function for board positionsby Jim Gillogly, rgcc, May 12, 1997
^ Re: Zobrist keys - measure of quality? by Rein Halbersma, CCC, February 24, 2015
^ J. Lawrence Carter, Mark N. Wegman (1977). Universal classes of hash functions. STOC '77
^ Mihai Pătrașcu, Mikkel Thorup (2011). The Power of Simple Tabulation Hashing. arXiv:1011.5200v2
^ Tabulation hashing from Wikipedia
^ King Wen sequence, I Ching divination involves obtaining a Hexagram by random generation
^ All of Cage's music since 1951 was composed using chance procedures, most commonly using the I Ching
^ Picture gallery "Recognition and Success 1955 - 1972" from The Official M.C. Escher Website
^ RANDOM.ORG - Integer Generator
^ The Marsaglia Random Number CDROM including the Diehard Battery of Tests by George Marsaglia
^ Re: Zobrist key random numbers by Zach Wegner, CCC, January 22, 2009
^ Overlapped Zobrist keys array by Stefano Gemma, CCC, October 06, 2009
^ Hashkey collisions (typical numbers) by Renze Steenhuisen, CCC, April 07, 2004
^ Robert Hyatt, Anthony Cozzie (2005). The Effect of Hash Signature Collisions in a Chess Program. ICGA Journal, Vol. 28, No. 3
^ Re: Hash tables - Clash!!! What happens next? by Jonathan Schaeffer, March 17, 1994
^ Garbochess-JS
^ Re: About random numbers and hashing by Sven Reichard, CCC, December 05, 2001
^ Mersenne twister from Wikipedia
^ 64-bit KISS RNGs by George Marsaglia, comp.lang.fortran | Computer Group, February 28, 2009
^ RKISS by Bob Jenkins

What links here?

Page	Date Edited
Abyss	Aug 5, 2017
Albert Zobrist	Jun 12, 2016
Aleks Peshkov	Jan 13, 2016
Algorithms	May 5, 2017
Andrew Grant	Jan 13, 2018
Array	Dec 1, 2016
Bagatur	Sep 10, 2016
Barbarossa	Dec 20, 2016
BCH Hashing	May 8, 2017
Belle	Jan 18, 2018
Bob Jenkins	Jun 3, 2017
Bookup	Feb 4, 2018
Carballo	Oct 2, 2016
Castling rights	Jan 7, 2017
Cheese	Feb 17, 2018
Chess Game	Mar 28, 2017
Chess Position	Sep 10, 2017
Claudia	Jun 1, 2016
Color Flipping	May 17, 2017
Dan Honeycutt	Mar 13, 2014
Databases	Mar 18, 2018
Debugging	Jan 20, 2018
Demolito	Mar 1, 2018
Diablo	May 17, 2016
Dictionary	Aug 24, 2017
Djinn	Feb 8, 2016
Dorpsgek	Apr 2, 2018
ECO	Nov 2, 2017
Ed Schroder	Feb 26, 2018
Eden	Apr 16, 2017
En passant	Jan 16, 2018
Encoding Moves	Mar 27, 2016
Enhanced Transposition Cutoff	May 19, 2017
Evaluation Hash Table	Dec 4, 2016
Evert Glebbeek	Sep 25, 2017
Floyd	Sep 11, 2016
Flux	Jan 12, 2016
General Setwise Operations	Feb 25, 2018
Godot	Apr 28, 2015
Hakkapeliitta	Apr 26, 2016
Harm Geert Muller	Mar 31, 2018
Hash Table	Jan 1, 2018
Ifrit	Feb 7, 2016
Incremental Updates	Sep 6, 2017
Iteration	May 5, 2017
James Swafford	Jan 1, 2018
JavaScript	Dec 11, 2017
Jonatan Pettersson	Feb 7, 2014
Jonathan Schaeffer	Jan 29, 2018
Jonathan Warkentin	Jun 29, 2014
Kanguruh	Jan 13, 2013
Kholin	Jan 3, 2018
Lachex	Jan 7, 2016
Laser	Dec 27, 2017
Leila	May 8, 2017
Little Wing	Oct 26, 2017
Lozza	Apr 18, 2018
Mac Hack	Apr 20, 2018
Make Move	Mar 2, 2016
Mathematician	Apr 9, 2018
Move List	Jul 19, 2017
Napoleon	Jun 25, 2017
Nemorino	Dec 21, 2017
Pawn Hash Table	Feb 1, 2018
Pawn Push	Mar 27, 2010
Perft	Sep 26, 2017
Phoenix	May 8, 2017
Population Count	Sep 3, 2017
Pseudorandom number generator	May 11, 2017
Quad-Bitboards	Jan 30, 2017
Repetitions	Jan 16, 2018
Severi Salminen	May 7, 2015
Shared Hash Table	Sep 11, 2017
SharpChess	Jun 6, 2017
Sharper	Jun 6, 2017
Sierżant	Apr 15, 2014
Sloppy	Sep 17, 2016
Soldat	Aug 20, 2017
Stefano Gemma	Dec 26, 2017
Steffan Westcott	Jan 21, 2014
Tech	Apr 20, 2018
TechMate	Aug 23, 2014
Teki	Mar 29, 2018
Tom King	Aug 19, 2017
Tom Truscott	Dec 22, 2017
Transposition	Jun 8, 2015
Transposition Table	Apr 19, 2018
Vajolet	Jan 25, 2018
Vice	Mar 8, 2016
Vlad Stamate	Dec 31, 2014
Wing	Oct 26, 2017
Winglet to include	Apr 25, 2015
WyldChess	Mar 10, 2018
Zach Wegner	Jan 7, 2016
Zeta Dva	Apr 11, 2017
Zobrist Hashing	Jan 22, 2018
Stockfish : home	Feb 2, 2014

Up one Level

Wikispaces : chessprogramming - items matching description

Ant

Table of Contents

Photos & Games

Ant beats Tiger

Ant draws Shredder

See also

When Ants Play Chess

Forum Posts

External Links

Chess Engine

Misc

References

What links here?

Bitboard Serialization

Table of Contents

Isolating Subsets

Single Bits

Multiple Bits

Converting Sets to Lists

Square Index Serialization

Scanning Forward

Scanning Reverse

Scanning with Reset

Intrinsic Version

Black or White

STL Iterator

Hashing Multiple Bits

See also

Forum Posts

External Links

References

What links here?

BitScan

Table of Contents

Hardware vs. Software

Non Empty Sets

Bitscan forward

Trailing Zero Count

De Bruijn Multiplication

With isolated LS1B

With separated LS1B

Matt Taylor's Folding trick

Walter Faxon's magic Bitscan

Bitscan by Modulo

Divide and Conquer

Double conversion of LS1B

Index of LS1B by Popcount

Bitscan reverse

Divide and Conquer

Tribute to Frank Zappa

De Bruijn Multiplication

Double conversion

Leading Zero Count

Bitscan versus Zero Count

Bitscan with Reset

Generalized Bitscan

Processor Instructions for Bitscans

x86

Emulating Intrinsics

Intrinsics versus asm

Bsf/Bsr x86-64 Timings

Bsf/Bsr behavior with zero source

ARM

Engine Samples

See also

Publications

Forum Posts

1996 ...

2000 ...

2005 ...

2010 ...

2015 ...

External Links

References

What links here?

Butterfly Boards

Table of Contents

Layout

Valid Entries