25,161
edits
Changes
Created page with "'''Home * Evaluation * Pawn Structure * Pawn Hash Table''' FILE:Elke_Rehder_Chess_Schach_Woodcut_Pawns_King_Bauer_Koenig.jpg|border|right|thumb|link=h..."
'''[[Main Page|Home]] * [[Evaluation]] * [[Pawn Structure]] * Pawn Hash Table'''
[[FILE:Elke_Rehder_Chess_Schach_Woodcut_Pawns_King_Bauer_Koenig.jpg|border|right|thumb|link=http://www.elke-rehder.de/Chess_Woodcuts.htm|Pawns threaten the King <ref>[http://www.elke-rehder.de/Chess_Woodcuts.htm Chess Woodcuts Graphic Arts Woodcut Art] by [[Arts#Rehder|Elke Rehder]]</ref> ]]
A '''Pawn Hash Table''' is often used inside a chess programs to [https://en.wikipedia.org/wiki/Cache cache] purely [[Pawn|pawn]] related [[Pawn Pattern and Properties|pattern]] and [[Pawn Structure|evaluation]] stuff. Compared to the [[Transposition Table|main transposition table]], since the [[Pawn Structure|pawn structure]] inside the [[Search|search]] changes rarely or transpose, the number of cached entries required might be quite low (a few K) to get a sufficient hit rate above 95% or even 99% for most positions, specially if the pawn structure is settled or relatively fixed after the [[Opening|opening]]. On the other hand, most programmers store not only pure aggregated pawn evaluation scores, but other computation expensive pawn structure stuff which is used in second pass [[Evaluation|evaluation]] considering [[Pieces|pieces]] and [[King|king]]. Terms for various [[Game Phases|game phases]] and king origins for all possible wings/center per side are often calculated [https://en.wikipedia.org/wiki/Speculative_execution speculatively], i.e. pawn shield or pawn storm stuff later used by [[King Safety|king safety]].
While the content of the pawn hash table entry varies a lot between different chess programs and their implementation, it is not uncommon that one entry exceeds 1/2 K-Byte. Some programs store sets or [[Bitboards|bitboards]] of strong pawns ([[Passed Pawn|passers]], [[Candidate Passed Pawn|candidates]]), square of most advanced passer, different kind of [[Weak Pawns|weak pawn sets]] and whatever else. Despite, some programs cache pawn-king stuff separately which requires king squares included inside the index calculation as well table entry for verifications.
=Pawn Hash Index=
Most simple, common and recommend is to keep an [[Incremental Updates|incremental updated]], dedicated [[Zobrist Hashing|Zobrist]]- or [[BCH Hashing|BCH-keys]] similar to the [[Transposition Table|main transposition table]], initialized from all squares occupied by pawns only, [[Side to move|side to move]] does not matter. The update of that key is therefor only necessary for the relative rare pawn moves or captures with pawns as aggressor or victim. The hash table index is computed by key modulo number of entries, which might be a cheap and-instruction from the key for power of two sized tables.
Alternatively, considering hits from the [[Transposition Table|transposition table]], or a dedicated [[Evaluation Hash Table|evaluation hash table]], one may use a fast [[Hash Table|hash function]] to compute an index from the white and black pawn bitboards on the fly, i.e. either a modulo or a multiplication and shift à la [[Magic Bitboards|magic bitboards]] by the difference of the disjoint pawn sets <ref>[https://www.stmintz.com/ccc/index.php?id=315478 Pawn hashing without Zobrist keys] by [[Gerd Isenberg]], [[CCC]], September 12, 2003</ref> . To verify correct entries while probing, one needs either to store (a part) of the dedicated Zobrist/BCH key, or for 100% correctness 2*48 bits from the pawn occupancy bitboards. This value could be further compressed with the expense of more calculation overhead by means of n-like men:
[[FILE:PawnHashFormla.jpg|none|border|text-bottom]]
This can be further reduced by mirroring the board, considering symmetric positions or detecting illegal positions.
=See also=
* [[Evaluation Hash Table]]
* [[Hash Table]]
* [[Material Hash Table]]
* [[Material Tables]]
* [[Transposition Table]]
=Forum Posts=
==1999==
* [https://www.stmintz.com/ccc/index.php?id=61063 Q: pawn hash?] by [[Scott Gasch]], [[CCC]], July 20, 1999
* [https://www.stmintz.com/ccc/index.php?id=68872 regular hash key & pawn hash key together - good idea?] by [[Tom Kerrigan]], [[CCC]], September 16, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=129406 A question about pawn hash tables] by [[Andreas Herrmann]], [[CCC]], September 13, 2000
* [https://www.stmintz.com/ccc/index.php?id=200037 A few hashing questions] by [[Severi Salminen]], [[CCC]], December 02, 2001
* [https://www.stmintz.com/ccc/index.php?id=200496 Pawn Hash Collisions in Crafty] by [[David Rasmussen]], [[CCC]], December 05, 2001
* [https://www.stmintz.com/ccc/index.php?id=200800 Crafty's 32-bit pawn hash collision figures?] by [[Severi Salminen]], [[CCC]], December 06, 2001
* [https://www.stmintz.com/ccc/index.php?id=237159 Pawn hash table: need some helps?] by [[Pham Hong Nguyen]], [[CCC]], June 23, 2002
* [https://www.stmintz.com/ccc/index.php?id=266544 Ultra small pawn hash efficiency] by [[Vladimir Medvedev]], [[CCC]], November 21, 2002
* [https://www.stmintz.com/ccc/index.php?id=288402 programmers: pawn hash tables] by Joel, [[CCC]], March 08, 2003
* [https://www.stmintz.com/ccc/index.php?id=309379 pawn hash tables] by Joshua Lee, [[CCC]], August 01, 2003
* [https://www.stmintz.com/ccc/index.php?id=314386 The key of pawn hash tables is based on what exactly?] by [[Uri Blass]], [[CCC]], September 06, 2003
* [https://www.stmintz.com/ccc/index.php?id=315478 Pawn hashing without Zobrist keys] by [[Gerd Isenberg]], [[CCC]], September 12, 2003
* [https://www.stmintz.com/ccc/index.php?id=354696 Pawn Hash Question] by [[Dan Honeycutt]], [[CCC]], March 15, 2004
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/cfe3b4da78ee890b/928457251da6ff40 Which pawn positions go into a pawn hash table?] by pd42, [[Computer Chess Forums|rgcc]], May 26, 2004
* [https://www.stmintz.com/ccc/index.php?id=373656 pawn hash] by [[Tor Lattimore]], [[CCC]], July 03, 2004
* [https://www.stmintz.com/ccc/index.php?id=389201 Initialization of pawn hash table] by [[Zach Wegner]], [[CCC]], September 26, 2004
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=13673 About pawn hash tables] by [[Uri Blass]], [[CCC]], May 10, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=15540 An interesting bug in Hamsters] by [[Alessandro Scotti]], [[CCC]], August 02, 2007 » [[Hamsters]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=33334 Pawn Hash] by [[Harm Geert Muller]], [[CCC]], March 18, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=40470 Possible pawn hash speed optimization? ] by [[John Merlino]], [[CCC]], September 19, 2011
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=59126 pawn hash and ep] by [[J. Wesley Cleveland]], [[CCC]], February 01, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=59154 Buckets for pawn hash?] by [[J. Wesley Cleveland]], [[CCC]], February 04, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=59319 pawn hash and eval tuning] by [[J. Wesley Cleveland]], [[CCC]], February 21, 2016 » [[Automated Tuning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59566 hash eval, hash pawn or twice ?] by [[Daniel Anulliero]], March 19, 2016 » [[Evaluation Hash Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61621 Pawn hash] by [[Karlo Bala Jr.]], [[CCC]], October 06, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62160&start=10 pawn hash] by [[Volker Annuss]], [[CCC]], November 18, 2016
=External Links=
* [https://en.wikipedia.org/wiki/Transposition_table#Related_techniques Transposition table - Related techniques, from Wikipedia]
* [http://www.cse.buffalo.edu/~regan/chess/computer/anomalies/DF10anomalies.htm Chess Engine Anomalies, evidently caused by hash-table collisions and effects of multithreading] by [[Kenneth Wingate Regan]]
=References=
<references />
'''[[Pawn Structure|Up one level]]'''
[[Category:Elke Rehder]]
[[FILE:Elke_Rehder_Chess_Schach_Woodcut_Pawns_King_Bauer_Koenig.jpg|border|right|thumb|link=http://www.elke-rehder.de/Chess_Woodcuts.htm|Pawns threaten the King <ref>[http://www.elke-rehder.de/Chess_Woodcuts.htm Chess Woodcuts Graphic Arts Woodcut Art] by [[Arts#Rehder|Elke Rehder]]</ref> ]]
A '''Pawn Hash Table''' is often used inside a chess programs to [https://en.wikipedia.org/wiki/Cache cache] purely [[Pawn|pawn]] related [[Pawn Pattern and Properties|pattern]] and [[Pawn Structure|evaluation]] stuff. Compared to the [[Transposition Table|main transposition table]], since the [[Pawn Structure|pawn structure]] inside the [[Search|search]] changes rarely or transpose, the number of cached entries required might be quite low (a few K) to get a sufficient hit rate above 95% or even 99% for most positions, specially if the pawn structure is settled or relatively fixed after the [[Opening|opening]]. On the other hand, most programmers store not only pure aggregated pawn evaluation scores, but other computation expensive pawn structure stuff which is used in second pass [[Evaluation|evaluation]] considering [[Pieces|pieces]] and [[King|king]]. Terms for various [[Game Phases|game phases]] and king origins for all possible wings/center per side are often calculated [https://en.wikipedia.org/wiki/Speculative_execution speculatively], i.e. pawn shield or pawn storm stuff later used by [[King Safety|king safety]].
While the content of the pawn hash table entry varies a lot between different chess programs and their implementation, it is not uncommon that one entry exceeds 1/2 K-Byte. Some programs store sets or [[Bitboards|bitboards]] of strong pawns ([[Passed Pawn|passers]], [[Candidate Passed Pawn|candidates]]), square of most advanced passer, different kind of [[Weak Pawns|weak pawn sets]] and whatever else. Despite, some programs cache pawn-king stuff separately which requires king squares included inside the index calculation as well table entry for verifications.
=Pawn Hash Index=
Most simple, common and recommend is to keep an [[Incremental Updates|incremental updated]], dedicated [[Zobrist Hashing|Zobrist]]- or [[BCH Hashing|BCH-keys]] similar to the [[Transposition Table|main transposition table]], initialized from all squares occupied by pawns only, [[Side to move|side to move]] does not matter. The update of that key is therefor only necessary for the relative rare pawn moves or captures with pawns as aggressor or victim. The hash table index is computed by key modulo number of entries, which might be a cheap and-instruction from the key for power of two sized tables.
Alternatively, considering hits from the [[Transposition Table|transposition table]], or a dedicated [[Evaluation Hash Table|evaluation hash table]], one may use a fast [[Hash Table|hash function]] to compute an index from the white and black pawn bitboards on the fly, i.e. either a modulo or a multiplication and shift à la [[Magic Bitboards|magic bitboards]] by the difference of the disjoint pawn sets <ref>[https://www.stmintz.com/ccc/index.php?id=315478 Pawn hashing without Zobrist keys] by [[Gerd Isenberg]], [[CCC]], September 12, 2003</ref> . To verify correct entries while probing, one needs either to store (a part) of the dedicated Zobrist/BCH key, or for 100% correctness 2*48 bits from the pawn occupancy bitboards. This value could be further compressed with the expense of more calculation overhead by means of n-like men:
[[FILE:PawnHashFormla.jpg|none|border|text-bottom]]
This can be further reduced by mirroring the board, considering symmetric positions or detecting illegal positions.
=See also=
* [[Evaluation Hash Table]]
* [[Hash Table]]
* [[Material Hash Table]]
* [[Material Tables]]
* [[Transposition Table]]
=Forum Posts=
==1999==
* [https://www.stmintz.com/ccc/index.php?id=61063 Q: pawn hash?] by [[Scott Gasch]], [[CCC]], July 20, 1999
* [https://www.stmintz.com/ccc/index.php?id=68872 regular hash key & pawn hash key together - good idea?] by [[Tom Kerrigan]], [[CCC]], September 16, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=129406 A question about pawn hash tables] by [[Andreas Herrmann]], [[CCC]], September 13, 2000
* [https://www.stmintz.com/ccc/index.php?id=200037 A few hashing questions] by [[Severi Salminen]], [[CCC]], December 02, 2001
* [https://www.stmintz.com/ccc/index.php?id=200496 Pawn Hash Collisions in Crafty] by [[David Rasmussen]], [[CCC]], December 05, 2001
* [https://www.stmintz.com/ccc/index.php?id=200800 Crafty's 32-bit pawn hash collision figures?] by [[Severi Salminen]], [[CCC]], December 06, 2001
* [https://www.stmintz.com/ccc/index.php?id=237159 Pawn hash table: need some helps?] by [[Pham Hong Nguyen]], [[CCC]], June 23, 2002
* [https://www.stmintz.com/ccc/index.php?id=266544 Ultra small pawn hash efficiency] by [[Vladimir Medvedev]], [[CCC]], November 21, 2002
* [https://www.stmintz.com/ccc/index.php?id=288402 programmers: pawn hash tables] by Joel, [[CCC]], March 08, 2003
* [https://www.stmintz.com/ccc/index.php?id=309379 pawn hash tables] by Joshua Lee, [[CCC]], August 01, 2003
* [https://www.stmintz.com/ccc/index.php?id=314386 The key of pawn hash tables is based on what exactly?] by [[Uri Blass]], [[CCC]], September 06, 2003
* [https://www.stmintz.com/ccc/index.php?id=315478 Pawn hashing without Zobrist keys] by [[Gerd Isenberg]], [[CCC]], September 12, 2003
* [https://www.stmintz.com/ccc/index.php?id=354696 Pawn Hash Question] by [[Dan Honeycutt]], [[CCC]], March 15, 2004
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/cfe3b4da78ee890b/928457251da6ff40 Which pawn positions go into a pawn hash table?] by pd42, [[Computer Chess Forums|rgcc]], May 26, 2004
* [https://www.stmintz.com/ccc/index.php?id=373656 pawn hash] by [[Tor Lattimore]], [[CCC]], July 03, 2004
* [https://www.stmintz.com/ccc/index.php?id=389201 Initialization of pawn hash table] by [[Zach Wegner]], [[CCC]], September 26, 2004
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=13673 About pawn hash tables] by [[Uri Blass]], [[CCC]], May 10, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=15540 An interesting bug in Hamsters] by [[Alessandro Scotti]], [[CCC]], August 02, 2007 » [[Hamsters]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=33334 Pawn Hash] by [[Harm Geert Muller]], [[CCC]], March 18, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=40470 Possible pawn hash speed optimization? ] by [[John Merlino]], [[CCC]], September 19, 2011
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=59126 pawn hash and ep] by [[J. Wesley Cleveland]], [[CCC]], February 01, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=59154 Buckets for pawn hash?] by [[J. Wesley Cleveland]], [[CCC]], February 04, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=59319 pawn hash and eval tuning] by [[J. Wesley Cleveland]], [[CCC]], February 21, 2016 » [[Automated Tuning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=59566 hash eval, hash pawn or twice ?] by [[Daniel Anulliero]], March 19, 2016 » [[Evaluation Hash Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61621 Pawn hash] by [[Karlo Bala Jr.]], [[CCC]], October 06, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62160&start=10 pawn hash] by [[Volker Annuss]], [[CCC]], November 18, 2016
=External Links=
* [https://en.wikipedia.org/wiki/Transposition_table#Related_techniques Transposition table - Related techniques, from Wikipedia]
* [http://www.cse.buffalo.edu/~regan/chess/computer/anomalies/DF10anomalies.htm Chess Engine Anomalies, evidently caused by hash-table collisions and effects of multithreading] by [[Kenneth Wingate Regan]]
=References=
<references />
'''[[Pawn Structure|Up one level]]'''
[[Category:Elke Rehder]]
