VCBuilder Class Reference

Builds the Virtual Connections (VCs) between groups of stones a single color. More...

#include <VCBuilder.hpp>

Classes
class	OrRule
class	WorkQueue
	Queue of endpoint pairs that need processing. More...
Public Member Functions
	VCBuilder (VCBuilderParam &param)
	Constructor.
	~VCBuilder ()
	Destrutor.
VCBuilderParam &	Parameters ()
	Returns parameters used in search.
const VCBuilderParam &	Parameters () const
	Returns parameters used in search.
VCBuilderStatistics	Statistics (HexColor color) const
	Returns statistics for the last run.
void	ClearStatistics ()
	Clears the statistics for both colors.
void	Build (VCSet &con, const Groups &groups, const PatternState &patterns)
	Computes connections from scratch.
void	Build (VCSet &cons, const Groups &oldGroups, const Groups &newGroups, const PatternState &patterns, bitset_t added[BLACK_AND_WHITE], ChangeLog< VC > *log)
	Updates connections from oldGroups to newGroups Assumes existing vc data is valid for oldGroups.
Private Types
enum	AndRule { CREATE_FULL, CREATE_SEMI }
	The types of VC to create when using the AND rule. More...
Private Member Functions
void	doAnd (HexPoint from, HexPoint over, HexPoint to, AndRule rule, const VC &vc, const bitset_t &capturedSet, const VCList *old)
	Compares vc to each connection in the softlimit of the given list.
void	andClosure (const VC &vc)
	Computes the and closure for the vc.
void	DoSearch ()
void	ProcessSemis (HexPoint xc, HexPoint yc)
void	ProcessFulls (HexPoint p1, HexPoint p2)
bool	AddNewFull (const VC &vc)
	Tries to add a new full-connection to list between (vc.x(), vc.y()).
bool	AddNewSemi (const VC &vc)
	Tries to add a new semi-connection to list between (vc.x(), vc.y()).
void	LoadCapturedSetPatterns ()
void	ComputeCapturedSets (const PatternState &patterns)
void	AddBaseVCs ()
	Computes the 0-connections defined by adjacency.
void	AddPatternVCs ()
	Adds vcs obtained by pre-computed patterns.
void	AbsorbMergeShrinkUpgrade (const bitset_t &added_black, const bitset_t &added_white)
void	Merge (const Groups &oldGroups, bitset_t added[BLACK_AND_WHITE])
void	MergeAndShrink (const bitset_t &affected, const bitset_t &added)
void	MergeAndShrink (const bitset_t &added, HexPoint xin, HexPoint yin, HexPoint xout, HexPoint yout)
void	RemoveAllContaining (const Groups &groups, const bitset_t &bs)
	Removes all connections whose intersection with given set is non-empty.
Private Attributes
OrRule	m_orRule
VCBuilderParam &	m_param
WorkQueue	m_queue
VCBuilderStatistics	m_statsForColor [BLACK_AND_WHITE]
VCBuilderStatistics *	m_statistics
const Groups *	m_groups
const StoneBoard *	m_brd
VCSet *	m_con
HexColor	m_color
ChangeLog< VC > *	m_log
bitset_t	m_capturedSet [BITSETSIZE]
PatternSet	m_capturedSetPatterns [BLACK_AND_WHITE]
HashedPatternSet	m_hash_capturedSetPatterns [BLACK_AND_WHITE]

Detailed Description

Builds the Virtual Connections (VCs) between groups of stones a single color.

VCs can be built from scratch or incrementally from a previous state. We use Anchelevich's rules for VC computation. This means that between each pair of cells on the board, we store a VCList of FULL connections and another VCList of SEMI connections.

IMPORTANT: Take a list of semis between x and y. If any subset of of these semis has an empty intersection, we require that the list of full connections between x and y has at least one connection.

Member Enumeration Documentation

enum VCBuilder::AndRule [private]

The types of VC to create when using the AND rule.

Enumerator:

CREATE_FULL
CREATE_SEMI

Definition at line 199 of file VCBuilder.hpp.

Constructor & Destructor Documentation

VCBuilder::VCBuilder ( VCBuilderParam & param )

Constructor.

Definition at line 34 of file VCBuilder.cpp.

References LoadCapturedSetPatterns().

VCBuilder::~VCBuilder ( )

Destrutor.

Definition at line 41 of file VCBuilder.cpp.

Member Function Documentation

void VCBuilder::AbsorbMergeShrinkUpgrade	(	const bitset_t &	added_black,
		const bitset_t &	added_white
	)			`[private]`

void VCBuilder::AddBaseVCs ( ) [private]

Computes the 0-connections defined by adjacency.

Definition at line 96 of file VCBuilder.cpp.

References VCSet::Add(), VCBuilderStatistics::base_attempts, VCBuilderStatistics::base_successes, HexColorSetUtil::ColorOrEmpty(), StoneBoard::GetEmpty(), m_brd, m_color, m_con, m_groups, m_log, m_queue, m_statistics, and VCBuilder::WorkQueue::push().

Referenced by Build().

bool VCBuilder::AddNewFull ( const VC & vc ) [private]

Tries to add a new full-connection to list between (vc.x(), vc.y()).

If vc is successfully added, then:

1) Removes any semi-connections between (vc.x(), vc.y()) that are supersets of vc.

2) Adds (vc.x(), vc.y()) to the queue if vc was added inside the softlimit.

Definition at line 764 of file VCBuilder.cpp.

References VCSet::Add(), VCList::ADD_FAILED, VCList::ADDED_INSIDE_SOFT_LIMIT, VC::carrier(), VC::FULL, VCSet::GetList(), HexAssert, m_con, m_log, m_queue, VCBuilder::WorkQueue::push(), VC::SEMI, VC::type(), VC::x(), and VC::y().

Referenced by doAnd().

bool VCBuilder::AddNewSemi ( const VC & vc ) [private]

Tries to add a new semi-connection to list between (vc.x(), vc.y()).

Does not add if vc is a superset of some full-connection between (vc.x(), and vc.y()).

If vc is successfully added and intersection on semi-list is empty, then:

1) if vc added inside soft limit, adds (vc.x(), vc.y()) to queue.

2) otherwise, if no full exists between (vc.x(), vc.y()), adds the or over the entire semi list.

Definition at line 797 of file VCBuilder.cpp.

References VCList::add(), VCList::ADD_FAILED, VCList::ADDED_INSIDE_SOFT_LIMIT, VC::carrier(), VCList::empty(), VC::FULL, VCList::getGreedyUnion(), VCSet::GetList(), VCList::getUnion(), VCList::getX(), VCList::getY(), VCList::hardIntersection(), VCList::isSupersetOfAny(), m_con, m_log, m_param, m_queue, benzene_bitset< _Nb >::none(), VCBuilder::WorkQueue::push(), VC::SEMI, VCBuilderParam::use_greedy_union, VC_RULE_ALL, VC::x(), and VC::y().

Referenced by doAnd().

void VCBuilder::AddPatternVCs ( ) [private]

Adds vcs obtained by pre-computed patterns.

Definition at line 115 of file VCBuilder.cpp.

References VCSet::Add(), VCPattern::Endpoint(), StoneBoard::GetColor(), VCPattern::GetPatterns(), StoneBoard::Height(), HexPointUtil::isEdge(), m_brd, m_color, m_con, m_log, m_param, m_queue, m_statistics, VCPattern::Matches(), VCPattern::NotOpponent(), VCBuilderStatistics::pattern_attempts, VCBuilderStatistics::pattern_successes, VCBuilder::WorkQueue::push(), benzene_bitset< _Nb >::reset(), VCBuilderParam::use_non_edge_patterns, VC_RULE_BASE, and StoneBoard::Width().

Referenced by Build().

void VCBuilder::andClosure ( const VC & vc ) [private]

Computes the and closure for the vc.

Let x and y be vc's endpoints. A single pass over the board is performed. For each z, we try to and the list of fulls between z and x and z and y with vc. This function is a major bottleneck. Every operation in it needs to be as efficient as possible.

Definition at line 505 of file VCBuilder.cpp.

References VCBuilderParam::and_over_edge, Groups::CaptainOf(), VC::carrier(), CREATE_FULL, CREATE_SEMI, doAnd(), EMPTY, benzene_bitset< _Nb >::flip(), VC::FULL, StoneBoard::GetColor(), VCSet::GetList(), HexAssert, HexPointUtil::isEdge(), LogInfo(), m_brd, m_capturedSet, m_color, m_con, m_groups, m_param, HexColorSetUtil::NotColor(), VCList::softIntersection(), benzene_bitset< _Nb >::test(), VC::x(), and VC::y().

Referenced by ProcessFulls().

void VCBuilder::Build	(	VCSet &	cons,
		const Groups &	oldGroups,
		const Groups &	newGroups,
		const PatternState &	patterns,
		bitset_t	added[BLACK_AND_WHITE],
		ChangeLog< VC > *	log
	)

Updates connections from oldGroups to newGroups Assumes existing vc data is valid for oldGroups.

Logging is used if passed log is not 0. Breaks all connections whose carrier contains a new stone unless a 1-connection of player color and p is the key; these are upgraded to 0-connections for player p.

Definition at line 170 of file VCBuilder.cpp.

References AddPatternVCs(), BLACK, Groups::Board(), VCBuilder::WorkQueue::clear(), VCSet::Color(), ComputeCapturedSets(), DoSearch(), Get(), HexAssert, LogFine(), m_brd, m_color, m_con, m_groups, m_log, m_param, m_queue, m_statistics, m_statsForColor, Merge(), VCBuilderParam::use_patterns, and WHITE.

void VCBuilder::Build	(	VCSet &	con,
		const Groups &	groups,
		const PatternState &	patterns
	)

Computes connections from scratch.

Old connections are removed prior to starting.

Definition at line 71 of file VCBuilder.cpp.

References AddBaseVCs(), AddPatternVCs(), Groups::Board(), VCBuilder::WorkQueue::clear(), VCSet::Clear(), VCSet::Color(), ComputeCapturedSets(), DoSearch(), Get(), LogFine(), m_brd, m_color, m_con, m_groups, m_log, m_param, m_queue, m_statistics, m_statsForColor, and VCBuilderParam::use_patterns.

Referenced by HexBoard::BuildVCs().

void VCBuilder::ClearStatistics ( ) [inline]

Clears the statistics for both colors.

Definition at line 302 of file VCBuilder.hpp.

References BLACK, m_statsForColor, and WHITE.

Referenced by HexBoard::ComputeAll(), HexBoard::PlayMove(), and HexBoard::PlayStones().

void VCBuilder::ComputeCapturedSets ( const PatternState & patterns ) [private]

Definition at line 143 of file VCBuilder.cpp.

References StoneBoard::Const(), ConstBoard::EdgesAndInterior(), EMPTY, EMPTY_BITSET, StoneBoard::GetColor(), m_brd, m_capturedSet, m_color, m_hash_capturedSetPatterns, PatternState::MatchOnCell(), and PatternState::STOP_AT_FIRST_HIT.

Referenced by Build().

void VCBuilder::doAnd	(	HexPoint	from,
		HexPoint	over,
		HexPoint	to,
		AndRule	rule,
		const VC &	vc,
		const bitset_t &	capturedSet,
		const VCList *	old
	)			`[private]`

Compares vc to each connection in the softlimit of the given list.

Creates a new connection if intersection is empty, or if the intersection is a subset of the captured set. Created connections are added with AddNewFull() or AddNewSemi().

Definition at line 557 of file VCBuilder.cpp.

References AddNewFull(), AddNewSemi(), VCBuilderStatistics::and_full_attempts, VCBuilderStatistics::and_full_successes, VCBuilderStatistics::and_semi_attempts, VCBuilderStatistics::and_semi_successes, VC::AndVCs(), VCList::begin(), VC::carrier(), CREATE_FULL, CREATE_SEMI, VCList::empty(), VCList::end(), BitsetUtil::IsSubsetOf(), m_statistics, benzene_bitset< _Nb >::none(), and VCList::softlimit().