H.G.Muller
Joined: 10 Mar 2006 Posts: 21783 Location: Amsterdam

Post subject: Re: Magic endgame material hash? Posted: Fri Dec 01, 2017 2:47 pm 


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 3dimarray 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 BN on the one hand, and Q2R on the other. That means there are 04 minors and 04 '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)4piece 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 endgame 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 244entry 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*(124*nQ2*nRnBnN) + 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 nonlinear, by making the last Pawns count heavier, e.g. 16, 2, 10, 20, 28, 35 instead of 0, 7, 14, 21, 28, 35 for 05 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 endgame 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 Bishoppair 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. 
