SmartGame Library: SgUctSearch Class Reference

typedef boost::recursive_mutex::scoped_lock SgUctSearch::GlobalLock [private]

Definition at line 922 of file SgUctSearch.h.

SgUctSearch::SgUctSearch	(	SgUctThreadStateFactory *	threadStateFactory,
		int	moveRange = `0`
	)

Constructor.

Parameters:

	threadStateFactory	The tread state factory (takes ownership). Can be null and set later (before using the search) with SetThreadStateFactory to allow multi-step construction.
	moveRange	Upper integer limit (exclusive) used for move representation. Certain enhancements of SgUctSearch (e.g. Rave()) need to store data in arrays using the move as an index for efficient implementation. If the game does not use a small integer range for its move representation, this parameter should be 0. Then, enhancements that require a small move range cannot be enabled.

Definition at line 206 of file SgUctSearch.cpp.

SgUctSearch::~SgUctSearch ( ) [virtual]

Definition at line 239 of file SgUctSearch.cpp.

References DeleteThreads().

void SgUctSearch::ApplyRootFilter ( std::vector< SgMoveInfo > & moves ) [private]

Definition at line 244 of file SgUctSearch.cpp.

References m_rootFilter.

Referenced by PlayInTree().

float SgUctSearch::BiasTermConstant ( ) const

Constant c in the bias term.

This constant corresponds to 2 C_p in the original UCT paper. The default value is 0.7, which works well in 9x9 Go.

Definition at line 1193 of file SgUctSearch.h.

References m_biasTermConstant.

bool SgUctSearch::CheckAbortSearch ( SgUctThreadState & state ) [private]

Definition at line 261 of file SgUctSearch.cpp.

References CheckCountAbort(), CheckEarlyAbort(), Debug(), GamesPlayed(), SgTimer::GetTime(), m_checkTimeInterval, m_earlyAbort, SgUctSearchStat::m_gamesPerSecond, m_maxGames, m_maxTime, m_moveSelect, m_numberGames, m_statistics, m_timer, m_wasEarlyAbort, SG_UCTMOVESELECT_COUNT, SgUserAbort(), and UpdateCheckTimeInterval().

Referenced by SearchLoop().

bool SgUctSearch::CheckCountAbort	(	SgUctThreadState &	state,
		std::size_t	remainingGames
	)			const `[private]`

Definition at line 327 of file SgUctSearch.cpp.

References FindBestChild(), SgUctThreadState::m_excludeMoves, m_tree, SgUctNode::Move(), SgUctNode::MoveCount(), SgUctTree::Root(), and SG_ASSERT.

Referenced by CheckAbortSearch().

bool SgUctSearch::CheckEarlyAbort ( ) const [private]

Definition at line 346 of file SgUctSearch.cpp.

References SgUctNode::HasMean(), m_earlyAbort, m_tree, SgUctNode::Mean(), SgUctNode::MoveCount(), and SgUctTree::Root().

Referenced by CheckAbortSearch().

void SgUctSearch::CreateChildren	(	SgUctThreadState &	state,
		const SgUctNode &	node,
		bool	deleteChildTrees
	)			`[private]`

Creates the children with the given moves and merges with existing children in the tree.

Definition at line 637 of file SgUctSearch.cpp.

References Debug(), SgUctTree::HasCapacity(), SgUctThreadState::m_isTreeOutOfMem, m_isTreeOutOfMemory, SgUctThreadState::m_moves, SgUctThreadState::m_threadId, m_tree, SgUctTree::MaxNodes(), SgUctTree::MergeChildren(), and SgSynchronizeThreadMemory().

Referenced by PlayInTree().

void SgUctSearch::CreateThreads ( )

Create threads.

The threads are created at the beginning of the first search (to allow multi-step construction with setting the policy after the constructor call). This function needs to be called explicitely only, if a thread state is going to be used before the first search.

Definition at line 355 of file SgUctSearch.cpp.

References SgUctTree::CreateAllocators(), DeleteThreads(), m_maxNodes, m_numberThreads, m_searchLoopFinished, m_threads, m_threadStateFactory, m_tree, SgUctTree::SetMaxNodes(), and Thread.

Referenced by GenerateAllMoves(), SearchOnePly(), SetNumberThreads(), and StartSearch().

void SgUctSearch::Debug	(	const SgUctThreadState &	state,
		const std::string &	textLine
	)			`[private]`

Write a debugging line of text from within a thread.

Prepends the line with the thread number if number of threads is greater than one. Also ensures that the line is written as a single string to avoid intermingling of text lines from different threads.

Parameters:

	state	The state of the thread (only used for state.m_threadId)
	textLine	The line of text without trailing newline character.

Definition at line 378 of file SgUctSearch.cpp.

References m_globalMutex, m_numberThreads, SgUctThreadState::m_threadId, and SgDebug().

Referenced by CheckAbortSearch(), CreateChildren(), and ExpandNode().

void SgUctSearch::DeleteThreads ( ) [private]

Definition at line 391 of file SgUctSearch.cpp.

References m_threads.

Referenced by CreateThreads(), SetThreadStateFactory(), and ~SgUctSearch().

void SgUctSearch::EndSearch ( )

Definition at line 1195 of file SgUctSearch.cpp.

References OnEndSearch().

Referenced by Search().

void SgUctSearch::ExpandNode	(	SgUctThreadState &	state,
		const SgUctNode &	node
	)			`[private]`

Expand a node.

Parameters:

	state	The thread state with state.m_moves already computed.
	node	The node to expand.

Definition at line 400 of file SgUctSearch.cpp.

References SgUctTree::CreateChildren(), Debug(), SgUctTree::HasCapacity(), SgUctThreadState::m_isTreeOutOfMem, m_isTreeOutOfMemory, SgUctThreadState::m_moves, SgUctThreadState::m_threadId, m_tree, SgUctTree::MaxNodes(), and SgSynchronizeThreadMemory().

Referenced by PlayInTree().

std::size_t SgUctSearch::ExpandThreshold ( ) const

Required number of simulations to expand a node in the tree.

The default is 2, which means a node will be expanded on the second visit.

Definition at line 1198 of file SgUctSearch.h.

References m_expandThreshold.

const SgUctNode * SgUctSearch::FindBestChild	(	const SgUctNode &	node,
		const std::vector< SgMove > *	excludeMoves = `0`
	)			const

Find child node with best move.

Parameters:

	node	The father node.
	excludeMoves	Optional list of moves to ignore in the children nodes.

Returns:: The best child or 0 if no child nodes exists.

Definition at line 416 of file SgUctSearch.cpp.

References GetBound(), GetValueEstimate(), SgUctNode::HasChildren(), InverseEval(), m_moveSelect, m_rave, m_tree, SG_ASSERT, SG_UCTMOVESELECT_BOUND, SG_UCTMOVESELECT_COUNT, SG_UCTMOVESELECT_ESTIMATE, and SG_UCTMOVESELECT_VALUE.

Referenced by CheckCountAbort(), FindBestSequence(), and PrintSearchProgress().

void SgUctSearch::FindBestSequence ( std::vector< SgMove > & sequence ) const

Extract sequence of best moves from root node.

Parameters:

[out] sequence The resulting sequence.

Definition at line 472 of file SgUctSearch.cpp.

References FindBestChild(), SgUctNode::HasChildren(), m_tree, SgUctNode::Move(), and SgUctTree::Root().

Referenced by Search().

float SgUctSearch::FirstPlayUrgency ( ) const

First play urgency.

The value for unexplored moves. According to UCT they should always be preferred to moves, that have been played at least once. According to the MoGo tech report, it can be useful to use smaller values (as low as 1) to encorouge early exploitation. Default value is 10000.

See also:: Estimator weights in SgUctSearch

Definition at line 1203 of file SgUctSearch.h.

References m_firstPlayUrgency.

size_t SgUctSearch::GamesPlayed ( ) const [virtual]

Definition at line 256 of file SgUctSearch.cpp.

References m_startRootMoveCount, m_tree, SgUctNode::MoveCount(), and SgUctTree::Root().

Referenced by CheckAbortSearch(), Search(), and UpdateCheckTimeInterval().

void SgUctSearch::GenerateAllMoves ( std::vector< SgMoveInfo > & moves )

Get a list of all generated moves.

Sets up thread state 0 for a seach and calls GenerateAllMoves of the thread state.

Definition at line 487 of file SgUctSearch.cpp.

References CreateThreads(), SgUctThreadState::GenerateAllMoves(), m_threads, OnStartSearch(), SgUctThreadState::StartSearch(), and ThreadState().

float SgUctSearch::GetBound	(	bool	useRave,
		float	logPosCount,
		const SgUctNode &	child
	)			const `[private]`

Definition at line 506 of file SgUctSearch.cpp.

References GetValueEstimate(), GetValueEstimateRave(), m_biasTermConstant, and SgUctNode::MoveCount().

float SgUctSearch::GetBound	(	bool	useRave,
		const SgUctNode &	node,
		const SgUctNode &	child
	)			const

Return the bound of a move.

This is the bound that was used for move selection. It can be the pure UCT bound or the combined bound if RAVE is used.

Parameters:

	useRave	Whether rave should be used or not.
	node	The node corresponding to the position
	child	The node corresponding to the move

Definition at line 499 of file SgUctSearch.cpp.

References Log(), and SgUctNode::PosCount().

Referenced by FindBestChild(), and SelectChild().

SgUctTree & SgUctSearch::GetTempTree ( )

Get temporary tree.

Returns a tree that is compatible in size and number of allocators to the tree of the search. This tree is used by the search itself as a temporary tree for certain operations during the search, but can be used by other code while the search is not running.

Definition at line 525 of file SgUctSearch.cpp.

References SgUctTree::Clear(), SgUctTree::CreateAllocators(), m_tempTree, SgUctTree::MaxNodes(), MaxNodes(), SgUctTree::NuAllocators(), NumberThreads(), and SgUctTree::SetMaxNodes().

Referenced by Search().

float SgUctSearch::GetValueEstimate	(	bool	useRave,
		const SgUctNode &	child
	)			const `[private]`

Definition at line 543 of file SgUctSearch.cpp.

References SgUctNode::HasMean(), SgUctNode::HasRaveValue(), InverseEval(), m_firstPlayUrgency, m_raveWeightParam1, m_raveWeightParam2, SgUctNode::Mean(), SgUctNode::MoveCount(), SgUctNode::RaveCount(), and SgUctNode::RaveValue().

Referenced by FindBestChild(), GetBound(), and GetValueEstimateRave().

float SgUctSearch::GetValueEstimateRave ( const SgUctNode & child ) const [private]

Optimized version of GetValueEstimate() if RAVE and not other estimators are used.

Previously there were more estimators than move value and RAVE value, and in the future there may be again. GetValueEstimate() is easier to extend, this function is more optimized for the special case.

Definition at line 579 of file SgUctSearch.cpp.

References GetValueEstimate(), SgUctNode::HasMean(), SgUctNode::HasRaveValue(), InverseEval(), m_firstPlayUrgency, m_lockFree, m_numberThreads, m_rave, m_raveWeightParam1, m_raveWeightParam2, SgUctNode::Mean(), SgUctNode::MoveCount(), SgUctNode::RaveCount(), SgUctNode::RaveValue(), and SG_ASSERT.

Referenced by GetBound().

float SgUctSearch::InverseEval ( float eval ) [static]

Definition at line 1208 of file SgUctSearch.h.

Referenced by SgUctTreeStatistics::Compute(), FindBestChild(), GetValueEstimate(), GetValueEstimateRave(), PlayGame(), SearchOnePly(), UpdateRaveValues(), and UpdateTree().

std::vector< std::size_t > SgUctSearch::KnowledgeThreshold ( ) const

Points at which to recompute children.

Specifies the number of visits at which GenerateAllMoves() is called again at the node. This is to allow multiple knowledge computations to occur as a node becomes more important. Returned move info will be merged with info in the tree. This is can be used prune, add children, give a bonus to a move, etc.

Definition at line 1331 of file SgUctSearch.h.

References m_knowledgeThreshold.

const SgUctGameInfo & SgUctSearch::LastGameInfo ( ) const

Info for last game.

Returns the last game info of the first thread. This function is not thread-safe.

Definition at line 1218 of file SgUctSearch.h.

References SgUctThreadState::m_gameInfo, and ThreadState().

Referenced by LastGameSummaryLine().

string SgUctSearch::LastGameSummaryLine ( ) const

One-line summary text for last game.

Contains: move, count and mean for all nodes; result Returns the last game info of the first thread. This function is not thread-safe.

Definition at line 617 of file SgUctSearch.cpp.

References LastGameInfo(), and SummaryLine().

bool SgUctSearch::LockFree ( ) const

Lock-free usage of multi-threaded search.

Lock-free mode in SgUctSearch

Definition at line 1213 of file SgUctSearch.h.

References m_lockFree.

float SgUctSearch::Log ( float x ) const [private]

Definition at line 622 of file SgUctSearch.cpp.

References SgFastLog::Log(), and m_fastLog.

Referenced by GetBound(), and SelectChild().

bool SgUctSearch::LogGames ( ) const

Log one-line summary for each game during Search() to a file.

Todo:: File name still is hard-coded to "uctsearch.log"

Definition at line 1223 of file SgUctSearch.h.

References m_logGames.

std::size_t SgUctSearch::MaxGameLength ( ) const

Maximum game length.

If the number of moves in a game exceed this length, it will be counted as a loss. The default is numeric_limits<size_t>::max()

Definition at line 1228 of file SgUctSearch.h.

References m_maxGameLength.

std::size_t SgUctSearch::MaxNodes ( ) const

Maximum number of nodes in the tree.

Note:: The search owns two trees, one of which is used as a temporary tree for some operations (see GetTempTree()). This functions sets the maximum number of nodes per tree.

Definition at line 1233 of file SgUctSearch.h.

References m_maxNodes.

Referenced by GetTempTree().

SgUctMoveSelect SgUctSearch::MoveSelect ( ) const

See SgUctMoveSelect.

Definition at line 1238 of file SgUctSearch.h.

References m_moveSelect.

virtual std::string SgUctSearch::MoveString ( SgMove move ) const [pure virtual]

Convert move to string (game dependent).

This function needs to be thread-safe.

Referenced by SummaryLine().

const SgMpiSynchronizerHandle SgUctSearch::MpiSynchronizer ( ) const

Definition at line 1369 of file SgUctSearch.h.

References m_mpiSynchronizer.

SgMpiSynchronizerHandle SgUctSearch::MpiSynchronizer ( )

Definition at line 1364 of file SgUctSearch.h.

References m_mpiSynchronizer.

bool SgUctSearch::NeedToComputeKnowledge ( const SgUctNode * current ) [private]

Definition at line 654 of file SgUctSearch.cpp.

References SgUctNode::KnowledgeCount(), m_knowledgeThreshold, SgUctNode::MoveCount(), and SG_ASSERT.

Referenced by PlayInTree().

std::size_t SgUctSearch::NumberPlayouts ( ) const

The number of playouts per simulated game.

Useful for multi-threading to increase the workload of the threads. Default is 1.

Definition at line 1248 of file SgUctSearch.h.

References m_numberPlayouts.

std::size_t SgUctSearch::NumberThreads ( ) const

The number of threads to use during the search.

Definition at line 1243 of file SgUctSearch.h.

References m_numberThreads.

Referenced by GetTempTree(), and SearchLoop().

void SgUctSearch::OnEndSearch ( ) [virtual]

Hook function that will be called when search completes.

Default implementation calls m_mpiSynchronizer.EndSearch(). This function does not need to be thread-safe.

Definition at line 684 of file SgUctSearch.cpp.

References m_mpiSynchronizer.

Referenced by EndSearch().

void SgUctSearch::OnSearchIteration	(	std::size_t	gameNumber,
		int	threadId,
		const SgUctGameInfo &	info
	)			`[virtual]`

Hook function that will be called by Search() after each game.

Default implementation does nothing. This function does not need to be thread-safe.

Parameters:

	gameNumber	The number of this iteration.
	threadId
	info	The game info of the thread which played this iteration.

Warning:: If LockFree() is enabled, this function will be called from multiple threads without locking. The subclass should handle this case appropriately by using its own lock or disabling functionality that will not work without locking.

Definition at line 717 of file SgUctSearch.cpp.

References SgTimer::GetTime(), m_lastScoreDisplayTime, m_mpiSynchronizer, m_timer, and PrintSearchProgress().

Referenced by SearchLoop(), and SearchOnePly().

void SgUctSearch::OnStartSearch ( ) [virtual]

Hook function that will be called by StartSearch().

Default implementation calls m_mpiSynchronizer.StartSearch(). This function does not need to be thread-safe.

Definition at line 679 of file SgUctSearch.cpp.

References m_mpiSynchronizer.

Referenced by GenerateAllMoves(), SearchOnePly(), and StartSearch().

void SgUctSearch::OnThreadEndSearch ( SgUctThreadState & state ) [virtual]

Definition at line 1034 of file SgUctSearch.cpp.

References m_mpiSynchronizer.

Referenced by SearchLoop().

void SgUctSearch::OnThreadStartSearch ( SgUctThreadState & state ) [virtual]

Definition at line 1029 of file SgUctSearch.cpp.

References m_mpiSynchronizer.

Referenced by SearchLoop().

void SgUctSearch::PlayGame	(	SgUctThreadState &	state,
		GlobalLock *	lock
	)			`[private]`

void SgUctSearch::PlayGame ( )

Play a single game.

Plays a single game using the thread state of the first thread. Call StartSearch() before calling this function.

Definition at line 1253 of file SgUctSearch.h.

References ThreadState().

Referenced by SearchLoop().

bool SgUctSearch::PlayInTree	(	SgUctThreadState &	state,
		bool &	isTerminal
	)			`[private]`

Play game until it leaves the tree.

Parameters:

	state
`[out]`	isTerminal	Was the sequence terminated because of a real terminal position (GenerateAllMoves() returned an empty list)?

Returns:: false, if game was aborted due to maximum length

Definition at line 814 of file SgUctSearch.cpp.

References ApplyRootFilter(), CreateChildren(), SgUctThreadState::Execute(), ExpandNode(), SgUctThreadState::GenerateAllMoves(), SgUctNode::HasChildren(), SgUctNode::IsProven(), SgUctNode::KnowledgeCount(), m_expandThreshold, SgUctThreadState::m_gameInfo, SgUctGameInfo::m_inTreeSequence, SgUctThreadState::m_isTreeOutOfMem, SgUctSearchStat::m_knowledge, m_maxGameLength, SgUctThreadState::m_moves, SgUctGameInfo::m_nodes, SgUctThreadState::m_randomizeCounter, m_statistics, m_tree, SgUctNode::Move(), SgUctNode::MoveCount(), NeedToComputeKnowledge(), SgUctTree::Root(), SelectChild(), SgUctNode::SetProvenNodeType(), and SG_NOT_PROVEN.

Referenced by PlayGame().

bool SgUctSearch::PlayoutGame	(	SgUctThreadState &	state,
		std::size_t	playout
	)			`[private]`

Finish the game using GeneratePlayoutMove().

Parameters:

	state	The thread state.
	playout	The number of the playout.

Returns:: false if game was aborted

Definition at line 905 of file SgUctSearch.cpp.

References SgUctThreadState::ExecutePlayout(), SgUctThreadState::GeneratePlayoutMove(), SgUctThreadState::m_gameInfo, m_maxGameLength, SgUctGameInfo::m_sequence, SgUctGameInfo::m_skipRaveUpdate, and SG_NULLMOVE.

Referenced by PlayGame(), and SearchOnePly().

void SgUctSearch::PrintSearchProgress ( double currTime ) const [private]

Print time, mean, nodes searched, and PV.

Definition at line 690 of file SgUctSearch.cpp.

References FindBestChild(), SgTime::Format(), SgUctNode::HasChildren(), m_tree, SgUctNode::Mean(), SgUctNode::Move(), SgUctNode::MoveCount(), SgUctTree::Root(), and SgDebug().

Referenced by OnSearchIteration().

bool SgUctSearch::PruneFullTree ( ) const

Prune nodes with low counts if tree is full.

This will prune nodes below a minimum count, if the tree gets full during a search. The minimum count is PruneMinCount() at the beginning of the search and is doubled every time a pruning operation does not reduce the tree by at least a factor of 2. The creation of the pruned tree uses the temporary tree (see GetTempTree()).

Definition at line 1258 of file SgUctSearch.h.

References m_pruneFullTree.

std::size_t SgUctSearch::PruneMinCount ( ) const

See PruneFullTree().

Definition at line 1263 of file SgUctSearch.h.

References m_pruneMinCount.

int SgUctSearch::RandomizeRaveFrequency ( ) const

See SetRandomizeRaveFrequency().

Definition at line 1374 of file SgUctSearch.h.

References m_randomizeRaveFrequency.

bool SgUctSearch::Rave ( ) const

Use the RAVE algorithm (Rapid Action Value Estimation).

See Gelly, Silver 2007 in the references in the class description. In difference to the original description of the RAVE algorithm, no "RAVE bias term" is used. The estimated value of a move is the weighted mean of the move value and the RAVE value and then a single UCT-like bias term is added.

See also:: RaveWeightFunc

Definition at line 1268 of file SgUctSearch.h.

References m_rave.

bool SgUctSearch::RaveCheckSame ( ) const

Don't update RAVE value if opponent played the same move first.

Default is false (since it depends on the game and move representation, if it should be used).

Definition at line 1273 of file SgUctSearch.h.

References m_raveCheckSame.

float SgUctSearch::RaveWeightFinal ( ) const

See Estimator weights in SgUctSearch.

Definition at line 1283 of file SgUctSearch.h.

References m_raveWeightFinal.

float SgUctSearch::RaveWeightInitial ( ) const

See Estimator weights in SgUctSearch.

Definition at line 1278 of file SgUctSearch.h.

References m_raveWeightInitial.

float SgUctSearch::Search	(	std::size_t	maxGames,
		double	maxTime,
		std::vector< SgMove > &	sequence,
		const std::vector< SgMove > &	rootFilter = `std::vector< SgMove >()`,
		SgUctTree *	initTree = `0`,
		SgUctEarlyAbortParam *	earlyAbort = `0`
	)

Calls StartSearch() and then maxGames times PlayGame().

Parameters:

	maxGames	The maximum number of games (greater or equal one).
	maxTime	The maximum time in seconds.
`[out]`	sequence	The move sequence with the best value.
	rootFilter	Moves to filter at the root node
	initTree	The tree to initialize the search with. 0 for no initialization. The trees are actually swapped, not copied.
	earlyAbort	See SgUctEarlyAbortParam. Null means not to do an early abort.

Returns:: The value of the root position.

Definition at line 925 of file SgUctSearch.cpp.

References SgUctTree::CopyPruneLowCount(), EndSearch(), FindBestSequence(), GamesPlayed(), GetTempTree(), SgTimer::GetTime(), m_aborted, m_earlyAbort, SgUctSearchStat::m_gamesPerSecond, m_isTreeOutOfMemory, m_log, m_logFileName, m_logGames, m_maxGames, m_maxTime, m_mpiSynchronizer, m_pruneFullTree, m_pruneMinCount, m_rootFilter, m_statistics, m_threads, SgUctSearchStat::m_time, m_timer, m_tree, SgUctNode::Mean(), SgUctNode::MoveCount(), SgUctTree::NuNodes(), SgUctTree::Root(), SgDebug(), SgSynchronizeThreadMemory(), SgTimer::Start(), StartSearch(), and SgUctTree::Swap().

void SgUctSearch::SearchLoop	(	SgUctThreadState &	state,
		GlobalLock *	lock
	)			`[private]`

Loop invoked by each thread for playing games.

Definition at line 991 of file SgUctSearch.cpp.

References CheckAbortSearch(), m_aborted, SgUctThreadState::m_gameInfo, SgUctThreadState::m_isSearchInitialized, SgUctThreadState::m_isTreeOutOfMem, m_isTreeOutOfMemory, m_lockFree, m_log, m_logGames, m_numberGames, m_pruneFullTree, m_searchLoopFinished, SgUctThreadState::m_threadId, NumberThreads(), OnSearchIteration(), OnThreadEndSearch(), OnThreadStartSearch(), PlayGame(), SgSynchronizeThreadMemory(), and SummaryLine().

Referenced by SgUctSearch::Thread::operator()().

SgPoint SgUctSearch::SearchOnePly	(	size_t	maxGames,
		double	maxTime,
		float &	value
	)

Do a one-ply Monte-Carlo search instead of the UCT search.

Parameters:

	maxGames
	maxTime
`[out]`	value	The value of the best move

Definition at line 1039 of file SgUctSearch.cpp.

const SgUctNode & SgUctSearch::SelectChild	(	int &	randomizeCounter,
		const SgUctNode &	node
	)			`[private]`

Definition at line 1099 of file SgUctSearch.cpp.

References GetBound(), SgUctNode::HasChildren(), Log(), m_randomizeRaveFrequency, m_rave, m_tree, SgUctNode::PosCount(), and SG_ASSERT.

Referenced by PlayInTree().

void SgUctSearch::SetBiasTermConstant ( float biasTermConstant )

See BiasTermConstant().

Definition at line 1288 of file SgUctSearch.h.

References m_biasTermConstant.

void SgUctSearch::SetExpandThreshold ( std::size_t expandThreshold )

See ExpandThreshold().

Definition at line 1293 of file SgUctSearch.h.

References m_expandThreshold, and SG_ASSERT.

void SgUctSearch::SetFirstPlayUrgency ( float firstPlayUrgency )

See FirstPlayUrgency().

Definition at line 1299 of file SgUctSearch.h.

References m_firstPlayUrgency.

void SgUctSearch::SetKnowledgeThreshold ( const std::vector< std::size_t > & counts )

See KnowledgeThreshold().

Definition at line 1337 of file SgUctSearch.h.

References m_knowledgeThreshold.

void SgUctSearch::SetLockFree ( bool enable )

See LockFree().

Definition at line 1304 of file SgUctSearch.h.

References m_lockFree.

void SgUctSearch::SetLogGames ( bool enable )

See LogGames().

Definition at line 1309 of file SgUctSearch.h.

References m_logGames.

void SgUctSearch::SetMaxGameLength ( std::size_t maxGameLength )

See MaxGameLength().

Definition at line 1314 of file SgUctSearch.h.

References m_maxGameLength.

void SgUctSearch::SetMaxNodes ( std::size_t maxNodes )

See MaxNodes().

Parameters:

maxNodes

Maximum number of nodes (>= 1)

Definition at line 1319 of file SgUctSearch.h.

References m_maxNodes, m_threads, m_tree, and SgUctTree::SetMaxNodes().

void SgUctSearch::SetMoveSelect ( SgUctMoveSelect moveSelect )

See SgUctMoveSelect.

Definition at line 1326 of file SgUctSearch.h.

References m_moveSelect.

void SgUctSearch::SetMpiSynchronizer ( const SgMpiSynchronizerHandle & synchronizerHandle )

Definition at line 1358 of file SgUctSearch.h.

References m_mpiSynchronizer.

void SgUctSearch::SetNumberPlayouts ( std::size_t n )

Definition at line 1342 of file SgUctSearch.h.

References m_numberPlayouts, and SG_ASSERT.

void SgUctSearch::SetNumberThreads ( std::size_t n )

See SetNumberThreads().

Definition at line 1131 of file SgUctSearch.cpp.

References CreateThreads(), m_numberThreads, and SG_ASSERT.

void SgUctSearch::SetPruneFullTree ( bool enable )

See PruneFullTree().

Definition at line 1348 of file SgUctSearch.h.

References m_pruneFullTree.

void SgUctSearch::SetPruneMinCount ( std::size_t n )

See PruneFullTree().

Definition at line 1353 of file SgUctSearch.h.

References m_pruneMinCount.

void SgUctSearch::SetRandomizeRaveFrequency ( int frequency )

Randomly turns off rave with given frequency - once in every frequency child selections.

Helps in rare cases where rave ignores the best move. Set frequency to 0 to switch it off.

Definition at line 1379 of file SgUctSearch.h.

References m_randomizeRaveFrequency.

void SgUctSearch::SetRave ( bool enable )

See Rave().

Definition at line 1140 of file SgUctSearch.cpp.

References m_moveRange, and m_rave.

void SgUctSearch::SetRaveCheckSame ( bool enable )

See RaveCheckSame().

Definition at line 1384 of file SgUctSearch.h.

References m_raveCheckSame.

void SgUctSearch::SetRaveWeightFinal ( float value )

See Estimator weights in SgUctSearch.

Definition at line 1389 of file SgUctSearch.h.

References m_raveWeightFinal.

void SgUctSearch::SetRaveWeightInitial ( float value )

See Estimator weights in SgUctSearch.

Definition at line 1394 of file SgUctSearch.h.

References m_raveWeightInitial.

void SgUctSearch::SetThreadStateFactory ( SgUctThreadStateFactory * factory )

Definition at line 1147 of file SgUctSearch.cpp.

References DeleteThreads(), m_threadStateFactory, and SG_ASSERT.

void SgUctSearch::SetVirtualLoss ( bool enable )

See VirtualLoss().

Definition at line 1409 of file SgUctSearch.h.

References m_virtualLoss.

void SgUctSearch::SetWeightRaveUpdates ( bool enable )

See WeightRaveUpdates().

Definition at line 1399 of file SgUctSearch.h.

References m_weightRaveUpdates.

void SgUctSearch::StartSearch	(	const std::vector< SgMove > &	rootFilter = `std::vector< SgMove >()`,
		SgUctTree *	initTree = `0`
	)

Start search.

Initializes search for current position and clears statistics.

Parameters:

	rootFilter	Moves to filter at the root node
	initTree	The tree to initialize the search with. 0 for no initialization. The trees are actually swapped, not copied.

Definition at line 1157 of file SgUctSearch.cpp.

References SgUctTree::ApplyFilter(), SgUctSearchStat::Clear(), SgUctTree::Clear(), CreateThreads(), SgTime::DefaultMode(), SgTimer::GetTime(), SgUctTree::HasCapacity(), m_aborted, m_checkTimeInterval, m_lastScoreDisplayTime, m_numberGames, m_numberThreads, m_raveWeightFinal, m_raveWeightInitial, m_raveWeightParam1, m_raveWeightParam2, m_startRootMoveCount, m_statistics, m_threads, m_timer, m_tree, m_wasEarlyAbort, SgUctNode::MoveCount(), SgUctNode::NuChildren(), OnStartSearch(), SgUctTree::Root(), SG_TIME_CPU, SgWarning(), SgUctThreadState::StartSearch(), SgUctTree::Swap(), and ThreadState().

Referenced by Search().

const SgUctSearchStat & SgUctSearch::Statistics ( ) const

Definition at line 1414 of file SgUctSearch.h.

References m_statistics.

string SgUctSearch::SummaryLine ( const SgUctGameInfo & info ) const [private]

Definition at line 1200 of file SgUctSearch.cpp.

References SgUctGameInfo::m_eval, SgUctGameInfo::m_nodes, and MoveString().

Referenced by LastGameSummaryLine(), and SearchLoop().

bool SgUctSearch::ThreadsCreated ( ) const

Check if threads are already created.

The threads are created at the beginning of the first search (to allow multi-step construction with setting the policy after the constructor call).

Definition at line 1419 of file SgUctSearch.h.

References m_threads.

SgUctThreadState & SgUctSearch::ThreadState ( int i ) const

Get state of one of the threads.

Requires: ThreadsCreated()

Definition at line 1424 of file SgUctSearch.h.

References m_threads, and SG_ASSERT.

Referenced by GenerateAllMoves(), LastGameInfo(), PlayGame(), SearchOnePly(), and StartSearch().

const SgUctTree & SgUctSearch::Tree ( ) const

Definition at line 1430 of file SgUctSearch.h.

References m_tree.

virtual float SgUctSearch::UnknownEval ( ) const [pure virtual]

Evaluation value to use if evaluation is unknown.

This value will be used, if games are aborted, because they exceed the maximum game length. This function needs to be thread-safe.

Referenced by PlayGame(), and SearchOnePly().

void SgUctSearch::UpdateCheckTimeInterval ( double time ) [private]

Definition at line 1216 of file SgUctSearch.cpp.

References GamesPlayed(), m_checkTimeInterval, SgUctSearchStat::m_gamesPerSecond, m_maxTime, m_numberThreads, and m_statistics.

Referenced by CheckAbortSearch().

void SgUctSearch::UpdateDynRaveBias ( ) [private]

void SgUctSearch::UpdateRaveValues	(	SgUctThreadState &	state,
		std::size_t	playout,
		float	eval,
		std::size_t	i,
		const std::size_t	firstPlay[],
		const std::size_t	firstPlayOpp[]
	)			`[private]`

Definition at line 1309 of file SgUctSearch.cpp.

References SgUctTree::AddRaveValue(), SgUtil::InRange(), SgUctThreadState::m_gameInfo, SgUctGameInfo::m_nodes, m_raveCheckSame, SgUctGameInfo::m_sequence, m_tree, m_weightRaveUpdates, and SG_ASSERT.

void SgUctSearch::UpdateRaveValues	(	SgUctThreadState &	state,
		std::size_t	playout
	)			`[private]`

Definition at line 1248 of file SgUctSearch.cpp.

References InverseEval(), SgUctGameInfo::m_eval, SgUctThreadState::m_firstPlay, SgUctThreadState::m_firstPlayOpp, SgUctThreadState::m_gameInfo, SgUctGameInfo::m_inTreeSequence, m_moveRange, SgUctGameInfo::m_nodes, SgUctGameInfo::m_sequence, SgUctGameInfo::m_skipRaveUpdate, SG_ASSERT, and UpdateRaveValues().

void SgUctSearch::UpdateRaveValues ( SgUctThreadState & state ) [private]

Update the RAVE values in the tree for both players after a game was played.

See also:: SgUctSearch::Rave()

Definition at line 1242 of file SgUctSearch.cpp.

References m_numberPlayouts.

Referenced by PlayGame(), and UpdateRaveValues().

void SgUctSearch::UpdateStatistics ( const SgUctGameInfo & info ) [private]

Definition at line 1339 of file SgUctSearch.cpp.

References SgStatistics< VALUE, COUNT >::Add(), SgStatisticsExt< VALUE, COUNT >::Add(), SgUctGameInfo::m_aborted, SgUctSearchStat::m_aborted, SgUctSearchStat::m_gameLength, SgUctGameInfo::m_inTreeSequence, SgUctSearchStat::m_movesInTree, m_numberPlayouts, SgUctGameInfo::m_sequence, and m_statistics.

Referenced by PlayGame().

void SgUctSearch::UpdateTree ( const SgUctGameInfo & info ) [private]

Definition at line 1351 of file SgUctSearch.cpp.

References SgUctTree::AddGameResults(), InverseEval(), SgUctGameInfo::m_eval, SgUctGameInfo::m_nodes, m_numberPlayouts, and m_tree.

Referenced by PlayGame().

bool SgUctSearch::VirtualLoss ( ) const

Whether search uses virtual loss.

Definition at line 1404 of file SgUctSearch.h.

References m_virtualLoss.

bool SgUctSearch::WasEarlyAbort ( ) const

See parameter earlyAbort in Search().

Definition at line 1435 of file SgUctSearch.h.

References m_wasEarlyAbort.

bool SgUctSearch::WeightRaveUpdates ( ) const

Weight RAVE updates.

Gives more weight to moves that are closer to the position for which the RAVE statistics are stored. The weighting function is linearly decreasing from 2 to 0 with the move number from the position for which the RAVE statistics are stored to the end of the simulated game.

Definition at line 1440 of file SgUctSearch.h.

References m_weightRaveUpdates.

void SgUctSearch::WriteStatistics ( std::ostream & out ) const

Definition at line 1368 of file SgUctSearch.cpp.

References SgUctSearchStat::m_knowledge, m_knowledgeThreshold, m_mpiSynchronizer, m_statistics, m_tree, SgUctNode::MoveCount(), SgUctTree::NuNodes(), SgUctTree::Root(), and SgUctSearchStat::Write().

friend class Thread [friend]

Definition at line 924 of file SgUctSearch.h.

Referenced by CreateThreads().

volatile bool SgUctSearch::m_aborted [private]

Flag indicating that the search was terminated because the maximum time or number of games was reached.

Definition at line 1000 of file SgUctSearch.h.

Referenced by Search(), SearchLoop(), and StartSearch().

float SgUctSearch::m_biasTermConstant [private]

See BiasTermConstant().

Definition at line 1073 of file SgUctSearch.h.

Referenced by BiasTermConstant(), GetBound(), and SetBiasTermConstant().

std::size_t SgUctSearch::m_checkTimeInterval [private]

Interval in number of games in which to check time abort.

Avoids that the potentially expensive SgTime::Get() is called after every game. The interval is updated dynamically according to the current games/sec, such that it is called ten times per second (if the total search time is at least one second, otherwise ten times per total maximum search time)

Definition at line 1068 of file SgUctSearch.h.

Referenced by CheckAbortSearch(), StartSearch(), and UpdateCheckTimeInterval().

std::auto_ptr<SgUctEarlyAbortParam> SgUctSearch::m_earlyAbort [private]

See SgUctEarlyAbortParam.

The auto pointer is empty, if no early abort is used.

Definition at line 1012 of file SgUctSearch.h.

Referenced by CheckAbortSearch(), CheckEarlyAbort(), and Search().

std::size_t SgUctSearch::m_expandThreshold [private]

See ExpandThreshold().

Definition at line 1051 of file SgUctSearch.h.

Referenced by ExpandThreshold(), PlayInTree(), and SetExpandThreshold().

SgFastLog SgUctSearch::m_fastLog [private]

Definition at line 1126 of file SgUctSearch.h.

Referenced by Log().

float SgUctSearch::m_firstPlayUrgency [private]

See FirstPlayUrgency().

Definition at line 1076 of file SgUctSearch.h.

Referenced by FirstPlayUrgency(), GetValueEstimate(), GetValueEstimateRave(), and SetFirstPlayUrgency().

boost::recursive_mutex SgUctSearch::m_globalMutex [private]

Mutex for protecting global variables during multi-threading.

Currently, only the play-out phase of games is thread safe, therefore this lock is always locked elsewhere (in-tree phase, updating of values and statistics, etc.)

Definition at line 1115 of file SgUctSearch.h.

Referenced by Debug().

volatile bool SgUctSearch::m_isTreeOutOfMemory [private]

Definition at line 1002 of file SgUctSearch.h.

Referenced by CreateChildren(), ExpandNode(), Search(), and SearchLoop().

std::vector<std::size_t> SgUctSearch::m_knowledgeThreshold [private]

See KnowledgeThreshold().

Definition at line 995 of file SgUctSearch.h.

Referenced by KnowledgeThreshold(), NeedToComputeKnowledge(), SetKnowledgeThreshold(), and WriteStatistics().

double SgUctSearch::m_lastScoreDisplayTime [private]

Definition at line 1070 of file SgUctSearch.h.

Referenced by OnSearchIteration(), and StartSearch().

bool SgUctSearch::m_lockFree [private]

See LockFree().

Definition at line 1024 of file SgUctSearch.h.

Referenced by GetValueEstimateRave(), LockFree(), SearchLoop(), and SetLockFree().

std::ofstream SgUctSearch::m_log [private]

Definition at line 1108 of file SgUctSearch.h.

Referenced by Search(), and SearchLoop().

std::string SgUctSearch::m_logFileName [private]

Definition at line 1096 of file SgUctSearch.h.

Referenced by Search().

bool SgUctSearch::m_logGames [private]

See LogGames().

Definition at line 989 of file SgUctSearch.h.

Referenced by LogGames(), Search(), SearchLoop(), and SetLogGames().

std::size_t SgUctSearch::m_maxGameLength [private]

See MaxGameLength().

Definition at line 1048 of file SgUctSearch.h.

Referenced by MaxGameLength(), PlayInTree(), PlayoutGame(), and SetMaxGameLength().

std::size_t SgUctSearch::m_maxGames [private]

Number of games limit for the current search.

Definition at line 1054 of file SgUctSearch.h.

Referenced by CheckAbortSearch(), and Search().

std::size_t SgUctSearch::m_maxNodes [private]

See MaxNodes().

Definition at line 1039 of file SgUctSearch.h.

Referenced by CreateThreads(), MaxNodes(), and SetMaxNodes().

double SgUctSearch::m_maxTime [private]

Time limit for current search.

Definition at line 1091 of file SgUctSearch.h.

Referenced by CheckAbortSearch(), Search(), and UpdateCheckTimeInterval().

const int SgUctSearch::m_moveRange [private]

See parameter moveRange in constructor.

Definition at line 1045 of file SgUctSearch.h.

Referenced by SetRave(), and UpdateRaveValues().

SgUctMoveSelect SgUctSearch::m_moveSelect [private]

See SgUctMoveSelect.

Definition at line 1015 of file SgUctSearch.h.

Referenced by CheckAbortSearch(), FindBestChild(), MoveSelect(), and SetMoveSelect().

boost::shared_ptr<SgMpiSynchronizer> SgUctSearch::m_mpiSynchronizer [private]

Definition at line 1129 of file SgUctSearch.h.

Referenced by MpiSynchronizer(), OnEndSearch(), OnSearchIteration(), OnStartSearch(), OnThreadEndSearch(), OnThreadStartSearch(), Search(), SetMpiSynchronizer(), and WriteStatistics().

std::size_t SgUctSearch::m_numberGames [private]

Number of games played in the current search.

Definition at line 1057 of file SgUctSearch.h.

Referenced by CheckAbortSearch(), SearchLoop(), and StartSearch().

std::size_t SgUctSearch::m_numberPlayouts [private]

See NumberPlayouts().

Definition at line 1036 of file SgUctSearch.h.

Referenced by NumberPlayouts(), PlayGame(), SetNumberPlayouts(), UpdateRaveValues(), UpdateStatistics(), and UpdateTree().

std::size_t SgUctSearch::m_numberThreads [private]

See NumberThreads().

Definition at line 1033 of file SgUctSearch.h.

Referenced by CreateThreads(), Debug(), GetValueEstimateRave(), NumberThreads(), SetNumberThreads(), StartSearch(), and UpdateCheckTimeInterval().

bool SgUctSearch::m_pruneFullTree [private]

See PruneFullTree().

Definition at line 1030 of file SgUctSearch.h.

Referenced by PruneFullTree(), Search(), SearchLoop(), and SetPruneFullTree().

std::size_t SgUctSearch::m_pruneMinCount [private]

See PruneMinCount().

Definition at line 1042 of file SgUctSearch.h.

Referenced by PruneMinCount(), Search(), and SetPruneMinCount().

int SgUctSearch::m_randomizeRaveFrequency [private]

See SetRandomizeRaveFrequency().

Definition at line 1021 of file SgUctSearch.h.

Referenced by RandomizeRaveFrequency(), SelectChild(), and SetRandomizeRaveFrequency().

bool SgUctSearch::m_rave [private]

See Rave().

Definition at line 992 of file SgUctSearch.h.

Referenced by FindBestChild(), GetValueEstimateRave(), PlayGame(), Rave(), SelectChild(), and SetRave().

bool SgUctSearch::m_raveCheckSame [private]

See RaveCheckSame().

Definition at line 1018 of file SgUctSearch.h.

Referenced by RaveCheckSame(), SetRaveCheckSame(), and UpdateRaveValues().

float SgUctSearch::m_raveWeightFinal [private]

See Estimator weights in SgUctSearch.

Definition at line 1082 of file SgUctSearch.h.

Referenced by RaveWeightFinal(), SetRaveWeightFinal(), and StartSearch().

float SgUctSearch::m_raveWeightInitial [private]

See Estimator weights in SgUctSearch.

Definition at line 1079 of file SgUctSearch.h.

Referenced by RaveWeightInitial(), SetRaveWeightInitial(), and StartSearch().

double SgUctSearch::m_raveWeightParam1 [private]

1 / m_raveWeightInitial precomputed for efficiency

Definition at line 1085 of file SgUctSearch.h.

Referenced by GetValueEstimate(), GetValueEstimateRave(), and StartSearch().

double SgUctSearch::m_raveWeightParam2 [private]

m_raveWeightInitial / m_raveWeightFinal precomputed for efficiency

Definition at line 1088 of file SgUctSearch.h.

Referenced by GetValueEstimate(), GetValueEstimateRave(), and StartSearch().

std::vector<SgMove> SgUctSearch::m_rootFilter [private]

See parameter rootFilter in function Search().

Definition at line 1106 of file SgUctSearch.h.

Referenced by ApplyRootFilter(), and Search().

std::auto_ptr<boost::barrier> SgUctSearch::m_searchLoopFinished [private]

Definition at line 1004 of file SgUctSearch.h.

Referenced by CreateThreads(), and SearchLoop().

std::size_t SgUctSearch::m_startRootMoveCount [private]

Definition at line 1059 of file SgUctSearch.h.

Referenced by GamesPlayed(), and StartSearch().

SgUctSearchStat SgUctSearch::m_statistics [private]

Definition at line 1117 of file SgUctSearch.h.

Referenced by CheckAbortSearch(), PlayInTree(), Search(), StartSearch(), Statistics(), UpdateCheckTimeInterval(), UpdateStatistics(), and WriteStatistics().

SgUctTree SgUctSearch::m_tempTree [private]

See GetTempTree().

Definition at line 1103 of file SgUctSearch.h.

Referenced by GetTempTree().

std::vector<boost::shared_ptr<Thread> > SgUctSearch::m_threads [private]

List of threads.

The elements are owned by the vector (shared_ptr is only used because auto_ptr should not be used with standard containers)

Definition at line 1123 of file SgUctSearch.h.

Referenced by CreateThreads(), DeleteThreads(), GenerateAllMoves(), Search(), SearchOnePly(), SetMaxNodes(), StartSearch(), ThreadsCreated(), and ThreadState().

std::auto_ptr<SgUctThreadStateFactory> SgUctSearch::m_threadStateFactory [private]

Definition at line 986 of file SgUctSearch.h.

Referenced by CreateThreads(), and SetThreadStateFactory().

SgTimer SgUctSearch::m_timer [private]

Definition at line 1098 of file SgUctSearch.h.

Referenced by CheckAbortSearch(), OnSearchIteration(), Search(), SearchOnePly(), and StartSearch().

SgUctTree SgUctSearch::m_tree [private]

Definition at line 1100 of file SgUctSearch.h.

Referenced by CheckCountAbort(), CheckEarlyAbort(), CreateChildren(), CreateThreads(), ExpandNode(), FindBestChild(), FindBestSequence(), GamesPlayed(), PlayGame(), PlayInTree(), PrintSearchProgress(), Search(), SelectChild(), SetMaxNodes(), StartSearch(), Tree(), UpdateRaveValues(), UpdateTree(), and WriteStatistics().

bool SgUctSearch::m_virtualLoss [private]

See VirtualLoss().

Definition at line 1094 of file SgUctSearch.h.

Referenced by PlayGame(), SetVirtualLoss(), and VirtualLoss().

bool SgUctSearch::m_wasEarlyAbort [private]

See SgUctEarlyAbortParam.

Definition at line 1007 of file SgUctSearch.h.

Referenced by CheckAbortSearch(), StartSearch(), and WasEarlyAbort().

bool SgUctSearch::m_weightRaveUpdates [private]

See WeightRaveUpdates().

Definition at line 1027 of file SgUctSearch.h.

Referenced by SetWeightRaveUpdates(), UpdateRaveValues(), and WeightRaveUpdates().

SgUctSearch Class Reference
[Monte Carlo tree search]

Detailed Description

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Classes

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation


Public Member Functions
	SgUctSearch (SgUctThreadStateFactory *threadStateFactory, int moveRange=0)
	Constructor.
virtual	~SgUctSearch ()
void	SetThreadStateFactory (SgUctThreadStateFactory *factory)
SgUctThreadState &	ThreadState (int i) const
	Get state of one of the threads.
bool	ThreadsCreated () const
	Check if threads are already created.
void	CreateThreads ()
	Create threads.
Pure virtual functions
virtual std::string	MoveString (SgMove move) const =0
	Convert move to string (game dependent).
virtual float	UnknownEval () const =0
	Evaluation value to use if evaluation is unknown.
Virtual functions
virtual void	OnSearchIteration (std::size_t gameNumber, int threadId, const SgUctGameInfo &info)
	Hook function that will be called by Search() after each game.
virtual void	OnStartSearch ()
	Hook function that will be called by StartSearch().
virtual void	OnEndSearch ()
	Hook function that will be called when search completes.
virtual void	OnThreadStartSearch (SgUctThreadState &state)
virtual void	OnThreadEndSearch (SgUctThreadState &state)
virtual std::size_t	GamesPlayed () const
Search functions
void	GenerateAllMoves (std::vector< SgMoveInfo > &moves)
	Get a list of all generated moves.
void	PlayGame ()
	Play a single game.
void	StartSearch (const std::vector< SgMove > &rootFilter=std::vector< SgMove >(), SgUctTree *initTree=0)
	Start search.
void	EndSearch ()
float	Search (std::size_t maxGames, double maxTime, std::vector< SgMove > &sequence, const std::vector< SgMove > &rootFilter=std::vector< SgMove >(), SgUctTree initTree=0, SgUctEarlyAbortParam earlyAbort=0)
	Calls StartSearch() and then maxGames times PlayGame().
SgPoint	SearchOnePly (size_t maxGames, double maxTime, float &value)
	Do a one-ply Monte-Carlo search instead of the UCT search.
const SgUctNode *	FindBestChild (const SgUctNode &node, const std::vector< SgMove > *excludeMoves=0) const
	Find child node with best move.
void	FindBestSequence (std::vector< SgMove > &sequence) const
	Extract sequence of best moves from root node.
float	GetBound (bool useRave, const SgUctNode &node, const SgUctNode &child) const
	Return the bound of a move.
Search data
const SgUctGameInfo &	LastGameInfo () const
	Info for last game.
std::string	LastGameSummaryLine () const
	One-line summary text for last game.
bool	WasEarlyAbort () const
	See parameter earlyAbort in Search().
const SgUctTree &	Tree () const
SgUctTree &	GetTempTree ()
	Get temporary tree.
Parameters
float	BiasTermConstant () const
	Constant c in the bias term.
void	SetBiasTermConstant (float biasTermConstant)
	See BiasTermConstant().
std::vector< std::size_t >	KnowledgeThreshold () const
	Points at which to recompute children.
void	SetKnowledgeThreshold (const std::vector< std::size_t > &counts)
	See KnowledgeThreshold().
std::size_t	MaxNodes () const
	Maximum number of nodes in the tree.
void	SetMaxNodes (std::size_t maxNodes)
	See MaxNodes().
std::size_t	NumberThreads () const
	The number of threads to use during the search.
void	SetNumberThreads (std::size_t n)
	See SetNumberThreads().
bool	LockFree () const
	Lock-free usage of multi-threaded search.
void	SetLockFree (bool enable)
	See LockFree().
int	RandomizeRaveFrequency () const
	See SetRandomizeRaveFrequency().
void	SetRandomizeRaveFrequency (int frequency)
	Randomly turns off rave with given frequency - once in every frequency child selections.
bool	RaveCheckSame () const
	Don't update RAVE value if opponent played the same move first.
void	SetRaveCheckSame (bool enable)
	See RaveCheckSame().
float	FirstPlayUrgency () const
	First play urgency.
void	SetFirstPlayUrgency (float firstPlayUrgency)
	See FirstPlayUrgency().
bool	LogGames () const
	Log one-line summary for each game during Search() to a file.
void	SetLogGames (bool enable)
	See LogGames().
std::size_t	MaxGameLength () const
	Maximum game length.
void	SetMaxGameLength (std::size_t maxGameLength)
	See MaxGameLength().
std::size_t	ExpandThreshold () const
	Required number of simulations to expand a node in the tree.
void	SetExpandThreshold (std::size_t expandThreshold)
	See ExpandThreshold().
std::size_t	NumberPlayouts () const
	The number of playouts per simulated game.
void	SetNumberPlayouts (std::size_t n)
bool	Rave () const
	Use the RAVE algorithm (Rapid Action Value Estimation).
void	SetRave (bool enable)
	See Rave().
SgUctMoveSelect	MoveSelect () const
	See SgUctMoveSelect.
void	SetMoveSelect (SgUctMoveSelect moveSelect)
	See SgUctMoveSelect.
float	RaveWeightInitial () const
	See Estimator weights in SgUctSearch.
void	SetRaveWeightInitial (float value)
	See Estimator weights in SgUctSearch.
float	RaveWeightFinal () const
	See Estimator weights in SgUctSearch.
void	SetRaveWeightFinal (float value)
	See Estimator weights in SgUctSearch.
bool	WeightRaveUpdates () const
	Weight RAVE updates.
void	SetWeightRaveUpdates (bool enable)
	See WeightRaveUpdates().
bool	VirtualLoss () const
	Whether search uses virtual loss.
void	SetVirtualLoss (bool enable)
	See VirtualLoss().
bool	PruneFullTree () const
	Prune nodes with low counts if tree is full.
void	SetPruneFullTree (bool enable)
	See PruneFullTree().
std::size_t	PruneMinCount () const
	See PruneFullTree().
void	SetPruneMinCount (std::size_t n)
	See PruneFullTree().
void	SetMpiSynchronizer (const SgMpiSynchronizerHandle &synchronizerHandle)
SgMpiSynchronizerHandle	MpiSynchronizer ()
const SgMpiSynchronizerHandle	MpiSynchronizer () const
Statistics
const SgUctSearchStat &	Statistics () const
void	WriteStatistics (std::ostream &out) const
Static Public Member Functions
static float	InverseEval (float eval)
Private Types
typedef boost::recursive_mutex::scoped_lock	GlobalLock
Private Member Functions
void	ApplyRootFilter (std::vector< SgMoveInfo > &moves)
bool	CheckAbortSearch (SgUctThreadState &state)
bool	CheckEarlyAbort () const
bool	CheckCountAbort (SgUctThreadState &state, std::size_t remainingGames) const
void	Debug (const SgUctThreadState &state, const std::string &textLine)
	Write a debugging line of text from within a thread.
void	DeleteThreads ()
void	ExpandNode (SgUctThreadState &state, const SgUctNode &node)
	Expand a node.
void	CreateChildren (SgUctThreadState &state, const SgUctNode &node, bool deleteChildTrees)
	Creates the children with the given moves and merges with existing children in the tree.
float	GetBound (bool useRave, float logPosCount, const SgUctNode &child) const
float	GetValueEstimate (bool useRave, const SgUctNode &child) const
float	GetValueEstimateRave (const SgUctNode &child) const
	Optimized version of GetValueEstimate() if RAVE and not other estimators are used.
float	Log (float x) const
bool	NeedToComputeKnowledge (const SgUctNode *current)
void	PlayGame (SgUctThreadState &state, GlobalLock *lock)
bool	PlayInTree (SgUctThreadState &state, bool &isTerminal)
	Play game until it leaves the tree.
bool	PlayoutGame (SgUctThreadState &state, std::size_t playout)
	Finish the game using GeneratePlayoutMove().
void	PrintSearchProgress (double currTime) const
	Print time, mean, nodes searched, and PV.
void	SearchLoop (SgUctThreadState &state, GlobalLock *lock)
	Loop invoked by each thread for playing games.
const SgUctNode &	SelectChild (int &randomizeCounter, const SgUctNode &node)
std::string	SummaryLine (const SgUctGameInfo &info) const
void	UpdateCheckTimeInterval (double time)
void	UpdateDynRaveBias ()
void	UpdateRaveValues (SgUctThreadState &state)
	Update the RAVE values in the tree for both players after a game was played.
void	UpdateRaveValues (SgUctThreadState &state, std::size_t playout)
void	UpdateRaveValues (SgUctThreadState &state, std::size_t playout, float eval, std::size_t i, const std::size_t firstPlay[], const std::size_t firstPlayOpp[])
void	UpdateStatistics (const SgUctGameInfo &info)
void	UpdateTree (const SgUctGameInfo &info)
Private Attributes
std::auto_ptr< SgUctThreadStateFactory >	m_threadStateFactory
bool	m_logGames
	See LogGames().
bool	m_rave
	See Rave().
std::vector< std::size_t >	m_knowledgeThreshold
	See KnowledgeThreshold().
volatile bool	m_aborted
	Flag indicating that the search was terminated because the maximum time or number of games was reached.
volatile bool	m_isTreeOutOfMemory
std::auto_ptr< boost::barrier >	m_searchLoopFinished
bool	m_wasEarlyAbort
	See SgUctEarlyAbortParam.
std::auto_ptr< SgUctEarlyAbortParam >	m_earlyAbort
	See SgUctEarlyAbortParam.
SgUctMoveSelect	m_moveSelect
	See SgUctMoveSelect.
bool	m_raveCheckSame
	See RaveCheckSame().
int	m_randomizeRaveFrequency
	See SetRandomizeRaveFrequency().
bool	m_lockFree
	See LockFree().
bool	m_weightRaveUpdates
	See WeightRaveUpdates().
bool	m_pruneFullTree
	See PruneFullTree().
std::size_t	m_numberThreads
	See NumberThreads().
std::size_t	m_numberPlayouts
	See NumberPlayouts().
std::size_t	m_maxNodes
	See MaxNodes().
std::size_t	m_pruneMinCount
	See PruneMinCount().
const int	m_moveRange
	See parameter moveRange in constructor.
std::size_t	m_maxGameLength
	See MaxGameLength().
std::size_t	m_expandThreshold
	See ExpandThreshold().
std::size_t	m_maxGames
	Number of games limit for the current search.
std::size_t	m_numberGames
	Number of games played in the current search.
std::size_t	m_startRootMoveCount
std::size_t	m_checkTimeInterval
	Interval in number of games in which to check time abort.
double	m_lastScoreDisplayTime
float	m_biasTermConstant
	See BiasTermConstant().
float	m_firstPlayUrgency
	See FirstPlayUrgency().
float	m_raveWeightInitial
	See Estimator weights in SgUctSearch.
float	m_raveWeightFinal
	See Estimator weights in SgUctSearch.
double	m_raveWeightParam1
	1 / m_raveWeightInitial precomputed for efficiency
double	m_raveWeightParam2
	m_raveWeightInitial / m_raveWeightFinal precomputed for efficiency
double	m_maxTime
	Time limit for current search.
bool	m_virtualLoss
	See VirtualLoss().
std::string	m_logFileName
SgTimer	m_timer
SgUctTree	m_tree
SgUctTree	m_tempTree
	See GetTempTree().
std::vector< SgMove >	m_rootFilter
	See parameter rootFilter in function Search().
std::ofstream	m_log
boost::recursive_mutex	m_globalMutex
	Mutex for protecting global variables during multi-threading.
SgUctSearchStat	m_statistics
std::vector< boost::shared_ptr< Thread > >	m_threads
	List of threads.
SgFastLog	m_fastLog
boost::shared_ptr< SgMpiSynchronizer >	m_mpiSynchronizer
Friends
class	Thread
Classes
class	Thread

SgUctSearch Class Reference [Monte Carlo tree search]

Detailed Description

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Classes

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

SgUctSearch Class Reference
[Monte Carlo tree search]