Horizon effect

The horizon effect, also known as the horizon problem, 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 plies down the game tree. Thus, for a computer searching only five plies, there is a possibility that it will make a detrimental move, but the effect is not visible because the computer 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.

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

Rewriting the evaluation function for leaf nodes and/or analyzing more nodes will solve many horizon effect problems.

Example

For example, in chess, assume a situation where the computer only searches the game tree to six plies, and from the current position, it determines that the queen is lost in the sixth ply, and suppose there is a move in the search depth where it 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 both a queen and a rook. However, because the loss of the queen was pushed over the horizon of search, it is not discovered and evaluated by the search. Losing the rook seems to be better than losing the queen, so the sacrifice is returned as the best option, while delaying the sacrifice of the queen has in fact additionally weakened the computer's position.

See also

References

This article is issued from Wikipedia - version of the 10/15/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.