Why material imbalance tables are needed

[Michael Sherwin]

Most chess programs have fixed values for the pieces.

These values have been tuned to get the best results for any given program.

Even so, these programs are still limited in strength, because, they get into positions where these values are just plain wrong and they make bad decisions based on them.

If a program could look up precomputed material balances in a table it could play much more strongly.

One way of doing this would be to analyze a database of high quality games. As each game is being processed, every time that the material changed, but, was still within a certain margine, update a hash key based on the numbers of each type of piece. So for example, 8 white pawns have one hash value and 7 white pawns has a different hash value. It does not matter where the pawns are on the board, as that is handled by the traditional evaluation function. Now just look up the material balance from the table as all reasonably close balances are there. Or just compute it normally if it is not in the table as that would mean that it is not a reasonably close balance.

[Tord Romstad]

One way of doing this would be to analyze a database of high quality games. As each game is being processed, every time that the material changed, but, was still within a certain margine, update a hash key based on the numbers of each type of piece. So for example, 8 white pawns have one hash value and 7 white pawns has a different hash value. It does not matter where the pawns are on the board, as that is handled by the traditional evaluation function. Now just look up the material balance from the table as all reasonably close balances are there. Or just compute it normally if it is not in the table as that would mean that it is not a reasonably close balance.

I've been thinking a lot about ideas similar to what you describe recently, but I think the exact method you describe above would be too simplistic to work well. I think you at least have to factor in the pawn structure and the colors of the bishops for both sides in addition to material. The problem with this is that you will end up with a table far too big to fit in RAM, and looking up the current material/pawn structure pattern in a disk file at every node would obviously be too expensive.

One possible solution to this problem would be to store not only patterns and scores in the disk file, but also the most common "child patterns" for each pattern. At the beginning of a new search, the program could initialize a hash table by reading in all patterns which occur frequently in games beginning with the pattern at the root node, and use this table in the search.

The material/pawn structure pattern file could also contain additional information, like thematic moves for both sides, or particularly good or bad squares for the individual piece types.

Perhaps it would be better to use a very rough classification of the pawn structure instead, for instance just closed/open/half-open centre combined with a list of open files for each side. There are countless approaches to try, but I don't think that there is a lot to gain by only looking at the material balance.

Tord

[hgm]

Joker keeps a material counter for each side, (differentially updated) where it uses B=1 or 2, N=4, R=12, Q=36. This gives a unique value for each piece composition, which is then uses in 144-entry lookup tables to get information on total material value, value of the highest piece, of the highest two pieces, the number of pieces, flags indicating if null-move pruning is allowed, etc. Pawn count is kept separately (in another byte of the same integer variable, so it can be updated together, by setting P = 256).

In the future I plan to use the pair of piece indicators (ignoring the Pawn part) as index in a larger (144x144) table for getting Pawn-evaluation parameters (base value of a Pawn, value of a passer, penalty for backward/isolated Pawns).

Currently the parameters only depend on the difference of the number of pieces: Passer bonuses are reduced by a factor 2 for the side with fewer pieces, and multiplied by 1.5 for the side with more pieces. Note that my encoding distinguishes Bishops by square color, so the table can take account of like Bishops / unlike Bishops scoring.

[Daniel Mehrmann]

Hi Michael,

you're on the right way
I'm working on such stuff already and you don't need a hashkey for your table, which saved a lot of space. Just calculate the max possible material if we assume only 2 minor or 2 major can be exist. If we have 3 bishops for example you don't need such table.

Ok, lets talk about some secrets and ideas.
So , here we go:

Code: Select all

typedef struct material_t {
	int light;			//material white
	int dark;			//material black
	int state;			//bit based flagtable
	EVAL_S evalFactors; //stored integer factors for mobility, 
						//pawn damged, king attack and so on..
} MATERIAL_STRUCT;

//2,4 mb total size
MATERIAL_STRUCT MaterialTable[9*3*3*3*2*9*3*3*3*2];

//key build on material:
key =  bq  +  br *2 + bb *2*3 + bn *2*3*3 + bp *2*3*3*3 + wq *2*3*3*3*9 + wr *2*3*3*3*9*2  + wb *2*3*3*3*9*2*3 +  wn *2*3*3*3*9*2*3*3 +  wp *2*3*3*3*9*2*3*3*3;

Best,
Daniel

[mclane]

why don't you use the ECO code to differenciate the positions ?

[hgm]

It seems important to allow 2 Queens, as this is the only way through which endings with Queens + Pawns are won.

It might also be desirable to maintain easy separability of the index into a white and black part, for not wasting unnecessesary space on tabulating things that depend only on the piece makeup of one side. (E.g. null-move pruning enabled on basis of your own pieces, King safety based on the opponent's pieces.)

Note that in the scheme you propose 2*3*3*3*9 = 486 is nearly 512, so with hardly any loss of space you could encode the white Queen as 512, allowing the white makeup to be extracted by a >>9 operation.

I am not really convinced that it is useful to keep track of the number of Pawns, as this is not really a good indicator for the Pawn situation. Other aspects of the Pawn structure can be more important. (E.g. you might have a doubled h-Pawn, which is closer to zero Pawns than to two.)

[Tord Romstad]

I am not really convinced that it is useful to keep track of the number of Pawns, as this is not really a good indicator for the Pawn situation. Other aspects of the Pawn structure can be more important. (E.g. you might have a doubled h-Pawn, which is closer to zero Pawns than to two.)

I think pawns are extremely important, and as Kaufmann's paper shows, at least the value of knights and rooks vary considerably with the number of pawns. But I agree that something more than just the number of pawns is needed. In particular, the relative values of light-squared bishops, dark-squared bishops and knights depend to a very large extent on the locations and mobility of the pawns.

A problem with all these things is of course how it interacts with the previously defined evaluation terms, especially mobility. For instance, the main reason why rooks are usually stronger with few pawns on the board is that they have higher mobility.

Tord

[Gerd Isenberg]

why don't you use the ECO code to differenciate the positions ?

Because same ECO code may lead to a lot of different material constallations and even more different positions. It might be worth to look for determinant center-pawn formation though, specialy to enumerate closed or rammed "strategical" formations like advanced french, benoni and rudi (Kmoch's term of benoni structure without c-panws) etc, and to index tables with, to find out where the good or bad places are for pieces or what lever-possibilities are required. Also i can imagine that majorities with closed/open center give some hints what to do - like I lose that pawn ending anyway - so I have to keep my pieces to attack the king.

I use the classical piece-signature of Chess 4.5 iirc, five incremental updated nybble counters per side inside one 64-bit word, modulo some small prime number (by reziprocal fixed-point multiplication) to index a material-hashtable - collision test included.

[Michael Sherwin]

I've been thinking a lot about ideas similar to what you describe recently, but I think the exact method you describe above would be too simplistic to work well.

Most of the time, simplistic ends up being better than complicated. The pawn structure and piece mobility factors may be best handled in the traditional style. The material balance tables will just supply a gentle modifier to keep from making mistakes based on static piece values that are 'out of whack' with praxis. The most appealing aspect of what I propose, is that it is within my ability to do it! And it can be done quickly, so it would not cost all that much if it were a failure. And if it does work, then it would provide a 'measureing stick' to judge the possible gain by trying something more complicated.

I think that hashing in the pawn structure and having specialized piece square tables as well as material composition factors is best for openings and can be stored in seperate files based on eco codes. These files would be tuned to the programs opening book and it would also allow for learning based on an engines results.

But, with the new 32GB memory sticks, anything is possible!

[Michael Sherwin]

Joker keeps a material counter for each side, (differentially updated) where it uses B=1 or 2, N=4, R=12, Q=36. This gives a unique value for each piece composition, which is then uses in 144-entry lookup tables to get information on total material value, value of the highest piece, of the highest two pieces, the number of pieces, flags indicating if null-move pruning is allowed, etc. Pawn count is kept separately (in another byte of the same integer variable, so it can be updated together, by setting P = 256).

In the future I plan to use the pair of piece indicators (ignoring the Pawn part) as index in a larger (144x144) table for getting Pawn-evaluation parameters (base value of a Pawn, value of a passer, penalty for backward/isolated Pawns).

Currently the parameters only depend on the difference of the number of pieces: Passer bonuses are reduced by a factor 2 for the side with fewer pieces, and multiplied by 1.5 for the side with more pieces. Note that my encoding distinguishes Bishops by square color, so the table can take account of like Bishops / unlike Bishops scoring.

Nice, very nice! How many bytes of total memory would be needed for a (144 x 144) table?