Quiescence search
Encyclopedia
Quiescence search is an algorithm typically used to evaluate minimax
game tree
s in game-playing computer programs. It is a remedy for the horizon problem
faced by AI
engine
s for various games like chess
and Go
.
where, in many games, the number of possible states or positions is immense and computers can only search a small portion of it, typically a few ply down the game tree. Thus, for a computer searching only five ply, there is a possibility that it could make a move that would prove to be detrimental later on (say, after six moves), but it cannot see the consequences because it cannot search far into the tree. Consider this chess position with black to move:
Here White is down a pawn in material, and a good move for black would be 39... Qxg3+ 40. Kxg3 f5. However, Fritz
chooses the suboptimal move 39... Bc2??. This move lets White force many of Black's moves, but Fritz doesn't care because it appears to be able to win more material along the way. White responds with 40. Qxh4 and Black resigns after 40. ... gxh4 41. Rc1 Rxb3? 42. Nxb3 Bxb3 43. a5 Nc4 44. b5 Ba4 45. bxa6 Bc6 46. a7 Kg7 47. a6 Ba8 48. Rb1.
This problem occurs because computers only search a certain number of moves ahead. Human players usually have enough intuition to decide whether to abandon a bad-looking move, or search a promising move to a great depth. A quiescence search attempts to emulate this behavior by instructing a computer to search "interesting" positions to a greater depth than "quiet" ones (hence its name) to make sure there are no hidden traps and, usually equivalently, to get a better estimate of its value.
Any sensible criterion may be used to distinguish "quiet" moves from "noisy" moves; high activity (high movement on a chess board, extensive capturing in Go, for example) is commonly used for board games. As the main motive of quiescence search is usually to get a good value out of a poor evaluation function
, it may also make sense to detect wide fluctuations in values returned by a simple heuristic evaluator over several ply. Modern chess engines may search certain moves up to 2 or 3 times deeper than the minimum. In highly "unstable" games like Go and reversi
, a rather large proportion of computer time may be spent on quiescence searching.
This pseudocode
illustrates the concept in an algorithmic manner:
function quiescence_search(node, depth)
if node appears quiet or node is a terminal node or depth = 0
return estimated value
of node
else
//One might use minimax
or alpha-beta
search here...
search children of node using recursive
applications of quiescence_search
return estimated value of children
//...and here
function normal_search(node, depth)
if node is a terminal node
return estimated value of node
else if depth = 0
if node appears quiet
return estimated value of node
else
return estimated value from quiescence_search(node, reasonable_depth_value)
else
search children of node using recursive applications of normal_search
return estimated value of children
Minimax
Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
game tree
Game tree
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...
s in game-playing computer programs. It is a remedy for the horizon problem
Horizon effect
The horizon effect is a problem in artificial intelligence where, in many games, the number of possible states or positions is immense and computers can only feasibly search a small portion of it, typically a few ply down the game tree...
faced by AI
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
engine
Game engine
A game engine is a system designed for the creation and development of video games. There are many game engines that are designed to work on video game consoles and personal computers...
s for various games like chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
and Go
Go (board game)
Go , is an ancient board game for two players that originated in China more than 2,000 years ago...
.
The horizon effect
The horizon effect is a problem in artificial intelligenceArtificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
where, in many games, the number of possible states or positions is immense and computers can only search a small portion of it, typically a few ply down the game tree. Thus, for a computer searching only five ply, there is a possibility that it could make a move that would prove to be detrimental later on (say, after six moves), but it cannot see the consequences because it cannot search far into the tree. Consider this chess position with black to move:
Here White is down a pawn in material, and a good move for black would be 39... Qxg3+ 40. Kxg3 f5. However, Fritz
Fritz (chess)
Fritz is a German chess program developed by Frans Morsch and Mathias Feist and published by ChessBase. There is also a version called Deep Fritz that is designed for multiprocessing....
chooses the suboptimal move 39... Bc2??. This move lets White force many of Black's moves, but Fritz doesn't care because it appears to be able to win more material along the way. White responds with 40. Qxh4 and Black resigns after 40. ... gxh4 41. Rc1 Rxb3? 42. Nxb3 Bxb3 43. a5 Nc4 44. b5 Ba4 45. bxa6 Bc6 46. a7 Kg7 47. a6 Ba8 48. Rb1.
This problem occurs because computers only search a certain number of moves ahead. Human players usually have enough intuition to decide whether to abandon a bad-looking move, or search a promising move to a great depth. A quiescence search attempts to emulate this behavior by instructing a computer to search "interesting" positions to a greater depth than "quiet" ones (hence its name) to make sure there are no hidden traps and, usually equivalently, to get a better estimate of its value.
Any sensible criterion may be used to distinguish "quiet" moves from "noisy" moves; high activity (high movement on a chess board, extensive capturing in Go, for example) is commonly used for board games. As the main motive of quiescence search is usually to get a good value out of a poor evaluation function
Evaluation function
An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing programs to estimate the value or goodness of a position in the minimax and related algorithms...
, it may also make sense to detect wide fluctuations in values returned by a simple heuristic evaluator over several ply. Modern chess engines may search certain moves up to 2 or 3 times deeper than the minimum. In highly "unstable" games like Go and reversi
Reversi
Reversi is a board game involving abstract strategy and played by two players on a board with 8 rows and 8 columns and a set of distinct pieces for each side. Pieces typically are disks with a light and a dark face, each face belonging to one player...
, a rather large proportion of computer time may be spent on quiescence searching.
This pseudocode
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
illustrates the concept in an algorithmic manner:
function quiescence_search(node, depth)
if node appears quiet or node is a terminal node or depth = 0
return estimated value
Evaluation function
An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing programs to estimate the value or goodness of a position in the minimax and related algorithms...
of node
else
//One might use minimax
Minimax
Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
or alpha-beta
Alpha-beta pruning
Alpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games...
search here...
search children of node using recursive
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
applications of quiescence_search
return estimated value of children
//...and here
function normal_search(node, depth)
if node is a terminal node
return estimated value of node
else if depth = 0
if node appears quiet
return estimated value of node
else
return estimated value from quiescence_search(node, reasonable_depth_value)
else
search children of node using recursive applications of normal_search
return estimated value of children