Evaluation

From Chessprogramming wiki
Jump to: navigation, search

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). 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 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

External Links

Mathematical Foundations

Chess Evaluation

References

Up one level