Material Signatures

Our first refinement to the index scheme of the lookup table replaces the exact piece counts by 1-bit flags that solely indicate the presence of any Pawns or pieces of the respective kinds. The refined scheme treats both Pawns and pieces in an identical way. The new index function comprises ten 1-bit parameters which are simply concatenated to yield the index number. The ten 1-bit parameters naturally break up into two groups of five bits, namely one each for Pawns and the four kinds of pieces per side. The two groups of five 1-bit values represent the ``material footprints'' of their sides. The separate concatenation of the five 1-bit values on their own results in 5-bit strings that we use as signatures for the material states of both sides. Below we summarize some important properties of these novel material signatures.

The integer values of material signatures range from 0 to 2⁵ - 1 = 31. Bit k $\in$ {0...4} = {Bishop,...,Pawn} of a material signature gets set if the side in question has at least one man of kind k on the board. Like other important state information in computer chess, material signatures lend themselves to efficient calculation by incremental updates during the execution of moves by the search. To this end DARKTHOUGHT includes two material signatures in its internal representation of the chess board, namely one for Black and one for White.

With the material signatures of Black and White spanning its index space, the refined lookup table contains 2¹⁰ = 32 * 32 = 1024 elements overall. Altogether the elements require 1024 * sizeof(pointer) bytes of memory which tranlsates to 4 KBytes in case of 4-byte pointers and to 8 KBytes in case of 8-byte pointers. Hence, the adoption of material signatures for indexing reduces the memory consumption of the lookup table more than 500-fold as compared with the initial naive approach from above. But even the refined lookup table still wastes a great deal of precious data-cache space due to poor information density. According to our extensive practical experiences with recognizers in DARKTHOUGHT, most entries of the table tend to be NULL.