Tree used in SgUctSearch. More...

#include <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, SgUctValue eval)
	Add a game result.
void	AddGameResults (const SgUctNode &node, const SgUctNode *father, SgUctValue eval, SgUctValue count)
	Adds a game result count times.
void	RemoveGameResult (const SgUctNode &node, const SgUctNode *father, SgUctValue eval)
	Removes a game result.
void	RemoveGameResults (const SgUctNode &node, const SgUctNode *father, SgUctValue eval, SgUctValue count)
	Removes a game result count times.
void	AddVirtualLoss (const SgUctNode &node)
	Adds a virtual loss to the given node.
void	RemoveVirtualLoss (const SgUctNode &node)
	Removes a virtual loss to the given node.
void	SetProvenType (const SgUctNode &node, SgUctProvenType type)
void	SetKnowledgeCount (const SgUctNode &node, SgUctValue count)
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< SgUctMoveInfo > &moves)
	Create children nodes.
void	MergeChildren (std::size_t allocatorId, const SgUctNode &node, const std::vector< SgUctMoveInfo > &moves, bool deleteChildTrees)
	Merge new children with old.
void	ExtractSubtree (SgUctTree &target, const SgUctNode &node, bool warnTruncate, double maxTime=std::numeric_limits< double >::max(), SgUctValue minCount=0) const
	Extract subtree to a different tree.
void	CopyPruneLowCount (SgUctTree &target, SgUctValue 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, SgUctValue value, SgUctValue weight)
	Add a game result value to the RAVE value of a node.
void	RemoveRaveValue (const SgUctNode &node, SgUctValue value, SgUctValue weight)
	Remove a game result from the RAVE value of a node.
void	InitializeValue (const SgUctNode &node, SgUctValue value, SgUctValue count)
	Initialize the value and count of a node.
void	SetPosCount (const SgUctNode &node, SgUctValue posCount)
void	InitializeRaveValue (const SgUctNode &node, SgUctValue value, SgUctValue 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
bool	CopySubtree (SgUctTree &target, SgUctNode &targetNode, const SgUctNode &node, SgUctValue minCount, std::size_t &currentAllocatorId, bool warnTruncate, bool &abort, SgTimer &timer, double maxTime, bool alwaysKeepProven) 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

Detailed Description

Tree used in SgUctSearch.

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 654 of file SgUctTree.h.

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 57 of file SgUctTree.cpp.

Member Function Documentation

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

Add a game result.

Parameters:

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

Definition at line 861 of file SgUctTree.h.

References Contains(), and SG_ASSERT.

void SgUctTree::AddGameResults	(	const SgUctNode &	node,
		const SgUctNode *	father,
		SgUctValue	eval,
		SgUctValue	count
	)

Adds a game result count times.

Definition at line 872 of file SgUctTree.h.

References Contains(), and SG_ASSERT.

Referenced by SgUctSearch::UpdateTree().

void SgUctTree::AddRaveValue	(	const SgUctNode &	node,
		SgUctValue	value,
		SgUctValue	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 950 of file SgUctTree.h.

References Contains(), and SG_ASSERT.

Referenced by SgUctSearch::UpdateRaveValues().

void SgUctTree::AddVirtualLoss ( const SgUctNode & node )

Adds a virtual loss to the given node.

Definition at line 940 of file SgUctTree.h.

Referenced by SgUctSearch::PlayInTree().

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

Definition at line 969 of file SgUctTree.h.

References m_allocators, and SG_ASSERT.

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

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

Definition at line 975 of file SgUctTree.h.

References m_allocators, and SG_ASSERT.

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 63 of file SgUctTree.cpp.

References Allocator(), Contains(), SgUctNode::CopyDataFrom(), SgUctAllocator::CreateOne(), SgUctAllocator::Finish(), HasCapacity(), SgUctNode::HasChildren(), SgUctNode::Move(), 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 147 of file SgUctTree.cpp.

References Contains(), and ThrowConsistencyError().

void SgUctTree::Clear ( )

Definition at line 154 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.

Check if node is in tree.

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.

Only used for assertions. May not be available in future implementations.

Definition at line 163 of file SgUctTree.cpp.

References Allocator(), SgUctAllocator::Contains(), m_root, and NuAllocators().

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

void SgUctTree::CopyPruneLowCount	(	SgUctTree &	target,
		SgUctValue	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 173 of file SgUctTree.cpp.

References CopySubtree(), m_root, and SgSynchronizeThreadMemory().

Referenced by SgUctSearch::Search().

bool SgUctTree::CopySubtree	(	SgUctTree &	target,
		SgUctNode &	targetNode,
		const SgUctNode &	node,
		SgUctValue	minCount,
		std::size_t &	currentAllocatorId,
		bool	warnTruncate,
		bool &	abort,
		SgTimer &	timer,
		double	maxTime,
		bool	alwaysKeepProven
	)			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()
	alwaysKeepProven	Copy proven nodes even if below minCount

Definition at line 202 of file SgUctTree.cpp.

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

Referenced by CopyPruneLowCount(), and ExtractSubtree().

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

Create node allocators for threads.

Definition at line 292 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< SgUctMoveInfo > &	moves
	)

Create children nodes.

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

Definition at line 885 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 303 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()`,
		SgUctValue	minCount = `0`
	)			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
	minCount

Definition at line 313 of file SgUctTree.cpp.

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

Referenced by SgUctTreeUtil::ExtractSubtree().

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

Definition at line 981 of file SgUctTree.h.

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

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

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

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

Definition at line 996 of file SgUctTree.h.

References Contains(), and SG_ASSERT.

void SgUctTree::InitializeValue	(	const SgUctNode &	node,
		SgUctValue	value,
		SgUctValue	count
	)

Initialize the value and count of a node.

Definition at line 987 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 1005 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< SgUctMoveInfo > &	moves,
		bool	deleteChildTrees
	)

Merge new children with old.

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

Definition at line 329 of file SgUctTree.cpp.

References Allocator(), Contains(), SgUctAllocator::Create(), SgUctAllocator::Finish(), SgUctNode::FirstChild(), SgUctAllocator::HasCapacity(), SgUctNode::HasChildren(), SgUctNode::KnowledgeCount(), SgUctNode::MergeResults(), SgUctNode::Move(), SgUctNode::MoveCount(), SgUctNode::NuChildren(), SgUctNode::PosCount(), SgUctNode::SetFirstChild(), SgUctNode::SetKnowledgeCount(), SgUctNode::SetNuChildren(), SgUctNode::SetPosCount(), SG_ASSERT, and SgSynchronizeThreadMemory().

Referenced by SgUctSearch::CreateChildren().

std::size_t SgUctTree::NuAllocators ( ) const

Definition at line 1010 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 ( ) const

Total number of nodes.

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

Definition at line 401 of file SgUctTree.cpp.

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

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

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

Number of nodes in one of the allocators.

Definition at line 1015 of file SgUctTree.h.

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

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,
		SgUctValue	eval
	)

Removes a game result.

Parameters:

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

Definition at line 917 of file SgUctTree.h.

References Contains(), and SG_ASSERT.

void SgUctTree::RemoveGameResults	(	const SgUctNode &	node,
		const SgUctNode *	father,
		SgUctValue	eval,
		SgUctValue	count
	)

Removes a game result count times.

Definition at line 928 of file SgUctTree.h.

References Contains(), and SG_ASSERT.

void SgUctTree::RemoveRaveValue	(	const SgUctNode &	node,
		SgUctValue	value,
		SgUctValue	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 959 of file SgUctTree.h.

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

void SgUctTree::RemoveVirtualLoss ( const SgUctNode & node )

Removes a virtual loss to the given node.

Definition at line 945 of file SgUctTree.h.

Referenced by SgUctSearch::UpdateTree().

const SgUctNode & SgUctTree::Root ( ) const

Definition at line 1020 of file SgUctTree.h.

References m_root.

Referenced by SgUctSearch::CheckAbortSearch(), 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())

Definition at line 100 of file SgUctTree.cpp.

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

void SgUctTree::SetKnowledgeCount	(	const SgUctNode &	node,
		SgUctValue	count
	)

Definition at line 1025 of file SgUctTree.h.

References Contains(), and SG_ASSERT.

Referenced by SgUctSearch::NeedToComputeKnowledge().

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 409 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().