Accessing Material Imbalance Information?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Steve Maughan
Posts: 1061
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Accessing Material Imbalance Information?

Post by Steve Maughan » Thu Dec 19, 2013 10:28 pm

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
http://www.chessprogramming.net - Maverick Chess Engine

User avatar
Rebel
Posts: 4663
Joined: Thu Aug 18, 2011 10:04 am

Re: Accessing Material Imbalance Information?

Post by Rebel » Fri Dec 20, 2013 12:10 am

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

mvk
Posts: 589
Joined: Tue Jun 04, 2013 8:15 pm

Re: Accessing Material Imbalance Information?

Post by mvk » Fri Dec 20, 2013 12:23 am

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.
[Account deleted]

jdart
Posts: 3816
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Accessing Material Imbalance Information?

Post by jdart » Fri Dec 20, 2013 12:27 am

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
Posts: 686
Joined: Thu Mar 03, 2011 3:57 pm
Location: Germany
Contact:

Re: Accessing Material Imbalance Information?

Post by tpetzke » Fri Dec 20, 2013 7:07 am

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

=======
http://macechess.blogspot.com - iCE Chess Engine

User avatar
hgm
Posts: 23615
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 Dec 20, 2013 8:42 am

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.

User avatar
Steve Maughan
Posts: 1061
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Re: Accessing Material Imbalance Information?

Post by Steve Maughan » Fri Dec 20, 2013 12:54 pm

Thanks everyone - food for thought!

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

Steve
http://www.chessprogramming.net - Maverick Chess Engine

User avatar
lucasart
Posts: 3037
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Accessing Material Imbalance Information?

Post by lucasart » Sat Dec 21, 2013 6:36 am

Steve Maughan wrote: 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)
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

mar
Posts: 1992
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 7:56 am

lucasart wrote: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 :)

User avatar
lucasart
Posts: 3037
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Accessing Material Imbalance Information?

Post by lucasart » Sat Dec 21, 2013 9:48 am

mar wrote:
lucasart wrote: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.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Post Reply