Our aforementioned practical experiences gave rise to an empirical investigation of all positions for which we knew or at least imagined automatic interior-node recognition to be possible. The ensuing characterization of potentially recognizable positions showed the following.
Based on the last two observations above, we further refined the lookup table and achieved another 16-fold reduction of its index space in our current version of DARKTHOUGHT. This decreased the number of elements in the lookup table to mere 64, resulting in a cache-friendly memory consumption of 256 bytes with 4-byte pointers and 512 bytes with 8-byte pointers.
The main idea of the new index scheme is to separate positions with lone Kings from the rest because only one of their two material signatures conveys interesting information. Hence, we split the lookup table into two halfs. In positions with a lone King the lower 32 entries correspond to the material signatures of the strong sides. The remaining positions get mapped to the upper 32 entries by combining the material signatures of both sides into a single value through a logical OR operation. With the material signatures of Black and White given by b mstate and w mstate respectively, the new index function allows for its efficient calculation as detailed below. Modern computers execute the six necessary operations in a few clock cycles after loading both material signatures into registers of their CPUs.
A minor drawback of the efficient index scheme springs from its mapping behaviour. The logical OR operation combines several distinct material signatures into one and the same result. Thence, the new index function maps different constellations of material distribution to identical entries of the lookup table. The constellations KBKN, KBBKN, KBBKBN, KBBKNN, KBNKB, and KBNKBN are good examples for this peculiar mapping behaviour because logical OR combinations of their material signatures always yield BN = Bishop + Knight. Consequently, the recognizer functions referred to in the lookup table do not know the exact material constellations of the positions they receive in advance. Instead, they must dynamically determine the actual material constellations during each call in order to select the appropriate recognition procedure (e.g. KXXK versus KXK for any kind of piece X other than a King). Our implementation assists the dynamic selection process by means of efficiently accessible 4-bit counters for Pawns and each kind of pieces per side. DARKTHOUGHT keeps the counters in its internal representation of the chess board and incrementally updates them whenever the search executes a move.
Furthermore, we make sure to avoid any senseless function calls in unrecognizable positions. Many such calls would normally ensue from the mapping behaviour of the new index scheme: KBBKBN, KBBKNN, and KBNKBN, for instance, are currently not recognizable but they get mapped to the same function pointer of the lookup table as KBKN for which an endgame database enables the perfect recognition. An additional lookup table with 1024 flag bits occupying just 128 bytes of memory provides an elegant solution for this problem. The new table employs the index scheme of the last section with fully concatenated material signatures of both sides. Each flag bit of this second lookup table indicates whether the function referred to by the main lookup table can really recognize positions with material constellations that correspond exactly to the full index of the second table. Hence, the additional lookup table allows for the quick and easy detection of superfluous function calls altogether. But it does not eliminate the minor drawback of mapping similar material constellations to the same entry of the recognizer lookup table (see above).
Thanks to the ample descriptions above, the implementation details of
our final solution for the efficient detection and selection of
recognizers should now be ready to understand. Figure 1.4
presents the skeleton of a normal search function that outlines the
necessary additions. Its verbose ANSI-C style and the various embedded
comments make this search skeleton quite self-explanatory. It assumes
all not explicitly declared identifiers to be suitably defined and
initialized. The search skeleton omits the handling of successful
recognitions because we already outlined it on its own in
Figure 1.3. What deserves special attention, however, is
the design of the second lookup table hosting the 1024 availability
flags. For the sake of efficient storage and access, we use an array of
32-bit unsigned integers to implement the table. While Black's material
signature selects the array element, White's material signature extracts
the desired bit of the selected value.
Last but not least, we like to sketch the proper initialization of the
two lookup tables for availability flags and recognizers.
Figure 1.5 shows the skeleton of an according
initialization function containing all the necessary actions. As before,
its verbose ANSI-C style and the embedded comments make the code easy to
comprehend. The initialization skeleton implicitly reuses the global
definitions of macros and variables from Figure 1.4. It
of course assumes all other not explicitly declared identifiers to be
suitably defined and initialized. As for the installation of new
recognizers, it is important to note that the efficient index scheme of
the recognizer lookup table is commutative in its parameters:
recog index(x,y) = recog index(y,x). Because such commutativity does
not hold for the index scheme of the availability lookup table we must
set two different flag bits therein for each new recognizer. These flag
bits correspond to the two material constellations which result from
interpreting two given material signatures mstate 1, mstate 2 as
representing either Black and White or White and Black respectively.
