Benson's classic algorithm for finding unconditionally alive blocks. More...
#include <GoBensonSolver.h>
Public Member Functions | |
| GoBensonSolver (GoBoard &board, GoRegionBoard *regions=0) | |
| If regions = 0, creates its own. | |
| void | FindSafePoints (SgBWSet *safe) |
| Main function, compute safe points. | |
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 | 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. | |
Detailed Description
Benson's classic algorithm for finding unconditionally alive blocks.
Definition at line 20 of file GoBensonSolver.h.
Constructor & Destructor Documentation
| GoBensonSolver::GoBensonSolver | ( | GoBoard & | board, | |
| GoRegionBoard * | regions = 0 | |||
| ) | [explicit] |
If regions = 0, creates its own.
Definition at line 24 of file GoBensonSolver.h.
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 GoSafetySolver::FindSafePair(), GoSafetySolver::FindSurroundedSingleRegion(), GoSafetySolver::GenBlocksRegions(), GoSafetySolver::Test2Vital(), and GoSafetySolver::UpToDate().
| void GoStaticSafetySolver::FindClosure | ( | SgVectorOf< GoBlock > * | blocks | ) | const [protected, virtual, inherited] |
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 GoStaticSafetySolver::FindTestSets().
| void GoStaticSafetySolver::FindHealthy | ( | ) | [protected, virtual, inherited] |
Find healthy regions for block, calls RegionHealthyForBlock.
Reimplemented in GoSafetySolver.
Definition at line 58 of file GoStaticSafetySolver.cpp.
References GoRegion::Blocks(), GoStaticSafetySolver::RegionHealthyForBlock(), GoStaticSafetySolver::Regions(), and GoRegionBoard::SetComputedHealthy().
Referenced by GoStaticSafetySolver::FindSafePoints().
| void GoBensonSolver::FindSafePoints | ( | SgBWSet * | safe | ) | [virtual] |
Main function, compute safe points.
Reimplemented from GoStaticSafetySolver.
Definition at line 19 of file GoBensonSolver.cpp.
References SgBWSet::Clear(), GoStaticSafetySolver::Regions(), and GoSafetyUtil::WriteStatistics().
Referenced by GoSafetyCommands::GetSafe().
| void GoStaticSafetySolver::FindTestSets | ( | SgVectorOf< SgVectorOf< GoBlock > > * | sets, | |
| SgBlackWhite | color | |||
| ) | const [protected, virtual, inherited] |
Main step of Benson's algorithm.
Reimplemented in GoSafetySolver.
Definition at line 184 of file GoStaticSafetySolver.cpp.
References GoStaticSafetySolver::FindClosure(), SgVectorOf< T >::PushBack(), GoStaticSafetySolver::Regions(), and SG_ASSERT.
Referenced by GoStaticSafetySolver::FindSafePoints().
| void GoStaticSafetySolver::GenBlocksRegions | ( | ) | [protected, virtual, inherited] |
Compute all GoBlock's and GoRegion's on board.
Reimplemented in GoSafetySolver.
Definition at line 47 of file GoStaticSafetySolver.cpp.
References GoRegionBoard::GenBlocksRegions(), GoStaticSafetySolver::Regions(), GoRegionBoard::ReInitializeBlocksRegions(), and GoStaticSafetySolver::UpToDate().
Referenced by GoStaticSafetySolver::FindSafePoints().
| bool GoStaticSafetySolver::RegionHealthyForBlock | ( | const GoRegion & | r, | |
| const GoBlock & | b | |||
| ) | const [protected, virtual, inherited] |
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 GoStaticSafetySolver::FindHealthy().
| const GoRegionBoard * GoStaticSafetySolver::Regions | ( | ) | const [inherited] |
our regions
Definition at line 120 of file GoStaticSafetySolver.h.
References GoStaticSafetySolver::m_regions, and SG_ASSERT.
Referenced by GoSafetySolver::Find2VitalAreas(), GoStaticSafetySolver::FindHealthy(), GoSafetySolver::FindHealthy(), GoSafetySolver::FindSafePair(), GoStaticSafetySolver::FindSafePoints(), GoSafetySolver::FindSafePoints(), FindSafePoints(), GoSafetySolver::FindSurroundedRegionPair(), GoSafetySolver::FindSurroundedSafeAreas(), GoSafetySolver::FindSurroundedSingleRegion(), GoStaticSafetySolver::FindTestSets(), GoSafetySolver::FindTestSets(), GoStaticSafetySolver::GenBlocksRegions(), GoSafetySolver::GenBlocksRegions(), GoSafetySolver::Merge(), GoStaticSafetySolver::TestAlive(), and GoStaticSafetySolver::UpToDate().
| GoRegionBoard * GoStaticSafetySolver::Regions | ( | ) | [protected, inherited] |
our regions
Definition at line 114 of file GoStaticSafetySolver.h.
References GoStaticSafetySolver::m_regions, and SG_ASSERT.
| 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().
Referenced by GoStaticSafetySolver::FindSafePoints().
| bool GoStaticSafetySolver::UpToDate | ( | ) | const [virtual, inherited] |
Reimplemented in GoSafetySolver.
Definition at line 42 of file GoStaticSafetySolver.cpp.
References GoStaticSafetySolver::Regions(), and GoRegionBoard::UpToDate().
Referenced by GoStaticSafetySolver::GenBlocksRegions().
The documentation for this class was generated from the following files: