Home * Search * Score
220px-Icosahedron.svg.png

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.
An Icosahedron has 20 faces [1]

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 [2] 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. [3] [4] [5] [6] [7].

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 [8].

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 [9] :
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 [10] :
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.

Bounds

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 [11] .

See also


Publications


Forum Posts

1995 ...

2000 ...

2005 ...

2010 ...

2015 ...


External Links


References

  1. ^ 20 (number) from Wikipedia
  2. ^ The Code for the Rybka-Mate-Bug by Chrilly Donninger, CCC, December 13, 2005
  3. ^ Evaluation: Aging - The Delay Penalty from Micro-Max by Harm Geert Muller
  4. ^ Re: Transposition Tables by Harm Geert Muller, CCC, September 26, 2007
  5. ^ Delayed-loss-bonus discussion goes here by Harm Geert Muller, CCC, September 28, 2007
  6. ^ Seeing a promotion, but not playing it... by Harm Geert Muller, CCC, January 24, 2010
  7. ^ Re: The cause of extreme piece shuffling by Harm Geert Muller, CCC, January 11, 2016
  8. ^ Harry Nelson, Robert Hyatt (1988). The Draw Heuristic of Cray Blitz. ICCA Journal, Vol. 11, No. 1
  9. ^ MTD(f) - A Minimax Algorithm faster than NegaScout by Aske Plaat
  10. ^ Sign Extension from The Aggregate Magic Algorithms by Hank Dietz
  11. ^ Don Beal (1995). An Integrated-Bounds-and-Values (IBV) Numeric Scale for Minimax Searches. ICCA Journal, Vol. 18, No. 2

What links here?


Up one Level