Difference between revisions of "Search"

From Chessprogramming wiki
Jump to: navigation, search
m
(15 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * Search'''
 
'''[[Main Page|Home]] * Search'''
  
[[FILE:AufderSuche.jpg|border|right|thumb|link=http://schachbilderwelten.tenners.de/html/auf_der_suche.html|[[Arts#Besser|Bernd Besser]], Auf der Suche <ref>[http://schachbilderwelten.tenners.de/html/galerie.html Schach Bilder Welten - Bernd Besser - Galerie]</ref> ]]
+
[[FILE:AufderSuche.jpg|border|right|thumb|link=http://schachbilderwelten.tenners.de/html/auf_der_suche.html|[[:Category:Bernd Besser|Bernd Besser]], Auf der Suche <ref>[http://schachbilderwelten.tenners.de/html/galerie.html Schach Bilder Welten - Bernd Besser - Galerie]</ref> ]]
  
 
Because finding or guessing a [[Best Move|good move]] in a [[Chess Position|chess position]] is hard to achieve statically, [[Engines|chess programs]] rely on some type of '''Search''' in order to play reasonably. Searching involves looking ahead at different [[Moves|move]] sequences and evaluating the positions after [[Make Move|making the moves]]. Formally, searching a two-player [https://en.wikipedia.org/wiki/Zero-sum_%28game_theory%29 zero-sum] board game with [https://en.wikipedia.org/wiki/Perfect_information perfect information] implies [https://en.wikipedia.org/wiki/Tree_traversal traversing] and min-maxing a [https://en.wikipedia.org/wiki/Tree_%28data_structure%29 tree-like data-structure] by various [https://en.wikipedia.org/wiki/Search_algorithm search algorithms].  
 
Because finding or guessing a [[Best Move|good move]] in a [[Chess Position|chess position]] is hard to achieve statically, [[Engines|chess programs]] rely on some type of '''Search''' in order to play reasonably. Searching involves looking ahead at different [[Moves|move]] sequences and evaluating the positions after [[Make Move|making the moves]]. Formally, searching a two-player [https://en.wikipedia.org/wiki/Zero-sum_%28game_theory%29 zero-sum] board game with [https://en.wikipedia.org/wiki/Perfect_information perfect information] implies [https://en.wikipedia.org/wiki/Tree_traversal traversing] and min-maxing a [https://en.wikipedia.org/wiki/Tree_%28data_structure%29 tree-like data-structure] by various [https://en.wikipedia.org/wiki/Search_algorithm search algorithms].  
Line 31: Line 31:
  
 
==Depth-First Search==  
 
==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 [[Memory#RAM|RAM]] in recent computers is utilized by a [[Transposition Table|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|perft]] framework for [[Engine Testing|testing]] the [[Move generation|move generator]]. Depth-first algorithms are generally embedded inside an [[Iterative Deepening|iterative deepening]] framework for [[Time Management|time control]] and [[Move Ordering|move ordering]] issues.
+
[[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 [[Memory#RAM|RAM]] in recent computers is utilized by a [[Transposition Table|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|perft]] framework for [[Engine Testing|testing]] the [[Move Generation|move generator]]. Depth-first algorithms are generally embedded inside an [[Iterative Deepening|iterative deepening]] framework for [[Time Management|time control]] and [[Move Ordering|move ordering]] issues.
 
* [[Minimax]]
 
* [[Minimax]]
 
* [[Negamax]]
 
* [[Negamax]]
Line 57: Line 57:
 
They usually have huge memory requirements, since they keep an exponentially growing search space in memory.
 
They usually have huge memory requirements, since they keep an exponentially growing search space in memory.
 
* [[B*]] as used by [[Hans Berliner|Hans Berliner's]] chess-program [[HiTech]]
 
* [[B*]] as used by [[Hans Berliner|Hans Berliner's]] chess-program [[HiTech]]
 +
* [[Best-First Minimax Search]]
 
* [[Conspiracy Number Search]]
 
* [[Conspiracy Number Search]]
 
* [[MCαβ]]
 
* [[MCαβ]]
 
* [[Monte-Carlo Tree Search]]
 
* [[Monte-Carlo Tree Search]]
* [[Proof-number Search]]
+
* [[Proof-Number Search]]
 
* [[SSS* and Dual*]]
 
* [[SSS* and Dual*]]
 
* [[UCT]]
 
* [[UCT]]
Line 69: 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 95: 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 105: 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 4. IJCAI 1975], 334-339. reprinted in [[Computer Chess Compendium]] by [[David Levy]] (Editor), pp. 136 - 142
+
* [[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]]
* [[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), pp. 373-384. Ellis Horwood, Chichester.
+
* [[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
* [[George Stockman]] ('''1979'''). ''A Minimax Algorithm Better than Alpha-Beta?'' Artificial Intelligence, Vol. 12, No. 2, pp. 179-196. ISSN 0004-3702.
+
* [[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?'' [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 21(2): 137-161, [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]
 
* [[Liwu Li]] ('''1989'''). ''[https://doi.org/10.7939/R3VX06F26 Probabilistic Analysis of Search]''. Ph.D. thesis, [[University of Alberta]], advisor [[Tony Marsland]]  
 
* [[Liwu Li]] ('''1989'''). ''[https://doi.org/10.7939/R3VX06F26 Probabilistic Analysis of Search]''. Ph.D. thesis, [[University of Alberta]], advisor [[Tony Marsland]]  
 +
* [[Wolfgang Nagl]] ('''1989'''). ''Best-Move Proving: A Fast Game Tree Searching Program''. [[1st Computer Olympiad#Workshop|Heuristic Programming in AI 1]]
 
==1990 ...==  
 
==1990 ...==  
 +
* [[Toshihide Ibaraki]], [[Naoki Katoh]] ('''1990'''). ''[https://link.springer.com/article/10.1007/BF01531075 Searching Minimax Game Trees Under Memory Space Constraint]''. [https://link.springer.com/journal/10472 Annals of Mathematics and Artificial Intelligence], Vol. 1, Nos. 1-4
 
* [[Victor Allis]], [[Maarten van der Meulen]], [[Jaap van den Herik]] ('''1991'''). ''Proof-Number Search.'' Technical Reports in Computer Science, CS 91-01. Department of Computer Science, [[Maastricht University|University of Limburg]]
 
* [[Victor Allis]], [[Maarten van der Meulen]], [[Jaap van den Herik]] ('''1991'''). ''Proof-Number Search.'' Technical Reports in Computer Science, CS 91-01. Department of Computer Science, [[Maastricht University|University of Limburg]]
 
* [[Tony Marsland]] ('''1992'''). ''Computer Chess and Search.'' Encyclopedia of Artificial Intelligence (2nd ed.) (ed. S.C. Shapiro) John Wiley & Sons, Inc. [http://webdocs.cs.ualberta.ca/~tony/RecentPapers/encyc.mac-1991.pdf pdf] <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/7df61a100528f201 Excellent Computer-Chess Overview Paper Found!] by [[Ernst A. Heinz]], [[Computer Chess Forums|rgcc]], March 6, 1997</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=221364 Great article for people who wants to write a chess engine] by [[Miguel A. Ballicora]], [[CCC]], April 03, 2002</ref>
 
* [[Tony Marsland]] ('''1992'''). ''Computer Chess and Search.'' Encyclopedia of Artificial Intelligence (2nd ed.) (ed. S.C. Shapiro) John Wiley & Sons, Inc. [http://webdocs.cs.ualberta.ca/~tony/RecentPapers/encyc.mac-1991.pdf pdf] <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/7df61a100528f201 Excellent Computer-Chess Overview Paper Found!] by [[Ernst A. Heinz]], [[Computer Chess Forums|rgcc]], March 6, 1997</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=221364 Great article for people who wants to write a chess engine] by [[Miguel A. Ballicora]], [[CCC]], April 03, 2002</ref>
Line 145: Line 151:
 
* [[Thomas Lincke]] ('''2002'''). ''Exploring the Computational Limits of Large Exhaustive Search Problems''. Ph.D thesis, [[ETH Zurich]], [http://e-collection.library.ethz.ch/eserv/eth:25905/eth-25905-02.pdf pdf] » [[Awari]], [[Repetitions]] <ref>[http://www.open-chess.org/viewtopic.php?f=5&t=2093#p17469 Re: Aquarium IDEA, repetitions, and minimax over cycles] by [[Ronald de Man|syzygy]], [[Computer Chess Forums|OpenChess Forum]], September 22, 2012</ref>
 
* [[Thomas Lincke]] ('''2002'''). ''Exploring the Computational Limits of Large Exhaustive Search Problems''. Ph.D thesis, [[ETH Zurich]], [http://e-collection.library.ethz.ch/eserv/eth:25905/eth-25905-02.pdf pdf] » [[Awari]], [[Repetitions]] <ref>[http://www.open-chess.org/viewtopic.php?f=5&t=2093#p17469 Re: Aquarium IDEA, repetitions, and minimax over cycles] by [[Ronald de Man|syzygy]], [[Computer Chess Forums|OpenChess Forum]], September 22, 2012</ref>
 
* [[Steven Walczak]] ('''2003'''). ''[http://portal.acm.org/citation.cfm?id=776752.776792&coll=DL&dl=GUIDE&CFID=34101495&CFTOKEN=18614940 Knowledge-Based Search in Competitive Domains]''. IEEE Transactions on Knowledge and Data Engineering, Vol. 15, No. 3
 
* [[Steven Walczak]] ('''2003'''). ''[http://portal.acm.org/citation.cfm?id=776752.776792&coll=DL&dl=GUIDE&CFID=34101495&CFTOKEN=18614940 Knowledge-Based Search in Competitive Domains]''. IEEE Transactions on Knowledge and Data Engineering, Vol. 15, No. 3
 +
* [[Arie de Bruin]], [[Wim Pijls]] ('''2003'''). ''[https://repub.eur.nl/pub/459 Trends in game tree search]''. [https://en.wikipedia.org/wiki/Erasmus_University_Rotterdam Erasmus University, Rotterdam]
 
* [[David Rasmussen]] ('''2004'''). ''Parallel Chess Searching and Bitboards.'' Masters thesis, [http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/3267/ps/imm3267.ps ps]
 
* [[David Rasmussen]] ('''2004'''). ''Parallel Chess Searching and Bitboards.'' Masters thesis, [http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/3267/ps/imm3267.ps ps]
* [[Yan Radovilsky]], [[Solomon Eyal Shimony]] ('''2004'''). ''Generalized Model for Rational Game Tree Search''. [http://www.cs.bgu.ac.il/%7Eyanr/Publications/smc04.pdf pdf]
+
* [[Yan Radovilsky]], [[Solomon Eyal Shimony]] ('''2004'''). ''Generalized Model for Rational Game Tree Search''. [https://dblp.uni-trier.de/db/conf/smc/smc2004-2.html  SMC 2004], [https://www.cs.bgu.ac.il/~yanr/Publications/smc04.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=57560&start=14 Re: Interesting ideas] by [[Karlo Balla|Karlo Bala Jr.]], [[CCC]], September 09, 2015</ref>
 
* [[Markian Hlynka]], [[Jonathan Schaeffer]] ('''2004'''). ''Pre-Searching''. [[ICGA Journal#27_4|ICGA Journal, Vol. 27, No. 4]]
 
* [[Markian Hlynka]], [[Jonathan Schaeffer]] ('''2004'''). ''Pre-Searching''. [[ICGA Journal#27_4|ICGA Journal, Vol. 27, No. 4]]
 
* [[Markian Hlynka]], [[Jonathan Schaeffer]] ('''2005'''). ''[http://link.springer.com/chapter/10.1007/11922155_3 Automatic Generation of Search Engines]''. [[Advances in Computer Games 11]]
 
* [[Markian Hlynka]], [[Jonathan Schaeffer]] ('''2005'''). ''[http://link.springer.com/chapter/10.1007/11922155_3 Automatic Generation of Search Engines]''. [[Advances in Computer Games 11]]
Line 165: Line 172:
 
* [[Jeff Rollason]] ('''2014'''). ''[http://www.aifactory.co.uk/newsletter/2014_01_interest_minimax.htm Interest Search - Another way to do Minimax]''. [[AI Factory]], Summer 2014
 
* [[Jeff Rollason]] ('''2014'''). ''[http://www.aifactory.co.uk/newsletter/2014_01_interest_minimax.htm Interest Search - Another way to do Minimax]''. [[AI Factory]], Summer 2014
 
* [[Tom Holden]] ('''2014'''). ''Notes on an alternative approach to move choice in games such as Chess''. [http://www.tholden.org/wp-content/uploads/2014/11/Notes-on-an-alternative-approach-to-move-choice-in-games-such-as-Chess.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=54324 A new algorithm accounting for the uncertainty in eval funcs] by [[Tom Holden]], [[CCC]],  November 12, 2014</ref>
 
* [[Tom Holden]] ('''2014'''). ''Notes on an alternative approach to move choice in games such as Chess''. [http://www.tholden.org/wp-content/uploads/2014/11/Notes-on-an-alternative-approach-to-move-choice-in-games-such-as-Chess.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=54324 A new algorithm accounting for the uncertainty in eval funcs] by [[Tom Holden]], [[CCC]],  November 12, 2014</ref>
 +
* [[Christopher D. Rosin]] ('''2014'''). ''Game playing''. [https://en.wikipedia.org/wiki/Wiley_Interdisciplinary_Reviews:_Cognitive_Science WIREs Cognitive Science], Vol. 5, [http://www.chrisrosin.com/Rosin-Game-Playing-submitted-ver.pdf pdf preprint]
 
==2015 ...==
 
==2015 ...==
 
* [[Jakub Pawlewicz]], [[Ryan Hayward]] ('''2015'''). ''Feature Strength and Parallelization of Sibling Conspiracy Number Search''. [[Advances in Computer Games 14]]
 
* [[Jakub Pawlewicz]], [[Ryan Hayward]] ('''2015'''). ''Feature Strength and Parallelization of Sibling Conspiracy Number Search''. [[Advances in Computer Games 14]]
Line 173: 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
Line 201: Line 211:
 
* [http://www.talkchess.com/forum/viewtopic.php?t=64390 search efficiency] by [[Marco Pampaloni]], [[CCC]], June 23, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=64390 search efficiency] by [[Marco Pampaloni]], [[CCC]], June 23, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65403 comparing between search or evaluation] by [[Uri Blass]], [[CCC]], October 09, 2017 » [[Evaluation]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65403 comparing between search or evaluation] by [[Uri Blass]], [[CCC]], October 09, 2017 » [[Evaluation]]
 +
==2020 ...==
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74170 Tactical search] by [[Alvaro Cardoso]], [[CCC]], June 13, 2020 » [[Tactics]]
  
 
=External Links=  
 
=External Links=  
Line 211: Line 223:
 
* [https://en.wikipedia.org/wiki/Breadth-first_search Breadth-first search from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Breadth-first_search Breadth-first search from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Dijkstra's algorithm from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Dijkstra's algorithm from Wikipedia]
* [http://homepages.ius.edu/RWISMAN/C463/html/Chapter3.htm Chapter 3 Solving Problems by Searching] from [http://homepages.ius.edu/RWISMAN/C463/html/syllabus.htm C463 Artificial Intelligence Syllabus] by [http://homepages.ius.edu/RWISMAN/ Raymond F. Wisman]
 
* [http://chess.verhelst.org/1997/03/10/search/ Tree Search] by [[Paul Verhelst]]
 
* [http://www.chessbin.com/post/Move-Searching-Alpha-Beta.aspx Move Searching and Alpha Beta] by [[Adam Berent]]
 
 
* [http://www.t-t.dk/go/cg2000/code20.html Lambda-search Java-code (version 2.0)] by [[Thomas Thomsen]]
 
* [http://www.t-t.dk/go/cg2000/code20.html Lambda-search Java-code (version 2.0)] by [[Thomas Thomsen]]
 
* [http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-iv-basic-search-r1171 Chess Programming Part IV: Basic Search] by [[François-Dominic Laramée]], [https://en.wikipedia.org/wiki/GameDev.net gamedev.net], Ausgust 2000
 
* [http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-iv-basic-search-r1171 Chess Programming Part IV: Basic Search] by [[François-Dominic Laramée]], [https://en.wikipedia.org/wiki/GameDev.net gamedev.net], Ausgust 2000
 
* [http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-v-advanced-search-r1197 Chess Programming Part V: Advanced Search] by [[François-Dominic Laramée]], [https://en.wikipedia.org/wiki/GameDev.net gamedev.net], September 2000
 
* [http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-v-advanced-search-r1197 Chess Programming Part V: Advanced Search] by [[François-Dominic Laramée]], [https://en.wikipedia.org/wiki/GameDev.net gamedev.net], September 2000
 
* [https://sites.google.com/site/hispanicchessengines/programs--interface---engines/engine Engine - Hispanic Chess Engines | The search function] by [[Pedro Castro]]
 
* [https://sites.google.com/site/hispanicchessengines/programs--interface---engines/engine Engine - Hispanic Chess Engines | The search function] by [[Pedro Castro]]
* [[Videos#MiroslavVitous|Miroslav Vitouš]] - [https://de.wikipedia.org/wiki/Infinite_Search Infinite Search] (1969), [https://en.wikipedia.org/wiki/YouTube YouTube] Video  
+
* [[:Category:Miroslav Vitouš|Miroslav Vitouš]] - [https://de.wikipedia.org/wiki/Infinite_Search Infinite Search] (1969), [https://en.wikipedia.org/wiki/YouTube YouTube] Video  
: [[Videos#JackDeJohnette|Jack DeJohnette]] ([https://en.wikipedia.org/wiki/Joe_Chambers Joe Chambers] track 6), [[Videos#JohnMcLaughlin|John McLaughlin]], [[Videos#HerbieHancock|Herbie Hancock]],  [[Videos#JoeHenderson|Joe Henderson]]
+
: [[:Category:Jack DeJohnette|Jack DeJohnette]], [[:Category:John McLaughlin|John McLaughlin]], [[:Category:Herbie Hancock|Herbie Hancock]],  [[:Category:Joe Henderson|Joe Henderson]]
: {{#evu:https://www.youtube.com/watch?v=41RgdUoGZ98|alignment=left|valignment=top}}
+
: {{#evu:https://www.youtube.com/watch?v=-OdIEbFwQEs|alignment=left|valignment=top}}
  
 
=References=  
 
=References=  
Line 226: Line 235:
  
 
'''[[Main Page|Up one Level]]'''
 
'''[[Main Page|Up one Level]]'''
 +
[[Category:Bernd Besser]]
 +
[[Category:Jack DeJohnette]]
 +
[[Category:Herbie Hancock]]
 +
[[Category:Joe Henderson]]
 +
[[Category:John McLaughlin]]
 +
[[Category:Miroslav Vitouš]]

Revision as of 09:19, 20 June 2020

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 ...

2020 ...

External Links

A* search algorithm from Wikipedia
Jack DeJohnette, 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. Re: Interesting ideas by Karlo Bala Jr., CCC, September 09, 2015
  9. Khet (game) from Wikipedia
  10. Information and search in computer chess (Godescu) by BB+, OpenChess Forum, December 12, 2011
  11. A new algorithm accounting for the uncertainty in eval funcs by Tom Holden, CCC, November 12, 2014

Up one Level