Difference between revisions of "Evaluation"

From Chessprogramming wiki
Jump to: navigation, search
 
(2020 ...)
 
(31 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * Evaluation'''
 
'''[[Main Page|Home]] * Evaluation'''
  
[[FILE:Schach-Theorie.jpg|border|right|thumb|link=https://www.pinterest.de/pin/58476495131654514/|  [[Arts#Kandinsky|Wassily Kandinsky]], Schach-Theorie, 1937 <ref>[https://www.pinterest.de/pin/58476495131654514/ Vassily Kandinsky - Schach-Theorie | Art I love | Pinterest]</ref> ]]  
+
[[FILE:Schach-Theorie.jpg|border|right|thumb|link=https://www.pinterest.de/pin/58476495131654514/|  [[:Category:Wassily Kandinsky|Wassily Kandinsky]] - Schach-Theorie, 1937 <ref>[https://www.pinterest.de/pin/58476495131654514/ Vassily Kandinsky - Schach-Theorie | Art I love | Pinterest]</ref> ]]  
  
 
'''Evaluation''',<br/>
 
'''Evaluation''',<br/>
a [https://en.wikipedia.org/wiki/Heuristic_(computer_science) heuristic function] to determine the [[Score|relative value]] of a [[Chess Position|position]], i.e. the chances of winning. If we could see to the end of the game in every line, the evaluation would only have values of -1 (loss), 0 (draw), and 1 (win). In practice, however, we do not know the exact value of a position, so we must make an approximation. Beginning chess players learn to do this starting with the [[Point Value|value]] of the [[Pieces|pieces]] themselves. Computer evaluation functions also use the value of the [[Material|material balance]] as the most significant aspect and then add other considerations.  
+
a [https://en.wikipedia.org/wiki/Heuristic_(computer_science) heuristic function] to determine the [[Score|relative value]] of a [[Chess Position|position]], i.e. the chances of winning. If we could see to the end of the game in every line, the evaluation would only have values of -1 (loss), 0 (draw), and 1 (win), and the chess engine should search to depth 1 only to get the best move. In practice, however, we do not know the exact value of a position, so we must make an approximation with the main purpose is to compare positions, and the chess engine now must search deeply and find the highest score position within a given period.
 +
 
 +
Recently, there are two main ways to build an evaluation: traditional '''hand-crafted evaluation''' (HCE) and multi-layer [[Neural Networks|neural networks]]. This page focuses on the traditional way considering explicit features of a [[Chess Position|chess position]].  
 +
 
 +
Beginning chess players learn to do this starting with the [[Point Value|value]] of the [[Pieces|pieces]] themselves. Computer evaluation functions also use the value of the [[Material|material balance]] as the most significant aspect and then add other considerations.  
  
 
=Where to Start=  
 
=Where to Start=  
Line 48: Line 52:
 
and second if the function is [https://en.wikipedia.org/wiki/Homogeneous_function homogeneous] of degree 1:
 
and second if the function is [https://en.wikipedia.org/wiki/Homogeneous_function homogeneous] of degree 1:
 
: [[FILE:EvalLinearFormula3.jpg|none|border|text-bottom]]
 
: [[FILE:EvalLinearFormula3.jpg|none|border|text-bottom]]
It depends on the definition and [https://en.wikipedia.org/wiki/Linear_independence independence] of features and the acceptance of the [https://en.wikipedia.org/wiki/Axiom_of_choice axiom of choice] ([[Ernst Zermelo]] 1904), whether additive real number functions are linear or not <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=288501&t=29552 Re: Linear vs. Nonlinear Evalulation] by [[Tord Romstad]], [[CCC]], August 27, 2009</ref> . Features are either related to single pieces ([[Material|material]]), their location ([[Piece-Square Tables|piece-square tables]]), or more sophisticated, considering interactions of multiple pawns and pieces, based on certain [[Evaluation Patterns|patterns]] or [[Chunking|chunks]]. Often several phases to first process simple features and after building appropriate data structures, in consecutive phases more complex features based on patterns and chunks are used.
+
It depends on the definition and [https://en.wikipedia.org/wiki/Linear_independence independence] of features and the acceptance of the [https://en.wikipedia.org/wiki/Axiom_of_choice axiom of choice] ([[Ernst Zermelo]] 1904), whether additive real number functions are linear or not <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=288501&t=29552 Re: Linear vs. Nonlinear Evaluation] by [[Tord Romstad]], [[CCC]], August 27, 2009</ref> . Features are either related to single pieces ([[Material|material]]), their location ([[Piece-Square Tables|piece-square tables]]), or more sophisticated, considering interactions of multiple pawns and pieces, based on certain [[Evaluation Patterns|patterns]] or [[Chunking|chunks]]. Often several phases to first process simple features and after building appropriate data structures, in consecutive phases more complex features based on patterns and chunks are used.
  
Based on that, to distinguish [https://en.wikipedia.org/wiki/First-order first-order], [https://en.wikipedia.org/wiki/Second-order second-order], etc. terms, makes more sense than using the arbitrary terms linear vs. nonlinear evaluation <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=288564&t=29552 Re: Linear vs. Nonlinear Evalulation] by [[Robert Hyatt]], [[CCC]], August 27, 2009</ref> . With respect to [[Automated Tuning|tuning]], one has to take care that features are independent, which is not always that simple. Hidden dependencies may otherwise make the evaluation function hard to maintain with undesirable nonlinear effects.
+
Based on that, to distinguish [https://en.wikipedia.org/wiki/First-order first-order], [https://en.wikipedia.org/wiki/Second-order second-order], etc. terms, makes more sense than using the arbitrary terms linear vs. nonlinear evaluation <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=288564&t=29552 Re: Linear vs. Nonlinear Evaluation] by [[Robert Hyatt]], [[CCC]], August 27, 2009</ref> . With respect to [[Automated Tuning|tuning]], one has to take care that features are independent, which is not always that simple. Hidden dependencies may otherwise make the evaluation function hard to maintain with undesirable nonlinear effects.
  
 
==General Aspects==  
 
==General Aspects==  
 
* [[Evaluation Philosophy]]
 
* [[Evaluation Philosophy]]
* [[Pawn Advantage, Win Percentage, and ELO]]
+
* [[Pawn Advantage, Win Percentage, and Elo]]
 
* [[Score#ValueRange|Value Range]]
 
* [[Score#ValueRange|Value Range]]
  
Line 62: Line 66:
 
* [[Pawn Structure]]
 
* [[Pawn Structure]]
 
* [[Evaluation of Pieces]]
 
* [[Evaluation of Pieces]]
 +
* [[Evaluation Patterns]]
 
* [[Mobility]]
 
* [[Mobility]]
 
* [[Center Control]]
 
* [[Center Control]]
Line 88: Line 93:
 
* [[Evaluation Patterns]]
 
* [[Evaluation Patterns]]
 
* [[Lazy Evaluation]]
 
* [[Lazy Evaluation]]
* [[Quantifying Evaluation features]] by [[Mark Watkins]]
+
* [[Quantifying Evaluation Features]] by [[Mark Watkins]]
* [[Simplified evaluation function]]
+
* [[Simplified Evaluation Function]]
 +
* [[PeSTO's Evaluation Function]]
  
 
=See also=  
 
=See also=  
Line 99: Line 105:
 
: [[Knowledge#SearchVersusEvaluation|Search versus Evaluation]]
 
: [[Knowledge#SearchVersusEvaluation|Search versus Evaluation]]
 
* [[Learning]]
 
* [[Learning]]
 +
* [[NNUE]]
 
* [[Oracle]]
 
* [[Oracle]]
 
* [[Point Value]]
 
* [[Point Value]]
Line 111: Line 118:
 
* [[Alan Turing]] ('''1953'''). '''''Chess'''''. part of the collection ''Digital Computers Applied to Games'', in [https://en.wikipedia.org/wiki/B._V._Bowden,_Baron_Bowden Bertram Vivian Bowden] (editor), [http://www.computinghistory.org.uk/cgi-bin/sitewise.pl?act=det&p=10719 Faster Than Thought], a symposium on digital computing machines, reprinted 1988 in [[Computer Chess Compendium]], reprinted 2004 in ''The Essential Turing'', [http://books.google.com/books?id=RSkxnKlv1D4C&lpg=PP882&ots=VOWmiIm_lD&dq=Turochamp%2C%20chess&pg=PP881#v=onepage&q&f=true google books]
 
* [[Alan Turing]] ('''1953'''). '''''Chess'''''. part of the collection ''Digital Computers Applied to Games'', in [https://en.wikipedia.org/wiki/B._V._Bowden,_Baron_Bowden Bertram Vivian Bowden] (editor), [http://www.computinghistory.org.uk/cgi-bin/sitewise.pl?act=det&p=10719 Faster Than Thought], a symposium on digital computing machines, reprinted 1988 in [[Computer Chess Compendium]], reprinted 2004 in ''The Essential Turing'', [http://books.google.com/books?id=RSkxnKlv1D4C&lpg=PP882&ots=VOWmiIm_lD&dq=Turochamp%2C%20chess&pg=PP881#v=onepage&q&f=true google books]
 
==1960 ...==  
 
==1960 ...==  
* [https://en.wikipedia.org/wiki/Israel_Albert_Horowitz Israel Albert Horowitz], [https://en.wikipedia.org/wiki/Mott-Smith_Trophy Geoffrey Mott-Smith] ('''1960,1970,2012'''). ''[http://www.chess-game-strategies.com/point-count-chess.html Point Count Chess]''.  [https://en.wikipedia.org/wiki/Samuel_Reshevsky Samuel Reshevsky] (Introduction), [[Sam Sloan]] (2012 Introduction), [http://www.amazon.com/Point-Count-Chess-Accurate-Winning/dp/4871874699/ref=sr_1_2?s=books&ie=UTF8&qid=1366734801&sr=1-2 Amazon] <ref>[https://www.stmintz.com/ccc/index.php?id=25046 Re: Books that help for evaluation] by [[Robert Hyatt]], [[CCC]], August 18, 1998</ref>
+
* [https://en.wikipedia.org/wiki/Israel_Albert_Horowitz Israel Albert Horowitz], [https://en.wikipedia.org/wiki/Mott-Smith_Trophy Geoffrey Mott-Smith] ('''1960,1970,2012'''). ''Point Count Chess''.  [https://en.wikipedia.org/wiki/Samuel_Reshevsky Samuel Reshevsky] (Introduction), [[Sam Sloan]] (2012 Introduction), [http://www.amazon.com/Point-Count-Chess-Accurate-Winning/dp/4871874699/ref=sr_1_2?s=books&ie=UTF8&qid=1366734801&sr=1-2 Amazon] <ref>[https://www.stmintz.com/ccc/index.php?id=25046 Re: Books that help for evaluation] by [[Robert Hyatt]], [[CCC]], August 18, 1998</ref>
 
* [[Jack Good]] ('''1968'''). ''A Five-Year Plan for Automatic Chess.'' Machine Intelligence II pp. 110-115
 
* [[Jack Good]] ('''1968'''). ''A Five-Year Plan for Automatic Chess.'' Machine Intelligence II pp. 110-115
 
==1970 ...==
 
==1970 ...==
*  [[Ron Atkin]] ('''1972'''). ''Multi-Dimensional Structure in the Game of Chess''. In [http://www.interaction-design.org/references/periodicals/international_journal_of_man-machine_studies_volume_4.html International Journal of Man-Machine Studies, Vol. 4]
+
*  [[Ron Atkin]] ('''1972'''). ''Multi-Dimensional Structure in the Game of Chess''. In International Journal of Man-Machine Studies, Vol. 4
* [[Ron Atkin]], [[Ian H. Witten]] ('''1975'''). ''[http://www.bibsonomy.org/bibtex/2b91106ea980eb48aa505f6b54c130707/dblp A Multi-Dimensional Approach to Positional Chess]''. [http://www.interaction-design.org/references/periodicals/international_journal_of_man-machine_studies_volume_7.html International Journal of Man-Machine Studies, Vol. 7, No. 6]
+
* [[Ron Atkin]], [[Ian H. Witten]] ('''1975'''). ''[http://www.bibsonomy.org/bibtex/2b91106ea980eb48aa505f6b54c130707/dblp A Multi-Dimensional Approach to Positional Chess]''. International Journal of Man-Machine Studies, Vol. 7, No. 6
 
* [[Gerard Zieliński]] ('''1976'''). ''[http://www.emeraldinsight.com/doi/abs/10.1108/eb005425 Simple Evaluation Function]''. [http://www.emeraldinsight.com/loi/k Kybernetes], Vol. 5, No. 3
 
* [[Gerard Zieliński]] ('''1976'''). ''[http://www.emeraldinsight.com/doi/abs/10.1108/eb005425 Simple Evaluation Function]''. [http://www.emeraldinsight.com/loi/k Kybernetes], Vol. 5, No. 3
 
* [[Ron Atkin]] ('''1977'''). ''Positional Play in Chess by Computer''. [[Advances in Computer Chess 1]]
 
* [[Ron Atkin]] ('''1977'''). ''Positional Play in Chess by Computer''. [[Advances in Computer Chess 1]]
Line 151: Line 158:
 
* [[Jeff Rollason]] ('''2005'''). ''[http://www.aifactory.co.uk/newsletter/2005_03_hill-climbing.htm Evaluation by Hill-climbing: Getting the right move by solving micro-problems]''. [[AI Factory]], Autumn 2005 » [[Automated Tuning]]
 
* [[Jeff Rollason]] ('''2005'''). ''[http://www.aifactory.co.uk/newsletter/2005_03_hill-climbing.htm Evaluation by Hill-climbing: Getting the right move by solving micro-problems]''. [[AI Factory]], Autumn 2005 » [[Automated Tuning]]
 
* [[Shogo Takeuchi]], [[Tomoyuki Kaneko]], [[Kazunori Yamaguchi]], [[Satoru Kawai]] ('''2007'''). ''Visualization and Adjustment of Evaluation Functions Based on Evaluation Values and Win Probability''. [http://www.informatik.uni-trier.de/~ley/db/conf/aaai/aaai2007.html AAAI 2007]
 
* [[Shogo Takeuchi]], [[Tomoyuki Kaneko]], [[Kazunori Yamaguchi]], [[Satoru Kawai]] ('''2007'''). ''Visualization and Adjustment of Evaluation Functions Based on Evaluation Values and Win Probability''. [http://www.informatik.uni-trier.de/~ley/db/conf/aaai/aaai2007.html AAAI 2007]
* [[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2008'''). ''Genetic Algorithms for Mentor-Assisted Evaluation Function Optimization'', ACM Genetic and Evolutionary Computation Conference ([http://www.sigevo.org/gecco-2008/ GECCO '08]), pp. 1469-1475, Atlanta, GA, July 2008.
+
* [[Eli David|Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2008'''). ''Genetic Algorithms for Mentor-Assisted Evaluation Function Optimization'', ACM Genetic and Evolutionary Computation Conference ([http://www.sigevo.org/gecco-2008/ GECCO '08]), pp. 1469-1475, Atlanta, GA, July 2008.
* [[Omid David]], [[Jaap van den Herik]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2009'''). ''Simulating Human Grandmasters: Evolution and Coevolution of Evaluation Functions''. [[ACM]] Genetic and Evolutionary Computation Conference ([http://www.sigevo.org/gecco-2009/ GECCO '09]), pp. 1483 - 1489, Montreal, Canada, July 2009.
+
* [[Eli David|Omid David]], [[Jaap van den Herik]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2009'''). ''Simulating Human Grandmasters: Evolution and Coevolution of Evaluation Functions''. [[ACM]] Genetic and Evolutionary Computation Conference ([http://www.sigevo.org/gecco-2009/ GECCO '09]), pp. 1483 - 1489, Montreal, Canada, July 2009.
* [[Omid David]] ('''2009'''). ''Genetic Algorithms Based Learning for Evolving Intelligent Organisms''. Ph.D. Thesis.
+
* [[Eli David|Omid David]] ('''2009'''). ''Genetic Algorithms Based Learning for Evolving Intelligent Organisms''. Ph.D. Thesis.
 
==2010 ...==  
 
==2010 ...==  
 
* [[Lyudmil Tsvetkov]] ('''2010'''). ''Little Chess Evaluation Compendium''. [http://www.winboardengines.de/doc/LittleChessEvaluationCompendium-2010-04-07.pdf 2010 pdf]
 
* [[Lyudmil Tsvetkov]] ('''2010'''). ''Little Chess Evaluation Compendium''. [http://www.winboardengines.de/doc/LittleChessEvaluationCompendium-2010-04-07.pdf 2010 pdf]
* [[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2011'''). ''Expert-Driven Genetic Algorithms for Simulating Evaluation Functions''. Genetic Programming and Evolvable Machines, Vol. 12, No. 1, pp. 5--22, March 2011. » [[Genetic Programming]]
+
* [[Eli David|Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2011'''). ''Expert-Driven Genetic Algorithms for Simulating Evaluation Functions''. Genetic Programming and Evolvable Machines, Vol. 12, No. 1, pp. 5--22, March 2011. » [[Genetic Programming]]
 
* [[Jeff Rollason]] ('''2011'''). ''[http://www.aifactory.co.uk/newsletter/2011_02_mcts_static.htm Mixing MCTS with Conventional Static Evaluation]''. [[AI Factory]], Winter 2011 » [[Monte-Carlo Tree Search]]
 
* [[Jeff Rollason]] ('''2011'''). ''[http://www.aifactory.co.uk/newsletter/2011_02_mcts_static.htm Mixing MCTS with Conventional Static Evaluation]''. [[AI Factory]], Winter 2011 » [[Monte-Carlo Tree Search]]
 
* [[Jeff Rollason]] ('''2012'''). ''[http://www.aifactory.co.uk/newsletter/2012_01_evaluation_options.htm Evaluation options - Overview of methods]''. [[AI Factory]], Summer 2012
 
* [[Jeff Rollason]] ('''2012'''). ''[http://www.aifactory.co.uk/newsletter/2012_01_evaluation_options.htm Evaluation options - Overview of methods]''. [[AI Factory]], Summer 2012
Line 177: Line 184:
 
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/40fe48d492e582bd Evaluation function question] by [[David Fotland|Dave Fotland]], [[Computer Chess Forums|rgcc]], February 07, 1997
 
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/40fe48d492e582bd Evaluation function question] by [[David Fotland|Dave Fotland]], [[Computer Chess Forums|rgcc]], February 07, 1997
 
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/99eec6923b0481db computer chess "oracle" ideas...] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], April 01, 1997 » [[Oracle]]
 
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/99eec6923b0481db computer chess "oracle" ideas...] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], April 01, 1997 » [[Oracle]]
* [https://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/77f10f072e907302 Evolutionary Evaluation] by [[Dan Homan]], [[Computer Chess Forums|rgcc]], September 09, 1997 » [[Automated Tuning]]
+
* [https://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/77f10f072e907302 Evolutionary Evaluation] by [[Daniel Homan]], [[Computer Chess Forums|rgcc]], September 09, 1997 » [[Automated Tuning]]
 
* [https://www.stmintz.com/ccc/index.php?id=25012 Books that help for evaluation] by [[Guido Schimmels]], [[CCC]], August 18, 1998
 
* [https://www.stmintz.com/ccc/index.php?id=25012 Books that help for evaluation] by [[Guido Schimmels]], [[CCC]], August 18, 1998
 
* [https://www.stmintz.com/ccc/index.php?id=80569 Static evaluation after the "Positional/Real Sacrifice"] by [[Andrew Williams]], [[CCC]], December 03, 1999
 
* [https://www.stmintz.com/ccc/index.php?id=80569 Static evaluation after the "Positional/Real Sacrifice"] by [[Andrew Williams]], [[CCC]], December 03, 1999
Line 189: Line 196:
 
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4155#p21292 Do you evaluate internal nodes?] by [[Tord Romstad]], [[Computer Chess Forums|Winboard Forum]], January 16, 2006 » [[Interior Node]]
 
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4155#p21292 Do you evaluate internal nodes?] by [[Tord Romstad]], [[Computer Chess Forums|Winboard Forum]], January 16, 2006 » [[Interior Node]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=13969 question about symmertic evaluation] by [[Uri Blass]], [[CCC]], May 23, 2007
 
* [http://www.talkchess.com/forum/viewtopic.php?t=13969 question about symmertic evaluation] by [[Uri Blass]], [[CCC]], May 23, 2007
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=15220 Trouble Spotter] by [[Harm Geert Muller]], [[CCC]], July 19, 2007 » [[Tactics]]
 
* [http://www.hiarcs.net/forums/viewtopic.php?t=402 Search or Evaluation?] by [[Ed Schroder|Ed Schröder]], [[Computer Chess Forums|Hiarcs Forum]], October 05, 2007 » [[Knowledge#SearchVersusEvaluation|Search versus Evaluation]], [[Search]]
 
* [http://www.hiarcs.net/forums/viewtopic.php?t=402 Search or Evaluation?] by [[Ed Schroder|Ed Schröder]], [[Computer Chess Forums|Hiarcs Forum]], October 05, 2007 » [[Knowledge#SearchVersusEvaluation|Search versus Evaluation]], [[Search]]
 
: [http://www.hiarcs.net/forums/viewtopic.php?p=2944 Re: Search or Evaluation?] by [[Mark Uniacke]], [[Computer Chess Forums|Hiarcs Forum]], October 14, 2007
 
: [http://www.hiarcs.net/forums/viewtopic.php?p=2944 Re: Search or Evaluation?] by [[Mark Uniacke]], [[Computer Chess Forums|Hiarcs Forum]], October 14, 2007
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=20340 Problems with eval function] by [[Fermin Serrano]], [[CCC]], March 25, 2008 » [[Evaluation]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=22817 Evaluation functions. Why integer?] by oysteijo, [[CCC]], August 06, 2008 » [[Float]], [[Score]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=22817 Evaluation functions. Why integer?] by oysteijo, [[CCC]], August 06, 2008 » [[Float]], [[Score]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=24052 Smooth evaluation] by [[Fermin Serrano]], [[CCC]], September 29, 2008
 
* [http://www.talkchess.com/forum/viewtopic.php?t=25795 Evaluating every node?] by [[Gregory Strong]], [[CCC]], January 03, 2009
 
* [http://www.talkchess.com/forum/viewtopic.php?t=25795 Evaluating every node?] by [[Gregory Strong]], [[CCC]], January 03, 2009
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=26700 Evaluation idea] by [[Fermin Serrano]], [[CCC]], February 24, 2009
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=27055 Accurate eval function] by [[Fermin Serrano]], [[CCC]], March 18, 2009
 
* [http://www.talkchess.com/forum/viewtopic.php?t=27299 Eval Dilemma] by [[Edsel Apostol]], [[CCC]], April 03, 2009
 
* [http://www.talkchess.com/forum/viewtopic.php?t=27299 Eval Dilemma] by [[Edsel Apostol]], [[CCC]], April 03, 2009
 
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=288424 Linear vs. Nonlinear Evalulation] by [[Gerd Isenberg]], [[CCC]], August 26, 2009
 
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=288424 Linear vs. Nonlinear Evalulation] by [[Gerd Isenberg]], [[CCC]], August 26, 2009
Line 251: Line 263:
 
'''2018'''
 
'''2018'''
 
* [http://www.talkchess.com/forum/viewtopic.php?t=66413 replace the evaluation by playing against yourself] by [[Uri Blass]], [[CCC]], January 25, 2018 » [[Fortress]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=66413 replace the evaluation by playing against yourself] by [[Uri Blass]], [[CCC]], January 25, 2018 » [[Fortress]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=67524 Poor man's neurones] by [[Pawel Koziol]], [[CCC]], May 21, 2018 » [[Neural Networks]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=67877 Xiangqi evaluation] by [[Harm Geert Muller]], [[CCC]], July 01, 2018 » [[Chinese Chess|Xiangqi]]
 +
==2020 ...==
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74652 romantic-style play] by [[Stuart Cracraft]], [[CCC]], August 02, 2020
 +
* [https://prodeo.actieforum.com/t120-engine-choosing-between-sets-of-piece-square-tables Engine choosing between sets of piece/square tables] by [[Pawel Koziol]], [[Computer Chess Forums|ProDeo Forum]], December 05, 2020 » [[Rodent]], [[Piece-Square Tables]]
 +
* [https://prodeo.actieforum.com/t123-controlled-randomness-of-evaluation-function Controlled randomness of evaluation function] by [[Pawel Koziol|nescitus]], [[Computer Chess Forums|ProDeo Forum]], December 06, 2020
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76161 Manually tuned evaluation] by [[Maksim Korzh]], [[CCC]], December 27, 2020 » [[Simplified Evaluation Function]]
 +
'''2021'''
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=76446 So what do we miss in the traditional evaluation?] by [[Ferdinand Mosca]], [[CCC]], January 29, 2021 » [[NNUE]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76556 HCE and NNUE and vectorisation] by [[Vivien Clauzon]], [[CCC]], February 11, 2021 » [[NNUE]], [[Minic]]
 +
* [https://groups.google.com/g/lczero/c/TLCMkkdm1hw/m/erjTVGUqAQAJ Idea: use range (evalMin - evalMax) for position evaluation] by Mirza Hadzic, [[Computer Chess Forums|LCZero Forum]], April 6, 2021
 +
: [https://groups.google.com/g/lczero/c/TLCMkkdm1hw/m/SgbGghzhBAAJ Re: Idea: use range (evalMin - evalMax) for position evaluation] by [[Álvaro Begué]], [[Computer Chess Forums|LCZero Forum]], May 28, 2021 <ref>[[Eric B. Baum]], [[Warren D. Smith]] ('''1999'''). ''[https://www.mitpressjournals.org/doi/abs/10.1162/089976699300016881?journalCode=neco Propagating Distributions Up Directed Acyclic Graphs]''. [https://en.wikipedia.org/wiki/Neural_Computation_%28journal%29 Neural Computation], Vol. 11, No. 1</ref>
 +
: [https://groups.google.com/g/lczero/c/TLCMkkdm1hw/m/F9JjnN8FBQAJ Re: Idea: use range (evalMin - evalMax) for position evaluation] by [[Warren D. Smith]], [[Computer Chess Forums|LCZero Forum]], May 29, 2021
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=77571 I declare that HCE is dead...] by [[Andrew Grant]], [[CCC]], June 29, 2021 » [[Ethereal]], [[NNUE]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77952 Evaluation questions] by [[Ellie Moore]], [[CCC]], August 16, 2021
  
 
=External Links=  
 
=External Links=  
Line 259: Line 286:
 
* [https://en.wikipedia.org/wiki/Orthogonality Orthogonality from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Orthogonality Orthogonality from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Principal_component_analysis Principal component analysis from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Principal_component_analysis Principal component analysis from Wikipedia]
 
 
==Chess Evaluation==
 
==Chess Evaluation==
 
* [https://en.wikipedia.org/wiki/Evaluation_function Evaluation function from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Evaluation_function Evaluation function from Wikipedia]
 
* [https://hxim.github.io/Stockfish-Evaluation-Guide/ Stockfish Evaluation Guide] » [[Stockfish#EvaluationGuide|Stockfish Evaluation Guide]]
 
* [https://hxim.github.io/Stockfish-Evaluation-Guide/ Stockfish Evaluation Guide] » [[Stockfish#EvaluationGuide|Stockfish Evaluation Guide]]
* [http://www.top-5000.nl/authors/rebel/chess840.htm#HW Evaluation in REBEL] by [[Ed Schroder|Ed Schröder]] » [[Rebel]]
+
* [https://github.com/gekomad/chess-engine-eval-debugger GitHub - gekomad/chess-engine-eval-debugger: Chess engine web evaluator] by [[Giuseppe Cannella]]
* [http://www.top-5000.nl/eval.htm The value of an evaluation function] by [[Ed Schroder|Ed Schröder]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=44014 The value of an evaluation function] by [[Ed Schroder|Ed Schröder]], [[CCC]], June 11, 2012</ref>
 
* [http://rebel13.nl/efs/index.html Rebel - The EFS project] from [http://rebel13.nl/index.html Rebel Pure Nostalgica] by [[Ed Schroder|Ed Schröder]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=57087 (E)valuation (F)or (S)tarters] by [[Ed Schroder|Ed Schröder]], [[CCC]], July 26, 2015</ref>
 
 
* [http://home.hccnet.nl/h.g.muller/eval.html Evaluation: Basics] of [[Micro-Max]] by [[Harm Geert Muller]]
 
* [http://home.hccnet.nl/h.g.muller/eval.html Evaluation: Basics] of [[Micro-Max]] by [[Harm Geert Muller]]
 
* [http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-vi-evaluation-functions-r1208 Chess Programming Part VI: Evaluation Functions] by [[François-Dominic Laramée]], [https://en.wikipedia.org/wiki/GameDev.net gamedev.net], October 2000
 
* [http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-vi-evaluation-functions-r1208 Chess Programming Part VI: Evaluation Functions] by [[François-Dominic Laramée]], [https://en.wikipedia.org/wiki/GameDev.net gamedev.net], October 2000
* [http://www.chessbin.com/post/Chess-Board-Evaluation.aspx Chess Board Evaluation] by [[Adam Berent]]
 
 
* [http://www.chessvariants.com/d.betza/pieceval/index.html About the Values of Chess Pieces] by [[Ralph Betza]]
 
* [http://www.chessvariants.com/d.betza/pieceval/index.html About the Values of Chess Pieces] by [[Ralph Betza]]
  

Latest revision as of 08:34, 9 September 2021

Home * Evaluation

Wassily Kandinsky - Schach-Theorie, 1937 [1]

Evaluation,
a heuristic function to determine the relative value of a position, i.e. the chances of winning. If we could see to the end of the game in every line, the evaluation would only have values of -1 (loss), 0 (draw), and 1 (win), and the chess engine should search to depth 1 only to get the best move. In practice, however, we do not know the exact value of a position, so we must make an approximation with the main purpose is to compare positions, and the chess engine now must search deeply and find the highest score position within a given period.

Recently, there are two main ways to build an evaluation: traditional hand-crafted evaluation (HCE) and multi-layer neural networks. This page focuses on the traditional way considering explicit features of a chess position.

Beginning chess players learn to do this starting with the value of the pieces themselves. Computer evaluation functions also use the value of the material balance as the most significant aspect and then add other considerations.

Where to Start

The first thing to consider when writing an evaluation function is how to score a move in Minimax or the more common NegaMax framework. While Minimax usually associates the white side with the max-player and black with the min-player and always evaluates from the white point of view, NegaMax requires a symmetric evaluation in relation to the side to move. We can see that one must not score the move per se – but the result of the move (i.e. a positional evaluation of the board as a result of the move). Such a symmetric evaluation function was first formulated by Claude Shannon in 1949 [2] :

f(p) = 200(K-K')
       + 9(Q-Q')
       + 5(R-R')
       + 3(B-B' + N-N')
       + 1(P-P')
       - 0.5(D-D' + S-S' + I-I')
       + 0.1(M-M') + ...

KQRBNP = number of kings, queens, rooks, bishops, knights and pawns
D,S,I = doubled, blocked and isolated pawns
M = Mobility (the number of legal moves)

Here, we can see that the score is returned as a result of subtracting the current side's score from the equivalent evaluation of the opponent's board scores (indicated by the prime letters K' Q' and R'.. ).

Side to move relative

In order for NegaMax to work, it is important to return the score relative to the side being evaluated. For example, consider a simple evaluation, which considers only material and mobility:

materialScore = kingWt  * (wK-bK)
              + queenWt * (wQ-bQ)
              + rookWt  * (wR-bR)
              + knightWt* (wN-bN)
              + bishopWt* (wB-bB)
              + pawnWt  * (wP-bP)

mobilityScore = mobilityWt * (wMobility-bMobility)

return the score relative to the side to move (who2Move = +1 for white, -1 for black):

Eval  = (materialScore + mobilityScore) * who2Move

Linear vs. Nonlinear

Most evaluations terms are a linear combination of independent features and associated weights in the form of

EvalLinearFormula1.jpg

A function f is linear if the function is additive:

EvalLinearFormula2.jpg

and second if the function is homogeneous of degree 1:

EvalLinearFormula3.jpg

It depends on the definition and independence of features and the acceptance of the axiom of choice (Ernst Zermelo 1904), whether additive real number functions are linear or not [3] . Features are either related to single pieces (material), their location (piece-square tables), or more sophisticated, considering interactions of multiple pawns and pieces, based on certain patterns or chunks. Often several phases to first process simple features and after building appropriate data structures, in consecutive phases more complex features based on patterns and chunks are used.

Based on that, to distinguish first-order, second-order, etc. terms, makes more sense than using the arbitrary terms linear vs. nonlinear evaluation [4] . With respect to tuning, one has to take care that features are independent, which is not always that simple. Hidden dependencies may otherwise make the evaluation function hard to maintain with undesirable nonlinear effects.

General Aspects

Basic Evaluation Features

Considering Game Phase

Opening
Middlegame
Endgame

Miscellaneous

See also

Search versus Evaluation

Publications

1949

1950 ...

1960 ...

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...

2015 ...

Blog & Forum Posts

1993 ...

1995 ...

2000 ...

2005 ...

Re: Search or Evaluation? by Mark Uniacke, Hiarcs Forum, October 14, 2007

2010 ...

2011

2012

2013

2014

2015 ...

2016

2017

2018

2020 ...

2021

Re: Idea: use range (evalMin - evalMax) for position evaluation by Álvaro Begué, LCZero Forum, May 28, 2021 [12]
Re: Idea: use range (evalMin - evalMax) for position evaluation by Warren D. Smith, LCZero Forum, May 29, 2021

External Links

Mathematical Foundations

Chess Evaluation

References

Up one level