Magic end-game material hash?

[AlvaroBegue]

Can you adapt a Bloom filter to do what you want? For instance, you could have an array of 256 values initialized to 0. If you want to store the value 300 for some material configuration, compute two hash functions of the material configuration and store 300 in both locations (actually, replace the existing value with 300 only if the value that was there was smaller than 300, in general). At lookup time, compute both hash functions, retrieve the corresponding locations and take the minimum. If you are not storing too many material configurations, you might be able to find two hash functions that make this scheme work.

[hgm]

Interesting idea. Especially if the second hash function could be something that the engine calculated ayway. Otherwise nothing would be saved compared to calculating a key of twice the size.

Now that the design of the engine is taking shape, it seems the following quantity is quite useful to maintain during search: a packed value of two 2-bit counters for the Queens + Rooks of each player, plus for single-bit flags for the presence of the 4 Bishops.

This can then be easily tested for slider presence, to switch off null move if there is none. It can also be used to detect presence of a Bishop pair. (Or actually, since I am doing that incrementally, of whether a lone Bishop is captured, and the incremental pstEval has to be adjusted for that.) Finally it is also helpful for detecting unlike Bishops, as it does indicate which Bishops are present.

This information can also be used to resolve the ambiguity between minors, releaving the material key from this task. So the 'reduced key' that just keeps track of the number of Pawns, minors and majors+Queens will be satisfactory in that case. A table indexed by the key can contain pointers to handler routines, (basically the implementation of a 256-case switch() statement), and the KM(P...), KMM(P) and KMMM(P) handlers could then determine the number of Bishops amongst the minors, and take decisions based on that. KM(P...) with a Bishop could then test the opponent's slider status for a Bishop of the opposite shade. KMM(P) could test for absence of Bishops, ad conclude KNN(P) from that, and for KMMM(P) it becomes relevant if the opponent is KR(M). None of that would slow down the search in cases that are not the end-game where it matters. The other cases would just exit the 'switch' immediately through the 'default' case.

The most-common handler would just figure out the opponent piece material from the opponent's key, to see if it is in a 'minor-ahead' situation without Pawn, or 'sacrificeable minor' with a Pawn. For this it only has to know the 'equivalent minor count' (where R=2 and Q=4) of the opponent's material combination, for which there could be another 256-entry lookup table.

There will actually be two sets of handlers, as I plan to use this material key for two purposes: one in the evaluation function, to do the actual score reduction at the end in the case of detected drawishness. This only has to bother with the end-games that can actually be reduced, i.e. 0 or 1 Pawn, at most 3 pieces (all for the leading side). The second place is for determining whether the futility condition has to be relaxed, because we might get into a discount situation after capture. This has to additionally handle all combinations with 2 Pawns and <= 3 pieces, and those with 0 or 1 Pawn and 4 pieces, and already trigger in a 'two-minors-ahead' situation, to make sure we will consider capturing one of those minors to achieve a draw (e.g. the recapture KxB in KBBK, being worth a full B-pair rather than just a Bishop).