#include <GoStaticSafetySolver.h>
Inheritance diagram for GoStaticSafetySolver:
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 22 of file GoStaticSafetySolver.h.
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? | |
| GoStaticSafetySolver::GoStaticSafetySolver | ( | const GoBoard & | board, | |
| GoRegionBoard * | regions = 0 | |||
| ) |
Constructor.
If regions = 0, allocates own.
Definition at line 19 of file GoStaticSafetySolver.cpp.
References m_regions.
| GoStaticSafetySolver::~GoStaticSafetySolver | ( | ) | [virtual] |
Destructor, deallocates if there are own regions.
Definition at line 30 of file GoStaticSafetySolver.cpp.
References m_allocRegion, and m_regions.
| GoStaticSafetySolver::GoStaticSafetySolver | ( | const GoStaticSafetySolver & | ) | [private] |
not implemented
| const GoBoard & GoStaticSafetySolver::Board | ( | ) | const |
our board
Definition at line 114 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 162 of file GoStaticSafetySolver.cpp.
References SgVectorOf< T >::Back(), SgVectorOf< T >::Contains(), 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 59 of file GoStaticSafetySolver.cpp.
References 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 207 of file GoStaticSafetySolver.cpp.
References FindHealthy(), FindTestSets(), GenBlocksRegions(), GO_REGION_SAFE, Regions(), GoRegionBoard::SetComputedFlagForAll(), and TestAlive().
Referenced by GoSafetySolver::FindSafePoints(), and GoBensonSolver::FindSafePoints().
| void GoStaticSafetySolver::FindTestSets | ( | SgVectorOf< SgVectorOf< GoBlock > > * | sets, | |
| SgBlackWhite | color | |||
| ) | const [protected, virtual] |
Main step of Benson's algorithm.
Reimplemented in GoSafetySolver.
Definition at line 185 of file GoStaticSafetySolver.cpp.
References FindClosure(), 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 48 of file GoStaticSafetySolver.cpp.
References GoRegionBoard::GenBlocksRegions(), Regions(), GoRegionBoard::ReInitializeBlocksRegions(), and UpToDate().
Referenced by FindSafePoints(), and GoSafetySolver::GenBlocksRegions().
| 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 37 of file GoStaticSafetySolver.cpp.
References GoBlock::AllEmptyAreLiberties(), and GoRegion::Points().
Referenced by FindHealthy(), and GoSafetySolver::RegionHealthyForBlock().
| GoRegionBoard * GoStaticSafetySolver::Regions | ( | ) | [protected] |
| const GoRegionBoard * GoStaticSafetySolver::Regions | ( | ) | const |
our regions
Definition at line 125 of file GoStaticSafetySolver.h.
References m_regions, and SG_ASSERT.
Referenced by GoSafetySolver::Find2VitalAreas(), FindHealthy(), GoSafetySolver::FindHealthy(), GoSafetySolver::FindSafePair(), FindSafePoints(), GoSafetySolver::FindSafePoints(), GoBensonSolver::FindSafePoints(), GoSafetySolver::FindSurroundedRegionPair(), GoSafetySolver::FindSurroundedSafeAreas(), GoSafetySolver::FindSurroundedSingleRegion(), FindTestSets(), GoSafetySolver::FindTestSets(), GenBlocksRegions(), GoSafetySolver::GenBlocksRegions(), GoSafetySolver::Merge(), TestAlive(), and UpToDate().
| void GoStaticSafetySolver::TestAdjacent | ( | SgVectorOf< GoRegion > * | regions, | |
| const SgVectorOf< GoBlock > & | blocks | |||
| ) | const [protected] |
Reduce regions: keep only if completely surrounded by blocks.
Definition at line 82 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 92 of file GoStaticSafetySolver.cpp.
References GoSafetyUtil::AddToSafe(), SgVectorOf< T >::Clear(), m_board, SgVectorOf< T >::NonEmpty(), SgVectorOf< T >::PushBack(), Regions(), SG_ASSERT, SG_DEBUG_ONLY, and TestAdjacent().
Referenced by FindSafePoints().
| bool GoStaticSafetySolver::UpToDate | ( | ) | const [virtual] |
Reimplemented in GoSafetySolver.
Definition at line 43 of file GoStaticSafetySolver.cpp.
References Regions(), and GoRegionBoard::UpToDate().
Referenced by GenBlocksRegions(), and GoSafetySolver::UpToDate().
bool GoStaticSafetySolver::m_allocRegion [private] |
Did we allocate the GoRegionBoard or did the user supply it?
Definition at line 104 of file GoStaticSafetySolver.h.
Referenced by ~GoStaticSafetySolver().
const GoBoard& GoStaticSafetySolver::m_board [private] |
The board we are computing on.
Definition at line 98 of file GoStaticSafetySolver.h.
Referenced by Board(), and TestAlive().
GoRegionBoard* GoStaticSafetySolver::m_regions [private] |
Contains the GoRegion's and GoBlock's we are using.
Definition at line 101 of file GoStaticSafetySolver.h.
Referenced by GoStaticSafetySolver(), Regions(), and ~GoStaticSafetySolver().