Efficient Detection and Selection of Recognizers

In order to select an appropriate recognizer for a given position you must first decide whether the position lends itself to recognition at all. This is an absolutely non-trivial task if executed at every node in the search tree with an overall frequency of several hundred thousand times per second. Moreover, it constitutes only a tiny fraction of the whole work done at each node. For the sake of simplicity and practical relevance let us assume that both sides can have at most 8 Pawns and 2 pieces of each kind. Under these simplified assumptions there are still (34 * 9) * (34 * 9) = 312 = 531441 different constellations of material distribution for Black and White to decide between (four kinds of 0 to 2 pieces and 0 to 8 Pawns per side).

Of course, a lookup table with 531441 pointer elements referring to the according recognizers of the different material constellations provides a straightforward solution to the detection problem. Just mark all elements in the lookup table with the special value NULL if there are no recognizers available for their constellations. The major drawback of this easy yet naive solution springs from its huge memory consumption. The lookup table requires 531441 * sizeof(pointer) bytes of memory which roughly tranlsates to 2 MBytes in case of 4-byte pointers and to 4 MBytes in case of 8-byte pointers. Frequently accessed lookup tables of large sizes like these are horribly inefficient because they tend to thrash the data caches and other data paths of modern computers, thus causing the whole application to slow down considerably.

The remainder of this section discusses how to refine the straightforward approach into a viable solution by greatly reducing the size of the lookup table. During the course of our work we discovered that the most effective way to do so is by means of shrinking the index space of the table. The implementation of our final solution in DARKTHOUGHT needs less than 1 KBytes of memory. It runs at a blazing speed and does not affect any other part of the program through cache thrashing or related effects.



 

Created by Ernst A. Heinz, Thu Dec 16 23:28:11 EST 1999