Index   Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

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:

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



See also:


namespace  SgUctTreeUtil
 Utility functions for users of SgUctTree.


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...


 Move selection strategy after search is finished. More...

Enumeration Type Documentation

enum SgUctMoveSelect

Move selection strategy after search is finished.

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