Horizon effect - Revision history

Karl Jones at 17:05, 29 August 2016

2016-08-29T17:05:33Z

Karl Jones at 17:04, 29 August 2016

2016-08-29T17:04:33Z

Karl Jones: Created page with "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..."

2016-08-29T17:02:26Z

Created page with "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..."

New page

The '''horizon effect''', also known as the '''horizon problem''', is a problem in [[artificial intelligence]] where, in many [[Game|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").

== Description ==

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.

== See also ==

* [[Fog of war]]

== External links ==

* [https://en.wikipedia.org/wiki/Horizon_effect Horizon effect] @ Wikipedia

[[Category:Artificial intelligence]]

@@ Line 5: / Line 5: @@
 == Description ==
-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.
+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.
@@ Line 13: / Line 13: @@
 == See also ==
 * [[Fog of war]]
 * [[Game tree]]
 * [[Ply (game theory)]]

@@ Line 1: / Line 1: @@
-The '''horizon effect''', also known as the '''horizon problem''', is a problem in [[artificial intelligence]] where, in many [[Game|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.
+The '''horizon effect''', also known as the '''horizon problem''', is a problem in [[artificial intelligence]] where, in many [[Game|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 (game theory)|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").
@@ Line 14: / Line 14: @@
 * [[Fog of war]]
 == External links ==