Difference between revisions of "Horizon Effect"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
Line 94: | Line 94: | ||
'''[[Search|Up one level]]''' | '''[[Search|Up one level]]''' | ||
+ | [[Category:Quotes]] | ||
+ | [[Category:Hyatt Quotes]] | ||
[[Category:Mezzoforte]] | [[Category:Mezzoforte]] |
Revision as of 13:08, 7 December 2019
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.
Contents
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
- Richard Greenblatt, Donald Eastlake, Stephen D. Crocker (1967). The Greenblatt Chess Program. Proceedings of the AfiPs Fall Joint Computer Conference, Vol. 31, pp. 801-810. Reprinted (1988) in Computer Chess Compendium, pdf from The Computer History Museum or as pdf or ps from DSpace at MIT
- Hans Berliner (1973). Some Necessary Conditions for a Master Chess Program. 3. IJCAI 1973
- Larry Harris (1975) The Heuristic Search And The Game Of Chess - A Study Of Quiescence, Sacrifices, And Plan Oriented Play. 4. IJCAI 1975, reprinted in Computer Chess Compendium by David Levy (Editor) B.T. Batsford, London 1988, ISBN 0-7134-4914-4, Pages 136 - 142.
- Hermann Kaindl (1982). Dynamic Control of the Quiescence Search in Computer Chess. Cybernetics and Systems Research (ed. R. Trappl), pp. 973-977. North-Holland, Amsterdam.
- 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.
- 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
- David Levy (2015). The "Horizon Effect" in Politics. ICGA Journal, Vol. 38, No. 2
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 ....
- Horizon Effects in modern chess programs? by Steve McCracken, rgcc, September 05, 1995
- Re: Horizon Effects in modern chess programs? by Brian Sheppard, rgcc, September 10, 1995
- What to do with Horizon effect? by Werner Inmann, CCC, October 31, 1998
2000 ...
- real job of the qSearch? find quiet vs stop horizon effect by Scott Farrell, CCC, August 28, 2003
- What is horizon effect? by Masros Tukiran, CCC, January 29, 2006
- Good Example of Horizon effect in Eval by Ross Boyd, CCC, February 02, 2008
- Horizon Effect by Charles Roberson, CCC, March 09, 2008 [14]
2010 ...
- Horizon detection by Harm Geert Muller, CCC, March 25, 2015
- Ostrich tactics and pointless checks by Colin Jenkins, CCC, May 29, 2015 » Check
- 'Analogy grafting' and the horizon effect by Harm Geert Muller, CCC, June 22, 2015
- Horizon effect by Harm Geert Muller, CCC, April 27, 2017
- Horizon effect by Harm Geert Muller, CCC, September 05, 2017
- Horizon effect and extensions by Vivien Clauzon, CCC, June 25, 2018 » Extensions
External Links
- Horizon effect from Wikipedia
- Horizon from Wikipedia
- Which nodes to search? Full-width vs. selective search, Lecture notes for February 4, 1999 by David Eppstein
- Mezzoforte - Beyond The Horizon, Live In Reykjavik, March 27, 2007, YouTube Video
References
- ↑ Sunset (created with Terragen on the PC, by Dellex, July 22, 2008)
- ↑ 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
- ↑ Hans Berliner (1973). Some Necessary Conditions for a Master Chess Program. 3. IJCAI 1973
- ↑ 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.
- ↑ Larry Harris (1973). The bandwidth heuristic search. 3. IJCAI 1973, pdf
- ↑ Re: What to do with Horizon effect? by Amir Ban, CCC, November 01, 1998
- ↑ Re: What is horizon effect? by Robert Hyatt, CCC, January 30, 2006
- ↑ July 1, 2010 letter from Dr. Gerald Tripard, hosted by Lawrence J. Krakauer
- ↑ Computer chess via ham radio by Lawrence J. Krakauer
- ↑ July 1, 2010 letter from Dr. Gerald Tripard, hosted by Lawrence J. Krakauer
- ↑ Ben Mittman (1971). Computer Chess Programs (Panel). pdf from The Computer History Museum
- ↑ Ostrich effect from Wikipedia
- ↑ James R. Slagle, Philip Bursky (1968). Experiments With a Multipurpose, Theorem-Proving Heuristic Program. Journal of the ACM, Vol. 15, No. 1
- ↑ Next (2007 film) from Wikipedia