Common algorithm for static safety. More...

#include <GoStaticSafetySolver.h>

Inheritance diagram for GoStaticSafetySolver:

Public Member Functions
	GoStaticSafetySolver (const GoBoard &board, GoRegionBoard *regions=0)
	Constructor.
virtual	~GoStaticSafetySolver ()
	Destructor, deallocates if there are own regions.
Accessors

const GoBoard &	Board () const
	our board
Forwarding accessors for GoRegionBoard

virtual bool	UpToDate () const
	See GoRegionBoard::UpToDate.
const GoRegionBoard *	Regions () const
	our regions
Protected Member Functions
GoRegionBoard *	Regions ()
	our regions
virtual void	FindTestSets (SgVectorOf< SgVectorOf< GoBlock > > *sets, SgBlackWhite color) const
	Main step of Benson's algorithm.
virtual void	FindClosure (SgVectorOf< GoBlock > *blocks) const
	Compute closure of blocks set for Benson's algorithm.
virtual void	GenBlocksRegions ()
	Compute all GoBlock's and GoRegion's on board.
virtual bool	RegionHealthyForBlock (const GoRegion &r, const GoBlock &b) const
	Is r healthy for b? Implements Benson, override for better tests Benson's classic healthyness test: all empty points of region must be liberties of the block.
virtual void	FindSafePoints (SgBWSet *safe)
	Main function, compute all safe points on board.
virtual void	FindHealthy ()
	Find healthy regions for block, calls RegionHealthyForBlock.
void	TestAlive (SgVectorOf< GoBlock > blocks, SgBWSet safe, SgBlackWhite color)
	Test if list of Benson blocks forms a living group.
void	TestAdjacent (SgVectorOf< GoRegion > *regions, const SgVectorOf< GoBlock > &blocks) const
	Reduce regions: keep only if completely surrounded by blocks.
Private Member Functions
	GoStaticSafetySolver (const GoStaticSafetySolver &)
	not implemented
GoStaticSafetySolver &	operator= (const GoStaticSafetySolver &)
	not implemented
Private Attributes
const GoBoard &	m_board
	The board we are computing on.
GoRegionBoard *	m_regions
	Contains the GoRegion's and GoBlock's we are using.
bool	m_allocRegion
	Did we allocate the GoRegionBoard or did the user supply it?

Detailed Description

Common algorithm for static safety.

The algorithm is used to implement both Benson's algorithm for unconditional safety and a solver using the extended 1-vitality and 2-vitality definitions from Martin Mueller's thesis [Mueller 95, p. 62-63] and from [Mueller 97b].

Definition at line 20 of file GoStaticSafetySolver.h.

Constructor & Destructor Documentation

GoStaticSafetySolver::GoStaticSafetySolver	(	const GoBoard &	board,
		GoRegionBoard *	regions = `0`
	)

Constructor.

If regions = 0, allocates own.

Definition at line 18 of file GoStaticSafetySolver.cpp.

References m_regions.

GoStaticSafetySolver::~GoStaticSafetySolver ( ) [virtual]

Destructor, deallocates if there are own regions.

Definition at line 29 of file GoStaticSafetySolver.cpp.

References m_allocRegion, and m_regions.

GoStaticSafetySolver::GoStaticSafetySolver ( const GoStaticSafetySolver & ) [private]

not implemented

Member Function Documentation

const GoBoard & GoStaticSafetySolver::Board ( ) const

our board

Definition at line 109 of file GoStaticSafetySolver.h.

References m_board.

Referenced by GoSafetySolver::FindSafePair(), GoSafetySolver::FindSurroundedSingleRegion(), GoSafetySolver::GenBlocksRegions(), GoSafetySolver::Test2Vital(), and GoSafetySolver::UpToDate().

void GoStaticSafetySolver::FindClosure ( SgVectorOf< GoBlock > * blocks ) const [protected, virtual]

Compute closure of blocks set for Benson's algorithm.

Expand set of blocks until all blocks adjacent to all adjacent regions are in set. see [Benson] for explanation.

Reimplemented in GoSafetySolver.

Definition at line 161 of file GoStaticSafetySolver.cpp.

References SgVectorOf< T >::Back(), GoRegion::Blocks(), SgVectorOf< T >::Contains(), GoBlock::Healthy(), SgVectorOf< T >::NonEmpty(), SgVectorOf< T >::PopBack(), and SgVectorOf< T >::PushBack().

Referenced by FindTestSets().

void GoStaticSafetySolver::FindHealthy ( ) [protected, virtual]

Find healthy regions for block, calls RegionHealthyForBlock.

Reimplemented in GoSafetySolver.

Definition at line 58 of file GoStaticSafetySolver.cpp.

References GoRegion::Blocks(), RegionHealthyForBlock(), Regions(), and GoRegionBoard::SetComputedHealthy().

Referenced by FindSafePoints().

void GoStaticSafetySolver::FindSafePoints ( SgBWSet * safe ) [protected, virtual]

Main function, compute all safe points on board.

Reimplemented in GoBensonSolver, and GoSafetySolver.

Definition at line 206 of file GoStaticSafetySolver.cpp.

References FindHealthy(), FindTestSets(), GenBlocksRegions(), GO_REGION_SAFE, Regions(), GoRegionBoard::SetComputedFlagForAll(), and TestAlive().

void GoStaticSafetySolver::FindTestSets	(	SgVectorOf< SgVectorOf< GoBlock > > *	sets,
		SgBlackWhite	color
	)			const `[protected, virtual]`

Main step of Benson's algorithm.

Reimplemented in GoSafetySolver.

Definition at line 184 of file GoStaticSafetySolver.cpp.

References FindClosure(), SgVectorOf< T >::PushBack(), Regions(), and SG_ASSERT.

Referenced by FindSafePoints().

void GoStaticSafetySolver::GenBlocksRegions ( ) [protected, virtual]

Compute all GoBlock's and GoRegion's on board.

Reimplemented in GoSafetySolver.

Definition at line 47 of file GoStaticSafetySolver.cpp.

References GoRegionBoard::GenBlocksRegions(), Regions(), GoRegionBoard::ReInitializeBlocksRegions(), and UpToDate().

Referenced by FindSafePoints().

GoStaticSafetySolver& GoStaticSafetySolver::operator= ( const GoStaticSafetySolver & ) [private]

not implemented

bool GoStaticSafetySolver::RegionHealthyForBlock	(	const GoRegion &	r,
		const GoBlock &	b
	)			const `[protected, virtual]`

Is r healthy for b? Implements Benson, override for better tests Benson's classic healthyness test: all empty points of region must be liberties of the block.

Reimplemented in GoSafetySolver.

Definition at line 36 of file GoStaticSafetySolver.cpp.

References GoBlock::AllEmptyAreLiberties(), and GoRegion::Points().

Referenced by FindHealthy().

GoRegionBoard * GoStaticSafetySolver::Regions ( ) [protected]

our regions

Definition at line 114 of file GoStaticSafetySolver.h.

References m_regions, and SG_ASSERT.

const GoRegionBoard * GoStaticSafetySolver::Regions ( ) const

void GoStaticSafetySolver::TestAdjacent	(	SgVectorOf< GoRegion > *	regions,
		const SgVectorOf< GoBlock > &	blocks
	)			const `[protected]`

Reduce regions: keep only if completely surrounded by blocks.

Definition at line 81 of file GoStaticSafetySolver.cpp.

References SgVectorOf< T >::PushBack().

Referenced by TestAlive().

void GoStaticSafetySolver::TestAlive	(	SgVectorOf< GoBlock > *	blocks,
		SgBWSet *	safe,
		SgBlackWhite	color
	)			`[protected]`

Test if list of Benson blocks forms a living group.

Each block must have a sure liberty count of at least 2. A region provides one sure liberty if it is healthy and its boundary consists only of blocks in the list.

Definition at line 91 of file GoStaticSafetySolver.cpp.

References GoSafetyUtil::AddToSafe(), SgVectorOf< T >::Clear(), GoBlock::Color(), SgVectorOf< T >::Contains(), SgVectorOf< T >::Exclude(), SgVectorOf< T >::Front(), m_board, SgVectorOf< T >::MinLength(), SgVectorOf< T >::NonEmpty(), SgVectorOf< T >::PushBack(), Regions(), SG_ASSERT, SG_DEBUG_ONLY, and TestAdjacent().