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: 21473
Location: Amsterdam

PostPost subject: Magic end-game material hash?    Posted: Thu Nov 30, 2017 11:35 pm Reply to topic Reply with quote

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