ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Magic end-game material hash?
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
H.G.Muller



Joined: 10 Mar 2006
Posts: 21465
Location: Amsterdam

PostPost subject: Re: Magic end-game material hash?    Posted: Fri Dec 01, 2017 2:47 pm Reply to topic Reply with quote

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.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
Magic end-game material hash? H.G.Muller Thu Nov 30, 2017 11:35 pm
      Re: Magic end-game material hash? Dennis Sceviour Fri Dec 01, 2017 1:50 pm
      Re: Magic end-game material hash? H.G.Muller Fri Dec 01, 2017 2:47 pm
      Re: Magic end-game material hash? Dennis Sceviour Fri Dec 01, 2017 4:18 pm
      Re: Magic end-game material hash? Álvaro Begué Fri Dec 01, 2017 7:03 pm
            Re: Magic end-game material hash? H.G.Muller Sat Dec 02, 2017 9:29 am
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads