Game-independent Monte Carlo tree search using UCT. More...

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...
Namespaces
namespace	SgUctTreeUtil
	Utility functions for users of SgUctTree.
Enumerations
enum	SgUctMoveSelect { SG_UCTMOVESELECT_VALUE, SG_UCTMOVESELECT_COUNT, SG_UCTMOVESELECT_BOUND, SG_UCTMOVESELECT_ESTIMATE }
	Move selection strategy after search is finished. More...

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:

$\bar{X}_j + c \sqrt{\frac{\log{n}}{T_j(n)}}$

with:

the move index
$X_{j,\gamma}$ reward for move at sample $\gamma$
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:

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 244 of file SgUctSearch.h.

Monte Carlo tree search

Classes

Namespaces

Enumerations

Detailed Description

Enumeration Type Documentation