Changes

Jump to: navigation, search

Search

826 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/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=
422
edits

Navigation menu