Difference between revisions of "Search"
GerdIsenberg (talk | contribs) |
m (→The Search Tree: todo: write DAG article, there was a Lc0 related paper to solve MCTS transpositions via DAG representation) |
||
(17 intermediate revisions by one other user not shown) | |||
Line 13: | Line 13: | ||
=The Search Tree= | =The Search Tree= | ||
− | The [[Search Tree|search tree]] as subset of the [[Search Space|search space]] is a [https://en.wikipedia.org/wiki/Graph_%28mathematics%29#Directed_graph directed graph] of [[Node|nodes]], the alternating white and black to move [[Chess Position|chess positions]] - and edges connecting two nodes, representing the [[Moves|moves]] of either side. The [[Root|root]] of the search-tree is the position we like to evaluate to find the [[Best Move|best move]]. Because of [[Transposition|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 [[Repetitions|repeat]] a former position with the minimum of two reversible moves each, or four [[Ply|plies]]. Cycles are usually eliminated and not searched twice, which results in searching a [https://en.wikipedia.org/wiki/Directed_acyclic_graph directed acyclic graph] | + | The [[Search Tree|search tree]] as subset of the [[Search Space|search space]] is a [https://en.wikipedia.org/wiki/Graph_%28mathematics%29#Directed_graph directed graph] of [[Node|nodes]], the alternating white and black to move [[Chess Position|chess positions]] - and edges connecting two nodes, representing the [[Moves|moves]] of either side. The [[Root|root]] of the search-tree is the position we like to evaluate to find the [[Best Move|best move]]. Because of [[Transposition|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 [[Repetitions|repeat]] a former position with the minimum of two reversible moves each, or four [[Ply|plies]]. Cycles are usually eliminated and not searched twice, which results in searching a [https://en.wikipedia.org/wiki/Directed_acyclic_graph directed acyclic graph] [[DAG]]. |
* [[Search Space]] | * [[Search Space]] | ||
* [[Search Tree]] | * [[Search Tree]] | ||
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]] | + | * [[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, | + | * [[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 | + | * [[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), | + | * [[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, | + | * [[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 | + | * [[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 | + | * [[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 | + | * [[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 148: | Line 153: | ||
* [[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] | * [[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''. [ | + | * [[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 174: | Line 179: | ||
* [[Ting-Han Wei]], [[Chao-Chin Liang]], [[I-Chen Wu]], [[Lung-Pin Chen]] ('''2015'''). ''Software Development Framework for Job-Level Algorithms''. [[ICGA Journal#38_3|ICGA Journal, Vol. 38, No. 3]] | * [[Ting-Han Wei]], [[Chao-Chin Liang]], [[I-Chen Wu]], [[Lung-Pin Chen]] ('''2015'''). ''Software Development Framework for Job-Level Algorithms''. [[ICGA Journal#38_3|ICGA Journal, Vol. 38, No. 3]] | ||
* [[Tobias Joppen]], [[Miriam Moneke]], [[Nils Schroder]], [[Christian Wirth]], [[Johannes Fürnkranz]] ('''2017'''). ''[http://ieeexplore.ieee.org/document/7970136/ Informed Hybrid Game Tree Search for General Video Game Playing]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. PP, No. 99 | * [[Tobias Joppen]], [[Miriam Moneke]], [[Nils Schroder]], [[Christian Wirth]], [[Johannes Fürnkranz]] ('''2017'''). ''[http://ieeexplore.ieee.org/document/7970136/ Informed Hybrid Game Tree Search for General Video Game Playing]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. PP, No. 99 | ||
+ | * [[Michael Hartisch]], [[Ulf Lorenz]] ('''2019'''). ''A Novel Application for Game Tree Search - Exploiting Pruning Mechanisms for Quantified Integer Programs''. [[Advances in Computer Games 16]] | ||
+ | ==2020 ...== | ||
+ | * [[Quentin Cohen-Solal]], [[Tristan Cazenave]] ('''2020'''). ''Minimax Strikes Back''. [https://arxiv.org/abs/2012.10700 arXiv:2012.10700] » [[Reinforcement Learning]] | ||
+ | * [[Quentin Cohen-Solal]] ('''2021'''). ''Completeness of Unbounded Best-First Game Algorithms''. [https://arxiv.org/abs/2109.09468 arXiv:2109.09468] | ||
=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 204: | Line 215: | ||
* [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]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77189 Listening for GUI input when searching] by [[Niels Abildskov]], [[CCC]], April 27, 2021 » [[GUI]], [[Thread]], [[UCI]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77202 On reaching maximum ply] by [[Martin Bryant]], [[CCC]], April 29, 2021 » [[Depth#MaxPly|Maximum Search Depth]], [[Ply]] | ||
+ | * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=78505 Search] by [[Vincent Diepeveen]], [[CCC]], October 26, 2021 | ||
+ | * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79276 Strategies to unit testing the search] by Olexiy Svitashev, [[CCC]], February 03, 2022 » [[Engine Testing]] | ||
=External Links= | =External Links= | ||
Line 214: | Line 231: | ||
* [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://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]] | ||
+ | * [http://hamedahmadi.com/gametree/ An Introduction to Game Tree Algorithms] by [[Hamed Ahmadi]] | ||
* [[:Category:Miroslav Vitouš|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 | ||
− | : [[:Category:Jack DeJohnette|Jack DeJohnette]] | + | : [[: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= | + | : {{#evu:https://www.youtube.com/watch?v=-OdIEbFwQEs|alignment=left|valignment=top}} |
=References= | =References= |
Revision as of 22:36, 17 May 2023
Home * Search
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.
Contents
Shannon's Types
Claude Shannon categorized searches into two types [2] :
- Type A - a brute-force search looking at every variation to a given depth
- Type B - a selective search looking at "important" branches only
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 Space
- Search Tree
- Root
- Node
- Conspiracy Numbers
- Move List
- Principal Variation
- Graph History Interaction
- Path-Dependency
- Repetitions
- Transposition
- Score
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.
- B* as used by Hans Berliner's chess-program HiTech
- Best-First Minimax Search
- Conspiracy Number Search
- MCαβ
- Monte-Carlo Tree Search
- Proof-Number Search
- SSS* and Dual*
- UCT
Opponent Model
Parallel Search
- Parallel Search
- Parallel Controlled Conspiracy Number Search as used by Ulf Lorenz's program P.ConNerS
Using Time
Related Issues
- Depth
- Horizon Effect
- Iterative Search
- Move Ordering
- Search Explosion
- Search Instability
- Search Pathology
- Search Statistics
- Search with Random Leaf Values
- Theorem-Proving and M & N procedure
See also
Publications
1960 ...
- Daniel Edwards, Timothy Hart (1961). The Alpha-Beta Heuristic, AIM-030, reprint available from DSpace at 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
- 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). Experiments with the Graph Traverser Program. Proceedings of the Royal Society, Series A, Vol. 294, No. 1437, pdf
- James R. Slagle, Philip Bursky (1968). Experiments With a Multipurpose, Theorem-Proving Heuristic Program. Journal of the ACM, Vol. 15, No. 1
- James R. Slagle, John K. Dixon (1969). Experiments With Some Programs That Search Game Trees. Journal of the ACM, Vol. 16, No. 2, pdf, pdf
1970 ...
- James R. Slagle, John K. Dixon (1970). Experiments with the M & N Tree-Searching Program. Communications of the ACM, Vol. 13, No. 3, pp. 147-154.
- James R. Slagle, Richard C. T. Lee (1971). Application of game tree searching techniques to sequential pattern recognition. Communications of the ACM, Vol. 14, No. 2
- Larry Harris (1973). The bandwidth heuristic search. 3. IJCAI 1973, pdf
- Gerhard Wolf (1973). Implementation of a dynamic tree searching algorithm in a chess programme. Proceedings of the ACM annual conference
- Larry Harris (1974). Heuristic Search under Conditions of Error. 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. IJCAI 1975, reprinted in Computer Chess Compendium
- Toshihide Ibaraki (1978). Depth-m search in branch-and-bound algorithms. International Journal of Parallel Programming, Vol. 7, No. 4
- Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (1979). Algorithms of adaptive search. 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
- John Gaschnig (1979). Performance Measurement and Analysis of Certain Search Algorithms. Ph.D. thesis, Carnegie Mellon University, pdf
1980 ...
- Judea Pearl (1981). Heuristic search theory: A survey of recent results. IJCAI-81, pdf
- Judea Pearl (1982). The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality. Communications of the ACM, Vol. 25, No. 8
- Murray Campbell, Tony Marsland (1983). A Comparison of Minimax Tree Search Algorithms. Artificial Intelligence, Vol. 20, No. 4, pdf
- Andrew L. Reibman, Bruce W. Ballard (1983). 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
- Toshihide Ibaraki (1986). Generalization of Alpha-Beta and SSS* Search Procedures. Artificial Intelligence, Vol. 29
- Tony Marsland, Nanda Srimani (1986). Phased State Search. Fall Joint Computer Conference, pdf
- Hermann Kaindl, Helmut Horacek, Marcus Wagner (1986). Selective Search versus Brute Force. ICCA Journal, Vol. 9, No. 3
- Ronald L. Rivest (1987). Game Tree Searching by Min/Max Approximation. Artificial Intelligence, Vol. 34, No. 1, pdf 1995
- Bruce Abramson (1989). Control Strategies for Two-Player Games. ACM Computing Surveys, Vol. 21, No. 2, pdf
- Stuart Russell, Eric Wefald (1989). On optimal game-tree search using rational metareasoning. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, Detroit, MI: Morgan Kaufmann, pdf
- Liwu Li (1989). 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. Heuristic Programming in AI 1
1990 ...
- Toshihide Ibaraki, Naoki Katoh (1990). Searching Minimax Game Trees Under Memory Space Constraint. 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, University of Limburg
- Tony Marsland (1992). Computer Chess and Search. Encyclopedia of Artificial Intelligence (2nd ed.) (ed. S.C. Shapiro) John Wiley & Sons, Inc. pdf [4] [5]
- Eric B. Baum (1992). On Optimal Game Tree Propagation for Imperfect Players. AAAI-92, pdf
- Claude G. Diderich (1993). A Bibliography on Minimax Trees. ACM SIGACT News, Vol. 24, No. 4
- Deniz Yuret (1994). The Principle of Pressure in Chess. TAINN 1994
- Hans Berliner, Chris McConnell (1995). B* Probability Based Search. Carnegie Mellon University Computer Science research report, Pittsburgh, PA, postscript
- Claude G. Diderich, Marc Gengler (1995). A Survey on Minimax Trees and Associated Algorithms. Minimax and Its Applications. Kluwer Academic Publishers
- Eric B. Baum, Warren D. Smith (1995). Best Play for Imperfect Players and Game Tree Search. Part 1 - Theory
- Eric B. Baum, Warren D. Smith (1995). Best Play for Imperfect Players and Game Tree Search. with pseudocode appendix by Charles Garrett, ps
- Warren D. Smith, Eric B. Baum, Charles Garrett, Rico Tudor (1995). Best Play for Imperfect Players and Game Tree Search. Part 2 - Experiments, ps
- Andrew N. Walker (1996). Hybrid Heuristic Search. ICCA Journal, Vol. 19, No. 1
- Ingo Althöfer (1997). On the k-best Mode in Computer Chess: Measuring the Similarity of Move Proposals. ICCA Journal, Vol. 20, No. 3
- Eric B. Baum, Warren D. Smith (1997). A Bayesian Approach to Relevance in Game Playing. Artificial Intelligence, Vol. 97, CiteSeerX
- Donald E. Knuth (1998). The Art Of Computer Programming Vol 3. Sorting and Searching, Second Edition, Addison-Wesley
- Wim Pijls, Arie de Bruin (1998). Game Tree Algorithms and Solution Trees. CG 1998
2000 ...
- Paul E. Utgoff, Richard P. Cochran (2000). A Least-Certainty Heuristic for Selective Search. CG 2000, pdf » LCF
- Thomas Thomsen (2000). Lambda-Search in Game Trees - with Application to Go. CG 2000 also published in ICGA Journal, Vol. 23, No. 4, winning the 2001 ICGA Journal Award, preprint as pdf » Lambda-Search
- Todd W. Neller (2000). Simulation-Based Search for Hybrid System Control and Analysis. Ph.D. thesis, Stanford University, advisor Richard Fikes, pdf
- Martin Müller (2001, 2002). Proof-Set Search. Technical Report TR 01-09, University of Alberta, CG 2002, CiteSeerX [6]
- Thomas Lincke (2002). Exploring the Computational Limits of Large Exhaustive Search Problems. Ph.D thesis, ETH Zurich, pdf » Awari, Repetitions [7]
- Steven Walczak (2003). Knowledge-Based Search in Competitive Domains. IEEE Transactions on Knowledge and Data Engineering, Vol. 15, No. 3
- Arie de Bruin, Wim Pijls (2003). Trends in game tree search. Erasmus University, Rotterdam
- David Rasmussen (2004). Parallel Chess Searching and Bitboards. Masters thesis, ps
- Yan Radovilsky, Solomon Eyal Shimony (2004). Generalized Model for Rational Game Tree Search. SMC 2004, pdf [8]
- Markian Hlynka, Jonathan Schaeffer (2004). Pre-Searching. ICGA Journal, Vol. 27, No. 4
- Markian Hlynka, Jonathan Schaeffer (2005). Automatic Generation of Search Engines. Advances in Computer Games 11
- Ulf Lorenz (2006). A new Implementation of Error Analysis in Game Trees. ICGA Journal, Vol. 29, No. 2
- Dmitry Batenkov (2006). Modern developments of Shannon’s Chess. pdf
- Pim Nijssen (2009). Using Intelligent Search Techniques to Play the Game Khet. Master's Thesis, Maastricht University, pdf [9]
- Claude G. Diderich, Marc Gengler (2009). Minimax Game Tree Searching. Encyclopedia of Optimization, Springer
- David Silver (2009). Reinforcement Learning and Simulation-Based Search. Ph.D. thesis, University of Alberta, pdf
2010 ...
- Junichi Hashimoto (2011). A Study on Game-Independent Heuristics in Game-Tree Search. Ph.D. thesis, JAIST
- Hung-Jui Chang, Meng-Tsung Tsai, Tsan-sheng Hsu (2011). Game Tree Search with Adaptive Resolution. Advances in Computer Games 13, pdf
- Alexandru Godescu (2011). Information and search in computer chess. [10]
- Pim Nijssen, Mark Winands (2012). An Overview of Search Techniques in Multi-Player Games. ECAI CGW 2012
- Abdallah Saffidine, Tristan Cazenave (2012). A General Multi-Agent Modal Logic K Framework for Game Tree Search. ECAI CGW 2012
- Akihiro Kishimoto, Mark Winands, Martin Müller, Jahn-Takeshi Saito (2012). Game-Tree Search using Proof Numbers: The First Twenty Years. ICGA Journal, Vol. 35, No. 3
- Kuo-Yuan Kao, I-Chen Wu, Yi-Chang Shan, Shi-Jim Yen (2012). Selection Search for Mean and Temperature of Multi-branch Combinatorial Games. ICGA Journal, Vol. 35, No. 3
- David Silver, Richard Sutton, Martin Mueller (2013). Temporal-Difference Search in Computer Go. Proceedings of the ICAPS-13 Workshop on Planning and Learning, pdf
- Jeff Rollason (2014). 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. pdf [11]
- Christopher D. Rosin (2014). Game playing. WIREs Cognitive Science, Vol. 5, pdf preprint
2015 ...
- Jakub Pawlewicz, Ryan Hayward (2015). Feature Strength and Parallelization of Sibling Conspiracy Number Search. Advances in Computer Games 14
- Mohd Nor Akmal Khalid, Umi Kalsom Yusof, Hiroyuki Iida, Taichi Ishitobi (2015). Critical Position Identification in Games and Its Application to Speculative Play. ICAART 2015
- Mohd Nor Akmal Khalid, E. Mei Ang, Umi Kalsom Yusof, Hiroyuki Iida, Taichi Ishitobi (2015). Identifying Critical Positions Based on Conspiracy Numbers. Agents and Artificial Intelligence, ICAART 2015 - Revised Selected Papers
- Ting-Han Wei, Chao-Chin Liang, I-Chen Wu, Lung-Pin Chen (2015). Software Development Framework for Job-Level Algorithms. ICGA Journal, Vol. 38, No. 3
- Tobias Joppen, Miriam Moneke, Nils Schroder, Christian Wirth, Johannes Fürnkranz (2017). Informed Hybrid Game Tree Search for General Video Game Playing. IEEE Transactions on Computational Intelligence and AI in Games, Vol. PP, No. 99
- Michael Hartisch, Ulf Lorenz (2019). A Novel Application for Game Tree Search - Exploiting Pruning Mechanisms for Quantified Integer Programs. Advances in Computer Games 16
2020 ...
- Quentin Cohen-Solal, Tristan Cazenave (2020). Minimax Strikes Back. arXiv:2012.10700 » Reinforcement Learning
- Quentin Cohen-Solal (2021). Completeness of Unbounded Best-First Game Algorithms. arXiv:2109.09468
Forum Posts
1999
- Some crazy ideas by Gareth McCaughan, CCC, March 29, 1999
2000 ...
- About search algorithms and heuristics by José Carlos, CCC, May 26, 2000
- Search algorithms and effeciency by Kim Roper Jensen, CCC, May 30, 2001
- Search algorithms in chess programs by Russell Reagan, CCC, December 12, 2001
- Search algorithms by Renze Steenhuisen, CCC, November 06, 2003
- Game tree search algorithms by Russell Reagan, CCC, January 20, 2004
2005 ...
- Search questions by Sven Schüle, Winboard Forum, July 17, 2007 » Fail-Soft, Principal Variation Search
- Even more search questions by Sven Schüle, Winboard Forum, July 17, 2007 » Root, Iterative Deepening
- Search or Evaluation? by Ed Schröder, Hiarcs Forum, October 05, 2007 » Search versus Evaluation, Evaluation
- Re: Search or Evaluation? by Mark Uniacke, Hiarcs Forum, October 14, 2007
- Efficient algorithm for k-best mode? by Gijsbert Wiesenekker, CCC, November 17, 2007
2010 ...
- Scaling at 2x nodes (or doubling time control). by Kai Laskos, CCC, July 23, 2013 » Doubling TC, Diminishing Returns, Playing Strength, Houdini
- Is search irrelevant when computing ahead of very big trees? by Fermin Serrano, CCC, July 24, 2013 » Knowledge
- Improve the search or the evaluation? by Jens Bæk Nielsen, CCC, August 31, 2013 » Evaluation, Search versus Evaluation
- Slow Searchers? by Michael Neish, CCC, November 02, 2013
- A new algorithm accounting for the uncertainty in eval funcs by Tom Holden, CCC, November 12, 2014
2015 ...
- Search algorithm in it's simplest forum by Mahmoud Uthman, CCC, February 25, 2015 » Alpha-Beta, Quiescence Search
- Time assignment to children by Matthew Lai, CCC, July 26, 2015
- Some musings about search by Ed Schroder, CCC, August 14, 2015 » Automated Tuning
- Search by Laurie Tunnicliffe, CCC, June 24, 2016
- Searching using slow eval with tactical verification by Matthew Lai, CCC, September 06, 2016
- Root search by Laurie Tunnicliffe, CCC, September 08, 2016 » Root
- Doubling of time control by Andreas Strangmüller, CCC, October 21, 2016 » Doubling TC, Diminishing Returns, Playing Strength, Komodo
- search efficiency by Marco Pampaloni, CCC, June 23, 2017
- comparing between search or evaluation by Uri Blass, CCC, October 09, 2017 » Evaluation
2020 ...
- Tactical search by Alvaro Cardoso, CCC, June 13, 2020 » Tactics
- Listening for GUI input when searching by Niels Abildskov, CCC, April 27, 2021 » GUI, Thread, UCI
- On reaching maximum ply by Martin Bryant, CCC, April 29, 2021 » Maximum Search Depth, Ply
- Search by Vincent Diepeveen, CCC, October 26, 2021
- Strategies to unit testing the search by Olexiy Svitashev, CCC, February 03, 2022 » Engine Testing
External Links
- Search algorithm from Wikipedia
- Combinatorial search from Wikipedia
- Depth-first search from Wikipedia
- Boost Graph Library: Depth-First Search
- Best-first search from Wikipedia
- Breadth-first search from Wikipedia
- Dijkstra's algorithm from Wikipedia
- Lambda-search Java-code (version 2.0) by Thomas Thomsen
- Chess Programming Part IV: Basic Search by François-Dominic Laramée, gamedev.net, Ausgust 2000
- Chess Programming Part V: Advanced Search by François-Dominic Laramée, gamedev.net, September 2000
- Engine - Hispanic Chess Engines | The search function by Pedro Castro
- An Introduction to Game Tree Algorithms by Hamed Ahmadi
- Miroslav Vitouš - Infinite Search (1969), YouTube Video
References
- ↑ Schach Bilder Welten - Bernd Besser - Galerie
- ↑ Claude Shannon (1949). Programming a Computer for Playing Chess. pdf
- ↑ 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)
- ↑ Excellent Computer-Chess Overview Paper Found! by Ernst A. Heinz, rgcc, March 6, 1997
- ↑ Great article for people who wants to write a chess engine by Miguel A. Ballicora, CCC, April 03, 2002
- ↑ Re: A new(?) technique to recognize draws by Dan Andersson, June 01, 2002
- ↑ Re: Aquarium IDEA, repetitions, and minimax over cycles by syzygy, OpenChess Forum, September 22, 2012
- ↑ Re: Interesting ideas by Karlo Bala Jr., CCC, September 09, 2015
- ↑ Khet (game) from Wikipedia
- ↑ Information and search in computer chess (Godescu) by BB+, OpenChess Forum, December 12, 2011
- ↑ A new algorithm accounting for the uncertainty in eval funcs by Tom Holden, CCC, November 12, 2014