Chess computer in 1990s

This is a list of terms used in computer chess.

A–M[edit]

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.
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.
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.

N–Z[edit]

opening book
A database of moves to be played in the chess opening from the beginning of the game. These moves can be selected directly from computer storage and so they do not require search.
ply
A move by either white or black, hence a half move. A full move is two ply. See ply.
principal variation
The best or correct line of play; the variation most advantageous to the current player assuming each player chooses the best moves.
pruning
Elimination of branches in the game tree without searching them.
A designation for moves which are legal based on every criterion except for exposure to check. Hardware move generators, such as that of Belle, produce pseudo-legal moves. These must be tested to ensure they do not place the moving side in check.[1]
An extension to the search algorithm that will continue to search a branch past what would normally have been the deepest part of the search (the terminal node) until a quiescent position is reached where no captures are possible and neither king is in check. This technique can be used to minimize the danger of the horizon effect.
refutation
A move that demonstrates that the previous move under consideration would be bad.
search depth
The number of plies to which the game tree is searched.
A search in which only some possibilities are examined at each level of the game tree; contrast with full-width search.
Shannon number
An estimated lower bound on the game-tree complexity of chess. In 1950 Claude Shannon estimated that there are approximately 10120 variations from the starting position in chess.
terminal node
terminal position
The deepest part of the search on a particular branch of the game tree. The evaluation function is applied to terminal nodes to assign a value to that branch.
transposition table
A record of positions and their evaluations as found in an earlier part of the search. A transposition table saves computation by allowing the value of a position to be looked up when it is reached again by a different order of moves rather than requiring that it be calculated again. See transposition table.
type-A strategy
Brute force, full-width search considering all possible legal moves at each level of the search tree. Coined by Claude Shannon in 1949. Contrast with type-B strategy.
type-B strategy
Selective search, considering certain lines more deeply than others. Coined by Claude Shannon in 1949. Contrast with type-A strategy.
variation
A particular sequence of moves, often used to describe future possibilities in a game rather than the moves that were played to reach the current position. See variation.
window
The difference between alpha and beta in the alpha-beta search algorithm. As the search progresses the window becomes smaller. In an aspiration search, the window is set to a narrow value. The most extreme case, zero-window search, is also called null-window search or scout search.

References

  1. ^ Frey 1983 p. 203.
Categories