Material Tables and Indexing

[Edsel Apostol]

I had been experimenting with adding a material correction table for my engine lately. I am using the method in Strelka that was also mentioned in other posts before Strelka code has came out.

I noticed that in positions where there are more than one queen for one or both sides, the game phase indexed by the material sum is not equal to the one when you are going to solve it on the fly.

This means that this method doesn't produce unique material signatures for some cases and it annoys me. There are other material signatures that will map to the same signature and there materials vary greatly that when you use this to index the game phase it would be inaccurate.

I want my implementation to be really correct. Is there any better ways to hash a unique material signature? I am thinking of reversing the order of queens and pawns so that when there are more than one queen of one side on the position, it will overflow in the table and it will not coincide with other material signatures.

I know this has been discussed somewhere but I couldn't find the threads. What all of you think of this?

[hgm]

The Strelka table was not so much a hash, as well a multi-dimensional array. And that of course gives trouble when you overflow the array bounds, which apparently were not chosen to handle multiple Queens.

If you want to handle this case correctly, making the array larger would solve it. Using Queens for the index with the largest stride is a good idea then, as it makes the usually unused part of the table with multiple Queens contiguous. I would use Pawns for the index with the smallest stride.

[mjlef]

I use a 16 bit value for each side, which has fields for the number of each piece type (other than king, of course):

QQQRRRBBBNNNPPPP

This handles up to 15 pawns, 7 bishops, 7 knights, 7 rooks and 7 queens. I know it is possible to have lots of promotions and end up with 10 rooks or something, but I just ignore that. When it comes time to apply the material table you can just use a test like this:

if (((pieces[white]& MagicMask)==0) && (pieces[black]& MagicMask)==0))
{
//add in the material bonus
}

You just set the bits in MagicMask to handle the cases where the material array would not handle them. Say more than one queen:

MagicMask = 0xc0000;

You can set other bits if you cannot hanlde say 4 rooks and 4 bishops and 4 knights, for example.

These bit fields have lots of uses in things like detecting specific endgames:

if (pieces[white]==RookPawn) .... handle rook and pawn ending...

just define RookPawn to be 0x401

Old NOW had a very small material bonus array, and only handled up tp 1 queen, 2 rooks, 2 bishops, 2 knights and 3 pawns. This was to keep it to 1024 elements (2^10) because it had to run in 640 k DOS. You can still pack a lot of endgame knowledge even in a small array like this. And if you do not want to use the Rybka/Strelka multiplication index, the array index can be quickly calculated from AND and shifts of these 16 bit materail words.

Mark

[Zach Wegner]

I had been experimenting with adding a material correction table for my engine lately. I am using the method in Strelka that was also mentioned in other posts before Strelka code has came out.

I noticed that in positions where there are more than one queen for one or both sides, the game phase indexed by the material sum is not equal to the one when you are going to solve it on the fly.

This means that this method doesn't produce unique material signatures for some cases and it annoys me. There are other material signatures that will map to the same signature and there materials vary greatly that when you use this to index the game phase it would be inaccurate.

I want my implementation to be really correct. Is there any better ways to hash a unique material signature? I am thinking of reversing the order of queens and pawns so that when there are more than one queen of one side on the position, it will overflow in the table and it will not coincide with other material signatures.

I know this has been discussed somewhere but I couldn't find the threads. What all of you think of this?

I don't use a material table, and I probably won't any time soon (it's rather ugly IMO). But if I were to make one, I'd do something like this:

0-10:Knights
0-10:Bishops
0-10:Rooks
0-9:Queens
0-8:Pawns

That is just the baseline. You would have a counter that would count how many possible promotions there were, and use that to narrow down the possiblities for higher indices. Like if you had 10 knights, you know that you can only have up to 2 bishops, 2 rooks, 1 queen, and no pawns. Pawns would be most significant in the index, because they start at the maximum and every other piece in the index can bring their count down. Probably Huffman coding would be nicely applicable in this case, and could bring common material configurations closer together in memory.

[Dann Corbit]

I had been experimenting with adding a material correction table for my engine lately. I am using the method in Strelka that was also mentioned in other posts before Strelka code has came out.

I noticed that in positions where there are more than one queen for one or both sides, the game phase indexed by the material sum is not equal to the one when you are going to solve it on the fly.

This means that this method doesn't produce unique material signatures for some cases and it annoys me. There are other material signatures that will map to the same signature and there materials vary greatly that when you use this to index the game phase it would be inaccurate.

I want my implementation to be really correct. Is there any better ways to hash a unique material signature? I am thinking of reversing the order of queens and pawns so that when there are more than one queen of one side on the position, it will overflow in the table and it will not coincide with other material signatures.

I know this has been discussed somewhere but I couldn't find the threads. What all of you think of this?

I don't use a material table, and I probably won't any time soon (it's rather ugly IMO). But if I were to make one, I'd do something like this:

0-10:Knights
0-10:Bishops
0-10:Rooks
0-9:Queens
0-8:Pawns

That is just the baseline. You would have a counter that would count how many possible promotions there were, and use that to narrow down the possiblities for higher indices. Like if you had 10 knights, you know that you can only have up to 2 bishops, 2 rooks, 1 queen, and no pawns. Pawns would be most significant in the index, because they start at the maximum and every other piece in the index can bring their count down. Probably Huffman coding would be nicely applicable in this case, and could bring common material configurations closer together in memory.

The material tables are just used to see who has a clear advantage.
If you have 7 queens on the board, I don't think there is any mystery to it.

Since the actual values are derived from OTB games I guess that the extreme values cannot be populated anyway, since there won't be any games that contain that data.

[hgm]

I think trying to accomodate super-numerary pieces (like 3 Rooks) is only counter-productive (except for Crazyhouse engines, of course). Even when you do search under-promotions, the probability that they are ever needed in a position where all other ieces of that type are still on the board is extremely small. If you want to be purits, just disable the material tables in the sub-tree from there.

[Zach Wegner]

I think trying to accomodate super-numerary pieces (like 3 Rooks) is only counter-productive (except for Crazyhouse engines, of course). Even when you do search under-promotions, the probability that they are ever needed in a position where all other ieces of that type are still on the board is extremely small. If you want to be purits, just disable the material tables in the sub-tree from there.

Exactly, and that's why I don't like material tables. I'd rather not have such gross discontinuities in my evaluation function. If I were to use them, I'd make them complete. Probably when you have large numbers of pieces the only important metric is the difference between them, which is another reason that I don't like material tables--too much redundancy.

The material tables are just used to see who has a clear advantage.
If you have 7 queens on the board, I don't think there is any mystery to it.

Since the actual values are derived from OTB games I guess that the extreme values cannot be populated anyway, since there won't be any games that contain that data.

But what if both players have 7 queens? Just kidding. I'd probably fill in the values with either search-based information or play a lot of really fast games in order to get those values.

[hgm]

Has anyone analysed what is actually in the material tables, and if that can be fitted by a simple equation?

How much of the material tables would, for instance, be explained by piece base values + bishop pair plus second-order cross terms Rooks*Pawns and Bishops*Pawns?

[Dann Corbit]

Has anyone analysed what is actually in the material tables, and if that can be fitted by a simple equation?

How much of the material tables would, for instance, be explained by piece base values + bishop pair plus second-order cross terms Rooks*Pawns and Bishops*Pawns?

I have not tried to verify it, but the articles by Larry Kaufman (who is part of the Rybka team) explain how he arrives at the values:
http://home.comcast.net/~danheisman/Art ... alance.htm

[hgm]

But the Kaufman evaluation is totally trivial. Using a table for that is like using a table of integer products to save a multiplication...