Skip to content
Last Dictionary
Plane
Symbolic & Classical AIReinforcement Learning

evaluation function

nounAlso: static evaluation function, heuristic evaluation function, position evaluation, horizon effect, quiescence search, NNUE

In plain wordsIn a game-playing program, a formula that looks at a board position and gives it a score saying how good it is, without playing the game out to the end.

  1. Game playing

    A function that estimates the value of a non-terminal game position from one player's point of view, applied at the frontier of a depth-limited game treegame tree, n.: A branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws. search such as minimaxminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best. with alpha–beta pruningalpha–beta pruning, n.: A shortcut for game programs: tracking the best result each side is already sure of, it ignores lines of play that could only do worse, and when promising moves come first it searches about twice as deep.. Classical evaluation functions are weighted sums of hand-designed features — material balance, mobility, king safety and pawn structure in chess — with weights set by hand or tuned automatically. Because a fixed depth cutoff can misjudge positions in the middle of an exchange (the horizon effect), programs extend the search in volatile positions (quiescence search). Since 2016 learned evaluations have dominated: AlphaGoAlphaGo, prop. n.: A DeepMind program that in 2016 beat Lee Sedol, one of the world's best players of the board game Go, a decade or more before many experts expected a computer to manage it. and AlphaZeroAlphaZero, prop. n.: A 2017 DeepMind program that taught itself chess, shogi and Go from nothing but the rules by playing against itself, and within hours of training beat the strongest existing programs. use a neural value functionvalue function, n.: An estimate of how promising a situation is for an AI agent, judged by the rewards it is likely to collect from that point on, the way a chess player sizes up a board., and the chess engine Stockfish adopted an efficiently updatable neural network (NNUE) evaluation in 2020.

Origin

Claude Shannon's 1950 paper proposed scoring chess positions by weighted features such as material and mobility, and Alan Turing hand-simulated a similar scheme around the same time. Arthur Samuel's checkers program (reported 1959) adjusted its evaluation weights from experience, one of the first instances of machine learning.

Usage note

Specific to game search; in machine learning, 'evaluation' usually means measuring model performance. The nearest learned analogue is the value functionvalue function, n.: An estimate of how promising a situation is for an AI agent, judged by the rewards it is likely to collect from that point on, the way a chess player sizes up a board. of reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time..

Related

See also
  • minimaxminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best.
  • alpha–beta pruningalpha–beta pruning, n.: A shortcut for game programs: tracking the best result each side is already sure of, it ignores lines of play that could only do worse, and when promising moves come first it searches about twice as deep.
  • game treegame tree, n.: A branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws.
  • value functionvalue function, n.: An estimate of how promising a situation is for an AI agent, judged by the rewards it is likely to collect from that point on, the way a chess player sizes up a board.
  • heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer.
  • Arthur SamuelArthur Samuel, prop. n.: An American IBM engineer whose checkers program improved by playing against itself, and whose 1959 paper helped make 'machine learning' the name of a field.

Sources

  1. Shannon, C. E. (1950). Programming a Computer for Playing Chess. Philosophical Magazine 41(314), 256–275.
  2. Samuel, A. L. (1959). Some Studies in Machine Learning Using the Game of Checkers. IBM Journal of Research and Development 3(3), 210–229.

Mentioned in

game treegame tree, n.: A branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws., minimaxminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best., alpha–beta pruningalpha–beta pruning, n.: A shortcut for game programs: tracking the best result each side is already sure of, it ignores lines of play that could only do worse, and when promising moves come first it searches about twice as deep., general game playinggeneral game playing, n.: Building AI players that are handed the rules of a game they have never seen and must work out how to play it well on their own, with no game-specific help from their programmers.