Improved static detection of safe blocks and regions Uses static rules to find 1-vital, 2-vital and safely surrounded areas. More...

#include <GoSafetySolver.h>

Inheritance diagram for GoSafetySolver:

[legend]

List of all members.

Public Member Functions
	GoSafetySolver (GoBoard &board, GoRegionBoard *regions=0)
	Constructor,.
void	FindSafePoints (SgBWSet *safe)
	Main function, compute safe points.
virtual void	FindSurroundedSafeAreas (SgBWSet *safe, SgBlackWhite color)
	Find areas surrounded by safe blocks where the opponent cannot live.
virtual void	FindHealthy ()
	call virtual RegionHealthyForBlock
virtual bool	UpToDate () const
	Check if internal state matches board.
Accessors

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

const GoRegionBoard *	Regions () const
	our regions
Protected Member Functions
virtual bool	RegionHealthyForBlock (const GoRegion &r, const GoBlock &b) const
	See GoStaticSafetySolver::RegionHealthyForBlock.
virtual void	GenBlocksRegions ()
	Compute all GoBlock's, GoChain's and GoRegion's on m_board.
virtual void	FindClosure (SgVectorOf< GoBlock > *blocks) const
	Like.
virtual void	FindTestSets (SgVectorOf< SgVectorOf< GoBlock > > *sets, SgBlackWhite color) const
	Like.
virtual void	Test2Vital (GoRegion r, SgBWSet safe)
	static test if r is 2-vital.
void	Find2VitalAreas (SgBWSet *safe)
	call Test2Vital for regions, add 2-vital ones to safe set
bool	FindSafePair (SgBWSet safe, SgBlackWhite color, const SgPointSet &anySafe, const GoRegion r1)
	try to find a safe pair of regions r1 + other, call AddToSafe()
void	Merge (GoChain c1, GoChain c2, GoRegion *r, bool bySearch)
	create new chain representing both chains connected in this region
GoRegionBoard *	Regions ()
	our regions
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
bool	FindSurroundedRegionPair (SgBWSet *safe, SgBlackWhite color)
	find pairs of regions that are safe together.
bool	FindSurroundedSingleRegion (SgBWSet *safe, SgBlackWhite color)
	Find new safe region.
Private Attributes
SgHashCode	m_code
	for chain info

Detailed Description

Improved static detection of safe blocks and regions Uses static rules to find 1-vital, 2-vital and safely surrounded areas.

Definition at line 18 of file GoSafetySolver.h.

Constructor & Destructor Documentation

GoSafetySolver::GoSafetySolver	(	GoBoard &	board,
		GoRegionBoard *	regions = `0`
	)			`[explicit]`

Constructor,.

See also:: GoStaticSafetySolver

Definition at line 22 of file GoSafetySolver.h.

References SgHash< N >::Invalidate(), and m_code.

Member Function Documentation

const GoBoard & GoStaticSafetySolver::Board ( ) const [inherited]

our board

Definition at line 109 of file GoStaticSafetySolver.h.

References GoStaticSafetySolver::m_board.

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

void GoSafetySolver::Find2VitalAreas ( SgBWSet * safe ) [protected]

call Test2Vital for regions, add 2-vital ones to safe set

Definition at line 113 of file GoSafetySolver.cpp.

References SgBWSet::AssertDisjoint(), GoStaticSafetySolver::Regions(), SG_BLACK, SG_WHITE, and Test2Vital().

Referenced by FindSafePoints().

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

Like.

See also:: GoStaticSafetySolver::FindClosure, but uses GoChain's

Reimplemented from GoStaticSafetySolver.

Definition at line 59 of file GoSafetySolver.cpp.

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

Referenced by FindTestSets().

void GoSafetySolver::FindHealthy ( ) [virtual]

call virtual RegionHealthyForBlock

Reimplemented from GoStaticSafetySolver.

Definition at line 32 of file GoSafetySolver.cpp.

References GoRegion::Chains(), GO_REGION_STATIC_1VITAL, RegionHealthyForBlock(), and GoStaticSafetySolver::Regions().

bool GoSafetySolver::FindSafePair	(	SgBWSet *	safe,
		SgBlackWhite	color,
		const SgPointSet &	anySafe,
		const GoRegion *	r1
	)			`[protected]`

try to find a safe pair of regions r1 + other, call AddToSafe()

Definition at line 146 of file GoSafetySolver.cpp.

References GoSafetyUtil::AddToSafe(), SgBWSet::AssertDisjoint(), GoRegion::Blocks(), GoStaticSafetySolver::Board(), GoSafetyUtil::IsTerritory(), SgPointSet::Overlaps(), GoRegion::Points(), GoStaticSafetySolver::Regions(), and GoRegionBoard::SetSafeFlags().

Referenced by FindSurroundedRegionPair().

void GoSafetySolver::FindSafePoints ( SgBWSet * safe ) [virtual]

Main function, compute safe points.

Reimplemented from GoStaticSafetySolver.

Definition at line 219 of file GoSafetySolver.cpp.

References SgBWSet::AssertDisjoint(), Find2VitalAreas(), FindSurroundedSafeAreas(), GoStaticSafetySolver::Regions(), and GoSafetyUtil::WriteStatistics().

Referenced by GoSafetyCommands::CmdDameStatic(), GoSafetyCommands::GetSafe(), and GoSafetyUtil::GetWinner().

bool GoSafetySolver::FindSurroundedRegionPair	(	SgBWSet *	safe,
		SgBlackWhite	color
	)			`[private]`

find pairs of regions that are safe together.

Definition at line 175 of file GoSafetySolver.cpp.

References SgBWSet::Both(), FindSafePair(), GoRegion::GetFlag(), GO_REGION_SAFE, SgPointSet::Overlaps(), GoRegion::Points(), GoStaticSafetySolver::Regions(), and GoRegion::SomeBlockIsSafe().

Referenced by FindSurroundedSafeAreas().

void GoSafetySolver::FindSurroundedSafeAreas	(	SgBWSet *	safe,
		SgBlackWhite	color
	)			`[virtual]`

Find areas surrounded by safe blocks where the opponent cannot live.

Definition at line 131 of file GoSafetySolver.cpp.

References FindSurroundedRegionPair(), FindSurroundedSingleRegion(), GoStaticSafetySolver::Regions(), and GoRegionBoard::SetSafeFlags().

Referenced by FindSafePoints().

bool GoSafetySolver::FindSurroundedSingleRegion	(	SgBWSet *	safe,
		SgBlackWhite	color
	)			`[private]`

Find new safe region.

Definition at line 193 of file GoSafetySolver.cpp.

References GoSafetyUtil::AddToSafe(), GoStaticSafetySolver::Board(), SgBWSet::Both(), GoSafetyUtil::ExtendedIsTerritory(), GoRegion::GetFlag(), GO_REGION_SAFE, SgPointSet::Overlaps(), GoRegion::Points(), GoRegion::PointsPlusInteriorBlocks(), GoStaticSafetySolver::Regions(), GoRegionBoard::SetSafeFlags(), and GoRegion::SomeBlockIsSafe().

Referenced by FindSurroundedSafeAreas().

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

Like.

See also:: GoStaticSafetySolver::FindTestSets, but uses GoChain's

Reimplemented from GoStaticSafetySolver.

Definition at line 77 of file GoSafetySolver.cpp.

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

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

Compute all GoBlock's, GoChain's and GoRegion's on m_board.

Reimplemented from GoStaticSafetySolver.

Definition at line 305 of file GoSafetySolver.cpp.

References SgVectorOf< T >::Back(), GoStaticSafetySolver::Board(), GoRegion::Chains(), GoRegion::ComputeFlag(), GoRegion::Find2Mergable(), SgVectorOf< T >::Front(), GoRegionBoard::GenChains(), GoRegion::GetFlag(), GoBoard::GetHashCode(), GO_REGION_CORRIDOR, GO_REGION_STATIC_1VC, GO_REGION_STATIC_1VITAL, GO_REGION_USED_FOR_MERGE, GoRegion::Has2Conn(), SgVectorOf< T >::IsLength(), m_code, Merge(), GoStaticSafetySolver::Regions(), and UpToDate().

void GoSafetySolver::Merge	(	GoChain *	c1,
		GoChain *	c2,
		GoRegion *	r,
		bool	bySearch
	)			`[protected]`

create new chain representing both chains connected in this region

Definition at line 250 of file GoSafetySolver.cpp.

References GoRegionBoard::AllChains(), GoBlock::Color(), GoRegion::ComputeFlag(), SgVectorOf< T >::Exclude(), GoRegion::Find2FreeLibs(), GoRegion::GetFlag(), GO_CHAIN_BY_SEARCH, GO_CHAIN_TWO_LIBERTIES_IN_REGION, GO_REGION_STATIC_1VITAL, GO_REGION_USED_FOR_MERGE, SgVectorOf< T >::Include(), GoStaticSafetySolver::Regions(), GoRegion::ReInitialize(), GoRegion::ReplaceChain(), GoRegion::SetFlag(), SG_ASSERT, SgDebug(), and GoChain::WriteID().

Referenced by GenBlocksRegions().

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

See GoStaticSafetySolver::RegionHealthyForBlock.

This implementation uses 1-vital information

Reimplemented from GoStaticSafetySolver.

Definition at line 98 of file GoSafetySolver.cpp.

References GoRegion::GetFlag(), and GO_REGION_STATIC_1VITAL.

Referenced by FindHealthy().

const GoRegionBoard * GoStaticSafetySolver::Regions ( ) const [inherited]

GoRegionBoard * GoStaticSafetySolver::Regions ( ) [protected, inherited]

our regions

Definition at line 114 of file GoStaticSafetySolver.h.

References GoStaticSafetySolver::m_regions, and SG_ASSERT.

void GoSafetySolver::Test2Vital	(	GoRegion *	r,
		SgBWSet *	safe
	)			`[protected, virtual]`

static test if r is 2-vital.

If yes add to safe set

Definition at line 106 of file GoSafetySolver.cpp.

References GoSafetyUtil::AddToSafe(), GoStaticSafetySolver::Board(), GoRegion::Color(), GoRegion::ComputeAndGetFlag(), GO_REGION_STATIC_2V, and GoRegion::Points().

Referenced by Find2VitalAreas().

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

Reduce regions: keep only if completely surrounded by blocks.

Definition at line 81 of file GoStaticSafetySolver.cpp.

References SgVectorOf< T >::PushBack().

Referenced by GoStaticSafetySolver::TestAlive().

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

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(), GoStaticSafetySolver::m_board, SgVectorOf< T >::MinLength(), SgVectorOf< T >::NonEmpty(), SgVectorOf< T >::PushBack(), GoStaticSafetySolver::Regions(), SG_ASSERT, SG_DEBUG_ONLY, and GoStaticSafetySolver::TestAdjacent().