Accessing Material Imbalance Information?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 23364
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Accessing Material Imbalance Information?

Post by hgm » Sat Dec 21, 2013 11:23 am

The downside of course is that you would have to hash the imbalance information (if you don't want to recompute it on every evaluation), because 2^40 or 2^60 is way too large to exhaustively tabulate it. And allowing 'over-complete' material combinations is of course nice (I definitely applaud that), but it would be of very little value if you would not actually have a way to compute the imbalance correction for such unusual material (e.g. for 3Q vs 7N).

I must admit that I am tempted to switch to hashing the material imbalance, rather than exhaustively tabulating it, however. A hash key can be simply calculated from the material signature (the packed counters) by a multiply + shift, and the entry could contain the signature and data.

The main reason for switching to hashing is that an exhaustive table gets awfully large when the number of piece types increases. In Capablanca Chess, for instance, it is important to distinguish Q, C and A in the signature (as KQNKQ is draw, but KQNKA is won). Packed counters could be 2 bits for N, B, R, A, C, Q plus 4 bits for Pawns, or 16 bits per side, perfectly fitting a 32-bit signature. This would allow 0-3 pieces of any type (and 0-15 Pawns), except that for the Bishops I would prefer to use 1 bit per square color. (Promotion to N, B or R is virtually never useful when you can also choose A, C or Q.)

For truly weird initial positions, the engine could always construct a custom packing of the counts (by making all masks, sifts and unit counts variables, rather than constants) depending on the material that is on the board in the initial position.

mar
Posts: 1979
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Accessing Material Imbalance Information?

Post by mar » Sat Dec 21, 2013 11:59 am

hgm wrote:A hash key can be simply calculated from the material signature (the packed counters) by a multiply + shift, and the entry could contain the signature and data.
I like this idea, because having a separate material hash would put more pressure on my domove which is already complicated enough because I incrementally update psq values as well as material key.
I think that sufficiently good magic multiplication constant may do (for good distribution), so computing material hash from material key could be straightforward: mask out pawns, multiply and mask lower bits (or shift).
I will most likely try this if I ever decide to implement imbalances in my engine.

User avatar
hgm
Posts: 23364
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Accessing Material Imbalance Information?

Post by hgm » Sat Dec 21, 2013 12:20 pm

Why would you want to mask out Pawns? They should have non-additive effects as well. (The best-known being the dependance of the B-N difference on the number of Pawns.) Also whether lack of mating potential in the piece material hurts or not is highly dependent on the number of Pawns. (KBKP: dead draw; KBPPKPPP: usually an easy win.)

That being said, if you choose the magic multiplier right, you might be able to make the result of the multiply independnet of the Pawn counters. (E.g. if the highes 8 bits were Pawn counters, multiplying by a 256 multiple would shift them out of the word.)

mar
Posts: 1979
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Accessing Material Imbalance Information?

Post by mar » Sat Dec 21, 2013 12:35 pm

hgm wrote:Why would you want to mask out Pawns? They should have non-additive effects as well. (The best-known being the dependance of the B-N difference on the number of Pawns.) Also whether lack of mating potential in the piece material hurts or not is highly dependent on the number of Pawns. (KBKP: dead draw; KBPPKPPP: usually an easy win.)
Actually you're right. I could then have one material hash table for everything including imbalances and recognizers.
Right now I have two small tables for recognizers (binary search): one with full key and another which I call scale recognizers with one side masked out to adjust scores where one side has no mating potential (to avoid showing +score in positions where one side has two knights and the other has king+some pawns for example).

sandermvdb
Posts: 153
Joined: Sat Jan 28, 2017 12:29 pm
Location: The Netherlands

Re: Accessing Material Imbalance Information?

Post by sandermvdb » Fri Feb 23, 2018 7:33 am

hgm wrote:A hash key can be simply calculated from the material signature (the packed counters) by a multiply + shift, and the entry could contain the signature and data.
Sorry for bringing up an old topic, but how can you calculate the hash when you have one number containing all material counters? Multiply + shift? I don't understand how that could work. I am using the following scheme:
qqqrrrbbbnnnppppQQQRRRBBBNNNPPPP

So 32 bits which is used as an index for a table with 2^14 (or so) entries. If I am going to multiply or shift, I'll lose information and get index collisions.

User avatar
hgm
Posts: 23364
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Accessing Material Imbalance Information?

Post by hgm » Fri Feb 23, 2018 9:55 am

You just do MM64*packedCounters >> 44, where MM64 is an unsigned 64-bit magic multiplier. This would give you a 20-bit number you could use as index in a 1M-entry material hash table. In hashing there will in general be collisions, but you can resolve those by storing the 32-bit counter word as a signature. Having to include a signature will of course drive up the size of an entry, perhaps by a significant factor (e.g. from 1 to 5 bytes). But it allows you to reduce the number of entries hugely, compared to the astronomical size you would need to store all over-complete material combinations (such as 3Q vs 7N). Or the huge size you would need in variants that also feature Archbishop and Chancellor, ad unp to 10 Pawns. Perhaps using 64K entries would already give you a hit rate > 99.9%, and then you don't care that it is 5 bytes per entry (320KB in total).

sandermvdb
Posts: 153
Joined: Sat Jan 28, 2017 12:29 pm
Location: The Netherlands

Re: Accessing Material Imbalance Information?

Post by sandermvdb » Fri Feb 23, 2018 4:49 pm

You were right, just copy with a random number :)
I had the wrong idea that multiplying is the same as shifting left, which is true for multiplying with 2,4,8, etc.
16k entries gives 99,5% hit :)

User avatar
cdani
Posts: 2103
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Accessing Material Imbalance Information?

Post by cdani » Sun Feb 25, 2018 12:21 pm

In Andscacs I use

Code: Select all

struct TMaterial taulamaterial[maxwhitequeen][maxwhiterook][maxwhitebishop][maxwhiteknight][maxblackqueen][maxblackrook][maxblackbishop][maxblackknight];
All max values are 4.

Is an small array more than enough to store exact values for all the meaningful piece combinations. And I store only the ones I have actually tuned.

Joost Buijs
Posts: 892
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Accessing Material Imbalance Information?

Post by Joost Buijs » Mon Feb 26, 2018 9:21 am

I use 40 bit for the material index as well.

With a mask operation I detect positions which have no more than 3 knights, bishops, rooks or queens for each side, if this is the case it is very simple to calculate a 24 bit key which I use as an index into a 16 MB. table with scaling information, positions with more than 3 pieces of each type are always scaled 100%.

The only problem is to fill the scaling table with useful information, in practice most of the entries in the table are also set at 100%.

Post Reply