Material Hash Table

From Chessprogramming wiki
Jump to: navigation, search

Home * Evaluation * Material * Material Hash Table

A Material Hash Table is used to cache once calculated material values for certain material constellations, considering not only the dot-product of the piece values, but material imbalance and even insufficient material. Of course, one has to take care the effort of hashing is not more expensive than the full calculation, assuming incremental update only for captures or promotions. Another pragmatical approach with todays computers and memory sizes is to use precomputed material tables.

Chess 4.5

The Material Hash Table was first described by David Slate and Larry Atkin as used in Chess 4.5 [1]. Chess had following fairly complicated function of only the number of each type of piece on the board, to modify the material difference by a "trade down" bonus that encourages the winning side to trade pieces but no pawns:

ChessMaterial1.jpg

and

ChessMaterial2.jpg

with MD as material difference computed by adding the standard values {100, 325, 350, 500, 900} of each piece and subtracting the total of the side with the least material from the side with the most, the winning side. PA is the number of pawns of the winning side, MT is the total material on the board.

The hash function must have three desired characteristics. First, it should be obviously faster than the function it is replacing. Second, it should distribute the positions that are likely occur in a single search, and third, it should be symmetric with respect to Black and White. Chess 4.5 had a material signature word, containing five nibble counters per piece type for each side, interpreted as 20-bit number each and also stored inside the hash entry to verify material signature when probing. The hash function used is the sum of the white side and black side, exclusive ored with the absolute value of their difference, folded over by further exclusive or to get a 7-bit number, the hash.

See also

Forum Posts

External Links

References

  1. David Slate, Larry Atkin (1977). CHESS 4.5 - The Northwestern University Chess Program. Chess Skill in Man and Machine (ed. Peter W. Frey), pp. 82-118. Springer-Verlag, New York, N.Y. 2nd ed. 1983. ISBN 0-387-90815-3. Reprinted (1988) in Computer Chess Compendium

Up one level