Glossary of computer chess terms

This is a list of terms used in computer chess.

• For terms used in chess in general, see Glossary of chess.
• For terms used in chess problems, see Glossary of chess problems.

Chess computer in 1990s

A–M

algorithm

A precisely defined step-by-step procedure for performing a task. See algorithm.

alpha

In the minimax search algorithm, the minimum value that the side to move can achieve according to the variations that have been evaluated so far.

alpha–beta pruning

An algorithm that reduces the number of nodes searched by the minimax algorithm. This refinement is essential to make it practical to search large game trees such as those in chess. See alpha–beta pruning.

array

A list stored in computer memory whose items can be retrieved quickly by a numerical index.

artificial intelligence

AI

The branch of computer science dealing with the reproduction or mimicking of human-level thought in computers. Game playing was an early area of research in AI. See artificial intelligence.

aspiration window

A refinement to alpha-beta pruning which further speeds the search by considering only a narrow window, generally based on experience. Zero-window search, null-window search, and negascout search are names for the extreme case in which alpha and beta are set to the same value. See aspiration window.

beta

In the minimax search algorithm, the maximum value the side to move can achieve based on the variations that have been evaluated so far.

bit

A binary digit, 0 or 1. The smallest piece of information that can be stored or manipulated by the computer

bit board

An array of 64 bits, each bit representing a square of the chess board. Multiple bit boards are used with each board recording a particular characteristic, such as all of the squares occupied by a particular type of piece or all squares under attack.

branching factor

The number of possibilities that must be considered at each level of the search tree.

brute force

A problem solving approach that relies on fast computer hardware rather than elegant algorithms.

candidate move

A move selected upon initial observation of the position as being worthy of further analysis. The alpha-beta algorithm can be more efficient if the candidate move list is properly ordered so that the best moves are considered first. See candidate move.

capture search

An extension to the search algorithm that continues from a terminal node considering only captures that can be made by each side.

cutoff

Elimination of a branch of the search tree without having to search it. This is the pruning action of the alpha-beta algorithm.

evaluation function

The algorithm used to evaluate the favorability of a position. Since most chess positions cannot be assigned a precise value (won, lost, or drawn), this is a heuristic based on factors such as material balance, space advantage, piece mobility, pawn structure, king safety, etc. Most evaluation functions return a numerical value in pawns and fractions of a pawn representing the advantage that white is judged to have in the given position. Zero indicates the position is balanced, and negative values indicate that black is judged to be ahead. See evaluation function.

full width search

A search in which all branches of the game tree are explored. Due to the high branching factor of chess, full width search is generally not practical except when few pieces remain on the board so the possible positions are greatly reduced.

game tree

All possible positions that could arise from all legal moves from the given position.

heuristic

A method used to solve a problem that is not guaranteed to be optimal or correct, employed when a method for the exact solution of the problem is unknown or impractical. Heuristics can be used in computer chess to evaluate positions and to guide the search algorithm.

horizon effect

The consequence that it is impractical in most positions for the search algorithm to search all the way to the conclusion of the game. The computer may make a poor move because it is unable to see the consequences even one ply beyond its maximum search depth. The horizon effect was a major problem in the early years of computer chess, but it is less of an issue today as modern chess engines can search many moves deep even in complex positions. See horizon effect.

iterative deepening

A search algorithm that first searches to a depth of N plies, then using results of that search reorders the candidate moves to conduct a search to N + 1 plies. See iterative deepening depth-first search.

killer heuristic

Assumption that a move (the killer move) that caused a search cutoff in another branch of the game tree at the same depth may cause a cutoff in the present position. This can make alpha-beta pruning more effective. See killer heuristic.

minimax algorithm

The basic algorithm used to search game trees. At each level in the game tree, the player to move selects the possibility that maximizes the minimum advantage that will result from any of the opponent's possible replies. See minimax algorithm.

move generator

The module that creates the list of moves to be considered from a particular position. This is usually part of the chess engine software, but some chess computers have performed move generation in hardware.