SmartGame Library: SgUctTree Class Reference

The nodes can be accessed only by getting non-const references or modified through accessor functions of SgUctTree, therefore SgUctTree can guarantee the integrity of the tree structure. The tree can be used in a lock-free way during a search (see Lock-free mode in SgUctSearch).

Definition at line 624 of file SgUctTree.h.


Public Member Functions
	SgUctTree ()
	Constructor.
void	CreateAllocators (std::size_t nuThreads)
	Create node allocators for threads.
void	AddGameResult (const SgUctNode &node, const SgUctNode *father, float eval)
	Add a game result.
void	AddGameResults (const SgUctNode &node, const SgUctNode *father, float eval, std::size_t count)
	Adds a game result count times.
void	RemoveGameResult (const SgUctNode &node, const SgUctNode *father, float eval)
	Removes a game result.
void	RemoveGameResults (const SgUctNode &node, const SgUctNode *father, float eval, std::size_t count)
	Removes a game result count times.
void	AddVirtualLoss (const std::vector< const SgUctNode * > &nodes)
	Adds a virtual loss to the given nodes.
void	RemoveVirtualLoss (const std::vector< const SgUctNode * > &nodes)
	Removes a virtual loss to the given nodes.
void	Clear ()
std::size_t	MaxNodes () const
	Return the current maximum number of nodes.
void	SetMaxNodes (std::size_t maxNodes)
	Change maximum number of nodes.
void	Swap (SgUctTree &tree)
	Swap content with another tree.
bool	HasCapacity (std::size_t allocatorId, std::size_t n) const
void	CreateChildren (std::size_t allocatorId, const SgUctNode &node, const std::vector< SgMoveInfo > &moves)
	Create children nodes.
void	MergeChildren (std::size_t allocatorId, const SgUctNode &node, const std::vector< SgMoveInfo > &moves, bool deleteChildTrees)
	Merge new children with old.
void	ExtractSubtree (SgUctTree &target, const SgUctNode &node, bool warnTruncate, double maxTime=std::numeric_limits< double >::max()) const
	Extract subtree to a different tree.
void	CopyPruneLowCount (SgUctTree &target, std::size_t minCount, bool warnTruncate, double maxTime=std::numeric_limits< double >::max()) const
	Get a copy of the tree with low count nodes pruned.
const SgUctNode &	Root () const
std::size_t	NuAllocators () const
std::size_t	NuNodes () const
	Total number of nodes.
std::size_t	NuNodes (std::size_t allocatorId) const
	Number of nodes in one of the allocators.
void	AddRaveValue (const SgUctNode &node, float value, float weight)
	Add a game result value to the RAVE value of a node.
void	RemoveRaveValue (const SgUctNode &node, float value, float weight)
	Remove a game result from the RAVE value of a node.
void	InitializeValue (const SgUctNode &node, float value, std::size_t count)
	Initialize the value and count of a node.
void	SetPosCount (const SgUctNode &node, std::size_t posCount)
void	InitializeRaveValue (const SgUctNode &node, float value, float count)
	Initialize the rave value and count of a move node with prior knowledge.
void	ApplyFilter (std::size_t allocatorId, const SgUctNode &node, const std::vector< SgMove > &rootFilter)
	Remove some children of a node according to a list of filtered moves.
void	SetChildren (std::size_t allocatorId, const SgUctNode &node, const vector< SgMove > &moves)
	Sets the children under node to be exactly those in moves, reusing the old children if possible.
Functions for debugging
void	CheckConsistency () const
	Do some consistency checks.
bool	Contains (const SgUctNode &node) const
	Check if tree contains node.
void	DumpDebugInfo (std::ostream &out) const
Private Member Functions
SgUctTree &	operator= (const SgUctTree &tree)
	Not implemented.
SgUctAllocator &	Allocator (std::size_t i)
const SgUctAllocator &	Allocator (std::size_t i) const
void	CopySubtree (SgUctTree &target, SgUctNode &targetNode, const SgUctNode &node, std::size_t minCount, std::size_t &currentAllocatorId, bool warnTruncate, bool &abort, SgTimer &timer, double maxTime) const
	Recursive function used by SgUctTree::ExtractSubtree and SgUctTree::CopyPruneLowCount.
void	ThrowConsistencyError (const std::string &message) const
Private Attributes
std::size_t	m_maxNodes
SgUctNode	m_root
std::vector< boost::shared_ptr< SgUctAllocator > >	m_allocators
	Allocators.
Friends
class	SgUctChildIterator

Constructor & Destructor Documentation

SgUctTree::SgUctTree ( )

Constructor.

Construct a tree. Before using the tree, CreateAllocators() and SetMaxNodes() must be called (in this order).

Definition at line 58 of file SgUctTree.cpp.

Member Function Documentation

void SgUctTree::AddGameResult	(	const SgUctNode &	node,
		const SgUctNode *	father,
		float	eval
	)

Add a game result.

Parameters:

	node	The node.
	father	The father (if not root) to update the position count.
	eval

Definition at line 844 of file SgUctTree.h.

References Contains(), and SG_ASSERT.

Referenced by AddVirtualLoss().

void SgUctTree::AddGameResults	(	const SgUctNode &	node,
		const SgUctNode *	father,
		float	eval,
		std::size_t	count
	)

Adds a game result count times.

Definition at line 855 of file SgUctTree.h.

References Contains(), SgUctNode::PosCount(), SetPosCount(), and SG_ASSERT.

Referenced by SgUctSearch::UpdateTree().

void SgUctTree::AddRaveValue	(	const SgUctNode &	node,
		float	value,
		float	weight
	)

Add a game result value to the RAVE value of a node.

Parameters:

	node	The node with the move
	value
	weight

See also:: SgUctSearch::Rave().

Definition at line 924 of file SgUctTree.h.

References Contains(), and SG_ASSERT.

Referenced by AddVirtualLoss(), and SgUctSearch::UpdateRaveValues().

void SgUctTree::AddVirtualLoss ( const std::vector< const SgUctNode * > & nodes )

Adds a virtual loss to the given nodes.

Definition at line 64 of file SgUctTree.cpp.

References AddGameResult(), and AddRaveValue().

Referenced by SgUctSearch::PlayGame().

const SgUctAllocator & SgUctTree::Allocator ( std::size_t i ) const [private]

Definition at line 949 of file SgUctTree.h.

References m_allocators, and SG_ASSERT.

SgUctAllocator & SgUctTree::Allocator ( std::size_t i ) [private]

Definition at line 943 of file SgUctTree.h.

References m_allocators, and SG_ASSERT.

Referenced by ApplyFilter(), Clear(), Contains(), CopySubtree(), CreateChildren(), DumpDebugInfo(), HasCapacity(), MergeChildren(), NuNodes(), SetMaxNodes(), and Swap().

void SgUctTree::ApplyFilter	(	std::size_t	allocatorId,
		const SgUctNode &	node,
		const std::vector< SgMove > &	rootFilter
	)

Remove some children of a node according to a list of filtered moves.

Requires: Allocator(allocatorId).HasCapacity(node.NuChildren())
For efficiency, no reorganization of the tree is done to remove the dead subtrees (and NuNodes() will not report the real number of nodes in the tree). This function can be used in lock-free mode.

Definition at line 74 of file SgUctTree.cpp.

References Allocator(), Contains(), SgUctNode::CopyDataFrom(), SgUctAllocator::CreateOne(), SgUctAllocator::Finish(), HasCapacity(), SgUctNode::HasChildren(), SgUctNode::NuChildren(), SgUctNode::SetFirstChild(), SgUctNode::SetNuChildren(), SG_ASSERT, and SgSynchronizeThreadMemory().

Referenced by SgUctSearch::StartSearch().

void SgUctTree::CheckConsistency ( ) const

Do some consistency checks.

Exceptions:

SgException

if inconsistencies are detected.

Definition at line 158 of file SgUctTree.cpp.

References Contains(), and ThrowConsistencyError().

void SgUctTree::Clear ( )

Definition at line 165 of file SgUctTree.cpp.

References Allocator(), SgUctAllocator::Clear(), m_root, NuAllocators(), and SG_NULLMOVE.

Referenced by CreateAllocators(), SgUctTreeUtil::ExtractSubtree(), ExtractSubtree(), SgUctSearch::GetTempTree(), SetMaxNodes(), and SgUctSearch::StartSearch().

bool SgUctTree::Contains ( const SgUctNode & node ) const

Check if tree contains node.

This function uses pointer comparisons. Since the result of comparisons for pointers to elements in different containers is platform-dependent, it is only guaranteed that it returns true, if not node belongs to the allocator, but not that it returns false for nodes not in the tree.

Definition at line 175 of file SgUctTree.cpp.

References Allocator(), m_root, and NuAllocators().

Referenced by AddGameResult(), AddGameResults(), AddRaveValue(), ApplyFilter(), CheckConsistency(), CopySubtree(), CreateChildren(), ExtractSubtree(), InitializeRaveValue(), InitializeValue(), MergeChildren(), RemoveGameResult(), RemoveGameResults(), RemoveRaveValue(), SetPosCount(), and SgUctChildIterator::SgUctChildIterator().

void SgUctTree::CopyPruneLowCount	(	SgUctTree &	target,
		std::size_t	minCount,
		bool	warnTruncate,
		double	maxTime = `std::numeric_limits< double >::max()`
	)			const

Get a copy of the tree with low count nodes pruned.

The tree will be truncated if one of the allocators overflows (can happen due to reassigning nodes to different allocators), the given max time is exceeded or on SgUserAbort().

Parameters:

`[out]`	target	The resulting tree. Must have the same maximum number of nodes. Will be cleared before using.
	minCount	The minimum count (SgUctNode::MoveCount())
	warnTruncate	Print warning to SgDebug() if tree was truncated
	maxTime	Truncate the tree, if the extraction takes longer than the given time

Definition at line 185 of file SgUctTree.cpp.

References CopySubtree(), and m_root.

Referenced by SgUctSearch::Search().

void SgUctTree::CopySubtree	(	SgUctTree &	target,
		SgUctNode &	targetNode,
		const SgUctNode &	node,
		std::size_t	minCount,
		std::size_t &	currentAllocatorId,
		bool	warnTruncate,
		bool &	abort,
		SgTimer &	timer,
		double	maxTime
	)			const `[private]`

Recursive function used by SgUctTree::ExtractSubtree and SgUctTree::CopyPruneLowCount.

Parameters:

	target	The target tree.
	targetNode	The target node; it is already created but the content not yet copied
	node	The node in the source tree to be copied.
	minCount	The minimum count (SgUctNode::MoveCount()) of a non-root node in the source tree to copy
	currentAllocatorId	The current node allocator. Will be incremented in each call to CopySubtree to use node allocators of target tree evenly.
	warnTruncate	Print warning to SgDebug() if tree was truncated (e.g due to reassigning nodes to different allocators)
`[in,out]`	abort	Flag to abort copying. Must be initialized to false by top-level caller
	timer
	maxTime	See ExtractSubtree()

Definition at line 212 of file SgUctTree.cpp.

References Allocator(), Contains(), SgUctNode::CopyDataFrom(), SgUctAllocator::CreateN(), SgUctAllocator::Finish(), SgUctAllocator::HasCapacity(), SgTimer::IsTimeOut(), NuAllocators(), SgUctNode::SetFirstChild(), SgUctNode::SetNuChildren(), SgUctNode::SetPosCount(), SG_ASSERT, SgDebug(), and SgUserAbort().

Referenced by CopyPruneLowCount(), and ExtractSubtree().

void SgUctTree::CreateAllocators ( std::size_t nuThreads )

Create node allocators for threads.

Definition at line 279 of file SgUctTree.cpp.

References Clear(), and m_allocators.

Referenced by SgUctSearch::CreateThreads(), and SgUctSearch::GetTempTree().

void SgUctTree::CreateChildren	(	std::size_t	allocatorId,
		const SgUctNode &	node,
		const std::vector< SgMoveInfo > &	moves
	)

Create children nodes.

Requires: Allocator(allocatorId).HasCapacity(moves.size())

Definition at line 869 of file SgUctTree.h.

References Allocator(), Contains(), SgUctAllocator::Create(), SgUctAllocator::Finish(), SgUctAllocator::HasCapacity(), SgUctNode::HasChildren(), NuAllocators(), SgUctNode::SetFirstChild(), SgUctNode::SetNuChildren(), SgUctNode::SetPosCount(), SG_ASSERT, and SgSynchronizeThreadMemory().

Referenced by SgUctSearch::ExpandNode().

void SgUctTree::DumpDebugInfo ( std::ostream & out ) const

Definition at line 290 of file SgUctTree.cpp.

References Allocator(), SgUctAllocator::Finish(), m_root, NuAllocators(), SgUctAllocator::NuNodes(), and SgUctAllocator::Start().

Referenced by ThrowConsistencyError().

void SgUctTree::ExtractSubtree	(	SgUctTree &	target,
		const SgUctNode &	node,
		bool	warnTruncate,
		double	maxTime = `std::numeric_limits< double >::max()`
	)			const

Extract subtree to a different tree.

The tree will be truncated if one of the allocators overflows (can happen due to reassigning nodes to different allocators), the given max time is exceeded or on SgUserAbort().

Parameters:

`[out]`	target	The resulting subtree. Must have the same maximum number of nodes. Will be cleared before using.
	node	The start node of the subtree.
	warnTruncate	Print warning to SgDebug() if tree was truncated
	maxTime	Truncate the tree, if the extraction takes longer than the given time

Definition at line 300 of file SgUctTree.cpp.

References Clear(), Contains(), CopySubtree(), m_root, MaxNodes(), and SG_ASSERT.

Referenced by SgUctTreeUtil::ExtractSubtree().

bool SgUctTree::HasCapacity	(	std::size_t	allocatorId,
		std::size_t	n
	)			const

Definition at line 955 of file SgUctTree.h.

References Allocator(), and SgUctAllocator::HasCapacity().

Referenced by ApplyFilter(), SgUctSearch::CreateChildren(), SgUctSearch::ExpandNode(), and SgUctSearch::StartSearch().

void SgUctTree::InitializeRaveValue	(	const SgUctNode &	node,
		float	value,
		float	count
	)

Initialize the rave value and count of a move node with prior knowledge.

Definition at line 970 of file SgUctTree.h.

References Contains(), and SG_ASSERT.

void SgUctTree::InitializeValue	(	const SgUctNode &	node,
		float	value,
		std::size_t	count
	)

Initialize the value and count of a node.

Definition at line 961 of file SgUctTree.h.

References Contains(), and SG_ASSERT.

std::size_t SgUctTree::MaxNodes ( ) const

Return the current maximum number of nodes.

This returns the maximum number of nodes as set by SetMaxNodes(). See SetMaxNodes() why the real maximum number of nodes can be higher or lower.

Definition at line 979 of file SgUctTree.h.

References m_maxNodes.

Referenced by SgUctSearch::CreateChildren(), SgUctSearch::ExpandNode(), ExtractSubtree(), SgUctSearch::GetTempTree(), and Swap().

void SgUctTree::MergeChildren	(	std::size_t	allocatorId,
		const SgUctNode &	node,
		const std::vector< SgMoveInfo > &	moves,
		bool	deleteChildTrees
	)

Merge new children with old.

Requires: Allocator(allocatorId).HasCapacity(moves.size())

Definition at line 314 of file SgUctTree.cpp.

References Allocator(), Contains(), SgUctAllocator::Create(), SgUctAllocator::Finish(), SgUctAllocator::HasCapacity(), SgUctNode::NuChildren(), SgUctNode::SetFirstChild(), SgUctNode::SetNuChildren(), SgUctNode::SetPosCount(), SG_ASSERT, and SgSynchronizeThreadMemory().

Referenced by SgUctSearch::CreateChildren().

std::size_t SgUctTree::NuAllocators ( ) const

Definition at line 984 of file SgUctTree.h.

References m_allocators.

Referenced by Clear(), Contains(), CopySubtree(), CreateChildren(), DumpDebugInfo(), SgUctSearch::GetTempTree(), NuNodes(), SetMaxNodes(), and Swap().

std::size_t SgUctTree::NuNodes ( std::size_t allocatorId ) const

Number of nodes in one of the allocators.

Definition at line 989 of file SgUctTree.h.

References Allocator(), and SgUctAllocator::NuNodes().

std::size_t SgUctTree::NuNodes ( ) const

Total number of nodes.

Includes the sum of nodes in all allocators plus the root node.

Definition at line 385 of file SgUctTree.cpp.

References Allocator(), NuAllocators(), and SgUctAllocator::NuNodes().

Referenced by SgUctSearch::Search(), and SgUctSearch::WriteStatistics().

SgUctTree& SgUctTree::operator= ( const SgUctTree & tree ) [private]

Not implemented.

Cannot be copied because allocators contain pointers to elements. Use SgUctTree::Swap instead.

void SgUctTree::RemoveGameResult	(	const SgUctNode &	node,
		const SgUctNode *	father,
		float	eval
	)

Removes a game result.

Parameters:

	node	The node.
	father	The father (if not root) to update the position count.
	eval

Definition at line 900 of file SgUctTree.h.

References Contains(), and SG_ASSERT.

Referenced by RemoveVirtualLoss().

void SgUctTree::RemoveGameResults	(	const SgUctNode &	node,
		const SgUctNode *	father,
		float	eval,
		std::size_t	count
	)

Removes a game result count times.

Definition at line 911 of file SgUctTree.h.

References Contains(), SgUctNode::PosCount(), SetPosCount(), and SG_ASSERT.

void SgUctTree::RemoveRaveValue	(	const SgUctNode &	node,
		float	value,
		float	weight
	)

Remove a game result from the RAVE value of a node.

Parameters:

	node	The node with the move
	value
	weight

See also:: SgUctSearch::Rave().

Definition at line 933 of file SgUctTree.h.

References Contains(), SG_ASSERT, and SG_UNUSED().

Referenced by RemoveVirtualLoss().

void SgUctTree::RemoveVirtualLoss ( const std::vector< const SgUctNode * > & nodes )

Removes a virtual loss to the given nodes.

Definition at line 393 of file SgUctTree.cpp.

References RemoveGameResult(), and RemoveRaveValue().

Referenced by SgUctSearch::PlayGame().

const SgUctNode & SgUctTree::Root ( ) const

Definition at line 994 of file SgUctTree.h.

References m_root.

Referenced by SgUctSearch::CheckCountAbort(), SgUctSearch::CheckEarlyAbort(), SgUctTreeUtil::ExtractSubtree(), SgUctSearch::FindBestSequence(), SgUctSearch::GamesPlayed(), SgUctSearch::PlayInTree(), SgUctSearch::PrintSearchProgress(), SgUctSearch::Search(), SgUctSearch::StartSearch(), and SgUctSearch::WriteStatistics().

void SgUctTree::SetChildren	(	std::size_t	allocatorId,
		const SgUctNode &	node,
		const vector< SgMove > &	moves
	)

Sets the children under node to be exactly those in moves, reusing the old children if possible.

Children not in moves are pruned, children missing from moves are added as leaves. Requires: Allocator(allocatorId).HasCapacity(moves.size())

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

Change maximum number of nodes.

Also clears the tree. This will call SetMaxNodes() at each registered allocator with maxNodes / numberAllocators as an argument. The real maximum number of nodes can be higher (because the root node is owned by this class, not an allocator) or lower (if maxNodes is not a multiple of the number of allocators).

Parameters:

maxNodes

Maximum number of nodes

Definition at line 403 of file SgUctTree.cpp.

References Allocator(), Clear(), m_maxNodes, NuAllocators(), SgUctAllocator::SetMaxNodes(), SG_ASSERT, and SgDebug().

Referenced by SgUctSearch::CreateThreads(), SgUctSearch::GetTempTree(), and SgUctSearch::SetMaxNodes().