Index   Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

GoRegion Class Reference

#include <GoRegion.h>

List of all members.

Detailed Description

GoRegion represents a region surrounded by blocks of one color.

Each empty point, and each point occupied by white, is contained in exactly one black region. Similarly each empty point, and each point occupied by black, is contained in exactly one white region.

A region keeps data such as its color, the blocks and chains of its color, the eye status, and a strategy to follow to keep the region safe.

Regions can provide liberties for its boundary blocks. They can be "1-vital" or "2-vital". This is used by safety solvers. For details see [Mueller 1997]: Playing it safe: Recognizing secure territories in computer Go by using static rules and search. In H. Matsubara, editor, Game Programming Workshop in Japan '97, pages 80-86, Computer Shogi Association, Tokyo, Japan, 1997.

Todo:
Avoid cyclic dependency with GoBlock

Definition at line 86 of file GoRegion.h.

Public Member Functions

 GoRegion (const GoBoard &board, const SgPointSet &points, SgBlackWhite color)
 Construct region on points in color.
 ~GoRegion ()
 Destructor.
void ReInitialize ()
 Clear all flags etc.
void CheckConsistency () const
 For debugging.
const SgPointSet & Points () const
 The points of the region.
SgPointSet Dep () const
 The dependency set, outside neighbors of m_points.
SgPointSet AllInsideLibs () const
 liberties not adjacent to boundary stones
const SgVectorOf< GoChain > & Chains () const
 Chains of region.
const SgVectorOf< GoBlock > & Blocks () const
 Blocks of region.
SgVectorOf< GoBlock > & BlocksNonConst ()
 Blocks of region.
SgVectorOf< GoBlock > InteriorBlocks () const
 Interior blocks of region: all liberties are in m_points.
bool IsInteriorBlock (const GoBlock *block) const
 Is block an interior block of this region?
bool IsBoundaryBlock (const GoBlock *block) const
 Is block a boundary block of this region?
SgPointSet BlocksPoints () const
 all points of region's blocks - even those not contained in Dep()
SgPointSet PointsPlusInteriorBlocks () const
 area of points plus interior blocks
SgBlackWhite Color () const
 color of region
int MinEyes () const
 minimum number of eyes in region
int MaxEyes () const
 maximum number of eyes in region
int MinPotEyes () const
 minimum number of potential eyes in region
int MaxPotEyes () const
 maximum number of potential eyes in region
void Write (std::ostream &out) const
 Write all information.
void WriteID (std::ostream &out) const
 Write short identifier.
bool GetFlag (GoRegionFlag flag) const
 get value of precomputed flag
bool ComputeAndGetFlag (GoRegionFlag flag)
 compute, then get value of precomputed flag
bool ComputedFlag (GoRegionFlag flag) const
 test if flag has been computed
void ComputeFlag (GoRegionFlag flag)
 compute the flag, set it to true or false
void ResetNonBlockFlags ()
 Only blocks are incrementally updated, others must be reset after move.
bool IsValid () const
 is region data valid?
void Invalidate ()
 reset valid flag, region data not current anymore
void ComputeBasicFlags ()
 Computes GO_REGION_SMALL, GO_REGION_CORRIDOR, GO_REGION_SINGLE_BLOCK_BOUNDARY, GO_REGION_STATIC_1VC, GO_REGION_STATIC_2V.
void DoComputeFlag (GoRegionFlag flag)
 compute flag
void SetComputedFlag (GoRegionFlag flag)
 mark that flag is computed now
void SetFlag (GoRegionFlag flag, bool value)
 set flag to value
void Set1VCDepth (int depth)
 store search depth used in ExVital1Task for 1vc search
bool Has2ConnForChains (const GoChain *c1, const GoChain *c2) const
 does region have two free (unused) liberties to connect chains?
bool Has2Conn () const
 call Has2ConnForBlocks for region with exactly two chains
bool HealthyForSomeBlock (const SgVectorOf< GoBlock > &blocks) const
 is this healthy for a block in list?
bool IsSurrounded (const SgVectorOf< GoBlock > &blocks) const
 Is region completely surrounded by blocks?
bool ComputedVitalForDepth (int depth) const
 did ExVital1Task have at least this search depth?
bool SomeBlockIsSafe () const
 is any adjacent block safe?
bool AllBlockIsSafe () const
 are all adjacent block safe?
bool AdjacentToBlock (SgPoint anchor) const
 Is block of anchor adjacent to region?
bool AdjacentToSomeBlock (const SgVector< SgPoint > &anchors) const
 Is one of blocks given by anchors adjacent to region?
bool Safe2Cuts (const GoBoard &board) const
 For flat region: cuts not occupied is enough to make region 1-vital.
bool AllEmptyAreLibs () const
 Test if all empty points are liberties of blocks.
bool Has2SureLibs (SgMiaiStrategy *miaiStrategy) const
 Test if points of region are 2-vital for color.
void InsideLibs (const GoBlock *b, SgVector< SgPoint > *libs) const
 block liberties in this region
bool HasBlockLibs (const GoBlock *b) const
 Is a liberty of b in region?
bool HasLibsForBlock (const GoBlock *b, int n) const
 Can a block get n libs inside region?
bool HasLibForAllBlocks () const
 Does each adjacent block have a liberty in region?
bool HasLibsForAllBlocks (int n) const
 Does each block have n liberties in region?
bool Find2ConnForAll () const
 Can we find two connection paths to each interior empty point? This implements only the simple, non-recursive case.
bool Find2ConnForAllInterior (SgMiaiStrategy *miaiStrategy, SgVector< SgPoint > &usedLibs) const
 find 2-connection paths for all interior empty points, using recursive extension.
bool Has2IPs (const SgVector< SgPoint > &interiorEmpty, SgMiaiPair *ips) const
 An IP divides a region into two eyes AND connects all surrounding blocks, this one defines that ip has to be adjancent to all interior points.
bool Has2IntersectionPoints (const SgVector< SgPoint > &usedLibs) const
 whether there are 2 intersection points, doesn't have to be adjacent to all interior points.
void GetIPs (SgVector< SgPoint > *ips) const
 Get all intersections points inside region.
void GetDivideMiaiPairs (SgVector< SgMiaiPair > &pairs) const
 Get all SgMiaiPairs that can divide the region.
void JointLibs (SgVector< SgPoint > *libs) const
 Compute joint liberties of all m_blocks.
bool IsCorridor () const
 See ExEye::IsCorridor().
bool ReplaceChain (const GoChain *old, const GoChain *newChain)
 update region if affected: old was merged into newChain
bool Find2Mergable (GoChain **c1, GoChain **c2) const
 chains are mergable if two connections are found
void Find2FreeLibs (const GoChain *c1, const GoChain *c2, SgPoint *lib1, SgPoint *lib2) const
 Find two so far unused liberties for connecting c1 and c2.
void FindBlocks (const GoRegionBoard &ra)
 Get blocks of color in area.
void SetBlocks (const SgVectorOf< GoBlock > &blocks)
 Set blocks for this region from pre-found blocks list.
void FindChains (const GoRegionBoard &ra)
 Get chain of color in area.
void SetToSafe ()
 Set safe flag for region.
void RemoveBlock (const GoBlock *b)
 For incremental update - block no longer adjacent.
void OnAddStone (SgPoint p)
 Stone was played: remove from m_points.
void OnRemoveStone (SgPoint p)
 Stone removed: add to m_points.

Static Public Member Functions

static void Fini ()
 class finalization

Private Member Functions

bool ProtectedCuts (const GoBoard &board) const
 A simple test if all cuts between blocks are protected.
bool ComputeIs1Vital () const
 Static test if region is 1-vital.
bool StaticIs1VitalAndConnected () const
 Static test if region is 1-vital and all blocks are connected.
void ComputeNakade ()
 Compute eye status for some standard small regions.
void ComputeSingleBlockEyeSpace ()
 Compute eye space for region having only 1 block.
void ComputeMultipleBlockEyeSpace ()
 Compute eye space for region having more than 1 block.
void ComputeEyeSpace ()
 Compute eye space for region.
void InteriorEmpty (SgVector< SgPoint > *interiorEmpty, int maxNu) const
 compute at most maxNu empty points in the interior

Private Attributes

const GoBoard & m_bd
 The board.
GoRegionFlags m_flags
 Flags describing attributes of region.
GoRegionFlags m_computedFlags
 Which flags have been computed?
SgPointSet m_points
 Points of region.
SgBlackWhite m_color
 Color of region = color of surrounding stones.
SgVectorOf< GoBlock > m_blocks
 Blocks of m_color adjacent to region.
SgVectorOf< GoChain > m_chains
 Chains of region.
GoEyeCount m_eyes
 Number of eyes in region.
SgPoint m_vitalPoint
 Point to change eye status.
int m_1vcDepth
 search depth used in ExVital1Task for 1vc search
SgMiaiStrategy m_miaiStrategy
 Miai strategy to keep region safe.

Static Private Attributes

static int s_alloc = 0
 debugging bookkeeping.
static int s_free = 0

Constructor & Destructor Documentation

GoRegion::GoRegion ( const GoBoard &  board,
const SgPointSet &  points,
SgBlackWhite  color 
)

Construct region on points in color.

Definition at line 76 of file GoRegion.cpp.

References s_alloc.

GoRegion::~GoRegion (  ) 

Destructor.

Definition at line 94 of file GoRegion.h.

References s_free.

Member Function Documentation

bool GoRegion::AdjacentToBlock ( SgPoint  anchor  )  const

Is block of anchor adjacent to region?

Definition at line 1235 of file GoRegion.cpp.

References m_blocks.

Referenced by CheckConsistency().

bool GoRegion::AdjacentToSomeBlock ( const SgVector< SgPoint > &  anchors  )  const

Is one of blocks given by anchors adjacent to region?

Definition at line 1225 of file GoRegion.cpp.

References SgVector< T >::Contains(), and m_blocks.

bool GoRegion::AllBlockIsSafe (  )  const

are all adjacent block safe?

Definition at line 1187 of file GoRegion.cpp.

References Blocks().

bool GoRegion::AllEmptyAreLibs (  )  const

Test if all empty points are liberties of blocks.

Todo:
does not test only for boundary block libs, but all libs.

Definition at line 123 of file GoRegion.cpp.

References Color(), GoBoard::HasNeighbors(), GoBoard::IsEmpty(), m_bd, and Points().

SgPointSet GoRegion::AllInsideLibs (  )  const

liberties not adjacent to boundary stones

Definition at line 408 of file GoRegion.cpp.

References GoBoard::AllEmpty(), Dep(), m_bd, m_points, and GoBoard::Size().

Referenced by Find2ConnForAll(), and Find2ConnForAllInterior().

const SgVectorOf<GoBlock>& GoRegion::Blocks (  )  const

Blocks of region.

Definition at line 130 of file GoRegion.h.

References m_blocks.

Referenced by AllBlockIsSafe(), Find2ConnForAll(), GoSafetySolver::FindSafePair(), GetDivideMiaiPairs(), GoRegionBoard::OnUndoneMove(), GoRegionBoard::RemoveRegion(), SomeBlockIsSafe(), and GoBlock::TestFor1Eye().

SgVectorOf<GoBlock>& GoRegion::BlocksNonConst (  ) 

Blocks of region.

Non const version used by GoRegionBoard.

Definition at line 138 of file GoRegion.h.

References m_blocks.

Referenced by GoRegionBoard::OnUndoneMove().

SgPointSet GoRegion::BlocksPoints (  )  const

all points of region's blocks - even those not contained in Dep()

Definition at line 1127 of file GoRegion.cpp.

References m_blocks.

const SgVectorOf<GoChain>& GoRegion::Chains (  )  const

Chains of region.

Definition at line 124 of file GoRegion.h.

References m_chains.

void GoRegion::CheckConsistency (  )  const

For debugging.

Definition at line 1202 of file GoRegion.cpp.

References AdjacentToBlock(), GoBoard::All(), Color(), m_bd, m_blocks, Points(), SG_ASSERT, and GoBoard::Size().

SgBlackWhite GoRegion::Color (  )  const

color of region

Definition at line 162 of file GoRegion.h.

References m_color.

Referenced by GoRegionBoard::AddRegion(), AllEmptyAreLibs(), CheckConsistency(), DoComputeFlag(), Find2ConnForAll(), FindBlocks(), FindChains(), InteriorEmpty(), IsCorridor(), GoRegionBoard::OnUndoneMove(), GoRegionBoard::PushStone(), GoRegionBoard::RemoveRegion(), ReplaceChain(), GoRegionBoard::SetRegionArrays(), GoSafetySolver::Test2Vital(), and WriteID().

bool GoRegion::ComputeAndGetFlag ( GoRegionFlag  flag  ) 

compute, then get value of precomputed flag

Definition at line 746 of file GoRegion.cpp.

References ComputeFlag(), IsValid(), m_flags, and SG_ASSERT.

Referenced by ComputeIs1Vital(), ComputeNakade(), and GoSafetySolver::Test2Vital().

void GoRegion::ComputeBasicFlags (  ) 

Computes GO_REGION_SMALL, GO_REGION_CORRIDOR, GO_REGION_SINGLE_BLOCK_BOUNDARY, GO_REGION_STATIC_1VC, GO_REGION_STATIC_2V.

Definition at line 1037 of file GoRegion.cpp.

References DoComputeFlag(), GO_REGION_CORRIDOR, GO_REGION_SINGLE_BLOCK_BOUNDARY, GO_REGION_SMALL, GO_REGION_STATIC_1VC, GO_REGION_STATIC_2V, GO_REGION_USED_FOR_MERGE, GO_REGION_VALID, IsValid(), m_flags, SetFlag(), and SG_ASSERT.

Referenced by GoRegionBoard::AddRegion(), and ReInitialize().

bool GoRegion::ComputedFlag ( GoRegionFlag  flag  )  const

test if flag has been computed

Definition at line 753 of file GoRegion.cpp.

References m_computedFlags.

Referenced by ComputedVitalForDepth(), and ComputeIs1Vital().

bool GoRegion::ComputedVitalForDepth ( int  depth  )  const

did ExVital1Task have at least this search depth?

Definition at line 1195 of file GoRegion.cpp.

References ComputedFlag(), GetFlag(), GO_REGION_1VC, GO_REGION_STATIC_1VC, and m_1vcDepth.

void GoRegion::ComputeEyeSpace (  )  [private]

Compute eye space for region.

Definition at line 966 of file GoRegion.cpp.

References ComputeMultipleBlockEyeSpace(), ComputeSingleBlockEyeSpace(), SgVectorOf< T >::IsLength(), and m_blocks.

void GoRegion::ComputeFlag ( GoRegionFlag  flag  ) 

compute the flag, set it to true or false

Definition at line 758 of file GoRegion.cpp.

References DoComputeFlag(), and m_computedFlags.

Referenced by ComputeAndGetFlag(), and GoSafetySolver::Merge().

bool GoRegion::ComputeIs1Vital (  )  const [private]

Static test if region is 1-vital.

Todo:
explain the algorithm.

Definition at line 558 of file GoRegion.cpp.

References ComputeAndGetFlag(), ComputedFlag(), Find2ConnForAll(), GetFlag(), GO_REGION_PROTECTED_CUTS, GO_REGION_STATIC_1VC, GO_REGION_STATIC_1VITAL, and HasLibForAllBlocks().

Referenced by DoComputeFlag().

void GoRegion::ComputeMultipleBlockEyeSpace (  )  [private]

Compute eye space for region having more than 1 block.

Definition at line 898 of file GoRegion.cpp.

References m_bd, m_blocks, m_color, m_eyes, m_points, m_vitalPoint, SgVectorOf< T >::MinLength(), GoEyeCount::SetExactPotEyes(), GoEyeCount::SetEyes(), GoEyeCount::SetMaxEyes(), GoEyeCount::SetMinEyes(), SG_ASSERT, SG_NULLPOINT, SgPointSet::Size(), and GoEyeUtil::TestNakade().

Referenced by ComputeEyeSpace().

void GoRegion::ComputeNakade (  )  [private]

Compute eye status for some standard small regions.

Definition at line 976 of file GoRegion.cpp.

References ComputeAndGetFlag(), GetFlag(), GO_REGION_STATIC_1VITAL, GO_REGION_STATIC_2V, SgUtil::InRange(), m_bd, m_color, m_eyes, m_points, m_vitalPoint, GoEyeCount::Normalize(), Points(), GoEyeCount::SetMaxEyes(), GoEyeCount::SetMaxPotEyes(), GoEyeCount::SetMinEyes(), GoEyeCount::SetMinPotEyes(), GoEyeCount::SetUnknown(), SG_NULLPOINT, SgPointSet::Size(), and GoEyeUtil::TestNakade().

Referenced by DoComputeFlag().

void GoRegion::ComputeSingleBlockEyeSpace (  )  [private]

Compute eye space for region having only 1 block.

Definition at line 844 of file GoRegion.cpp.

References SgVectorOf< T >::IsLength(), m_bd, m_blocks, m_color, m_eyes, m_vitalPoint, Points(), GoEyeCount::SetExactPotEyes(), GoEyeCount::SetEyes(), GoEyeCount::SetLocalSeki(), GoEyeCount::SetMaxEyes(), GoEyeCount::SetMaybeLocalSeki(), GoEyeCount::SetMinEyes(), SG_ASSERT, SG_NULLPOINT, SgPointSet::Size(), and GoEyeUtil::TestNakade().

Referenced by ComputeEyeSpace().

SgPointSet GoRegion::Dep (  )  const

The dependency set, outside neighbors of m_points.

Definition at line 115 of file GoRegion.h.

References SgPointSet::Border(), m_bd, m_points, and GoBoard::Size().

Referenced by AllInsideLibs(), DoComputeFlag(), and Find2ConnForAllInterior().

void GoRegion::DoComputeFlag ( GoRegionFlag  flag  ) 

compute flag

Definition at line 764 of file GoRegion.cpp.

References Color(), ComputeIs1Vital(), ComputeNakade(), Dep(), GO_REGION_1VC, GO_REGION_1VITAL, GO_REGION_2V, GO_REGION_AT_LEAST_SEKI, GO_REGION_COMPUTED_BLOCKS, GO_REGION_COMPUTED_NAKADE, GO_REGION_CORRIDOR, GO_REGION_OPP_CAN_LIVE_INSIDE, GO_REGION_PROTECTED_CUTS, GO_REGION_SAFE, GO_REGION_SINGLE_BLOCK_BOUNDARY, GO_REGION_SMALL, GO_REGION_STATIC_1VC, GO_REGION_STATIC_1VITAL, GO_REGION_STATIC_2V, Has2SureLibs(), IsCorridor(), GoRegionUtil::IsSmallRegion(), m_bd, m_blocks, m_computedFlags, m_miaiStrategy, SgVectorOf< T >::MaxLength(), GoSafetyUtil::MightMakeLife(), Points(), ProtectedCuts(), SetFlag(), SG_ASSERT, SgOppBW(), and StaticIs1VitalAndConnected().

Referenced by ComputeBasicFlags(), and ComputeFlag().

bool GoRegion::Find2ConnForAll (  )  const

Can we find two connection paths to each interior empty point? This implements only the simple, non-recursive case.

See Find2ConnForAllInterior() for a more general solution.

Definition at line 414 of file GoRegion.cpp.

References GoBoard::AllEmpty(), AllInsideLibs(), Blocks(), Color(), GoSafetyUtil::Find2Libs(), SgVectorOf< T >::Front(), GetFlag(), GO_REGION_SINGLE_BLOCK_BOUNDARY, m_bd, Points(), and GoBlock::Stones().

Referenced by ComputeIs1Vital().

bool GoRegion::Find2ConnForAllInterior ( SgMiaiStrategy *  miaiStrategy,
SgVector< SgPoint > &  usedLibs 
) const

find 2-connection paths for all interior empty points, using recursive extension.

Erik v.d.Werf's recursive extension to Find2ConnForAll.

Definition at line 452 of file GoRegion.cpp.

References GoBoard::AllEmpty(), AllInsideLibs(), SgPointUtil::AreAdjacent(), SgPointSet::Border(), SgVector< T >::Contains(), Dep(), SgPointSet::Exclude(), SgVector< T >::Exclude(), GoSafetyUtil::Find2BestLibs(), GetIPs(), SgVector< T >::Include(), SgPointSet::Include(), SgPointSet::IsEmpty(), JointLibs(), m_bd, SgPointSet::PointOf(), Points(), SgVector< T >::PushBack(), SgMiaiStrategy::SetStrategy(), SG_ASSERT, SgDebug(), GoBoard::Size(), and SgPointSet::Write().

Referenced by Has2SureLibs().

void GoRegion::Find2FreeLibs ( const GoChain *  c1,
const GoChain *  c2,
SgPoint *  lib1,
SgPoint *  lib2 
) const

Find two so far unused liberties for connecting c1 and c2.

Todo:
In future, must respect all other chain conditions active in this region.

Definition at line 635 of file GoRegion.cpp.

References CHECK, GoChain::FreeLiberties(), SgPointSet::MinSetSize(), Points(), and SG_ASSERT.

Referenced by GoSafetySolver::Merge().

bool GoRegion::Find2Mergable ( GoChain **  c1,
GoChain **  c2 
) const

chains are mergable if two connections are found

Definition at line 619 of file GoRegion.cpp.

References Has2ConnForChains(), and m_chains.

void GoRegion::FindBlocks ( const GoRegionBoard &  ra  ) 

Get blocks of color in area.

Definition at line 1113 of file GoRegion.cpp.

References GoRegionBoard::AllBlocks(), Color(), GO_REGION_COMPUTED_BLOCKS, SgVectorOf< T >::IsEmpty(), m_bd, m_blocks, m_computedFlags, Points(), SgVectorOf< T >::PushBack(), SG_ASSERT, and GoBoard::Size().

Referenced by GoRegionBoard::AddRegion().

void GoRegion::FindChains ( const GoRegionBoard &  ra  ) 

Get chain of color in area.

Todo:
There must be faster ways to do this.

Definition at line 1149 of file GoRegion.cpp.

References GoRegionBoard::AllChains(), Color(), GO_REGION_COMPUTED_CHAINS, SgVectorOf< T >::IsEmpty(), m_bd, m_chains, m_computedFlags, Points(), SgVectorOf< T >::PushBack(), SG_ASSERT, and GoBoard::Size().

void GoRegion::Fini (  )  [static]

class finalization

Definition at line 1021 of file GoRegion.cpp.

References GoRegionBoard::Fini(), GoBlock::Fini(), GoChain::Fini(), s_alloc, s_free, and SG_ASSERT.

Referenced by GoFini().

void GoRegion::GetDivideMiaiPairs ( SgVector< SgMiaiPair > &  pairs  )  const

Get all SgMiaiPairs that can divide the region.

A dividing SgMiaiPair has two adjacent points that are libs from the same boundary block, and they are split points for region. This is a loose condition for SgMiaiPairs.

Definition at line 359 of file GoRegion.cpp.

References SgPointUtil::AreAdjacent(), Blocks(), InsideLibs(), GoEyeUtil::IsSplitPt(), Points(), SgVector< T >::PushBack(), SgVector< T >::PushBackList(), SgDebug(), and WRITEDEBUG.

bool GoRegion::GetFlag ( GoRegionFlag  flag  )  const

get value of precomputed flag

Definition at line 739 of file GoRegion.cpp.

References IsValid(), m_computedFlags, m_flags, and SG_ASSERT.

Referenced by ComputedVitalForDepth(), ComputeIs1Vital(), ComputeNakade(), Find2ConnForAll(), JointLibs(), GoSafetySolver::Merge(), ProtectedCuts(), GoSafetySolver::RegionHealthyForBlock(), StaticIs1VitalAndConnected(), and GoBlock::TestFor1Eye().

void GoRegion::GetIPs ( SgVector< SgPoint > *  ips  )  const

Get all intersections points inside region.

Definition at line 350 of file GoRegion.cpp.

References GoEyeUtil::IsSplitPt(), JointLibs(), Points(), and SgVector< T >::PushBack().

Referenced by Find2ConnForAllInterior().

bool GoRegion::Has2Conn (  )  const

call Has2ConnForBlocks for region with exactly two chains

Definition at line 1049 of file GoRegion.cpp.

References SgVectorOf< T >::Back(), SgVectorOf< T >::Front(), Has2ConnForChains(), SgVectorOf< T >::IsLength(), m_chains, and SG_ASSERT.

bool GoRegion::Has2ConnForChains ( const GoChain *  c1,
const GoChain *  c2 
) const

does region have two free (unused) liberties to connect chains?

Definition at line 1057 of file GoRegion.cpp.

References GoChain::FreeLiberties(), and Points().

Referenced by Find2Mergable(), and Has2Conn().

bool GoRegion::Has2IntersectionPoints ( const SgVector< SgPoint > &  usedLibs  )  const

whether there are 2 intersection points, doesn't have to be adjacent to all interior points.

Definition at line 329 of file GoRegion.cpp.

References SgVector< T >::Contains(), GoEyeUtil::IsSplitPt(), JointLibs(), SgVector< T >::MinLength(), and Points().

Referenced by Has2SureLibs().

bool GoRegion::Has2IPs ( const SgVector< SgPoint > &  interiorEmpty,
SgMiaiPair *  ips 
) const

An IP divides a region into two eyes AND connects all surrounding blocks, this one defines that ip has to be adjancent to all interior points.

Definition at line 300 of file GoRegion.cpp.

References AdjacentToAll(), GoEyeUtil::IsSplitPt(), JointLibs(), SgVector< T >::MinLength(), Points(), and SG_NULLPOINT.

Referenced by Has2SureLibs().

bool GoRegion::Has2SureLibs ( SgMiaiStrategy *  miaiStrategy  )  const

Test if points of region are 2-vital for color.

Condition 1: all empty points are in liberties of some boundary block Condition 2: two intersection points (

See also:
Has2IPs) refined version: points need not be liberty, if next to both IP. Example: bent-5 in the corner, as in Berlekamp/Wolfe C.11 top left corner

find all interior points connected to boundary recursively, that have 2 intersection points inside region

Definition at line 182 of file GoRegion.cpp.

References SgMiaiStrategy::AddPair(), Find2ConnForAllInterior(), Has2IntersectionPoints(), Has2IPs(), InteriorEmpty(), SgVectorOf< T >::IsEmpty(), m_blocks, and SG_ASSERT.

Referenced by DoComputeFlag().

bool GoRegion::HasBlockLibs ( const GoBlock *  b  )  const

Is a liberty of b in region?

Definition at line 233 of file GoRegion.cpp.

References GoBlock::Anchor(), Contains(), m_bd, and Points().

Referenced by HasLibForAllBlocks().

bool GoRegion::HasLibForAllBlocks (  )  const

Does each adjacent block have a liberty in region?

Definition at line 217 of file GoRegion.cpp.

References HasBlockLibs(), and m_blocks.

Referenced by ComputeIs1Vital().

bool GoRegion::HasLibsForAllBlocks ( int  n  )  const

Does each block have n liberties in region?

Definition at line 225 of file GoRegion.cpp.

References HasLibsForBlock(), and m_blocks.

bool GoRegion::HasLibsForBlock ( const GoBlock *  b,
int  n 
) const

Can a block get n libs inside region?

Definition at line 241 of file GoRegion.cpp.

References GoBlock::Anchor(), Contains(), m_bd, and Points().

Referenced by HasLibsForAllBlocks().

bool GoRegion::HealthyForSomeBlock ( const SgVectorOf< GoBlock > &  blocks  )  const

is this healthy for a block in list?

Definition at line 1171 of file GoRegion.cpp.

void GoRegion::InsideLibs ( const GoBlock *  b,
SgVector< SgPoint > *  libs 
) const

block liberties in this region

Definition at line 210 of file GoRegion.cpp.

References GoBlock::Anchor(), Contains(), m_bd, Points(), and SgVector< T >::PushBack().

Referenced by GetDivideMiaiPairs(), and JointLibs().

SgVectorOf< GoBlock > GoRegion::InteriorBlocks (  )  const

Interior blocks of region: all liberties are in m_points.

Definition at line 134 of file GoRegion.cpp.

References IsInteriorBlock(), m_blocks, and SgVectorOf< T >::PushBack().

void GoRegion::InteriorEmpty ( SgVector< SgPoint > *  interiorEmpty,
int  maxNu 
) const [private]

compute at most maxNu empty points in the interior

Todo:
does not test only for boundary block libs, but all libs.

Definition at line 167 of file GoRegion.cpp.

References Color(), GoBoard::HasNeighbors(), SgVector< T >::Include(), GoBoard::IsEmpty(), m_bd, and Points().

Referenced by Has2SureLibs().

void GoRegion::Invalidate (  ) 

reset valid flag, region data not current anymore

Definition at line 212 of file GoRegion.h.

References GO_REGION_VALID, and m_flags.

Referenced by ResetNonBlockFlags().

bool GoRegion::IsBoundaryBlock ( const GoBlock *  block  )  const

Is block a boundary block of this region?

Definition at line 150 of file GoRegion.h.

References IsInteriorBlock().

bool GoRegion::IsCorridor (  )  const

See ExEye::IsCorridor().

Definition at line 584 of file GoRegion.cpp.

References Color(), GO_REGION_CORRIDOR, m_bd, m_computedFlags, GoBoard::NumEmptyNeighbors(), GoBoard::NumNeighbors(), Points(), SG_ASSERT, and SgOppBW().

Referenced by DoComputeFlag().

bool GoRegion::IsInteriorBlock ( const GoBlock *  block  )  const

Is block an interior block of this region?

Definition at line 143 of file GoRegion.cpp.

References GoBlock::Anchor(), GoBlock::Color(), SgPointSet::Contains(), SgVectorOf< T >::Contains(), GoBoard::IsColor(), GoBoard::IsEmpty(), m_bd, m_blocks, m_points, SG_ASSERT, and SgOppBW().

Referenced by InteriorBlocks(), IsBoundaryBlock(), PointsPlusInteriorBlocks(), and Write().

bool GoRegion::IsSurrounded ( const SgVectorOf< GoBlock > &  blocks  )  const

Is region completely surrounded by blocks?

Definition at line 1162 of file GoRegion.cpp.

References SgPointSet::IsEmpty(), m_bd, Points(), and GoBoard::Size().

bool GoRegion::IsValid (  )  const

is region data valid?

Definition at line 209 of file GoRegion.h.

References GO_REGION_VALID, and m_flags.

Referenced by ComputeAndGetFlag(), ComputeBasicFlags(), and GetFlag().

void GoRegion::JointLibs ( SgVector< SgPoint > *  libs  )  const

Compute joint liberties of all m_blocks.

Since we need at least 2 joint libs, we stop computing if we find that this is impossible.

Definition at line 253 of file GoRegion.cpp.

References GoBlock::Anchor(), Contains(), SgVectorOf< T >::Front(), GetFlag(), GO_REGION_SINGLE_BLOCK_BOUNDARY, InsideLibs(), m_bd, m_blocks, SgVectorOf< T >::MinLength(), Points(), SgVector< T >::PushBack(), and SG_ASSERT.

Referenced by Find2ConnForAllInterior(), GetIPs(), Has2IntersectionPoints(), and Has2IPs().

int GoRegion::MaxEyes (  )  const

maximum number of eyes in region

Definition at line 171 of file GoRegion.h.

References m_eyes, and GoEyeCount::MaxEyes().

int GoRegion::MaxPotEyes (  )  const

maximum number of potential eyes in region

Definition at line 177 of file GoRegion.h.

References m_eyes, and GoEyeCount::MaxPotEyes().

int GoRegion::MinEyes (  )  const

minimum number of eyes in region

Definition at line 168 of file GoRegion.h.

References m_eyes, and GoEyeCount::MinEyes().

int GoRegion::MinPotEyes (  )  const

minimum number of potential eyes in region

Definition at line 174 of file GoRegion.h.

References m_eyes, and GoEyeCount::MinPotEyes().

void GoRegion::OnAddStone ( SgPoint  p  ) 

Stone was played: remove from m_points.

Definition at line 1245 of file GoRegion.cpp.

References SgPointSet::Contains(), SgPointSet::Exclude(), m_points, ResetNonBlockFlags(), and SG_ASSERT.

Referenced by GoRegionBoard::OnExecutedUncodedMove().

void GoRegion::OnRemoveStone ( SgPoint  p  ) 

Stone removed: add to m_points.

Definition at line 1252 of file GoRegion.cpp.

References SgPointSet::Contains(), SgPointSet::Include(), m_points, ResetNonBlockFlags(), and SG_ASSERT.

Referenced by GoRegionBoard::OnUndoneMove().

const SgPointSet& GoRegion::Points (  )  const

The points of the region.

Definition at line 109 of file GoRegion.h.

References m_points.

Referenced by AllEmptyAreLibs(), CheckConsistency(), ComputeNakade(), ComputeSingleBlockEyeSpace(), DoComputeFlag(), Find2ConnForAll(), Find2ConnForAllInterior(), Find2FreeLibs(), FindBlocks(), FindChains(), GoSafetySolver::FindSafePair(), GetDivideMiaiPairs(), GetIPs(), Has2ConnForChains(), Has2IntersectionPoints(), Has2IPs(), HasBlockLibs(), HasLibsForBlock(), InsideLibs(), InteriorEmpty(), IsCorridor(), IsSurrounded(), JointLibs(), GoRegionBoard::OnExecutedUncodedMove(), ProtectedCuts(), GoStaticSafetySolver::RegionHealthyForBlock(), GoRegionBoard::RemoveRegion(), Safe2Cuts(), SetBlocks(), GoRegionBoard::SetRegionArrays(), StaticIs1VitalAndConnected(), GoSafetySolver::Test2Vital(), Write(), and WriteID().

SgPointSet GoRegion::PointsPlusInteriorBlocks (  )  const

area of points plus interior blocks

Definition at line 158 of file GoRegion.cpp.

References IsInteriorBlock(), m_blocks, and m_points.

bool GoRegion::ProtectedCuts ( const GoBoard &  board  )  const [private]

A simple test if all cuts between blocks are protected.

Works only for corridors (

See also:
IsCorridor): If corridor, then opp. can get at most 2 libs (Opp2L). If Opp2L && cut point empty then opp cut move is self atari, therefore cut is protected (and remains protected if opponent is captured and plays inside again)

Definition at line 1081 of file GoRegion.cpp.

References SgPointSet::Border(), GetFlag(), GO_REGION_CORRIDOR, SgVectorOf< T >::IsLength(), m_blocks, Points(), Safe2Cuts(), and GoBlock::Stones().

Referenced by DoComputeFlag().

void GoRegion::ReInitialize (  ) 

Clear all flags etc.

to recompute region

Definition at line 647 of file GoRegion.cpp.

References SgMiaiStrategy::Clear(), ComputeBasicFlags(), GO_REGION_COMPUTED_BLOCKS, m_computedFlags, m_flags, and m_miaiStrategy.

Referenced by GoSafetySolver::Merge().

void GoRegion::RemoveBlock ( const GoBlock *  b  ) 

For incremental update - block no longer adjacent.

Definition at line 1217 of file GoRegion.cpp.

References SgVectorOf< T >::Exclude(), m_blocks, ResetNonBlockFlags(), SG_ASSERT, and SG_UNUSED().

bool GoRegion::ReplaceChain ( const GoChain *  old,
const GoChain *  newChain 
)

update region if affected: old was merged into newChain

Definition at line 601 of file GoRegion.cpp.

References GoBlock::Color(), Color(), SgVectorOf< T >::Contains(), SgVectorOf< T >::Exclude(), HEAVYCHECK, SgVectorOf< T >::Include(), m_chains, m_computedFlags, SG_ASSERT, and SgVectorOf< T >::UniqueElements().

Referenced by GoSafetySolver::Merge().

void GoRegion::ResetNonBlockFlags (  ) 

Only blocks are incrementally updated, others must be reset after move.

Definition at line 201 of file GoRegion.h.

References GoEyeCount::Clear(), GO_REGION_COMPUTED_BLOCKS, Invalidate(), m_computedFlags, and m_eyes.

Referenced by OnAddStone(), OnRemoveStone(), and RemoveBlock().

bool GoRegion::Safe2Cuts ( const GoBoard &  board  )  const

For flat region: cuts not occupied is enough to make region 1-vital.

Definition at line 1066 of file GoRegion.cpp.

References GoBoard::AllEmpty(), SgVectorOf< T >::Back(), SgPointSet::Border(), SgVectorOf< T >::Front(), SgPointSet::IsEmpty(), SgVectorOf< T >::IsLength(), m_blocks, Points(), SG_ASSERT, GoBoard::Size(), and GoBlock::Stones().

Referenced by ProtectedCuts().

void GoRegion::Set1VCDepth ( int  depth  ) 

store search depth used in ExVital1Task for 1vc search

Definition at line 233 of file GoRegion.h.

References m_1vcDepth.

void GoRegion::SetBlocks ( const SgVectorOf< GoBlock > &  blocks  ) 

Set blocks for this region from pre-found blocks list.

Definition at line 1135 of file GoRegion.cpp.

References GO_REGION_COMPUTED_BLOCKS, SgVectorOf< T >::IsEmpty(), m_bd, m_blocks, m_computedFlags, Points(), SgVectorOf< T >::PushBack(), SG_ASSERT, and GoBoard::Size().

void GoRegion::SetComputedFlag ( GoRegionFlag  flag  ) 

mark that flag is computed now

Definition at line 224 of file GoRegion.h.

References m_computedFlags.

void GoRegion::SetFlag ( GoRegionFlag  flag,
bool  value 
)

set flag to value

Definition at line 227 of file GoRegion.h.

References m_computedFlags, and m_flags.

Referenced by ComputeBasicFlags(), DoComputeFlag(), GoSafetySolver::Merge(), and SetToSafe().

void GoRegion::SetToSafe (  ) 

Set safe flag for region.

Definition at line 362 of file GoRegion.h.

References GO_REGION_SAFE, and SetFlag().

bool GoRegion::SomeBlockIsSafe (  )  const

is any adjacent block safe?

Definition at line 1179 of file GoRegion.cpp.

References Blocks().

bool GoRegion::StaticIs1VitalAndConnected (  )  const [private]

Static test if region is 1-vital and all blocks are connected.

Definition at line 92 of file GoRegion.cpp.

References GetFlag(), GO_REGION_SINGLE_BLOCK_BOUNDARY, GO_REGION_SMALL, IsAdjacentToAll(), GoBoard::IsEmpty(), m_bd, m_blocks, SgVectorOf< T >::MinLength(), and Points().

Referenced by DoComputeFlag().

void GoRegion::Write ( std::ostream &  out  )  const

Write all information.

Definition at line 680 of file GoRegion.cpp.

References _GO_REGION_FLAG_COUNT, IsInteriorBlock(), kRegionFlagStrings, m_blocks, m_chains, m_computedFlags, m_eyes, m_flags, m_miaiStrategy, Points(), SgPointSet::Size(), and WriteID().

Referenced by operator<<().

void GoRegion::WriteID ( std::ostream &  out  )  const

Write short identifier.

Definition at line 656 of file GoRegion.cpp.

References Color(), Points(), and SgBW().

Referenced by Write().

Member Data Documentation

int GoRegion::m_1vcDepth [private]

search depth used in ExVital1Task for 1vc search

Definition at line 407 of file GoRegion.h.

Referenced by ComputedVitalForDepth(), and Set1VCDepth().

const GoBoard& GoRegion::m_bd [private]

The board.

Definition at line 380 of file GoRegion.h.

Referenced by AllEmptyAreLibs(), AllInsideLibs(), CheckConsistency(), ComputeMultipleBlockEyeSpace(), ComputeNakade(), ComputeSingleBlockEyeSpace(), Dep(), DoComputeFlag(), Find2ConnForAll(), Find2ConnForAllInterior(), FindBlocks(), FindChains(), HasBlockLibs(), HasLibsForBlock(), InsideLibs(), InteriorEmpty(), IsCorridor(), IsInteriorBlock(), IsSurrounded(), JointLibs(), SetBlocks(), and StaticIs1VitalAndConnected().

SgVectorOf<GoBlock> GoRegion::m_blocks [private]

Blocks of m_color adjacent to region.

Some may be on inside

Definition at line 395 of file GoRegion.h.

Referenced by AdjacentToBlock(), AdjacentToSomeBlock(), Blocks(), BlocksNonConst(), BlocksPoints(), CheckConsistency(), ComputeEyeSpace(), ComputeMultipleBlockEyeSpace(), ComputeSingleBlockEyeSpace(), DoComputeFlag(), FindBlocks(), Has2SureLibs(), HasLibForAllBlocks(), HasLibsForAllBlocks(), InteriorBlocks(), IsInteriorBlock(), JointLibs(), PointsPlusInteriorBlocks(), ProtectedCuts(), RemoveBlock(), Safe2Cuts(), SetBlocks(), StaticIs1VitalAndConnected(), and Write().

SgVectorOf<GoChain> GoRegion::m_chains [private]

Chains of region.

Definition at line 398 of file GoRegion.h.

Referenced by Chains(), Find2Mergable(), FindChains(), Has2Conn(), ReplaceChain(), and Write().

SgBlackWhite GoRegion::m_color [private]

Color of region = color of surrounding stones.

Definition at line 392 of file GoRegion.h.

Referenced by Color(), ComputeMultipleBlockEyeSpace(), ComputeNakade(), and ComputeSingleBlockEyeSpace().

GoRegionFlags GoRegion::m_computedFlags [private]

Which flags have been computed?

Definition at line 386 of file GoRegion.h.

Referenced by ComputedFlag(), ComputeFlag(), DoComputeFlag(), FindBlocks(), FindChains(), GetFlag(), IsCorridor(), ReInitialize(), ReplaceChain(), ResetNonBlockFlags(), SetBlocks(), SetComputedFlag(), SetFlag(), and Write().

GoEyeCount GoRegion::m_eyes [private]

Number of eyes in region.

Definition at line 401 of file GoRegion.h.

Referenced by ComputeMultipleBlockEyeSpace(), ComputeNakade(), ComputeSingleBlockEyeSpace(), MaxEyes(), MaxPotEyes(), MinEyes(), MinPotEyes(), ResetNonBlockFlags(), and Write().

GoRegionFlags GoRegion::m_flags [private]

Flags describing attributes of region.

Definition at line 383 of file GoRegion.h.

Referenced by ComputeAndGetFlag(), ComputeBasicFlags(), GetFlag(), Invalidate(), IsValid(), ReInitialize(), SetFlag(), and Write().

SgMiaiStrategy GoRegion::m_miaiStrategy [private]

Miai strategy to keep region safe.

Definition at line 410 of file GoRegion.h.

Referenced by DoComputeFlag(), ReInitialize(), and Write().

SgPointSet GoRegion::m_points [private]

Points of region.

Definition at line 389 of file GoRegion.h.

Referenced by AllInsideLibs(), ComputeMultipleBlockEyeSpace(), ComputeNakade(), Dep(), IsInteriorBlock(), OnAddStone(), OnRemoveStone(), Points(), and PointsPlusInteriorBlocks().

SgPoint GoRegion::m_vitalPoint [private]

Point to change eye status.

Can be SG_NULLPOINT

Definition at line 404 of file GoRegion.h.

Referenced by ComputeMultipleBlockEyeSpace(), ComputeNakade(), and ComputeSingleBlockEyeSpace().

int GoRegion::s_alloc = 0 [static, private]

debugging bookkeeping.

Definition at line 448 of file GoRegion.h.

Referenced by Fini(), and GoRegion().

int GoRegion::s_free = 0 [static, private]

Definition at line 448 of file GoRegion.h.

Referenced by Fini(), and ~GoRegion().

The documentation for this class was generated from the following files:

17 Jun 2010 Doxygen 1.4.7