General utility functions used in GoUct. More...

Functions
void	ClearStatistics (SgPointArray< SgUctStatistics > &stats)
template<class BOARD >
bool	DoSelfAtariCorrection (const BOARD &bd, SgPoint &p)
	Check if move is self-atari and find other liberty, if yes.
template<class BOARD >
bool	DoClumpCorrection (const BOARD &bd, SgPoint &p)
	Check if p makes ugly clump.
template<class BOARD >
bool	GainsLiberties (const BOARD &bd, SgPoint anchor, SgPoint lib)
	Check, if playing at a lib gains liberties.
SgPoint	GenForcedOpeningMove (const GoBoard &bd)
	Generate a forced opening move.
template<class BOARD >
bool	GeneratePoint (const BOARD &bd, SgBalancer &balancer, SgPoint p, SgBlackWhite toPlay)
	Filter for generating moves in random phase.
void	GfxBestMove (const SgUctSearch &search, SgBlackWhite toPlay, std::ostream &out)
	Print information about search as Gfx commands for GoGui.
void	GfxCounts (const SgUctTree &tree, std::ostream &out)
	Print move counts as Gfx commands for GoGui.
void	GfxMoveValues (const SgUctSearch &search, SgBlackWhite toPlay, std::ostream &out)
	Print the move values as Gfx commands for GoGui.
void	GfxSequence (const SgUctSearch &search, SgBlackWhite toPlay, std::ostream &out)
	Print best sequence of search in GoGui live-gfx format.
void	GfxStatus (const SgUctSearch &search, std::ostream &out)
	Print information about search as GoGui Gfx commands for text in the status line.
void	GfxTerritoryStatistics (const SgPointArray< SgUctStatistics > &territoryStatistics, const GoBoard &bd, std::ostream &out)
	Print territory statistics as GoGui gfx commands.
template<class BOARD >
bool	IsMutualAtari (const BOARD &bd, SgBalancer &balancer, SgPoint p, SgBlackWhite toPlay)
	selfatari of a larger number of stones and also atari on opponent.
void	SaveTree (const SgUctTree &tree, int boardSize, const SgBWSet &stones, SgBlackWhite toPlay, std::ostream &out, int maxDepth=-1)
	Save tree contained in a search as a Go SGF file.
template<class BOARD >
SgPoint	SelectRandom (const BOARD &bd, SgBlackWhite toPlay, GoPointList &emptyPts, SgRandom &random, SgBalancer &balancer)
	Select a random move from a list of empty points.
template<class BOARD >
void	SetEdgeCorrection (const BOARD &bd, SgPoint p, int &edgeCorrection)
	Utility function used in DoClumpCorrection().
std::string	ChildrenStatistics (const SgUctSearch &search, bool bSort, const SgUctNode &node)
	Return statistics of all children of a node.
template<class BOARD >
bool	SubsetOfBlocks (const BOARD &bd, const SgPoint anchor[], SgPoint nb)
	check if anchors[] are subset of neighbor blocks of nb
Variables
const bool	REMOVE_SELF_ATARI = false
	reject random move if it was self atari
const bool	REMOVE_MUTUAL_ATARI = true
	reject random move if it was both atari and self atari
const int	SELF_ATARI_LIMIT = 8
const int	MUTUAL_ATARI_LIMIT = 2
const bool	CONSERVATIVE_CLUMP = true
	Conservative clump correction.
const int	LINE_1_LIMIT = CONSERVATIVE_CLUMP ? 4 : 3
	Used in clump correction.
const int	LINE_2_OR_MORE_LIMIT = CONSERVATIVE_CLUMP ? 6 : 5
	Used in clump correction.

Detailed Description

General utility functions used in GoUct.

These functions are used in GoUct, but should not depend on other classes in GoUct to avoid cyclic dependencies.

Function Documentation

string GoUctUtil::ChildrenStatistics	(	const SgUctSearch &	search,
		bool	bSort,
		const SgUctNode &	node
	)

Return statistics of all children of a node.

Parameters:

	search	The search containing the tree and statistics
	bSort	Whether sort the children
	node	The node

Definition at line 247 of file GoUctUtil.cpp.

References SgUctNode::Mean(), SgUctNode::Move(), SgUctNode::MoveCount(), SgUctSearch::MoveString(), and SgUctSearch::Tree().

void GoUctUtil::ClearStatistics ( SgPointArray< SgUctStatistics > & stats )

Definition at line 91 of file GoUctUtil.cpp.

template<class BOARD >

bool GoUctUtil::DoClumpCorrection	(	const BOARD &	bd,
		SgPoint &	p
	)

Check if p makes ugly clump.

Possibly replace by neighbor. If p is close to many own stones: check if neighboring point looks better. If yes, replace by neighbor.

Definition at line 229 of file GoUctUtil.h.

References CONSERVATIVE_CLUMP, GoEyeUtil::EmptyNeighbor(), LINE_1_LIMIT, LINE_2_OR_MORE_LIMIT, GoBoardUtil::SelfAtari(), SetEdgeCorrection(), SG_ASSERT, and SG_ENDPOINT.

Referenced by GoUctPlayoutPolicy< BOARD >::GenerateMove().

template<class BOARD >

bool GoUctUtil::DoSelfAtariCorrection	(	const BOARD &	bd,
		SgPoint &	p
	)

Check if move is self-atari and find other liberty, if yes.

This can be applied as a filter in the playout policy, after a move was generated. It is a useful correction to the move generation using GoBoardUtil::IsCompletelySurrounded, which prunes backfilling moves. Does not check if the move is legal, because this is usually already checked in the playout policy, and requires that the move is no suicide move (checked with an assertion).

1. If the move is a self-atari of more than 1 stone it is replaced by the liberty of the resulting block, unless it is also a self-atari.

2. If p is single stone self-atari, possibly replace by neighbor. If p is a single stone with only one liberty and it is not a capture move: check if neighboring point has more liberties. If yes, replace by neighbor.

Parameters:

	bd
	p	A (legal) move

Returns:: The replacement move, if one was found, otherwise the original move.

Definition at line 286 of file GoUctUtil.h.

References GoEyeUtil::EmptyNeighbor(), GoBoardUtil::SelfAtari(), SG_ASSERT, SG_EMPTY, SG_NULLMOVE, and SgOppBW().

Referenced by GoUctPlayoutPolicy< BOARD >::GenerateMove().

template<class BOARD >

bool GoUctUtil::GainsLiberties	(	const BOARD &	bd,
		SgPoint	anchor,
		SgPoint	lib
	)

Check, if playing at a lib gains liberties.

Does not handle capturing moves for efficiency. Not needed, because capturing moves have a higher priority in the playout.

Definition at line 353 of file GoUctUtil.h.

References SG_ASSERT, and SG_EMPTY.

Referenced by GoUctPlayoutPolicy< BOARD >::PlayGoodLiberties().

template<class BOARD >

bool GoUctUtil::GeneratePoint	(	const BOARD &	bd,
		SgBalancer &	balancer,
		SgPoint	p,
		SgBlackWhite	toPlay
	)

Filter for generating moves in random phase.

Checks if a point (must be empty) is a legal move and GoBoardUtil::IsCompletelySurrounded() returns false. If a policy generates no pass move as long as there are still moves on the board that this function would return true for, then the end position can be scored with GoBoardUtil::ScoreSimpleEndPosition().

Definition at line 414 of file GoUctUtil.h.

References GoBoardUtil::IsCompletelySurrounded(), IsMutualAtari(), REMOVE_MUTUAL_ATARI, REMOVE_SELF_ATARI, SELF_ATARI_LIMIT, GoBoardUtil::SelfAtari(), and SG_ASSERT.

Referenced by GoUctPureRandomGenerator< BOARD >::Generate(), GoUctGlobalSearchState< POLICY >::GeneratePlayoutMove(), and SelectRandom().

SgPoint GoUctUtil::GenForcedOpeningMove ( const GoBoard & bd )

Generate a forced opening move.

This function can be used to generate opening moves instead of doing a Monte-Carlo tree search, which often returns random looking moves in the opening on large boards. Experiments showed also an improvement in playing strength if this function is used. The function currently generates a move on the 4-4 point of an empty corner under the following conditions: # The board size is 13 or larger # There are no more than 5 stones of each color on the board (avoids that the move generation triggers in positions containing lots of setup stones) # All points in the corner up to and including the 5th row are empty

Returns:: A randomly selected move that fulfills the conditions or SG_NULLPOINT if no such move exists.

Definition at line 98 of file GoUctUtil.cpp.

References SgRandom::Global(), SgArrayList< T, SIZE >::IsEmpty(), SgArrayList< T, SIZE >::Length(), Pt(), SgArrayList< T, SIZE >::PushBack(), SG_BLACK, SG_NULLMOVE, SG_WHITE, GoBoard::Size(), SgRandom::SmallInt(), and GoBoard::TotalNumStones().

Referenced by GoUctPlayer< SEARCH, THREAD >::GenMove().

void GoUctUtil::GfxBestMove	(	const SgUctSearch &	search,
		SgBlackWhite	toPlay,
		std::ostream &	out
	)

Print information about search as Gfx commands for GoGui.

Can be used for GoGui live graphics during the search or GoGui analyze command type "gfx" after the search (see http://gogui.sf.net). Best move and best response move as variation (shown as shadow stones in GoGui).

Parameters:

	search	The search containing the tree and statistics
	toPlay	The color toPlay at the root node of the tree
	out	The stream to write the gfx commands to

Definition at line 118 of file GoUctUtil.cpp.

References SgUctSearch::FindBestChild(), SgUctNode::Move(), SgUctTree::Root(), SG_BLACK, and SgUctSearch::Tree().

Referenced by GoUctCommands::CmdGfx(), GoUctSearch::DisplayGfx(), and GoUctGlobalSearch< POLICY, FACTORY >::DisplayGfx().

void GoUctUtil::GfxCounts	(	const SgUctTree &	tree,
		std::ostream &	out
	)

Print move counts as Gfx commands for GoGui.

Can be used for GoGui live graphics during the search or GoGui analyze command type "gfx" after the search (see http://gogui.sf.net). Prints a LABEL command to display the move counts.

Parameters:

	tree
	out	The stream to write the gfx commands to

Definition at line 134 of file GoUctUtil.cpp.

References SgUctNode::HasChildren(), SgUctNode::HasMean(), SgUctNode::Move(), SgUctNode::MoveCount(), PointToString(), and SgUctTree::Root().

Referenced by GoUctCommands::CmdGfx(), and GoUctSearch::DisplayGfx().

void GoUctUtil::GfxMoveValues	(	const SgUctSearch &	search,
		SgBlackWhite	toPlay,
		std::ostream &	out
	)

Print the move values as Gfx commands for GoGui.

Can be used for GoGui live graphics during the search or GoGui analyze command type "gfx" after the search (see http://gogui.sf.net). The values of the moves in the root node are shown using an INFLUENCE gfx command.

Parameters:

	search	The search containing the tree and statistics
	toPlay	The color to play in the root node of the UCT tree
	out	The stream to write the gfx commands to

Definition at line 149 of file GoUctUtil.cpp.

References SgUctNode::HasChildren(), SgUctNode::HasMean(), SgUctSearch::InverseEval(), SgUctNode::Mean(), SgUctNode::Move(), SgUctTree::Root(), SG_WHITE, and SgUctSearch::Tree().

Referenced by GoUctCommands::CmdGfx(), and GoUctSearch::DisplayGfx().

void GoUctUtil::GfxSequence	(	const SgUctSearch &	search,
		SgBlackWhite	toPlay,
		std::ostream &	out
	)

Print best sequence of search in GoGui live-gfx format.

Definition at line 173 of file GoUctUtil.cpp.

References SgUctSearch::FindBestSequence(), SG_BLACK, and SgOppBW().

Referenced by GoUctCommands::CmdSequence(), and GoUctSearch::DisplayGfx().

void GoUctUtil::GfxStatus	(	const SgUctSearch &	search,
		std::ostream &	out
	)

Print information about search as GoGui Gfx commands for text in the status line.

Can be used for GoGui live graphics during the search or GoGui analyze command type "gfx" after the search (see http://gogui.sf.net). The following information is in the status line:

N = Number games
V = Value of root node
Len = Average simulation sequence length
Tree = Average/maximum moves of simulation sequence in tree
Abrt = Percentage of games aborted (due to maximum game length)
Gm/s = Simulations per second
Parameters:

search The search containing the tree and statistics

out The stream to write the gfx commands to

Definition at line 188 of file GoUctUtil.cpp.

References SgUctSearchStat::m_aborted, SgUctSearchStat::m_gameLength, SgUctSearchStat::m_gamesPerSecond, SgUctSearchStat::m_movesInTree, SgStatisticsExt< VALUE, COUNT >::Max(), SgStatisticsExt< VALUE, COUNT >::Mean(), SgUctNode::Mean(), SgStatisticsBase< VALUE, COUNT >::Mean(), SgUctNode::MoveCount(), SgUctTree::Root(), SgUctSearch::Statistics(), and SgUctSearch::Tree().

Referenced by GoUctCommands::CmdGfx(), GoUctSearch::DisplayGfx(), and GoUctGlobalSearch< POLICY, FACTORY >::DisplayGfx().

void GoUctUtil::GfxTerritoryStatistics	(	const SgPointArray< SgUctStatistics > &	territoryStatistics,
		const GoBoard &	bd,
		std::ostream &	out
	)

Print territory statistics as GoGui gfx commands.

Can be used for GoGui live graphics during the search or GoGui analyze command type "gfx" after the search (see http://gogui.sf.net). Uses INFLUENCE gfx command.

Definition at line 201 of file GoUctUtil.cpp.

Referenced by GoUctGlobalSearch< POLICY, FACTORY >::DisplayGfx().

template<class BOARD >

bool GoUctUtil::IsMutualAtari	(	const BOARD &	bd,
		SgBalancer &	balancer,
		SgPoint	p,
		SgBlackWhite	toPlay
	)

selfatari of a larger number of stones and also atari on opponent.

Definition at line 384 of file GoUctUtil.h.

References GoEyeUtil::MakesNakadeShape(), MUTUAL_ATARI_LIMIT, GoEyeUtil::NAKADE_LIMIT, SgBalancer::Play(), GoBoardUtil::SelfAtari(), GoBoardUtil::SelfAtariForColor(), SG_ASSERT, and SgOppBW().

Referenced by GeneratePoint().

void GoUctUtil::SaveTree	(	const SgUctTree &	tree,
		int	boardSize,
		const SgBWSet &	stones,
		SgBlackWhite	toPlay,
		std::ostream &	out,
		int	maxDepth = `-1`
	)

Save tree contained in a search as a Go SGF file.

The SGF file is written directly without using SgGameWriter to avoid a memory-intensive construction of an intermediate game tree.

Parameters:

	tree	The tree
	boardSize	The size of the board
	stones	The Go position corresponding to the root node of the tree
	toPlay	The color toPlay at the root node of the tree
	out	The stream to save to tree to
	maxDepth	Only save tree to a certain depth. -1 means no limit.

Definition at line 215 of file GoUctUtil.cpp.

References PointToSgfString(), SgUctTree::Root(), SG_BLACK, SG_PROPPOINTFMT_GO, and SgPointSet::Size().

template<class BOARD >

SgPoint GoUctUtil::SelectRandom	(	const BOARD &	bd,
		SgBlackWhite	toPlay,
		GoPointList &	emptyPts,
		SgRandom &	random,
		SgBalancer &	balancer
	)

Select a random move from a list of empty points.

The check if GeneratePoint() returns true for the point is done after the random selection to avoid calling this function for every point in the list. If GeneratePoint() returns false, the point is removed from the list and the process is repeated.

Parameters:

	bd	The board
	toPlay	The color to generate the move for
	emptyPts	The list of empty points (will potentially be modified in this function for efficiency reasons)
	random	The random generator
	balancer	The balancer used in GeneratePoint()