Software:Evaluation function

From HandWiki
Short description: Function in a computer game-playing program that evaluates a game position

An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing computer programs to estimate the value or goodness of a position (usually at a leaf or terminal node) in a game tree.[1] Most of the time, the value is either a real number or a quantized integer, often in nths of the value of a playing piece such as a stone in go or a pawn in chess, where n may be tenths, hundredths or other convenient fraction, but sometimes, the value is an array of three values in the unit interval, representing the win, draw, and loss percentages of the position.

There do not exist analytical or theoretical models for evaluation functions for unsolved games, nor are such functions entirely ad-hoc. The composition of evaluation functions is determined empirically by inserting a candidate function into an automaton and evaluating its subsequent performance. A significant body of evidence now exists for several games like chess, shogi and go as to the general composition of evaluation functions for them.

Games in which game playing computer programs employ evaluation functions include chess,[2] go,[2] shogi (Japanese chess),[2] othello, hex, backgammon,[3] and checkers.[4][5] In addition, with the advent of programs such as MuZero, computer programs also use evaluation functions to play video games, such as those from the Atari 2600.[6] Some games like tic-tac-toe are strongly solved, and do not require search or evaluation because a discrete solution tree is available.

Relation to search

A tree of such evaluations is usually part of a search algorithm, such as Monte Carlo tree search or a minimax algorithm like alpha–beta search. The value is presumed to represent the relative probability of winning if the game tree were expanded from that node to the end of the game. The function looks only at the current position (i.e. what spaces the pieces are on and their relationship to each other) and does not take into account the history of the position or explore possible moves forward of the node (therefore static). This implies that for dynamic positions where tactical threats exist, the evaluation function will not be an accurate assessment of the position. These positions are termed non-quiescent; they require at least a limited kind of search extension called quiescence search to resolve threats before evaluation. Some values returned by evaluation functions are absolute rather than heuristic, if a win, loss or draw occurs at the node.

There is an intricate relationship between search and knowledge in the evaluation function. Deeper search favors less near-term tactical factors and more subtle long-horizon positional motifs in the evaluation. There is also a trade-off between efficacy of encoded knowledge and computational complexity: computing detailed knowledge may take so much time that performance decreases, so approximations to exact knowledge are often better. Because the evaluation function depends on the nominal depth of search as well as the extensions and reductions employed in the search, there is no generic or stand-alone formulation for an evaluation function. An evaluation function which works well in one application will usually need to be substantially re-tuned or re-trained to work effectively in another application.

In chess

In computer chess, the output of an evaluation function is typically an integer, and the units of the evaluation function are typically referred to as pawns. The term 'pawn' refers to the value when the player has one more pawn than the opponent in a position, as explained in Chess piece relative value. The integer 1 usually represents some fraction of a pawn, and commonly used in computer chess are centipawns, which are a hundredth of a pawn. Larger evaluations indicate a material imbalance or positional advantage or that a win of material is usually imminent. Very large evaluations may indicate that checkmate is imminent. An evaluation function also implicitly encodes the value of the right to move, which can vary from a small fraction of a pawn to win or loss.

Handcrafted evaluation functions

Historically in computer chess, the terms of an evaluation function are constructed (i.e. handcrafted) by the engine developer, as opposed to discovered through training neural networks. The general approach for constructing handcrafted evaluation functions is as a linear combination of various weighted terms determined to influence the value of a position. However, not all terms in a handcrafted evaluation function are linear, some, such as king safety and pawn structure, are nonlinear. Each term may be considered to be composed of first order factors (those that depend only on the space and any piece on it), second order factors (the space in relation to other spaces), and nth-order factors (dependencies on history of the position).

A handcrafted evaluation function typically has of a material balance term that usually dominates the evaluation. The conventional values used for material are Queen=9, Rook=5; Knight or Bishop=3; Pawn=1; the king is assigned an arbitrarily large value, usually larger than the total value of all the other pieces.[1] In addition, it typically has a set of positional terms usually totaling no more than the value of a pawn, though in some positions the positional terms can get much larger, such as when checkmate is imminent. Handcrafted evaluation functions typically contain dozens to hundreds of individual terms.

In practice, effective handcrafted evaluation functions are created not by ever expanding the list of evaluated parameters, but by careful tuning or training of the weights relative to each other, of a modest set of parameters such as those described above. Toward this end, positions from various databases are employed, such as from master games, engine games, Lichess games, or even from self-play, as in reinforcement learning.

Example

An example handcrafted evaluation function for chess might look like the following:

  • c1 * material + c2 * mobility + c3 * king safety + c4 * center control + c5 * pawn structure + c6 * king tropism + ...

Each of the terms is a weight multiplied by a difference factor: the value of white's material or positional terms minus black's.

  • The material term is obtained by assigning a value in pawn-units to each of the pieces.
  • Mobility is the number of legal moves available to a player, or alternately the sum of the number of spaces attacked or defended by each piece, including spaces occupied by friendly or opposing pieces. Effective mobility, or the number of "safe" spaces a piece may move to, may also be taken into account.
  • King safety is a set of bonuses and penalties assessed for the location of the king and the configuration of pawns and pieces adjacent to or in front of the king, and opposing pieces bearing on spaces around the king.
  • Center control is derived from how many pawns and pieces occupy or bear on the four center spaces and sometimes the 12 spaces of the extended center.
  • Pawn structure is a set of penalties and bonuses for various strengths and weaknesses in pawn structure, such as penalties for doubled and isolated pawns.
  • King tropism is a bonus for closeness (or penalty for distance) of certain pieces, especially queens and knights, to the opposing king.

Neural networks

While neural networks have been used in the evaluation functions of chess engines since the late 1980s,[7][8] they did not become popular in computer chess until the late 2010s, as the hardware needed to train neural networks was not strong enough at the time, and fast training algorithms and network topology and architectures have not been developed yet. Initially, neural network based evaluation functions generally consisted of one neural network for the entire evaluation function, with input features selected from the board and whose output is an integer, normalized to the centipawn scale so that a value of 100 is roughly equivalent to a material advantage of a pawn. The parameters in neural networks are typically trained using reinforcement learning or supervised learning. More recently, evaluation functions in computer chess have started to use multiple neural networks, with each neural network trained for a specific part of the evaluation, such as pawn structure or endgames. This allows for hybrid approaches where an evaluation function consists of both neural networks and handcrafted terms.

Deep neural networks have been used, albeit infrequently, in computer chess after Matthew Lai's Giraffe[9] in 2015 and Deepmind's AlphaZero in 2017 demonstrated the feasibility of deep neural networks in evaluation functions. The distributed computing project Leela Chess Zero was started shortly after to attempt to replicate the results of Deepmind's AlphaZero paper. Apart from the size of the networks, the neural networks used in AlphaZero and Leela Chess Zero also differ from those used in traditional chess engines as they have two outputs, one for evaluation (the value head) and one for move ordering (the policy head), rather than only one output for evaluation.[10] In addition, while it is possible to set the output of the value head of Leela's neural network to a real number to approximate the centipawn scale used in traditional chess engines, by default the output is the win-draw-loss percentages, a vector of three values each from the unit interval.[10] Since deep neural networks are very large, engines using deep neural networks in their evaluation function usually require a graphics processing unit in order to efficiently calculate the evaluation function.

Piece-square tables

An important technique in evaluation since at least the early 1990s is the use of piece-square tables (also called piece-value tables) for evaluation.[11][12] Each table is a set of 64 values corresponding to the squares of the chessboard. The most basic implementation of piece-square table consists of separate tables for each type of piece per player, which in chess results in 12 piece-square tables in total. More complex variants of piece-square tables are used in computer chess, one of the most prominent being the king-piece-square table, used in Stockfish, Komodo Dragon, Ethereal, and many other engines, where each table considers the position of every type of piece in relation to the player's king, rather than the position of the every type of piece alone. The values in the tables are bonuses/penalties for the location of each piece on each space, and encode a composite of many subtle factors difficult to quantify analytically. In handcrafted evaluation functions, there are sometimes two sets of tables: one for the opening/middlegame, and one for the endgame; positions of the middle game are interpolated between the two.[13]

A common handcrafted evaluation function used in computer chess is the Piece-Square Table Only, or PeSTO for short, which is a very simple evaluation function consisting of material terms and only two sets of piece square tables, one for the opening and one for the endgame, for the positional terms. Nevertheless, PeSTO is able to perform as well as many other handcrafted evaluation functions used in computer chess. PeSTO was first created by Tomasz Michniewski in 2003 under the name "Simplified Evaluation Function", and the current name was introduced by Ronald Friederich when he implemented PeSTO in his engine rofChade.[14]

Originally developed in computer shogi in 2018 by Yu Nasu,[15][16] the most common evaluation function used in computer chess today is the efficiently updatable neural network, or NNUE for short, a sparse and shallow neural network that has only piece-square tables as the inputs into the neural network.[17] In fact, the most basic NNUE architecture is simply the 12 piece-square tables described above, a neural network with only one layer and no activation functions. An efficiently updatable neural network architecture, using king-piece-square tables as its inputs, was first ported to chess in a Stockfish derivative called Stockfish NNUE, publicly released on May 30, 2020,[18] and was adopted by many other engines before eventually being incorporated into the official Stockfish engine on August 6, 2020.[19][20]

Endgame tablebases

Chess engines frequently use endgame tablebases in their evaluation function, as it allows the engine to play perfectly in the endgame.

In Go

Historically, evaluation functions in Computer Go took into account both territory controlled, influence of stones, number of prisoners and life and death of groups on the board. However, modern go playing computer programs largely use deep neural networks in their evaluation functions, such as AlphaGo, Leela Zero, Fine Art, and KataGo, and output a win/draw/loss percentage rather than a value in number of stones.

References

  1. ↑ 1.0 1.1 Shannon, Claude (1950), Programming a Computer for Playing Chess, Ser. 7, 41, Philosophical Magazine, https://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf, retrieved 12 December 2021 
  2. ↑ 2.0 2.1 2.2 Silver, David; Hubert, Thomas; Schrittwieser, Julian; Antonoglou, Ioannis; Lai, Matthew; Guez, Arthur; Lanctot, Marc; Sifre, Laurent et al. (7 December 2018). "A general reinforcement learning algorithm that masters chess, shogi, and go through self-play". Science 362 (6419): 1140–1144. doi:10.1126/science.aar6404. PMID 30523106. Bibcode: 2018Sci...362.1140S. 
  3. ↑ Tesauro, Gerald (March 1995). "Temporal Difference Learning and TD-Gammon". Communications of the ACM 38 (3): 58–68. doi:10.1145/203330.203343. http://www.bkgm.com/articles/tesauro/tdl.html. Retrieved Nov 1, 2013. 
  4. ↑ Schaeffer, J.; Burch, N.; Y. Björnsson; Kishimoto, A.; Müller, M.; Lake, R.; Lu, P.; Sutphen, S. (2007). "Checkers is Solved". Science 317 (5844): 1518–22. doi:10.1126/science.1144079. PMID 17641166. http://www.cs.nyu.edu/courses/spring13/CSCI-UA.0472-001/Checkers/checkers.solved.science.pdf. 
  5. ↑ Schaeffer, J.; Björnsson, Y.; Burch, N.; Kishimoto, A.; Müller, M.; Lake, R.; Lu, P.; Sutphen, S.. "Solving Checkers". Proceedings of the 2005 International Joint Conferences on Artificial Intelligence Organization. https://www.ijcai.org/Proceedings/05/Papers/0515.pdf. 
  6. ↑ Schrittwieser, Julian; Antonoglou, Ioannis; Hubert, Thomas; Simonyan, Karen; Sifre, Laurent; Schmitt, Simon; Guez, Arthur; Lockhart, Edward et al. (2020). "Mastering Atari, Go, chess and shogi by planning with a learned model". Nature 588 (7839): 604–609. doi:10.1038/s41586-020-03051-4. PMID 33361790. Bibcode: 2020Natur.588..604S. 
  7. ↑ Thurn, Sebastian (1995), Learning to Play the Game of Chess, MIT Press, https://proceedings.neurips.cc/paper/1994/file/d7322ed717dedf1eb4e6e52a37ea7bcd-Paper.pdf, retrieved 12 December 2021 
  8. ↑ Levinson, Robert (1989), A Self-Learning, Pattern-Oriented Chess Program, 12, ICCA Journal 
  9. ↑ Lai, Matthew (4 September 2015), Giraffe: Using Deep Reinforcement Learning to Play Chess 
  10. ↑ 10.0 10.1 "Neural network topology". https://lczero.org/dev/backend/nn/. 
  11. ↑ Beal, Don; Smith, Martin C., Learning Piece-Square Values using Temporal Differences, 22, ICCA Journal 
  12. ↑ Jun Nagashima; Masahumi Taketoshi; Yoichiro Kajihara; Tsuyoshi Hashimoto; Hiroyuki Iida (2002), An Efficient Use of Piece-Square Tables in Computer Shogi, Information Processing Society of Japan, https://ci.nii.ac.jp/naid/110006381103 
  13. ↑ Stockfish Evaluation Guide, https://hxim.github.io/Stockfish-Evaluation-Guide/, retrieved 12 December 2021 
  14. ↑ Ronald Friederich (January 4, 2020). "PeSTO: Piece Square Tables Only". https://rofchade.nl/?p=307. 
  15. ↑ Yu Nasu (April 28, 2018). "Efficiently Updatable Neural-Network-based Evaluation Function for computer Shogi" (in Japanese). https://www.apply.computer-shogi.org/wcsc28/appeal/the_end_of_genesis_T.N.K.evolution_turbo_type_D/nnue.pdf. 
  16. ↑ Yu Nasu (April 28, 2018). "Efficiently Updatable Neural-Network-based Evaluation Function for computer Shogi (Unofficial English Translation)" (in English). https://github.com/asdfjkl/nnue/blob/main/nnue_en.pdf. 
  17. ↑ Gary Linscott (April 30, 2021). "NNUE". https://github.com/glinscott/nnue-pytorch/blob/master/docs/nnue.md. 
  18. ↑ Noda, Hisayori (30 May 2020). "Release stockfish-nnue-2020-05-30". https://github.com/nodchip/Stockfish/releases/tag/stockfish-nnue-2020-05-30. 
  19. ↑ "Introducing NNUE Evaluation". 6 August 2020. https://blog.stockfishchess.org/post/625828091343896577/introducing-nnue-evaluation. 
  20. ↑ Joost VandeVondele (July 25, 2020). "official-stockfish / Stockfish, NNUE merge". https://github.com/official-stockfish/Stockfish/issues/2823#issue-665540175. 
  • Slate, D and Atkin, L., 1983, "Chess 4.5, the Northwestern University Chess Program" in Chess Skill in Man and Machine 2nd Ed., pp. 93–100. Springer-Verlag, New York, NY.
  • Ebeling, Carl, 1987, All the Right Moves: A VLSI Architecture for Chess (ACM Distinguished Dissertation), pp. 56–86. MIT Press, Cambridge, MA

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Software:Evaluation_function&oldid=3469042"