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

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:**

enum SgUctMoveSelect |

Move selection strategy after search is finished.

**Enumerator:**

Definition at line 244 of file SgUctSearch.h.

Sun Mar 13 2011 Doxygen 1.7.1