Magic end-game material hash?

[hgm]

I am looking for a hash key that is the sum (or XOR) of individual piece contributions (so that it can be incrementally updated) that would uniquely identify material combinations of one player that lack mating potential, or could otherwise be candidate for reduction of the advantage due to fragility of the mating potential. Normally end games can be drawish if they have 0 or 1 Pawns, and not more other material than Q+minor (E.g. KQBKQ).

I want to use this key for determinig the limit for futility pruning, however, so it must be able to already flag situations with one more piece than the drawish endgame, to see if capture of that piece is made worthwile by triggering the reduction of what is left. E.g. in KBPK, when 300cP below alpha, I don't want KxP to be futility pruned because the Pawn is worth a lot less than 300cP, because in this situation it is actually worth over 400cP, as KBK = 0. Similarly, in KQBPKQ the Pawn is worth a lot more than just a Pawn, as KQBKQ is also almost certainly a draw, and will be discounted to,perhaps, +75cP. So the Pawn is worth > 300cP.

The snag is that the key must be only 8 bits. (As I am writing a chess program for an 8-bit computer.) ow even without promotions the number of possible material combinations for 1 side is 3*3*3*2*9 = 486. This is larger than 256, so obviously there cannot be a perfect hash or multi-dimensional array-type access. Collissions are unavoidable. Even if I reduce the requirement somewhat by not being interested in seeing the difference between RR and Q. (So there are only 5 QR states, instead of 2*3.) I am just hoping the collisions can be focused in a part of the table with the 'crowded' combinations, and kept out of the part of the table with up to 7 men.

I was wondering if something like this is already kown. an alternative would of course be to use a wider key. But since the overloadig of the key is less than a factor two, I had at least some hope that I would have to update only a single key byte. Of course I could also involve the game state, and only check the material key when the game advances to the phase with only half the material. Point is that I am not sure it makes sense to have a material key in the usual sense, as interpolation between end-game and opening evaluations would be very difficult, on a machine without multiplication.

But as a poor-man's substitute I could perhaps use the game phase as a trading bonus for the side that has a winning advantage (say > 150cP), to encourage him to advance the game phase. In that case the primary filter for testing drawishness could be based on that game phase (which might be just a piece count).

[D Sceviour]

Assuming there is only one type of piece on the board (e.g. KRKN) and no pairs then a non-pawn material key can be kept in 8 bits:

WR
BR
WN
BN
WB
BB
WQ
BQ

Using a 13-bit number (0x1FFF), an additional 4 bits can store the difference between black and white pawns. The last bit has to flag whether black or white has more pawns. This could suffice for a great many endgames.

1 1111 1111 1111

Further, the extra 3 bits could be used in a 16-bit number to indicate many different ideas. For example, both sides have two rooks, and rook redundancy.

[hgm]

The best I could come up with so far is the weighting minor=6, R=5, Q=2R=10, P=25. This gives a perfect hashing, (it is basically the 1,5,25 3dim-array indexing, where the 1 is shifted to 6 by adding one of the higher weights (5), which can always be done without introducig collisions), ignoring the difference between B-N on the one hand, and Q-2R on the other. That means there are 0-4 minors and 0-4 'rooks', 5*5 = 25 combinations. The maximum value is 8*25 + 10 + 2*5 + 4*6 = 244, so it fits in one byte.

The only combinations eligible for discount are those without Pawns, or with (maximally) 3 pieces + 1 Pawn. These can be reached from positions with maximally 4 pieces and 1 Pawn, or 3 pieces and 2 Pawns. The highest key for 3 pieces (if we count a Q for 2) is MMM = 18, and the lowest (pseudo-)4-piece key (for QRR) is 20. So MMMPP is 68. The primary filter for the drawishness code could be key <= 69.

This then includes all combinations with only a single Pawn, as the maximum pawnless key is 44 (QRRMMMM). This is perfect, as they all could convert to a pawnless end-game by taking the Pawn, and would then have to be discounted by 50%.

Note that this key would also contain all information needed to reconstruct the game phase, which in general does have equal weights for all minors, and weight Q twice as much as R ({1,2,4}, {1,3,6} or {2,3,6}). So a lookup in a 244-entry table could give the game phase. Now the game phase itself is hardly useful on a machine without multiplication, but the lookup table could contain a simplification bonus to be added to winning scores (say >150cP), of th kind 5*(12-4*nQ-2*nR-nB-nN) + 7*min(5,nP). This encourages trading pieces when ahead, but in contrast to the usual interpolation method modestly discourages trading of Pawns in this situation when you have 5 or fewer left. Since it is a table, this could easily be made non-linear, by making the last Pawns count heavier, e.g. -16, -2, 10, 20, 28, 35 instead of 0, 7, 14, 21, 28, 35 for 0-5 Pawns, so that it gets extra stingy over itse forelast Pawn. (The last Pawn will of course mostly be taken care of by the drawishness recogition code.)

I probably can afford a second table with only half that bonus, to be applied when 125 < score < 150, for a less bumpy eval. And perhaps even get subtracted when 75 < score < 100, to discourage trading when it will likely only hasten an unavoidable draw. (But the table for that should probably also discourage trading Pawns.)

If the 'impending drawishness' filter triggers, futility pruning of Pawn capture should be suppressed if alpha < 0 (i.e. score discounting towards zero could help to get above alpha). More subtly, we could only suppress it if we are in the 'minor behind' situation. When behind more (e.g. R vs RRP behind), the Pawn capture would not lead to any unexpected score bonus. For capturing the forelast Pawn we should also beware of the 'equal material with minor' situation, as the resulting end-game would be discounted because of the possibility to sac the minor for the last Pawn. But in that case we could remain at most a Pawn behind, so the discount would not amount to much. With a minor behind, we stand to gain most (like 75%) of the value of that minor, in addition to the captured Pawn. But we could not gain more. So shifting down the futility threshold by the value of a minor should also be sufficient. (It works even in the KBPK situation.)

The only regret is that it is ot possible to recognize KNNK as a draw from the key alone, as it does not distinguish between minors. (And, of even less importance, that it cannot distinguish between KBBNKR and KBNNKR.) For this we would either have to update a second piece key during MakeMove for the entire game, or do a somewhat cumbersome explicit test for two Knights (e.g. in the piece list) if the described key says our only possession is KMM. It might be possible to compare this with Bishop-pair scoring; the latter requires us to be aware of the number of Bishops, and if that is zero...

Discounting of unlike Bishops is another open problem. This has to be done even with many Pawns.

[D Sceviour]

I want to use this key for determinig the limit for futility pruning, however, so it must be able to already flag situations with one more piece than the drawish endgame, to see if capture of that piece is made worthwile by triggering the reduction of what is left.

It is difficult to be all things to all demands. Unlike pawn hash, material hash never seemed to be of much benefit. The extra hash calculation was little improvement over simply adding up the material. Even if multiple promotions are unlikely to be found in a principal variation, the search still has to be prepared to identify and reject multiple promotions.

It is not clear if material inadequacy is reason to reduce depth or prune for futility. Stockfish can squeeze a win out of KRKN unless the other engine can search deep enough to find the refutation (or there is an egtb).

[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).