Horizon Effect

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Horizon Effect

The Horizon Effect is caused by the depth limitation of the search algorithm, and became manifest when some negative event is inevitable but postponable. Because only a partial game tree has been analyzed, it will appear to the system that the event can be avoided when in fact this is not the case. Beside obligatory quiescence search, extensions, specially check extensions are designed to reduce horizon effects.

Quotes

By Tony Marsland

Quote by Tony Marsland from Computer Chess and Search. [2] :

2. 6. Horizon Effect
An unresolved defect of chess programs is the insertion of delaying moves that cause any inevitable loss of material to occur beyond the program’s horizon (maximum search depth), so that the loss is hidden (Berliner, 1973 [3]). The ‘horizon effect’ is said to occur when the delaying moves unnecessarily weaken the position or give up additional material to postpone the eventual loss. The effect is less apparent in programs with more knowledgeable quiescence searches (Hermann Kaindl, 1982 [4]), but all programs exhibit this phenomenon. There are many illustrations of the difficulty; the example in Figure 4, which is based on a study by Kaindl, is clear. Here a program with a simple quiescence search involving only captures would assume that any blocking move saves the queen. Even an 8-ply search (..., Pb2; Bxb2, Pc3; Bxc3, Pd4; Bxd4, Pe5; Bxe5) might not show the inevitable, ‘believing’ that the queen has been saved at the expense of four pawns! 
Thus programs with a poor or inadequate quiescence search suffer more from the horizon effect.
The best way to provide automatic extension of non-quiescent positions is still an open question, despite proposals such as bandwidth heuristic search (Larry Harris, 1973 [5] ). 
    
    
    
    
    
    
    
    
      
     
       
     
      
      
       
      
     ♜ ♚
    ♕♟♛ 
    ♟   
 ♟ ♟  ♙ 
  ♟  ♙  
 ♟  ♙   
   ♙    
♗♔      
5r1k/4Qpq1/4p3/1p1p2P1/2p2P2/1p2P3/3P4/BK6 b - -

By Amir Ban

Amir Ban in a reply to Robert Hyatt on Horizon Effect 1998 [6] :

>not much you can do... horizon effect happens anytime you stop the search
>in a non-quiet position... everybody sees it... just get faster.. :)
I don't agree with this statement. The exposure to horizon effects is what usually limits a program's strength, more than the depth it can reach. The fact that it cannot be totally overcome is irrelevant to the fact that limiting its damage is a first priority. Just getting generally deeper is a poor way to do that, and not very effective either. 

By Robert Hyatt

Robert Hyatt states on Horizon Effect in 2006 [7] :

The "horizon effect" is something caused by a fixed search horizon that the search can't penetrate. If the search can therefore force something out beyond the horizon, in effect "delaying the problem for a while" that delaying can appear to be a "permanent solution" to the problem, since if the problem is pushed beyond the horizon, so far as the search is concerned, the problem no longer exists.
Search extensions are one way to mitigate this, but it is impossible to eliminate. 

By Gerald Tripard

Gerald Tripard in a 2010 letter [8] on his time at ETH Zurich, his chess program Charly, and the match versus Mac Hack VI in 1968 [9]:

One of the more interesting problems of artificial intelligence that I learned about in working on the chess program was called, "The Horizon Effect". If a problem could be pushed "beyond the preprogrammed" tree search limit, the program would make the "bad" choice of sacrificing material to avoid losing, say, a queen "within" the horizon in the situation where the queen was going to be lost eventually anyway. I see this as not just a problem of "artificial" intelligence but human thinking in general, especially of politicians. You can find wonderful examples of this in today's headlines. For example politicians "buy" the favor of a certain class of workers by offering them fabulous retirement benefits. That effectively pushes an "accounting negative balance" beyond the horizon of the politician's career. The politician gets the immediate benefit of support from the affected workers but society will eventually have to pay the bill after the politician is gone. 

Crossovers

Lawrence J. Krakauer in an additional note on Gerald Tripard's letter [10]:

Richard Greenblatt also noted the "Horizon Effect", of course, although I don't know if he called it by that name. One way that Mac Hack VI attempted to combat it was via a mechanism that I believe was called "crossovers". If at the conclusion of the program's lookahead (typically six plies deep) there were still pieces under attack, the program extended the lookahead, for those positions only, to an even greater depth. This introduced some other problems, such as comparing board evaluations of different depths. However, this seemed better than working with a board evaluation based on a position that was still in a state of flux. 

Ostrich Effect

by Gary J. Boos on Mr. Turk from Ben Mittman's 1971 Panel [11] [12]:

Mundstock noticed an article by Slagle and Bursky in the Journal of the ACM  [13], that pointed toward an algorithm that seemed better than alpha-beta pruning. Based upon this article, and guided by Mundstock, I wrote a lookahead routine whose main theme is that the best line is analyzed until it is shown that it is no longer the best line.
This process eliminates many common problems that accompany a fixed depth search, one of which is the Ostrich Effect which existed in even Northwestern University's  Chess 3.0. Tests showed that in a small set of positions, Mr. Turk could find the main variation on the first try. We believe that the basic theme of our lookahead routine is better than alpha-beta pruning. ... 

See also

Publications

Horizon Effect Elsewhere

  • Guangjie Li (2009). The Horizon Effect of Stock Return Predictability and Model Uncertainty on Portfolio Choice: UK Evidence, as pdf

Forum Posts

1995 ....

2000 ...

2010 ...

2020 ...

External Links

References

  1. Sunset (created with Terragen on the PC, by Dellex, July 22, 2008)
  2. Tony Marsland (1992). Computer Chess and Search. Encyclopedia of Artificial Intelligence (2nd ed.) (ed. S.C. Shapiro) pp. 224-241. John Wiley & Sons, Inc., New York, NY. ISBN 0-471-50305-3. pdf
  3. Hans Berliner (1973). Some Necessary Conditions for a Master Chess Program. 3. IJCAI 1973
  4. Hermann Kaindl (1982). Quiescence Search in Computer Chess. SIGART Newsletter, 80, pp. 124-131. Reprinted (1983) in Computer-Game-Playing: Theory and Practice, pp. 39-52. Ellis Horwood Ltd., Chichester.
  5. Larry Harris (1973). The bandwidth heuristic search. 3. IJCAI 1973, pdf
  6. Re: What to do with Horizon effect? by Amir Ban, CCC, November 01, 1998
  7. Re: What is horizon effect? by Robert Hyatt, CCC, January 30, 2006
  8. July 1, 2010 letter from Dr. Gerald Tripard, hosted by Lawrence J. Krakauer
  9. Computer chess via ham radio by Lawrence J. Krakauer
  10. July 1, 2010 letter from Dr. Gerald Tripard, hosted by Lawrence J. Krakauer
  11. Ben Mittman (1971). Computer Chess Programs (Panel). pdf from The Computer History Museum
  12. Ostrich effect from Wikipedia
  13. James R. Slagle, Philip Bursky (1968). Experiments With a Multipurpose, Theorem-Proving Heuristic Program. Journal of the ACM, Vol. 15, No. 1
  14. Next (2007 film) from Wikipedia

Up one level