Horizon effect

From Wikipedia, the free encyclopedia

The horizon effect (or horizon problem) is a problem in AI.

When searching a large game tree (for instance using minimax or alpha-beta pruning) it is often not feasible to search the entire tree, so the tree is only searched down to a certain depth. This results in the horizon effect where a significant change exists just over the "horizon" (slightly beyond the depth the tree has been searched). Evaluating the partial tree thus gives a misleading result.

An example of the horizon effect occurs when some negative event is inevitable but postponable, but because only a partial game tree has been analysed, it will appear to the system that the event can be avoided when in fact this is not the case. For example, in chess, if the white player is one move away from queening a pawn, the black AI can play moves to stall white and push the queening "over the horizon", and mistakenly believe that it avoided it entirely.

The horizon effect can be avoided by using "singular extension" in addition to the search algorithm. This gives the search algorithm the ability to look beyond its horizon, but only at moves of major importance (such as the queening in the previous example). This does not make the search much more expensive, as only a few specific moves are considered.

[edit] References

• Russell, Stuart J.; Norvig, Peter (2002). Artificial Intelligence: A Modern Approach. Upper Saddle River, NJ: Prentice Hall, 174.