Efficiently index material signatures and lookup

[mathmoi]

Hi,

During the last CCT I once again witnessed MatMoi trading all its pawns to end up in a KBK position and draw while it could have possibly won if it had keep the pawns.

One solution to this is to implement Interior Node Recognizers that in this particular case would have return a draw score instead of a wining (+3.25) score.

One problem that I'll have to solve to implement recognizer is to find a way to index the materials signatures. That is not too difficult, I can do some kind of perfect hash allowing for up to 9 queen, 10 rook 10 bishop... that would give me billions of material signatures. Not good. I could account for say up to 3 of each pieces per side. That would give me 5 millions signatures better, but I still can't make a 5 million table elements and I can't reduce the number of positions much more without ignoring position that could really happens in games.

I plan on having only a small number of recognizer, so instead of putting them in a table indexed on the material signature I could put them in a small list and scan the list searching for the current signature whenever there is less than 5 or 6 pieces on the table. I think that could work and cost too much.

However there is another situation in which I would like to index data by material signature, it's for material table. and in this case I would have a lot more that 5-6 elements.

So the question is, how can store and efficiently retrieved data based on a material signature (recognizer function pointer, material evaluation)? Are you using hash table or sorted list or any special trick?

[Edmund]

Ernst Heinz released a paper called "Efficient interior node recognition" which you can find on dann corbits ftp server (http://cap.connx.com/chess-papers). In it he describes how to efficently index the algorithms and how to access them in the search.

Concerning Material Imbalance Tables, I think most programs that implement them restrict them to the most common piece configurations (ie. max 1 Queen, 2 Rooks, 2 Bishops, 2 Knights, 8 Pawns per side). Another option would be to use a zobrist hash function for the key and generate the data on the fly with a small cache. Similar to pawn hash tables the hit rate should be close to 100%.

regards,
Edmund

[mathmoi]

Ernst Heinz released a paper called "Efficient interior node recognition" which you can find on dann corbits ftp server (http://cap.connx.com/chess-papers). In it he describes how to efficently index the algorithms and how to access them in the search.

Concerning Material Imbalance Tables, I think most programs that implement them restrict them to the most common piece configurations (ie. max 1 Queen, 2 Rooks, 2 Bishops, 2 Knights, 8 Pawns per side). Another option would be to use a zobrist hash function for the key and generate the data on the fly with a small cache. Similar to pawn hash tables the hit rate should be close to 100%.

regards,
Edmund

Hi Edmund, I like the hash and cache idea. It's a shame I did not though of that, thanks. Is there any engine implementing this?

[michiguel]

Ernst Heinz released a paper called "Efficient interior node recognition" which you can find on dann corbits ftp server (http://cap.connx.com/chess-papers). In it he describes how to efficently index the algorithms and how to access them in the search.

Concerning Material Imbalance Tables, I think most programs that implement them restrict them to the most common piece configurations (ie. max 1 Queen, 2 Rooks, 2 Bishops, 2 Knights, 8 Pawns per side). Another option would be to use a zobrist hash function for the key and generate the data on the fly with a small cache. Similar to pawn hash tables the hit rate should be close to 100%.

regards,
Edmund

That is what I do. I cache any type of calculation concerning material. The hit rate is so high that the calculation could be "phoning a friend" and it won't matter. The hit rate from the original position is 99.966%

Miguel

[Edmund]

Hi Edmund, I like the hash and cache idea. It's a shame I did not though of that, thanks. Is there any engine implementing this?

Glaurung and also Stockfish for example

[hgm]

If the only purpose is to recognize theoretical draws with large material advantage (i.e. KBK, KNK and KNNK), it would work to have N=1, B=2, P=R=Q=3. Then every total <= 2 is draw. You would not recognize KBPK with a wrong edge Pawn, though. But that is not really a material draw, it depends on position, like KPK.

The hashing sounds like a good idea. I guess you can easily construct a perfect hash with a 32-bit key. It does not make sense to include positions with super-nominal numbers of Knights, Rooks, Bishops anyway. For one, they never occur. And even if they do, you would not have an idea what to put in the table for them. (Would you have guessed 7 Knights totally slaughter 3 Queens, in K+3Q+8P vs K+7N+8P?)