Score
The Score is a value assigned to a node inside a search process, representing the chances of winning or losing. While interior node scores were backed-up from their child nodes by minimaxing, and terminal nodes hold perfect game theoretic values, further leaf nodes have heuristic values assigned.
Contents
Terminal Nodes
Terminal nodes hold perfect game theoretic values for either mate and draw, that is {1,-1,0} for a White win, Black win, or draw, practically, dependent on the type, resolution and range, multiplied by some factor, for instance SHRT_MAX/2 for signed 16-bit words in C or C++.
Mate Scores
A mate score is assigned to terminal mate root position, in White relative minimax either the maximum (black mated) or minimum (white mated) values of the whole value range, in side to move relative negamax metric always the minimum, i.e. VALUE_MATED = -SHRT_MAX/2. Below the root the absolute values of mate scores are usually decremented by ply distance to the root, to encourage programs to prefer shorter mates if winning or longer mates if losing.
Inside a negamax based search, most [1] programs assign VALUE_MATED + ply distance to the root as worst case score if entering a node, which if propagated as mate score along the principal variation to the root, translates in mate in odd plies (positive values), or getting mated in even plies. However, those scores need ply-adjustment if stored as exact score inside the transposition table, and re-adjustment if retrieving from TT. An alternative approach, not only related to mate scores was proposed by Harm Geert Muller, the Delayed-loss bonus as implemented in Micro-Max et al. [2] [3] [4] [5] [6].
Draw Scores
Zero
Assuming symmetric evaluation and negamaxed values, positive scores indicate the side to move is ahead, and negative if behind, which defines the value of zero as a natural draw score, no matter whether the draw is caused by a stalemate, three-fold repetitions, fifty-move rule draw, or draws by insufficient material.
Contempt Factor
Some programs apply a contempt factor, to avoid early draws against apparently weaker opponents, or to prefer draws versus stronger opponents otherwise.
Around Zero
Cray Blitz applied a special draw heuristic, not uniformly using zero as draw score, but rather zero plus the ply distance to the root to prefer later draws rather than a draw now. Additionally, the draw score range is disjoint from evaluation scores, which then exclude values around zero by adding or subtracting appropriate offsets if either greater or equal, or less than zero [7].
Heuristic Nodes
Other leaf nodes than terminal nodes determine a heuristic value of the position by an evaluation function. The value range of heuristic values has a symmetrical reduced value range far outside the mate scores, dominated by the material balance, with the theoretical maximum of
9*VALUE_QUEEN + 2*VALUE_ROOK + 2*VALUE_BISHOP + 2*VALUE_KNIGHT
which is about 115 pawn units, or about 11,500 in centipawn units. Practically it is quite safe to saturate the heuristic eval value range with +-30 to +-50 pawn units, which leaves enough space for disjoint scores for interior node recognizers. Some programs exclude zero as heuristic score, to make heuristic values absolutely disjoint from perfect terminal node scores, which has some issues considering contempt.
Value Range
The value range of the score is determined by the mate scores, which range should be disjoint from the heuristic scores. Therefore, pure heuristic scores often saturate with a usual winning advantage of +- three or four queens. Mate scores or winning scores determined by interior node recognizer aka endgame tablebases, may intersect the range of heuristic scores with huge material difference, for instance to avoid "dumb" queen sacrifices to transpose into a won KBNK with mate in 30 or so.
-oo zero +oo +----------------+-+--------+-+---------------+----+---------------+-+---------+-+---------------+ | mated in 0...N |~| losing |~| -4 queens ... |draw| ... 4 queens |~| winning |~| mate in N...1 | +----------------+-+--------+-+---------------+----+---------------+-+---------+-+---------------+
Value Type
Since floating point arithmetic was too slow or even not available, it was and is quite common to use integers with fixed point pawn unit interpretation. However, if Float and Double are available intrinsic data types inside the target architecture, certain expressions in heuristic evaluation might be done by floating point arithmetic to deal with Precision loss and overflow issues in temporary scaling terms using multiplicative or none-linear functions.
Fixed Point
Heuristic integer scores need to define a fixed point resolution. What is one integer unit about? To cover fractional pawn relative piece values, a pawn unit is a multiple of one integer unit, something like 32, 50, 64, 100 (centipawns), 128, 256 or up to 1000 (millipawns) or more, to allow a smooth relation of all piece values and to make the granularity or grain fine enough to distinguish positional evaluation terms.
Grain
On the other hand, some programmers perform a final rounding of heuristic integer scores from evaluation for a coarser grain, i.e. divide by two or four, yielding in a reduced value range accordingly. The basic idea is to increase search efficiency in alpha-beta and that like, because move ordering becomes less sensitive from arbitrary or noisy centi- or millipawn improvements from later moves. Depending on the program, its search algorithm and evaluation, that may work to some extend. Aske Plaat's MTD(f) Implementation Tips cover the grain of the evaluation [8] :
The coarser the grain of eval, the less passes MTD(f) has to make to converge to the minimax value. Some programs have a fine grained evaluation function, where positional knowledge can be worth as little as one hundredth of a pawn. Big score swings can become inefficient for these programs. It may help to dynamically increase the step size: instead of using the previous bound, one can, for example, add an extra few points in the search direction (for failing high, or searching upward, adding the bonus, and for failing low, or searching downward, subtracting the bonus) every two passes or so. (Don Dailey found that a scheme like this works well in a version of CilkChess.) At the end, if you overshoot the minimax value, you have to make a small search in the opposite direction, using the previous search bound without an extra bonus, to make the final convergence. Also, it can be quite instructive to experiment with different evaluation function grain sizes. Sometimes coarse grain functions work better than fine grain, both for NegaScout and MTD(f).
Arbitrary Bit-field Scores
While calculating and keeping scores in registers or stack is best done 32-bit wise with todays processors, also dealing with Precision loss and overflow issues in temporary multiplicative scaling terms, fewer bits are desirable when storing scores in Hash tables.
For instance, with centipawn resolution a 15-bit signed integer type is appropriate. Sign extended to 16 bit already avoids short signed overflow issues in various additive score comparison terms. Absolute mate score in centipawn resolution is usually SHRT_MAX/2 as defined in C.
Sign Extension
A shiftless sign extension of stored signed values with less bits required than available inside a register (16, 32, 64) might be done by exclusive or and subtraction of the value of the sign bit from the zero extended (shift right and mask, or x86-64 BMI1 BEXTR instruction) value [9] :
X_signextended ::= (X_zeroextended ^ signbit) - signbit
or, since masking is usually required anyway,
X_signextended ::= (X & (signbit-1)) - (X & signbit)
A 15 bit signed integer two's complement value with bit 14 as sign bit, has a signbit value of 0x4000 or 16384. Alternatively, almost with same effort, one may store only positive values, that is signed value + OFFSET, to adjust the retrieved values accordantly.
Floating Point
While todays processors like x86-64 provide fast SIMD instructions with vectors of 32-bit floats, it might be worth to try floating point scores in pawn-units in evaluation, interior node recognizers and search. However, that requires 32-bit inside a hash table entry as well.
Score Types
In alpha-beta, the vast majority of the nodes hold either upper (All-nodes) or lower bounds (Cut-nodes) rather than an exact scores of confirmed PV-nodes. Rather than associate some bound-bits with a score, Don Beal proposed integrated bounds and values integers [10] .
See also
- Alpha-Beta
- B*
- Bound
- Chess Game
- Integrated Bounds and Values
- Interior Node Recognizer
- Mate Distance Pruning
- Pawn Advantage, Win Percentage, and Elo
- Transposition Table
- Score Oscillation
- Tempo
Publications
- Don Beal (1984). Mixing Heuristic and Perfect Evaluations: Nested Minimax. ICCA Journal, Vol. 7, No. 1
- Don Beal (1995). An Integrated-Bounds-and-Values (IBV) Numeric Scale for Minimax Searches. ICCA Journal, Vol. 18, No. 2
- Jacek Mańdziuk, Daniel Osman (2004). Alpha-Beta Search Enhancements with a Real-Value Game-State Evaluation Function. ICGA Journal, Vol. 27, No. 1, pdf
- Mitja Luštrek, Matjaž Gams, Ivan Bratko (2006). Is Real-Valued Minimax Pathological? Artificial Intelligence, Vol. 170, pdf
- Kazutomo Shibahara, Yoshiyuki Kotani (2008). Combining Final Score with Winning Percentage using Sigmoid Function in Monte-Carlo Algorithm. 13th Game Programming Workshop, pdf
Forum Posts
1995 ...
- Re: Which is better, IYHO by Ian Kennedy, rgcc, August 20, 1995
- Using too-shallow mate scores from the hash table by David Eppstein, CCC, July 05, 1998 » Transposition Table, Mate Score
- Re: Using too-shallow mate scores from the hash table by David Eppstein, CCC, July 06, 1998
- Re: Using too-shallow mate scores from the hash table by Don Dailey, CCC, July 07, 1998
2000 ...
- a standard for evaluation score by Gianluigi Masciulli, CCC, May 18, 2000
- Max positional score difference by Nagendra Singh Tomar, CCC, November 15, 2002
- Resign Score by Darren Rushton, CCC, November 20, 2002
- A high pressure squeezed idea - mate and mate score, and speed in verify by Scott Farrell, CCC, December 03, 2002
- Bounds... when is an exact score an EXACT score? by Ross Boyd, CCC, August 01, 2003
2005 ...
- Mate scores in the hash table by Eduardo Waghabi, Winboard Forum, September 02, 2005 » Transposition Table, Checkmate
- Re: Mate scores in the hash table by Bruce Moreland, Winboard Forum, September 04, 2005
- Re: Mate scores in the hash table by Josué Forte, Winboard Forum, September 04, 2005
- The Code for the Rybka-Mate-Bug by Chrilly Donninger, CCC, December 13, 2005 » Rybka
- Delayed-loss-bonus discussion goes here by Harm Geert Muller, CCC, September 28, 2007
- Draw scores by Carey, CCC, October 05, 2007 » Draw, Draw Score
- Evaluation functions. Why integer? by oysteijo, CCC, August 06, 2008
- Centipawns and Millipawns by Ricardo Gibert, CCC, September 08, 2009
2010 ...
- Seeing a promotion, but not playing it... by Harm Geert Muller, CCC, January 24, 2010
- TT score by Luca Hemmerich, CCC, February 03, 2010
- Puzzle with mate scores in TT by Robert Purves, CCC, December 10, 2010 » Transposition Table, Checkmate
- Mate score in TT by Marco Costalba, CCC, December 28, 2011 » Transposition Table, Mate Score
- Rounding by Larry Kaufman, CCC, January 18, 2012
- Multi dimensional score by Nicu Ionita, CCC, April 20, 2012
- houdini3 search and mate scores by Uri Blass, CCC, October 29, 2012 » Houdini
- Stockfish Syzygy: how to interpret mates? by Jouni Uski, CCC, December 01, 2013 » Stockfish, Syzygy Bases
- Mate score from the transposition table by Evert Glebbeek, CCC, October 25, 2014 » Transposition Table, Checkmate
2015 ...
- TT Mate scores by rgoomes, OpenChess Forum, February 10, 2016 » Transposition Table, Checkmate
- Score from white side or from playing side? by Luis Babboni, CCC, September 10, 2016
- reporting engine scores by Mike Adams, CCC, May 02, 2017
- Update Best Score and Best Move by Tamás Kuzmics, CCC, May 10, 2017 » Best Move
- Mate Score by Tamás Kuzmics, CCC, June 27, 2017 » Mate Score
- Statistical interpretation of search and eval scores by J. Wesley Cleveland, CCC, November 18, 2017 » Match Statistics, Pawn Advantage, Win Percentage, and Elo
- Mate scores in TT (a new?... approach) by Vince Sempronio, CCC, April 09, 2018
- Yet another Mate scores in TT thread by Andrew Grant, CCC, April 12, 2018 » Checkmate, Transposition Table
- Draw scores in TT by Srdja Matovic, CCC, April 14, 2018 » Draw, Draw Score, Transposition Table
- Why does stockfish randomise draw evaluations? by Vincent Tang, CCC, September 01, 2019 » Stockfish, Draw Evaluation, Draw Score, Search with Random Leaf Values
- UCI Win/Draw/Loss reporting by Gian-Carlo Pascutto, CCC, October 22, 2019 » UCI, Pawn Advantage, Win Percentage, and Elo
2020 ...
- Win-Draw-Loss evaluation by crem, LCZero blog, April 20, 2020 » TCEC Season 17 Superfinal, Pawn Advantage, Win Percentage, and Elo
- Stockfish has included WDL stats in engine output by Deberger, CCC, July 02, 2020 » Stockfish, Pawn Advantage, Win Percentage, and Elo
- Correct way to store and extract mate scores by Ian Mitchell, CCC, July 08, 2020 » Checkmate, Transposition Table
External Links
- Checkmate/Stalemate Scoring from Bruce Moreland's Programming Topics
- Handling Mate Scores from Bruce Moreland's Programming Topics
- Score from Wikipedia
- Score (game) from Wikipedia
- Fixed point arithmetic from Wikipedia
- Floating point from Wikipedia
- Rounding from Wikipedia
- Kinga Głyk - Difficult Choices, album Dream (2017), YouTube Video
References
- ↑ The Code for the Rybka-Mate-Bug by Chrilly Donninger, CCC, December 13, 2005
- ↑ Evaluation: Aging - The Delay Penalty from Micro-Max by Harm Geert Muller
- ↑ Re: Transposition Tables by Harm Geert Muller, CCC, September 26, 2007
- ↑ Delayed-loss-bonus discussion goes here by Harm Geert Muller, CCC, September 28, 2007
- ↑ Seeing a promotion, but not playing it... by Harm Geert Muller, CCC, January 24, 2010
- ↑ Re: The cause of extreme piece shuffling by Harm Geert Muller, CCC, January 11, 2016
- ↑ Harry Nelson, Robert Hyatt (1988). The Draw Heuristic of Cray Blitz. ICCA Journal, Vol. 11, No. 1
- ↑ MTD(f) - A Minimax Algorithm faster than NegaScout by Aske Plaat
- ↑ Sign Extension from The Aggregate Magic Algorithms by Hank Dietz
- ↑ Don Beal (1995). An Integrated-Bounds-and-Values (IBV) Numeric Scale for Minimax Searches. ICCA Journal, Vol. 18, No. 2