Editing Horizon effect (section)

{{Short description|Weakness of game-playing artificial intelligence}}
{{more footnotes|date=July 2012}}
The '''horizon effect''', also known as the '''horizon problem''', is a problem in [[artificial intelligence]] whereby, in many games, the number of possible states or positions is immense and computers can only feasibly search a small portion of them, typically a few [[Ply (game theory)|plies]] down the [[game tree]]. Thus, for a computer searching only a fixed number of plies, there is a possibility that it will make a  poor long-term move.  The drawbacks of the move are not "visible" because the computer does not search to the depth at which its [[evaluation function]] reveals the true evaluation of the line.  The analogy is to peering at a distance on a sphere like the earth, but a threat being beneath the horizon and hence unseen.

When evaluating a large [[game tree]] using techniques such as [[minimax]] with [[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.

In 1973 [[Hans Berliner]] named this phenomenon, which he and other researchers had observed, the "Horizon Effect."<ref>{{cite journal|last1=Berliner|first1=Hans J.|title=Some Necessary Conditions for a Master Chess Program |journal=Proceedings of the 3rd International Joint Conference on Artificial Intelligence. Stanford, CA, USA, August 20–23, 1973 |date=1973|pages=77–85 |url=http://dblp.org/rec/conf/ijcai/Berliner73}}</ref> He split the effect into two: the Negative Horizon Effect "results in creating diversions which ineffectively delay an unavoidable consequence or make an unachievable one appear achievable." For the "largely overlooked" Positive Horizon Effect, "the program grabs much too soon at a consequence that can be imposed on an opponent at leisure, frequently in a more effective form."

The horizon effect can be somewhat mitigated by [[quiescence search]].  This technique extends the effort and time spent searching board states left in volatile positions and allocates less effort to easier-to-assess board states. For example, "scoring" the worth of a chess position often involves a [[Chess piece relative value|material value count]], but this count is misleading if there are [[Hanging Piece|hanging piece]]s or an imminent checkmate.  A board state after the white queen has captured a protected black knight would appear to the naive material count to be advantageous to white as they are now up a knight, but is probably disastrous as the queen will be taken in the exchange one ply later.  A quiescence search may tell a search algorithm to play out the [[capture (chess)|capture]]s and [[check (chess)|check]]s before scoring [[leaf node]]s with volatile positions.