Randomly select from empty points on the board. More...

#include <GoUctPureRandomGenerator.h>

Public Member Functions
	GoUctPureRandomGenerator (const BOARD &bd, SgRandom &random)
void	Start ()
	Finds and shuffles the empty points currently on the board.
void	OnPlay ()
	Update state.
const std::vector< SgPoint > &	Candidates () const
	Return a list of points that are currently potentially empty.
SgPoint	Generate (SgBalancer &balancer)
	Generate a pure random move.
SgPoint	GenerateFillboardMove (int numberTries)
	Generate a move using the fillboard heuristic.
Private Member Functions
bool	Empty3x3 (SgPoint p) const
void	CheckConsistency () const
void	Insert (SgPoint p)
	Insert new candidate at random place.
Private Attributes
const BOARD &	m_bd
float	m_invNuPoints
float	m_nuEmptyFloat
SgRandom &	m_random
std::vector< SgPoint >	m_candidates
	Points that are potentially empty.

Detailed Description

template<class BOARD>
class GoUctPureRandomGenerator< BOARD >

Randomly select from empty points on the board.

Finds and shuffles the empty points on the board at the beginning to avoid repeated loops over the board to find empty points.

Note:: For efficiency reasons, newly occupied points are not immediately removed from the list but only checked at the time of move generation. This can cause a deviation from a uniform probability distribution if those points become empty because of capture before they are generated. Experiments have shown that this does not impact the playing strength (as in other cases in the playout policy where the computational cost for a fully uniform distribution outweighs its benfits, e.g. GoUctPlayoutPolicy does not filter duplicate points in the move lists generated by patterns). Even a constant time algorithm for removing points from the list is slower than the current implementation.

Definition at line 29 of file GoUctPureRandomGenerator.h.

Constructor & Destructor Documentation

template<class BOARD>

GoUctPureRandomGenerator< BOARD >::GoUctPureRandomGenerator	(	const BOARD &	bd,
		SgRandom &	random
	)

Definition at line 88 of file GoUctPureRandomGenerator.h.

References GO_MAX_NUM_MOVES, and GoUctPureRandomGenerator< BOARD >::m_candidates.

Member Function Documentation

template<class BOARD >

const std::vector< SgPoint > & GoUctPureRandomGenerator< BOARD >::Candidates ( ) const

Return a list of points that are currently potentially empty.

As a side-benefit, the generator can be used to get the list of empty points on the board to speed up full-board loops over empty points or to get a shuffled list of the empty points (e.g. for finding legal moves when expanding a node in the in-tree-phase of UCT). Points in the list are candidates, they still have to be tested, if they are really empty.

Definition at line 98 of file GoUctPureRandomGenerator.h.

References GoUctPureRandomGenerator< BOARD >::m_candidates.

template<class BOARD >

void GoUctPureRandomGenerator< BOARD >::CheckConsistency ( ) const [private]

Definition at line 105 of file GoUctPureRandomGenerator.h.

References GoUctPureRandomGenerator< BOARD >::m_bd, GoUctPureRandomGenerator< BOARD >::m_candidates, SG_ASSERT, and SgDebug().

Referenced by GoUctPureRandomGenerator< BOARD >::Generate(), GoUctPureRandomGenerator< BOARD >::OnPlay(), and GoUctPureRandomGenerator< BOARD >::Start().

template<class BOARD >

bool GoUctPureRandomGenerator< BOARD >::Empty3x3 ( SgPoint p ) const [private]

Definition at line 130 of file GoUctPureRandomGenerator.h.

References GoUctPureRandomGenerator< BOARD >::m_bd.

Referenced by GoUctPureRandomGenerator< BOARD >::GenerateFillboardMove().

template<class BOARD >

SgPoint GoUctPureRandomGenerator< BOARD >::Generate ( SgBalancer & balancer )

Generate a pure random move.

Randomly select an empty point on the board that fulfills GoUctUtil::GeneratePoint() for the color currently to play on the board.

Definition at line 138 of file GoUctPureRandomGenerator.h.

References GoUctPureRandomGenerator< BOARD >::CheckConsistency(), GoUctUtil::GeneratePoint(), GoUctPureRandomGenerator< BOARD >::m_bd, GoUctPureRandomGenerator< BOARD >::m_candidates, and SG_NULLMOVE.

template<class BOARD >

SgPoint GoUctPureRandomGenerator< BOARD >::GenerateFillboardMove ( int numberTries )

Generate a move using the fillboard heuristic.

Tries numberTries times to select a point on the board and returns it, if it is empty and all adjacent and diagonal neighbors are empty. Otherwise it returns SG_NULLMOVE. Using this heuristic before any other heuristics is helpful to increase playout diversity on large boards. See section 6.1 of: Chatriot, Gelly, Hoock, Perez, Rimmel, Teytaud: Combining expert, offline, transient and online learning in Monte-Carlo exploration

Definition at line 166 of file GoUctPureRandomGenerator.h.

References GoUctPureRandomGenerator< BOARD >::Empty3x3(), GoUctPureRandomGenerator< BOARD >::m_bd, GoUctPureRandomGenerator< BOARD >::m_candidates, GoUctPureRandomGenerator< BOARD >::m_invNuPoints, GoUctPureRandomGenerator< BOARD >::m_nuEmptyFloat, GoUctPureRandomGenerator< BOARD >::m_random, SG_NULLMOVE, and SgRandom::SmallInt().