Material Tables

From Chessprogramming wiki
Revision as of 18:44, 16 May 2018 by GerdIsenberg (talk | contribs) (Created page with "'''Home * Evaluation * Material * Material Tables''' '''Material Tables''' contain precomputed material values for all possible material constellations...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Home * Evaluation * Material * Material Tables

Material Tables contain precomputed material values for all possible material constellations of both sides, considering not only the dot-product of the piece values times number of pieces, but material imbalance features and even insufficient material. The up to ten piece counters of {white, black} x {pawns, knights, bishops, rooks, queen(s)} act as index into a 10-dimensional array, where each dimension covers one piece kind and color. However, since there are up to eight pawns (0..8), rarely up to ten pieces and nine queens per side, the size of such an array would be with

(9 * 11 * 11 * 11 * 10)² = 119790² = 14,349,644,100

much to huge, which was the main reason to use a smaller material hash table instead, to cache the once calculated values. A material key needs only incremental update if captures or promotions occur, so that even small tables are sufficient for a hit-rate of 99% or greater. A compromise for precomputed tables is to consider only "usual" material constellations, that is no more than two knights, bishops or rooks and one queen per side, ...

(9 * 3 * 3 * 3 * 2)² = 486² = 236,196

... which makes a reasonable size for todays computers below 1/4 MByte entries.

value_t matValue[9][9][3][3][3][3][3][3][2][2];

or better a one dimensional error with an incremental updated material key.

value_t matValue[9*9*3*3*3*3*3*3*2*2];

Material tables along with imbalance tables, first appeared in Jury Osipov's disputed [1] open source engine Strelka 2.0, apparently reverse engineered from Rybka 1.0 [2] [3]. Indices were initialized that way - with bitboards even the population count of a board-definition is used:

  materialSum_key =
    pieceCount[WhiteQueen]  +
    pieceCount[BlackQueen]  * 2 +
    pieceCount[WhiteRook]   * 2*2 +
    pieceCount[BlackRook]   * 2*2*3 +
    pieceCount[WhiteBishop] * 2*2*3*3 +
    pieceCount[BlackBishop] * 2*2*3*3*3 +
    pieceCount[WhiteKnight] * 2*2*3*3*3*3 +
    pieceCount[BlackKnight] * 2*2*3*3*3*3*3 +
    pieceCount[WhitePawn]   * 2*2*3*3*3*3*3*3 +
    pieceCount[BlackPawn]   * 2*2*3*3*3*3*3*3*9;

  materialDiff_key =
    (pieceCount[WhiteQueen]  - pieceCount[BlackQueen])  * 10 +
    (pieceCount[WhiteRook]   - pieceCount[BlackRook])   * 5  +
    (pieceCount[WhiteBishop] - pieceCount[BlackBishop]) * 3  +
    (pieceCount[WhiteKnight] - pieceCount[BlackKnight]) * 3  +
    (pieceCount[WhitePawn]   - pieceCount[BlackPawn]);

An array of ten nibble piece counters can be interpreted as 40-bit number where each piece count is multiplied with consecutive power of sixteen factors with exponents of 0 to 9, the materialSum_key key has minimal population factors which result in only a 18-bit word. While this dot-product and its incremental update looks like a reversible perfect hashing-function, is more like a multi-dimensional array-lookup.

In 2010, Harm Geert Muller proposed a similar, cache friendlier scheme for common minor piece exchanges, by altering rooks, bishops and knights with appropriate offsets [4] .

See also

Forum Posts

2000 ...

Re: Material Tables and Indexing by Lance Perkins, CCC, April 22, 2008

2010 ...

External Links

References

Up one level