Difference between revisions of "Search"

From Chessprogramming wiki
Jump to: navigation, search
(3 intermediate revisions by the same user not shown)
Line 70: Line 70:
 
=Parallel Search=  
 
=Parallel Search=  
 
* [[Parallel Search]]
 
* [[Parallel Search]]
* [[Parallel Controlled Conspiracy Number Search]] as used by [[Ulf Lorenz|Ulf Lorenz's]] program [[P.ConNerS]]
+
* [[Conspiracy Number Search#PCCNS|Parallel Controlled Conspiracy Number Search]] as used by [[Ulf Lorenz|Ulf Lorenz's]] program [[P.ConNerS]]
  
 
=Using Time=  
 
=Using Time=  
Line 96: Line 96:
 
=Publications=  
 
=Publications=  
 
==1960 ...==  
 
==1960 ...==  
* [[Daniel Edwards]], [[Timothy Hart]] ('''1961'''). ''The Alpha-Beta Heuristic'', AIM-030, reprint available from [http://dspace.mit.edu/handle/1721.1/6098 DSpace] at [[Massachusetts Institute of Technology|MIT]]. Retrieved on 2006-12-21.
+
* [[Daniel Edwards]], [[Timothy Hart]] ('''1961'''). ''The Alpha-Beta Heuristic'', AIM-030, reprint available from [http://dspace.mit.edu/handle/1721.1/6098 DSpace] at [[Massachusetts Institute of Technology|MIT]]
 
* [[Alexander Brudno]] ('''1963'''). ''Bounds and valuations for shortening the search of estimates''. Problemy Kibernetiki (10) 141–150 and Problems of Cybernetics (10) 225–241
 
* [[Alexander Brudno]] ('''1963'''). ''Bounds and valuations for shortening the search of estimates''. Problemy Kibernetiki (10) 141–150 and Problems of Cybernetics (10) 225–241
 
* [[James R. Slagle]] ('''1963'''). ''Game Trees, M & N Minimaxing, and the M & N alpha-beta procedure.'' Artificial Intelligence Group Report 3, UCRL-4671, University of California
 
* [[James R. Slagle]] ('''1963'''). ''Game Trees, M & N Minimaxing, and the M & N alpha-beta procedure.'' Artificial Intelligence Group Report 3, UCRL-4671, University of California
 +
* [[Jim Doran]], [[Donald Michie]] ('''1966'''). ''[https://royalsocietypublishing.org/doi/10.1098/rspa.1966.0205 Experiments with the Graph Traverser Program]''. [https://en.wikipedia.org/wiki/Proceedings_of_the_Royal_Society Proceedings of the Royal Society], Series A, Vol. 294, No. 1437, [https://stacks.stanford.edu/file/druid:yf330xx7624/yf330xx7624.pdf pdf]
 
* [[James R. Slagle]], [[Philip Bursky]] ('''1968'''). ''[http://portal.acm.org/citation.cfm?id=321444 Experiments With a Multipurpose, Theorem-Proving Heuristic Program]''. [[ACM#Journal|Journal of the ACM]], Vol. 15, No. 1
 
* [[James R. Slagle]], [[Philip Bursky]] ('''1968'''). ''[http://portal.acm.org/citation.cfm?id=321444 Experiments With a Multipurpose, Theorem-Proving Heuristic Program]''. [[ACM#Journal|Journal of the ACM]], Vol. 15, No. 1
 
* [[James R. Slagle]], [[John K. Dixon]] ('''1969'''). ''[http://portal.acm.org/citation.cfm?id=321510.321511 Experiments With Some Programs That Search Game Trees]''. [[ACM#Journal|Journal of the ACM]], Vol. 16, No. 2, [http://wiki.cs.pdx.edu/cs542-spring2011/nfp/abmin.pdf pdf], [http://wiki.cs.pdx.edu/wurzburg2009/nfp/abmin.pdf pdf]
 
* [[James R. Slagle]], [[John K. Dixon]] ('''1969'''). ''[http://portal.acm.org/citation.cfm?id=321510.321511 Experiments With Some Programs That Search Game Trees]''. [[ACM#Journal|Journal of the ACM]], Vol. 16, No. 2, [http://wiki.cs.pdx.edu/cs542-spring2011/nfp/abmin.pdf pdf], [http://wiki.cs.pdx.edu/wurzburg2009/nfp/abmin.pdf pdf]
Line 106: Line 107:
 
* [[Larry Harris]] ('''1973'''). ''The bandwidth heuristic search''. [http://dblp.uni-trier.de/db/conf/ijcai/ijcai73.html 3. IJCAI 1973], [http://www.ijcai.org/Past%20Proceedings/IJCAI-73/PDF/004.pdf pdf]
 
* [[Larry Harris]] ('''1973'''). ''The bandwidth heuristic search''. [http://dblp.uni-trier.de/db/conf/ijcai/ijcai73.html 3. IJCAI 1973], [http://www.ijcai.org/Past%20Proceedings/IJCAI-73/PDF/004.pdf pdf]
 
* [[Gerhard Wolf]] ('''1973'''). ''[http://dl.acm.org/citation.cfm?id=805704 Implementation of a dynamic tree searching algorithm in a chess programme]''. [http://dl.acm.org/citation.cfm?id=800192&picked=prox Proceedings of the ACM annual conference]
 
* [[Gerhard Wolf]] ('''1973'''). ''[http://dl.acm.org/citation.cfm?id=805704 Implementation of a dynamic tree searching algorithm in a chess programme]''. [http://dl.acm.org/citation.cfm?id=800192&picked=prox Proceedings of the ACM annual conference]
* [[Larry Harris]] ('''1974'''). ''Heuristic Search under Conditions of Error''. Artificial Intelligence, Vol. 5, No. 3, pp. 217-234. ISSN 0004-3702. Also published ('''1977''') under the title: ''The heuristic search: An alternative to the alpha-beta minimax procedure.'' [[Chess Skill in Man and Machine]] (ed. [[Peter W. Frey]]), pp. 157-166
+
* [[Larry Harris]] ('''1974'''). ''Heuristic Search under Conditions of Error''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 5, No. 3, also published ('''1977''') under the title: ''The heuristic search: An alternative to the alpha-beta minimax procedure.'' [[Chess Skill in Man and Machine]] (ed. [[Peter W. Frey]])
 
* [[Larry Harris]] ('''1975''') ''The Heuristic Search And The Game Of Chess - A Study Of Quiescence, Sacrifices, And Plan Oriented Play''. [http://dblp.uni-trier.de/db/conf/ijcai/ijcai75.html IJCAI 1975], reprinted in [[Computer Chess Compendium]]
 
* [[Larry Harris]] ('''1975''') ''The Heuristic Search And The Game Of Chess - A Study Of Quiescence, Sacrifices, And Plan Oriented Play''. [http://dblp.uni-trier.de/db/conf/ijcai/ijcai75.html IJCAI 1975], reprinted in [[Computer Chess Compendium]]
 
* [[Toshihide Ibaraki]] ('''1978'''). ''[https://link.springer.com/article/10.1007/BF00991818 Depth-m search in branch-and-bound algorithms]''. [https://link.springer.com/journal/10766 International Journal of Parallel Programming], Vol. 7, No. 4
 
* [[Toshihide Ibaraki]] ('''1978'''). ''[https://link.springer.com/article/10.1007/BF00991818 Depth-m search in branch-and-bound algorithms]''. [https://link.springer.com/journal/10766 International Journal of Parallel Programming], Vol. 7, No. 4
 
* [[Georgy Adelson-Velsky]], [[Vladimir Arlazarov]], [[Mikhail Donskoy]] ('''1979'''). ''Algorithms of adaptive search''. [http://www.doc.ic.ac.uk/~shm/MI/mi9.html Machine Intelligence 9] (eds. [[Jean Hayes Michie]], [[Donald Michie]] and L.I. Mikulich), Ellis Horwood, Chichester.
 
* [[Georgy Adelson-Velsky]], [[Vladimir Arlazarov]], [[Mikhail Donskoy]] ('''1979'''). ''Algorithms of adaptive search''. [http://www.doc.ic.ac.uk/~shm/MI/mi9.html Machine Intelligence 9] (eds. [[Jean Hayes Michie]], [[Donald Michie]] and L.I. Mikulich), Ellis Horwood, Chichester.
* [[George Stockman]] ('''1979'''). ''A Minimax Algorithm Better than Alpha-Beta?'' Artificial Intelligence, Vol. 12, No. 2, pp. 179-196. ISSN 0004-3702.
+
* [[George Stockman]] ('''1979'''). ''A Minimax Algorithm Better than Alpha-Beta?'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 12, No. 2
 +
* [[John Gaschnig]] ('''1979'''). ''[https://dl.acm.org/citation.cfm?id=909244 Performance Measurement and Analysis of Certain Search Algorithms]''. Ph.D. thesis, [[Carnegie Mellon University]], [http://reports-archive.adm.cs.cmu.edu/anon/scan/CMU-CS-79-124.pdf pdf]
 
==1980 ...==  
 
==1980 ...==  
 
* [[Judea Pearl]] ('''1981'''). ''Heuristic search theory: A survey of recent results''. [http://www.informatik.uni-trier.de/%7Eley/db/conf/ijcai/ijcai81.html IJCAI-81], [http://ijcai.org/Past%20Proceedings/IJCAI-81-VOL%201/PDF/100.pdf pdf]
 
* [[Judea Pearl]] ('''1981'''). ''Heuristic search theory: A survey of recent results''. [http://www.informatik.uni-trier.de/%7Eley/db/conf/ijcai/ijcai81.html IJCAI-81], [http://ijcai.org/Past%20Proceedings/IJCAI-81-VOL%201/PDF/100.pdf pdf]
 
* [[Judea Pearl]] ('''1982'''). ''[http://portal.acm.org/citation.cfm?id=358616&dl=ACM&coll=DL&CFID=27355608&CFTOKEN=40935826 The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality]''. [[ACM#Communications|Communications of the ACM]], Vol. 25, No. 8
 
* [[Judea Pearl]] ('''1982'''). ''[http://portal.acm.org/citation.cfm?id=358616&dl=ACM&coll=DL&CFID=27355608&CFTOKEN=40935826 The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality]''. [[ACM#Communications|Communications of the ACM]], Vol. 25, No. 8
* [[Murray Campbell]], [[Tony Marsland]] ('''1983'''). ''A Comparison of Minimax Tree Search Algorithms''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 20, No. 4, pp. 347-367. ISSN 0004-3702, [http://webdocs.cs.ualberta.ca/~tony/OldPapers/TR82-3.pdf pdf]
+
* [[Murray Campbell]], [[Tony Marsland]] ('''1983'''). ''A Comparison of Minimax Tree Search Algorithms''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 20, No. 4, [http://webdocs.cs.ualberta.ca/~tony/OldPapers/TR82-3.pdf pdf]
 
* [[Andrew L. Reibman]], [[Bruce W. Ballard]] ('''1983'''). ''[http://www.aaai.org/Library/AAAI/1983/aaai83-084.php Non-Minimax Search Strategies for Use against Fallible Opponents]''. Proceedings of [[AAAI]] 83
 
* [[Andrew L. Reibman]], [[Bruce W. Ballard]] ('''1983'''). ''[http://www.aaai.org/Library/AAAI/1983/aaai83-084.php Non-Minimax Search Strategies for Use against Fallible Opponents]''. Proceedings of [[AAAI]] 83
 
* [[Nanda Srimani]] ('''1985'''). ''A New Algorithm (PS*) for Searching Game Trees''. Master's thesis, [[University of Alberta]]
 
* [[Nanda Srimani]] ('''1985'''). ''A New Algorithm (PS*) for Searching Game Trees''. Master's thesis, [[University of Alberta]]
* [[Toshihide Ibaraki]] ('''1986'''). ''Generalization of Alpha-Beta and SSS* Search Procedures.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 29, pp. 73-117. ISSN 0004-3702.
+
* [[Toshihide Ibaraki]] ('''1986'''). ''Generalization of Alpha-Beta and SSS* Search Procedures.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 29
 
* [[Tony Marsland]], [[Nanda Srimani]] ('''1986'''). ''Phased State Search''. [http://www.informatik.uni-trier.de/~ley/db/conf/fjcc/fjcc86.html#MarslandS86 Fall Joint Computer Conference], [http://webdocs.cs.ualberta.ca/~tony/OldPapers/fjcc.1986.pdf pdf]
 
* [[Tony Marsland]], [[Nanda Srimani]] ('''1986'''). ''Phased State Search''. [http://www.informatik.uni-trier.de/~ley/db/conf/fjcc/fjcc86.html#MarslandS86 Fall Joint Computer Conference], [http://webdocs.cs.ualberta.ca/~tony/OldPapers/fjcc.1986.pdf pdf]
 
* [[Hermann Kaindl]], [[Helmut Horacek]], [[Marcus Wagner]] ('''1986'''). ''Selective Search versus Brute Force.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]
 
* [[Hermann Kaindl]], [[Helmut Horacek]], [[Marcus Wagner]] ('''1986'''). ''Selective Search versus Brute Force.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]
* [[Ronald L. Rivest]] ('''1987'''). ''Game Tree Searching by Min/Max Approximation''. Artificial Intelligence Vol. 34, 1, [http://people.csail.mit.edu/rivest/Rivest-GameTreeSearchingByMinMaxApproximation.pdf pdf 1995]
+
* [[Ronald L. Rivest]] ('''1987'''). ''Game Tree Searching by Min/Max Approximation''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 34, No. 1, [http://people.csail.mit.edu/rivest/Rivest-GameTreeSearchingByMinMaxApproximation.pdf pdf 1995]
 
* [[Bruce Abramson]] ('''1989'''). ''Control Strategies for Two-Player Games.'' ACM Computing Surveys, Vol. 21, No. 2, [http://www.theinformationist.com/pdf/constrat.pdf/ pdf]
 
* [[Bruce Abramson]] ('''1989'''). ''Control Strategies for Two-Player Games.'' ACM Computing Surveys, Vol. 21, No. 2, [http://www.theinformationist.com/pdf/constrat.pdf/ pdf]
 
* [[Stuart Russell]], [[Eric Wefald]] ('''1989'''). ''[http://portal.acm.org/citation.cfm?id=1623807 On optimal game-tree search using rational metareasoning].'' In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, Detroit, MI: Morgan Kaufmann, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.9229&rep=rep1&type=pdf pdf]
 
* [[Stuart Russell]], [[Eric Wefald]] ('''1989'''). ''[http://portal.acm.org/citation.cfm?id=1623807 On optimal game-tree search using rational metareasoning].'' In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, Detroit, MI: Morgan Kaufmann, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.9229&rep=rep1&type=pdf pdf]
Line 179: Line 181:
  
 
=Forum Posts=  
 
=Forum Posts=  
 +
==1999==
 +
* [https://www.stmintz.com/ccc/index.php?id=47379 Some crazy ideas] by Gareth McCaughan, [[CCC]], March 29, 1999
 
==2000 ...==
 
==2000 ...==
 
* [https://www.stmintz.com/ccc/index.php?id=112586 About search algorithms and heuristics] by [[José Carlos Martínez Galán|José Carlos]], [[CCC]], May 26, 2000
 
* [https://www.stmintz.com/ccc/index.php?id=112586 About search algorithms and heuristics] by [[José Carlos Martínez Galán|José Carlos]], [[CCC]], May 26, 2000

Revision as of 16:10, 8 December 2019

Home * Search

Bernd Besser, Auf der Suche [1]

Because finding or guessing a good move in a chess position is hard to achieve statically, chess programs rely on some type of Search in order to play reasonably. Searching involves looking ahead at different move sequences and evaluating the positions after making the moves. Formally, searching a two-player zero-sum board game with perfect information implies traversing and min-maxing a tree-like data-structure by various search algorithms.

Shannon's Types

Claude Shannon categorized searches into two types [2] :

Inspired by the experiments of Adriaan de Groot [3] , Shannon and early programmers favored Type B strategy. Type B searches use some type of static heuristics in order to only look at branches that look important - with some risk to oversee some serious tactics not covered by the plausible move selector. Type B was most popular until the 1970's, when Type A programs had enough processing power and more efficient brute force algorithms to become stronger. Today most programs are closer to Type A, but have some characteristics of a Type B as mentioned in selectivity.

The Search Tree

The search tree as subset of the search space is a directed graph of nodes, the alternating white and black to move chess positions - and edges connecting two nodes, representing the moves of either side. The root of the search-tree is the position we like to evaluate to find the best move. Because of transpositions due to different move sequences, nodes inside the tree may occur from various ancestors - even within a different number of moves. The search tree contains various cycles, since both sides may repeat a former position with the minimum of two reversible moves each, or four plies. Cycles are usually eliminated and not searched twice, which results in searching a directed acyclic graph (DAG).

Search Algorithms

Most chess-programs use a variation of the alpha-beta algorithm to search the tree in a depth-first manner to attain an order of magnitude performance improvement over a pure minimax algorithm. Although move ordering doesnt affect the performance of a pure mini-max search (as all branches and nodes are searched) — it becomes crucial for the performance of alpha beta search and enhancements such as PVS, NegaScout and MTD(f). Hans Berliner's chess-program HiTech and Ulf Lorenz's program P.ConNerS used best-first approaches quite successfully.

Depth-First Search

Depth-First search starts at the root and explores as far as possible along each branch before backtracking. Memory requirements are moderate, since only one path from the root to one leaf is kept in memory. The giga bytes of RAM in recent computers is utilized by a transposition table. Minimax and Negamax are mentioned for educational reasons as the prototypes for the more advanced algorithms. They otherwise have no practical relevance in software, except traversing a minimax tree inside a perft framework for testing the move generator. Depth-first algorithms are generally embedded inside an iterative deepening framework for time control and move ordering issues.

Alpha-Beta Enhancements

Obligatory

Selectivity

Scout and Friends

Alpha-Beta goes Best-First

Best-First Search

Best-First approaches build a search-tree by visiting the most promising nodes first. They usually have huge memory requirements, since they keep an exponentially growing search space in memory.

Opponent Model

Parallel Search

Using Time

Related Issues

See also

Search versus Evaluation

Publications

1960 ...

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...

2015 ...

Forum Posts

1999

2000 ...

2005 ...

Re: Search or Evaluation? by Mark Uniacke, Hiarcs Forum, October 14, 2007

2010 ...

2015 ...

External Links

A* search algorithm from Wikipedia
Jack DeJohnette (Joe Chambers track 6), John McLaughlin, Herbie Hancock, Joe Henderson

References

  1. Schach Bilder Welten - Bernd Besser - Galerie
  2. Claude Shannon (1949). Programming a Computer for Playing Chess. pdf
  3. Adriaan de Groot (1946). Het denken van den Schaker, een experimenteel-psychologische studie. Ph.D. thesis, University of Amsterdam; N.V. Noord-Hollandse Uitgevers Maatschappij, Amsterdam. Translated with the help of George Baylor, with additions (in 1965) as Thought and Choice in Chess. Mouton Publishers, The Hague. ISBN 90-279-7914-6. (amazon)
  4. Excellent Computer-Chess Overview Paper Found! by Ernst A. Heinz, rgcc, March 6, 1997
  5. Great article for people who wants to write a chess engine by Miguel A. Ballicora, CCC, April 03, 2002
  6. Re: A new(?) technique to recognize draws by Dan Andersson, June 01, 2002
  7. Re: Aquarium IDEA, repetitions, and minimax over cycles by syzygy, OpenChess Forum, September 22, 2012
  8. Khet (game) from Wikipedia
  9. Information and search in computer chess (Godescu) by BB+, OpenChess Forum, December 12, 2011
  10. A new algorithm accounting for the uncertainty in eval funcs by Tom Holden, CCC, November 12, 2014

Up one Level