Changes

Jump to: navigation, search

Piece-Square Tables

13,298 bytes added, 14:32, 14 May 2018
Created page with "'''Home * Evaluation * Piece-Square Tables''' FILE:CageChessPieces.jpg|border|right|thumb|link=http://www.artnet.com/magazineus/reviews/davis/davis11-1-05..."
'''[[Main Page|Home]] * [[Evaluation]] * Piece-Square Tables'''

[[FILE:CageChessPieces.jpg|border|right|thumb|link=http://www.artnet.com/magazineus/reviews/davis/davis11-1-05_detail.asp?picnum=2|[[Arts#Cage|John Cage]], Chess Pieces, ca. 1944 <ref>[http://www.artnet.com/magazineus/reviews/davis/davis11-1-05_detail.asp?picnum=2 John Cage - Chess Pieces, Ca. 1944], Courtesy [http://johncagetrust.blogspot.com/ The John Cage Trust] from [http://www.artnet.com/magazineus/reviews/davis/davis11-1-05.asp artnet Magazine - We Are Duchampians] by Ben Davis</ref> ]]

'''Piece-Square Tables''',<br/>
a simple way to assign values to specific [[Pieces|pieces]] on specific [[Squares|squares]]. A table is created for each piece of each [[Color|color]], and values assigned to each square. This scheme is fast, since the evaluation term from the piece square tables can be [[Incremental Updates|incrementally updated]] as [[Moves|moves]] are [[Make Move|made]] and [[Unmake Move|unmade]] in the [[Search Tree|search tree]]. Because of that speed, piece-square tables are of great help when conducting [[Lazy Evaluation|lazy evaluation]].

The same technique can be used for a more subtle evaluation terms, instead of one fixed value for, say, an [[Isolated Pawn|isolated pawn]]. It is also possible to use piece-square tables for [[Move Ordering|move ordering]], though [[History Heuristic|history heuristic]] tends to perform better. Some programs, like [[Rebel]], use the combination of the two <ref>[[Ed Schroder|Ed Schröder]] ''How REBEL Plays Chess'' as [http://members.home.nl/matador/Inside%20Rebel.pdf pdf], see page 1,2 [[Move Ordering]]</ref>.

<span id="MultipleTables"></span>
=Multiple Tables=
Most modern programs, influenced by [[Fruit]], use two sets of tables. One for the [[Opening|opening]] of the game and another for the [[Endgame|endgame]]. The final evaluation is them [[Tapered Eval|interpolated]] between these two based on [[Game Phases|game stage]] (often [[Material|material]] on the board). This allows for changes in material as well, since the material part of the evaluation can also be stored in these tables. Using two tables also lets pieces change in evaluation as the game proceeds. For example, [[Pawn|pawns]] can gain in value in the endgame using this method.
<span id="Preprocessing"></span>
=Pre-processing=
Older programs, running on slow hardware and reaching low depths, used an [[Oracle|oracle approach]] to speed up their evaluation by initializing the piece-square tables at the [[Root|beginning of each search]], taking into account complex characteristics of position, influence of [[Pawn Structure|pawn structure]], distance to the enemy king etc <ref>[https://www.stmintz.com/ccc/index.php?id=18181 Re: What is "pre-processing"] by [[Don Dailey]], [[CCC]], May 07, 1998</ref>. Pre-processing, also dubbed '''Pre Scan Heuristics''' as applied in [[David Kittinger|Kittinger]] programs <ref>[http://www.schach-computer.info/wiki/index.php/PSH PSH] from [http://www.schach-computer.info/wiki/index.php/Hauptseite_En Schachcomputer.info Wiki] (German)</ref>, most notably the [[Super Constellation]] <ref>[http://www.schach-computer.info/wiki/index.php/Novag_Super_Constellation Novag Super Constellation] from [http://www.schach-computer.info/wiki/index.php/Hauptseite_En Schachcomputer.info - Wiki] (German)</ref>, were used by [[Kaare Danielsen]] <ref>"[[Oracle#Donninger|This approach]] seems to have been invented by [[Kaare Danielsen]] for his program [[CXG Star Chess#Advanced|CXG Advanced Star Chess]]" from [[Chrilly Donninger]] ('''1996'''). ''CHE: A Graphical Language for Expressing Chess Knowledge''. [[ICGA Journal#19_4|ICCA Journal, Vol. 19, No. 4]]</ref>, [[Richard Lang]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=475574&t=44507 Re: Some thoughts on QS] by [[Ed Schroder|Ed Schröder]], [[CCC]], July 25, 2012</ref>, [[Don Dailey]], who even developed a little language so that [[Larry Kaufman]] could express evaluation concepts in a more natural way <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=475603&t=44507 Re: Some thoughts on QS] by [[Don Dailey]], [[CCC]], July 25, 2012</ref>, [[Chrilly Donninger]] with [[Nimzo|Nimzo 3]], and [[Frans Morsch]] and [[Mathias Feist]] with [[Fritz|Fritz 3]], to name a few, the latter even with user modifiable rules or tables. However, the idea already originated from the program [[Tech]] by [[James Gillogly]] in the late 1960's <ref>[[David Kittinger]] and [[Scott McDonald]] ('''1984'''). ''Report from the U.S. Open''. [[Computer Chess Reports|Computer Chess Digest Annual 1984]] pp. 15-33</ref>.

With today's search depth this approach seems to be impractical, since the difference between the root and leaf position may be very big. There also might be a problem with re-using hash scores from the previous entries. About the only recent chess program that sticks with pre-processing for good or bad is [[RomiChess]] <ref>[https://www.stmintz.com/ccc/index.php?id=18203 Re: What is "pre-processing"] by [[Ulrich Türke]], [[CCC]], May 08, 1998</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=18213 Re: What is "pre-processing"] by [[Amir Ban]], [[CCC]], May 08, 1998</ref>.

=Example=
Material and piece-square tables alone are enough for a program to play a semi-decent game of chess. Indeed, [[Tomasz Michniewski]] advocated a method of testing requiring all the tested programs to have identical, simplistic evaluation function, so that only search and efficiency issues would influence the result. One such tournament has been carried out in Poland.
* [[Simplified evaluation function]]

=See also=
* [[Center Distance]]
* [[Center Manhattan-Distance]]
* [[Rookie#Evaluation|Evaluation in Rookie 2.0]]
* [[Evaluation of Pieces]]
* [[Game Phases]]
* [[Material]]
* [[Mop-up Evaluation]]
* [[Oracle]]
* [[Space]]

=Publications=
* [[Jack Good]] ('''1968'''). ''A Five-Year Plan for Automatic Chess - Appendix F. The Value of the Pieces and Squares''. [http://www.doc.ic.ac.uk/~shm/MI/mi2.html Machine Intelligence Vol. 2]
* [[Don Beal]], [[Martin C. Smith]] ('''1999'''). ''Learning Piece-Square Values using Temporal Differences.'' [[ICGA Journal#22_4|ICCA Journal, Vol. 22, No. 4]]
* [[Jun Nagashima]], [[Masahumi Taketoshi]], [[Yoichiro Kajihara]], [[Tsuyoshi Hashimoto]], [[Hiroyuki Iida]] ('''2002'''). ''[http://ci.nii.ac.jp/naid/110006381103 An Efficient Use of Piece-Square Tables in Computer Shogi]''.
* [[Sacha Droste]], [[Johannes Fürnkranz]] ('''2008'''). ''Learning of Piece Values for Chess Variants.'' Technical Report TUD–KE–2008-07, Knowledge Engineering Group, [[Darmstadt University of Technology|TU Darmstadt]], [http://www.ke.tu-darmstadt.de/publications/reports/tud-ke-2008-07.pdf pdf]

=Forum Posts=
==1996 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/4e27d53cd9b6cc5e Re:Rebel Transposition Table discussion] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], April 18, 1996, ''about clearing [[Transposition Table|TT]] if using a preprocessor''.
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/d962cff95d967c3 The Diep Home page (more correction needed)] by [[Ed Schroder|Ed Schröder]], [[Computer Chess Forums|rgcc]], January 21, 1997
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/d67609b6c2e3063d Question about prescan and evaluating in Crafty] by Willem Broekema, [[Computer Chess Forums|rgcc]], January 07, 1998
* [https://www.stmintz.com/ccc/index.php?id=18179 What is "pre-processing"] by Howard Exner, [[CCC]], May 07, 1998
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/ce25565232355c61 Preprocessing vs leaf evaluating - any preprocessors left?] by [[Tom King]], [[Computer Chess Forums|rgcc]], July 05, 1998
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=95525 Preprocessor blues?] by [[Ernst Walet]], [[CCC]], February 07, 2000
* [https://www.stmintz.com/ccc/index.php?id=132894 Re: What is Prescan Heuristics ??] by [[Vincent Diepeveen]], [[CCC]], October 13, 2000
* [https://www.stmintz.com/ccc/index.php?id=304684 Program settings (Re: Programmers Should Take A Cue From Chessmaster)] by [[Albert Bertilsson]], [[CCC]], July 04, 2003 » [[Sharper]]
* [http://www.talkchess.com/forum/viewtopic.php?t=29825 Determining values for piece-square tables.] by [[Mike Leany]], [[CCC]], September 21, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=37191 dynamically modified evaluation function] by [[Don Dailey]], [[CCC]], December 20, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=38766 Move ordering by PST] by [[Onno Garms]], [[CCC]], April 16, 2011 » [[History Heuristic]], [[Move Ordering]], [[Onno]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=1535 Questions for BB about Rybka PST = Fruit PST] by [[Ed Schroder|Rebel]], [[Computer Chess Forums|OpenChess Forum]], August 4, 2011 » [[Rybka Controversy]]
* [http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=22572 PST Calculation] by [[Miguel A. Ballicora|michiguel]], [[Computer Chess Forums|Rybka Forum]], August 5, 2011
* [http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=22635 Fruit and Crafty Bishop PSTs] by [[Miguel A. Ballicora|michiguel]], [[Computer Chess Forums|Rybka Forum]], August 12, 2011 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=40047 Crafty accused of copying Fruit PST] by William O, [[CCC]], August 13, 2011</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=40085 Crafty *NOT* accused of copying Fruit PST] by [[Miguel A. Ballicora]], [[CCC]], August 17, 2011</ref>
* [http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=22642 A small detail about additive constants to PSTs] by [[Chris Whittington|Trotsky]], [[Computer Chess Forums|Rybka Forum]], August 13, 2011
* [http://www.open-chess.org/viewtopic.php?f=5&t=1552 Fruit 1.0 PST] by BB+ ([[Mark Watkins]]), [[Computer Chess Forums|OpenChess Forum]], August 13, 2011
* [http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=22662 About PSQ tables] by [[Richard Vida]], [[Computer Chess Forums|Rybka Forum]], August 15, 2011
* [http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=22669 Take the Fruit Bishop tables...] by [[Miguel A. Ballicora|michiguel]], [[Computer Chess Forums|Rybka Forum]], August 16, 2011
* [http://www.open-chess.org/viewtopic.php?f=5&t=1570 PST of Fruit 2.1 and Rybka 1.0 Beta] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], August 22, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=42167 Incremental or non-incremental PST evaluation calcs] by [[Mark Pearce]], [[CCC]], January 26, 2012 » [[Incremental Updates]]
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=475603&t=44507 Re: Some thoughts on QS] by [[Don Dailey]], [[CCC]], July 25, 2012 » [[Quiescence Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48102 On history and piece square tables] by [[Evert Glebbeek]], [[CCC]], May 24, 2013 » [[History Heuristic]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50294 PSQ tables depending on king sides, pawn patterns etc.] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], December 01, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=50840 Piece/square table challenge] by [[Pawel Koziol]], [[CCC]], January 09, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=51518 SEE logic] by [[Youri Matiounine]], [[CCC]], March 08, 2014 » [[Static Exchange Evaluation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=52861 multi-dimensional piece/square tables] by [[Pawel Koziol]], [[CCC]], July 04, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=57384 about pst] by [[Daniel Anulliero]], [[CCC]], August 26, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57575 high values of pst] by [[Daniel Anulliero]], [[CCC]], September 09, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58231 pieces psqt] by [[Alexandru Mosoi]], [[CCC]], November 11, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=61631 Sanity check on piece-value tables] by [[Stuart Riffle]], [[CCC]], October 06, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62257 Simple method for simple mates for programs without TBs] by [[J. Wesley Cleveland]], [[CCC]], November 25, 2016 » [[KBNK Endgame]], [[Mop-up Evaluation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64972 Approximating Stockfish's Evaluation by PSQTs] by [[Thomas Dybdahl Ahle]], [[CCC]], August 23, 2017 » [[Automated Tuning#Regression|Regression]], [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66588 Learning piece-square table] by [[Mathieu Pagé]], [[CCC]], February 13, 2018 » [[Automated Tuning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66966 'ab-initio' piece values] by [[Harm Geert Muller]], [[CCC]], March 30, 2018 » [[Point Value]]

=External Links=
* [http://home.hccnet.nl/h.g.muller/pcsqr.html Evaluation: Piece-Square Tables] from [[Micro-Max]] by [[Harm Geert Muller]]
* [http://www.chessbin.com/post/Piece-Square-Table.aspx piece square table] from [[ChessBin.com]] by [[Adam Berent]]

=References=
<references />

'''[[Evaluation|Up one level]]'''
[[Category:John Cage]]

Navigation menu