Difference between revisions of "Evaluation"

From Chessprogramming wiki
Jump to: navigation, search
(12 intermediate revisions by 2 users not shown)
Line 4: Line 4:
  
 
'''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 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==  
Line 91: Line 95:
 
* [[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 100: Line 105:
 
: [[Knowledge#SearchVersusEvaluation|Search versus Evaluation]]
 
: [[Knowledge#SearchVersusEvaluation|Search versus Evaluation]]
 
* [[Learning]]
 
* [[Learning]]
 +
* [[NNUE]]
 
* [[Oracle]]
 
* [[Oracle]]
 
* [[Point Value]]
 
* [[Point Value]]
Line 259: Line 265:
 
* [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=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]]
 
* [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/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]]
  
 
=External Links=  
 
=External Links=  
Line 267: Line 280:
 
* [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]

Revision as of 20:56, 8 March 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 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

External Links

Mathematical Foundations

Chess Evaluation

References

Up one level