25,161
edits
Changes
Created page with "'''Home * Evaluation * Material * Material Tables''' '''Material Tables''' contain precomputed material values for all possible material constellations..."
'''[[Main Page|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 [[Material#InsufficientMaterial|insufficient material]]. The up to ten piece counters of <span style="background-color: #c0c0c0; font-family: 'Courier New',Courier,monospace;">{white, black} x {pawns, knights, bishops, rooks, queen(s)}</span> act as index into a 10-dimensional [[Array|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|material hash table]] instead, to cache the once calculated values. A material key needs only [[Incremental Updates|incremental update]] if [[Captures|captures]] or [[Promotions|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.
<pre>
value_t matValue[9][9][3][3][3][3][3][3][2][2];
</pre>
or better a one dimensional error with an [[Incremental Updates|incremental updated]] material key.
<pre>
value_t matValue[9*9*3*3*3*3*3*3*2*2];
</pre>
Material tables along with imbalance tables, first appeared in [[Jury Osipov|Jury Osipov's]] disputed <ref>[https://en.wikipedia.org/wiki/Rybka#Strelka_controversy Strelka controversy from Wikipedia]</ref> [[Open Source Engines|open source engine]] [[Strelka|Strelka 2.0]], apparently [https://en.wikipedia.org/wiki/Reverse_engineering reverse engineered] from [[Rybka|Rybka 1.0]] <ref>[http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=3006 Strelka 2.0] by [[Vasik Rajlich]], [[Computer Chess Forums|Rybka Forum]], January 11, 2008</ref> <ref>[http://www.top-5000.nl/mb.htm A Material Base for everybody] from [http://www.top-5000.nl/ Home of the Dutch Rebel] by [[Ed Schroder|Ed Schröder]]</ref>. Indices were initialized that way - with [[Bitboards|bitboards]] even the [[Population Count|population count]] of a [[Bitboard Board-Definition|board-definition]] is used:
<pre>
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]);
</pre>
An array of ten [[Nibble|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 [[Hash Table#PerfectHashing|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 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=33561 Cache-friendier material index] by [[Harm Geert Muller]], [[CCC]], March 31, 2010</ref> .
=See also=
* [[Material Hash Table]]
* [[Rookie#Evaluation|Evaluation in Rookie 2.0]]
=Forum Posts=
==2000 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5377 Piece Cooperation and Penalties] by [[Mark Lefler|mjlef]], [[Computer Chess Forums|Winboard Forum]], August 14, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=15679 Why material imbalance tables are needed] by [[Michael Sherwin]], [[CCC]], August 09, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=20659 Material Tables and Indexing] by [[Edsel Apostol]], [[CCC]], April 14, 2008
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=185340 Re: Material Tables and Indexing] by [[Lance Perkins]], [[CCC]], April 22, 2008
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=33021 Material tables] by [[Harm Geert Muller]], [[CCC]], March 03, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=33035 Efficiently index material signatures and lookup] by [[Mathieu Pagé]], [[CCC]], March 03, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=47713 An experiment with material imbalances and game-phase] by [[Evert Glebbeek]], [[CCC]], April 06, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=50550 Accessing Material Imbalance Information?] by [[Steve Maughan]], [[CCC]], December 19, 2013
=External Links=
* [http://www.danheisman.com/evaluation-of-material-imbalances.html The Evaluation of Material Imbalances] by [[Larry Kaufman]] (first published in [https://en.wikipedia.org/wiki/Chess_Life Chess Life] March 1999, on-line version edited by [[Dan Heisman]])
* [http://www.top-5000.nl/mb.htm A Material Base for everybody] from [http://www.top-5000.nl/ Home of the Dutch Rebel] by [[Ed Schroder|Ed Schröder]]
=References=
<references />
'''[[Material|Up one level]]'''
'''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 [[Material#InsufficientMaterial|insufficient material]]. The up to ten piece counters of <span style="background-color: #c0c0c0; font-family: 'Courier New',Courier,monospace;">{white, black} x {pawns, knights, bishops, rooks, queen(s)}</span> act as index into a 10-dimensional [[Array|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|material hash table]] instead, to cache the once calculated values. A material key needs only [[Incremental Updates|incremental update]] if [[Captures|captures]] or [[Promotions|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.
<pre>
value_t matValue[9][9][3][3][3][3][3][3][2][2];
</pre>
or better a one dimensional error with an [[Incremental Updates|incremental updated]] material key.
<pre>
value_t matValue[9*9*3*3*3*3*3*3*2*2];
</pre>
Material tables along with imbalance tables, first appeared in [[Jury Osipov|Jury Osipov's]] disputed <ref>[https://en.wikipedia.org/wiki/Rybka#Strelka_controversy Strelka controversy from Wikipedia]</ref> [[Open Source Engines|open source engine]] [[Strelka|Strelka 2.0]], apparently [https://en.wikipedia.org/wiki/Reverse_engineering reverse engineered] from [[Rybka|Rybka 1.0]] <ref>[http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=3006 Strelka 2.0] by [[Vasik Rajlich]], [[Computer Chess Forums|Rybka Forum]], January 11, 2008</ref> <ref>[http://www.top-5000.nl/mb.htm A Material Base for everybody] from [http://www.top-5000.nl/ Home of the Dutch Rebel] by [[Ed Schroder|Ed Schröder]]</ref>. Indices were initialized that way - with [[Bitboards|bitboards]] even the [[Population Count|population count]] of a [[Bitboard Board-Definition|board-definition]] is used:
<pre>
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]);
</pre>
An array of ten [[Nibble|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 [[Hash Table#PerfectHashing|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 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=33561 Cache-friendier material index] by [[Harm Geert Muller]], [[CCC]], March 31, 2010</ref> .
=See also=
* [[Material Hash Table]]
* [[Rookie#Evaluation|Evaluation in Rookie 2.0]]
=Forum Posts=
==2000 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5377 Piece Cooperation and Penalties] by [[Mark Lefler|mjlef]], [[Computer Chess Forums|Winboard Forum]], August 14, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=15679 Why material imbalance tables are needed] by [[Michael Sherwin]], [[CCC]], August 09, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=20659 Material Tables and Indexing] by [[Edsel Apostol]], [[CCC]], April 14, 2008
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=185340 Re: Material Tables and Indexing] by [[Lance Perkins]], [[CCC]], April 22, 2008
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=33021 Material tables] by [[Harm Geert Muller]], [[CCC]], March 03, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=33035 Efficiently index material signatures and lookup] by [[Mathieu Pagé]], [[CCC]], March 03, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=47713 An experiment with material imbalances and game-phase] by [[Evert Glebbeek]], [[CCC]], April 06, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=50550 Accessing Material Imbalance Information?] by [[Steve Maughan]], [[CCC]], December 19, 2013
=External Links=
* [http://www.danheisman.com/evaluation-of-material-imbalances.html The Evaluation of Material Imbalances] by [[Larry Kaufman]] (first published in [https://en.wikipedia.org/wiki/Chess_Life Chess Life] March 1999, on-line version edited by [[Dan Heisman]])
* [http://www.top-5000.nl/mb.htm A Material Base for everybody] from [http://www.top-5000.nl/ Home of the Dutch Rebel] by [[Ed Schroder|Ed Schröder]]
=References=
<references />
'''[[Material|Up one level]]'''
