Changes

Jump to: navigation, search

Search

1,438 bytes added, 22:36, 17 May 2023
m
The Search Tree: todo: write DAG article, there was a Lc0 related paper to solve MCTS transpositions via DAG representation
=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] ([[DAG)]].
* [[Search Space]]
* [[Search Tree]]
* [[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
* [[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=
* [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]]
==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=
* [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]]
* [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:Jack DeJohnette|Jack DeJohnette]], [[:Category:John McLaughlin|John McLaughlin]], [[:Category:Herbie Hancock|Herbie Hancock]], [[:Category:Joe Henderson|Joe Henderson]]
422
edits

Navigation menu