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
Accessing Material Imbalance Information?
Moderators: hgm, Rebel, chrisw
-
- Posts: 1221
- Joined: Wed Mar 08, 2006 8:28 pm
- Location: Florida, USA
Accessing Material Imbalance Information?
http://www.chessprogramming.net - Maverick Chess Engine
-
- Posts: 6991
- Joined: Thu Aug 18, 2011 12:04 pm
Re: Accessing Material Imbalance Information?
Here is an example (of the many ways), http://www.top-5000.nl/mb.htm
-
- Posts: 589
- Joined: Tue Jun 04, 2013 10:15 pm
Re: Accessing Material Imbalance Information?
I have an additive key for material, like this:
The high bits act as a hash.
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
[Account deleted]
-
- Posts: 4366
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: Accessing Material Imbalance Information?
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
--Jon
-
- Posts: 686
- Joined: Thu Mar 03, 2011 4:57 pm
- Location: Germany
Re: Accessing Material Imbalance Information?
Hi,
I'm lazy. I'm just misusing my normal zobrist keys for the material hash.
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...
I'm lazy. I'm just misusing my normal zobrist keys for the material hash.
Code: Select all
//Full Initial Calculation:
for (EPiece piece = W_PAWN; piece <= B_KING; piece++)
for (int i = 1; i <= bb.pcsTypeCnt[piece]; i++) hash ^= zKeys.squares[i][piece];
// And in makemove e.g if a piece is captured, promotions are similar
boardHistory->getCurrentState()->materialHash ^= zKeys.squares[bb.pcsTypeCnt[piece]][piece];
The hash hits for the material hash are rather high, so this code is executed rarely.
Thomas...
-
- Posts: 27795
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Accessing Material Imbalance Information?
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.
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.
-
- Posts: 1221
- Joined: Wed Mar 08, 2006 8:28 pm
- Location: Florida, USA
Re: Accessing Material Imbalance Information?
Thanks everyone - food for thought!
It seems as if this is one area where there is little consistency between engines,
Steve
It seems as if this is one area where there is little consistency between engines,
Steve
http://www.chessprogramming.net - Maverick Chess Engine
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Accessing 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:Steve Maughan wrote: How do others access material imbalance information?
* 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.
-
- Posts: 2555
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: Accessing Material Imbalance Information?
I do that too, except using 6 bits per piece type so 60 bits. My engine can never crash even with artificial positions.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).
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
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Accessing Material Imbalance Information?
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.mar wrote:I do that too, except using 6 bits per piece type so 60 bits. My engine can never crash even with artificial positions.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).
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
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.