Monte Carlo tree search

---

Detailed Description

Game-independent Monte Carlo tree search using UCT.

The main class SgUctSearch keeps a tree with statistics for each node visited more than a certain number of times, and then continues with random playout (not necessarily uniform random). Within the tree, the move with the highest upper confidence bound is chosen according to the basic UCT formula:

with:

• the move index
• reward for move at sample
• number of times the father node was visited
• number of times the move has been played
• an appropriate constant

References:

• Kocsis, Szepesvari: Bandit based Monte-Carlo Planning
• Auer, Cesa-Bianchi, Fischer: Finite-time Analysis of the Multiarmed Bandit Problem
• Gelly, Wang, Munos, Teytaud: Modification of UCT with patterns in Monte-Carlo Go
• Silver, Gelly: >Combining Online and Offline Knowledge in UCT

See also:

• Lock-free mode in SgUctSearch
• Estimator weights in SgUctSearch
• Proven Nodes in SgUctSearch

Namespaces
namespace	SgUctTreeUtil
	Utility functions for users of SgUctTree.
Classes
struct	SgUctGameInfo
	Game result, sequence and nodes of one Monte-Carlo game in SgUctSearch. More...
class	SgUctThreadState
	Base class for the thread state. More...
class	SgUctThreadStateFactory
	Create game specific thread state. More...
class	SgUctSearch
	Monte Carlo tree search using UCT. More...
class	SgUctNode
	Node used in SgUctTree. More...
class	SgUctAllocator
	Allocater for nodes used in the implementation of SgUctTree. More...
class	SgUctTree
	Tree used in SgUctSearch. More...
class	SgUctChildIterator
	Iterator over all children of a node. More...
class	SgUctTreeIterator
	Iterator for traversing a tree depth-first. More...
class	SgUctTreeStatistics
	Statistical properties of a SgUctTree. More...
Enumerations
enum	SgUctMoveSelect { SG_UCTMOVESELECT_VALUE, SG_UCTMOVESELECT_COUNT, SG_UCTMOVESELECT_BOUND, SG_UCTMOVESELECT_ESTIMATE }
	Move selection strategy after search is finished. More...

---

Enumeration Type Documentation

enum SgUctMoveSelect

Move selection strategy after search is finished.

Enumerator:

SG_UCTMOVESELECT_VALUE	Select move with highest mean value.
SG_UCTMOVESELECT_COUNT	Select move with highest count.
SG_UCTMOVESELECT_BOUND	Use UCT bound (or combined bound if RAVE is enabled).
SG_UCTMOVESELECT_ESTIMATE	Use the weighted sum of UCT and RAVE value (but without bias terms).

Definition at line 261 of file SgUctSearch.h.

---

17 Jun 2010 Doxygen 1.4.7