Accessing Material Imbalance Information?

[Steve Maughan]

Maverick has no knowledge of material imbalance (over and above piece values). I've seen some ugly games where Maverick has come out of the wrong end of imbalanced material exchange. So I think this is the next piece of knowledge I'm going to add.

My question is - what's the best way to encode the material imbalance? The most obvious is to simply count the pieces for each side and use this to look-up the imbalance. But this seem a little clumsy and possibly expensive. I'd prefer some sort of material hash solution but can't think of a slick solution.

How do others access material imbalance information?

Steve

[Rebel]

Here is an example (of the many ways), http://www.top-5000.nl/mb.htm

[mvk]

I have an additive key for material, like this:

Code: Select all

/*
 *  Constants for the material key
 */
#define BOARD_MATERIAL_KEY_WHITE_PAWN           0x514e000000000001ull
#define BOARD_MATERIAL_KEY_WHITE_KNIGHT         0x6ab5000000000010ull
#define BOARD_MATERIAL_KEY_WHITE_BISHOP_LIGHT   0x2081000000000100ull
#define BOARD_MATERIAL_KEY_WHITE_BISHOP_DARK    0xb589000000001000ull
#define BOARD_MATERIAL_KEY_WHITE_ROOK           0xae45000000010000ull
#define BOARD_MATERIAL_KEY_WHITE_QUEEN          0x9ac3000000100000ull
#define BOARD_MATERIAL_KEY_BLACK_PAWN           0x696d000001000000ull
#define BOARD_MATERIAL_KEY_BLACK_KNIGHT         0xd903000010000000ull
#define BOARD_MATERIAL_KEY_BLACK_BISHOP_LIGHT   0x3d15000100000000ull
#define BOARD_MATERIAL_KEY_BLACK_BISHOP_DARK    0x67f5001000000000ull
#define BOARD_MATERIAL_KEY_BLACK_ROOK           0x7de9010000000000ull
#define BOARD_MATERIAL_KEY_BLACK_QUEEN          0xa96f100000000000ull

The high bits act as a hash.

[jdart]

I have a packed bit array that encodes how many pieces of each type there are. It is updated on each move. This makes it easy to test for particular piece configurations.

--Jon

[tpetzke]

Hi,

I'm lazy. I'm just misusing my normal zobrist keys for the material hash.

Code: Select all

//Full Initial Calculation:
for &#40;EPiece piece = W_PAWN; piece <= B_KING; piece++)
		for &#40;int i = 1; i <= bb.pcsTypeCnt&#91;piece&#93;; i++) hash ^= zKeys.squares&#91;i&#93;&#91;piece&#93;;

// And in makemove e.g if a piece is captured, promotions are similar
boardHistory->getCurrentState&#40;)->materialHash ^= zKeys.squares&#91;bb.pcsTypeCnt&#91;piece&#93;&#93;&#91;piece&#93;;

In my evaluation I check for certain imbalances, just with some "if" statements. If one is found the score associated with it is added to the material value and becomes part of the hashed material score.

The hash hits for the material hash are rather high, so this code is executed rarely.

Thomas...

[hgm]

In Spartacus I don't hash material, but I have a complete table with all possibililities, which is layed out like a multi-dimensional array. So it can be indexed by

nWLB + 2*nWDB + 4*nBLB + 8*nBDB + 16*nWN + 48*nBN + 144*(nWQ + 2*nBQ + 4*nWR + 12*nBR + 36*nWP + 9*36*nBP)

where nWQ = number of white Queens, and nBLB = number of black Bishops on dark squares, etc. That seems clumsy to evaluate, but of course it is incrementally updated in MakeMove, by merely subtracting the multiplier for each piece that gets captured (the multipliers being stored in the piece list). For orthodox Chess the array is only 81*36*144 ~ 410k entries. It does not allow for multiple Queens or otherwise over-complete material, but since Pawns have the largest strides, such material combinations will never cause out-of-bounds access of the material table, just overflow into another hyper-plane of it, returning a non-sensical value. (The Rybka trick.) As the value is only a relatively small correction to the score, this does not hurt. Purists can always redefine the mapping in the root and re-initialize the table as material is captured, to allow for such possibilities long before promotion becomes a possibility. Note that light and dark Bishops are considered different piece types, so it can be seen from the index if there is a drawish unlike-Bishops situation.

The table contains just 1 byte per position, so that makes it bearably small. So I figured there wan no point in hashing it into a smaller table, mimicking in software what the CPU's caching hardware already does. Codes 0-200 are just added to the eval score (white POV) after subtracting 100, allowing corrections of upto 100 cP in either direction. Codes above 200 are intercepted by a single compare and branch, and invoke special end-game knowledge. These can be of two types (again distinguished by a simple compare and branch): one type is used (after subtracting 201) to index a table of white and black factors with which the naive evaluation should be multiplied (the factor for the side that is ahead according to this naive evaluation being picked). This is used to discount drawish end-games. The remaining codes can be used as index in a table of routines that implement special knowledge, depending not only on material, but on actual board position (e.g. KPK, KQKP, KBPK).

Note that the lowest bits of the index can be directly interpreted as flags indicating which Bishops are present; they can thus be used in the naive evaluation for awarding bonus/penalty for good or bad Bishops, in combination with light/dark Pawn counts obtained from the Pawn hash. Also note that positions with 2 white Queens overflow into positions with one more Black Queen, and that two Black Queens would be seen as a White Rook. This avoids such positions (which amongst the over-complete ones are the most likely to occur) would map onto positions with special codes, which typically apply to positions with minors-only.

[Steve Maughan]

Thanks everyone - food for thought!

It seems as if this is one area where there is little consistency between engines,

Steve

[lucasart]

How do others access material imbalance information?

Very simple: a material key. You can use random numbers like zobrist, or build a key directly. I build the key directly in DiscoCheck:
* bit 0..3 = nb of white pawns
* bit 4..7 = nb of black pawns
* bit 8..11 = nb of white knights
* bit 12..15 = nb of black knights
* etc.

So 8 x 5 = 40 bits used. Unlike many engines, mine will not crash or become buggy when there are many pieces of the same type (often more than 3 is enough to crash many engines that have some hardcoded limit). 8 is a conservative limit (in theory you can have 10 rooks, 2 initial ones and 8 promoted ones, but in practice limiting to 8 is fine).

The material key can be used for many things, including imbalance evaluation.

The implementation is all rather trivial (update your key dynamically and also write a function to compute it from scratch and put an assert() to verify their equality after every move is played/undone).

The real difficulty is tuning. Yes, you can add a ton of parameters, and give them some guessed weights. But will that make your engine better? Will it make it easier to improve in the long run? Already with piece values you have:
* pawn opening and endgame: 2 param
* knight, bishop, rook, queen: 4 param
* bishop pair opening and endgame: 2 param

Total = 8 param. How do you co-tune 8 parameters? I've never had any success with CLOP for tuning more than 3 at once, and already 3 is pretty hard. So writing code and adding feature is easy, but the real wisdom is to use restraint.

As far as DiscoCheck is concerned, the only material imbalance knowledge I have are:
* bishop pair bonus
* rook pair penalty (redundancy)

[mar]

So 8 x 5 = 40 bits used. Unlike many engines, mine will not crash or become buggy when there are many pieces of the same type (often more than 3 is enough to crash many engines that have some hardcoded limit). 8 is a conservative limit (in theory you can have 10 rooks, 2 initial ones and 8 promoted ones, but in practice limiting to 8 is fine).

I do that too, except using 6 bits per piece type so 60 bits. My engine can never crash even with artificial positions.
6 bits and 63 maximum may seem too much but it doesn't really matter if you use 40, 50 or 60 bits. It's more than 32 anyway so no direct indexing possible.
I'm doing this since cheng3 with the purpose of detecting simple endgame material configurations and it works fine for me.
I even use it to detect some trivial draws by insufficient material.
The good thing about this is that you can:
- mask out information you don't need
- quickly detect things like has some side mating material?, pair of rooks? etc. => just mask and compare
Right now I have a simple table and do a binary search on that (at the moment the table is so small that this is probably overkill and linear search would do better).
I'm not sure if this approach would be good for material imbalance though.
So a small hashtable and material hash key would probably be a better solution (this is what Thomas said).
Of course noone says you can't have both

[lucasart]

So 8 x 5 = 40 bits used. Unlike many engines, mine will not crash or become buggy when there are many pieces of the same type (often more than 3 is enough to crash many engines that have some hardcoded limit). 8 is a conservative limit (in theory you can have 10 rooks, 2 initial ones and 8 promoted ones, but in practice limiting to 8 is fine).

I do that too, except using 6 bits per piece type so 60 bits. My engine can never crash even with artificial positions.
6 bits and 63 maximum may seem too much but it doesn't really matter if you use 40, 50 or 60 bits. It's more than 32 anyway so no direct indexing possible.
I'm doing this since cheng3 with the purpose of detecting simple endgame material configurations and it works fine for me.
I even use it to detect some trivial draws by insufficient material.
The good thing about this is that you can:
- mask out information you don't need
- quickly detect things like has some side mating material?, pair of rooks? etc. => just mask and compare

Yes, what is useful about is indeed that you can mask out the bits you don't want and quickly retrieve some info in a branchless way.

Another thing I like with using 4 bits is that you can read the key in hexadecimal and know directly what it means (4 bits = 1 hex digit).

PS: Limit is 15 for 4 bits. I don't know why I had 8 in mind earlier. Scrap that.