Horizon effect
Encyclopedia
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
. Thus, for a computer searching only five ply, there is a possibility that it will make a move which is detrimental, but the detrimental effect is not visible because it does not search to the depth of the error (i.e. beyond its horizon).
When evaluating a large game tree
using techniques such as minimax
or alpha-beta pruning
, search depth is limited for feasibility reasons. However, evaluating a partial tree may give a misleading result. When a significant change exists just over the 'horizon' of the search depth, the computational device falls victim to the horizon effect.
For example, in chess
, assume a situation where black only searches the game tree to six plies
, and from the current position, it determines that the queen is lost in the sixth ply. Also, suppose there is a move in the search depth where the computer may sacrifice a rook, and the loss of the queen is pushed to the eighth ply. This is, of course, a worse move than sacrificing the queen, because it leads to losing a queen as well as a rook. Because the loss of the queen was pushed over the horizon of search, it is not discovered and evaluated by the search. Sacrificing of the rook seems to be better than losing the queen, so the sacrificing move is returned as the best option.
The horizon effect can be mitigated by extending the search algorithm with a quiescence search
. This gives the search algorithm ability to look beyond its horizon for a certain class of moves of major importance to the game state, such as captures.
Rewriting the evaluation function for leaf nodes and/or analyzing sufficiently more nodes will solve many horizon effect problems.
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...
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
Ply (game theory)
In two-player sequential games, a ply refers to one turn taken by one of the players. The word is used to clarify what is meant when one might otherwise say "turn"....
down the 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...
. Thus, for a computer searching only five ply, there is a possibility that it will make a move which is detrimental, but the detrimental effect is not visible because it does not search to the depth of the error (i.e. beyond its horizon).
When evaluating a large 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...
using techniques such as 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 pruning
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 depth is limited for feasibility reasons. However, evaluating a partial tree may give a misleading result. When a significant change exists just over the 'horizon' of the search depth, the computational device falls victim to the horizon effect.
For example, in 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...
, assume a situation where black only searches the game tree to six plies
Ply (game theory)
In two-player sequential games, a ply refers to one turn taken by one of the players. The word is used to clarify what is meant when one might otherwise say "turn"....
, and from the current position, it determines that the queen is lost in the sixth ply. Also, suppose there is a move in the search depth where the computer may sacrifice a rook, and the loss of the queen is pushed to the eighth ply. This is, of course, a worse move than sacrificing the queen, because it leads to losing a queen as well as a rook. Because the loss of the queen was pushed over the horizon of search, it is not discovered and evaluated by the search. Sacrificing of the rook seems to be better than losing the queen, so the sacrificing move is returned as the best option.
The horizon effect can be mitigated by extending the search algorithm with a quiescence search
Quiescence search
Quiescence search is an algorithm typically used to evaluate minimax game trees in game-playing computer programs. It is a remedy for the horizon problem faced by AI engines for various games like chess and Go.-The horizon effect:...
. This gives the search algorithm ability to look beyond its horizon for a certain class of moves of major importance to the game state, such as captures.
Rewriting the evaluation function for leaf nodes and/or analyzing sufficiently more nodes will solve many horizon effect problems.