InferiorCells Class Reference

Set of inferior cells. More...

#include <InferiorCells.hpp>

Public Member Functions
	InferiorCells ()
	Constructs empty inferior cell set.
bitset_t	Dead () const
bitset_t	Captured (HexColor color) const
bitset_t	PermInf (HexColor color) const
bitset_t	PermInfCarrier (HexColor color) const
bitset_t	MutualFillin (HexColor color) const
bitset_t	MutualFillinCarrier (HexColor color) const
bitset_t	Vulnerable () const
	Returns the set of vulnerable cells.
bitset_t	Reversible () const
	Returns the set of reversible cells.
bitset_t	Dominated () const
	Returns the set of dominated cells.
bitset_t	All () const
bitset_t	Fillin (HexColor color) const
const std::set < VulnerableKiller > &	Killers (HexPoint p) const
const std::set< HexPoint > &	Reversers (HexPoint p) const
bitset_t	AllReversers () const
bitset_t	AllReversibleCarriers () const
std::string	GuiOutput () const
	Returns a string representation of its internal state.
bitset_t	FindPresimplicialPairs () const
	Examines the vulnerable cells; returns the set of presimplicial cells on the cells they kill.
bitset_t	DeductionSet (HexColor color) const
	Uses the inferior cell information to compute the deduction set.
void	AddDead (const bitset_t &dead)
void	AddDead (HexPoint dead)
void	AddCaptured (HexColor color, const bitset_t &captured)
void	AddCaptured (HexColor color, HexPoint captured)
void	AddPermInf (HexColor color, const bitset_t &cells, const bitset_t &carrier)
void	AddPermInf (HexColor color, HexPoint cell, const bitset_t &carrier)
void	AddMutualFillin (HexColor color, const bitset_t &cells, const bitset_t &carrier)
void	AddMutualFillin (HexColor color, HexPoint cell, const bitset_t &carrier)
void	AddDominated (HexPoint cell, HexPoint dominator)
void	AddDominated (HexPoint cell, const std::set< HexPoint > &dom)
void	AddVulnerable (HexPoint cell, HexPoint killer)
void	AddVulnerable (HexPoint cell, const std::set< HexPoint > &killers)
void	AddVulnerable (HexPoint cell, const VulnerableKiller &killer)
void	AddVulnerable (HexPoint cell, const std::set< VulnerableKiller > &dom)
void	AddReversible (HexPoint cell, bitset_t carrier, HexPoint reverser)
void	AddReversible (HexPoint cell, bitset_t carrier, const std::set< HexPoint > &reversers)
void	AddDominatedFrom (const InferiorCells &other)
void	AddVulnerableFrom (const InferiorCells &other)
void	AddReversibleFrom (const InferiorCells &other)
void	AddPermInfFrom (HexColor color, const InferiorCells &other)
void	AddMutualFillinFrom (HexColor color, const InferiorCells &other)
void	Clear ()
void	ClearDead ()
void	ClearVulnerable ()
void	ClearReversible ()
void	ClearDominated ()
void	ClearCaptured (HexColor color)
void	ClearPermInf (HexColor color)
void	ClearMutualFillin (HexColor color)
void	RemoveDead (const bitset_t &dead)
void	RemoveCaptured (HexColor color, const bitset_t &captured)
void	RemoveDominated (const bitset_t &dominated)
void	RemoveVulnerable (const bitset_t &vulnerable)
void	RemoveReversible (const bitset_t &reversible)
void	RemoveReversible (HexPoint reversible)
void	RemovePermInf (HexColor color, const bitset_t &perminf)
void	RemoveMutualFillin (HexColor color, const bitset_t &mutual)
Private Member Functions
void	AssertPairwiseDisjoint () const
Private Attributes
bitset_t	m_dead
bitset_t	m_captured [BLACK_AND_WHITE]
bitset_t	m_perm_inf [BLACK_AND_WHITE]
bitset_t	m_perm_inf_carrier [BLACK_AND_WHITE]
bitset_t	m_mutual_fillin [BLACK_AND_WHITE]
bitset_t	m_mutual_fillin_carrier [BLACK_AND_WHITE]
bitset_t	m_vulnerable
	Vulnerable cells; not those involved in presimplicial pairs, though.
std::set< VulnerableKiller >	m_killers [BITSETSIZE]
bitset_t	m_reversible
	Reversible cells and their reversers.
std::set< HexPoint >	m_reversers [BITSETSIZE]
bitset_t	m_allReversibleCarriers
	Data to test for independent captured-reversible sets.
bitset_t	m_allReversers
Digraph< HexPoint >	m_dom_graph
	Graph of domination; dominated cells point to their dominators.
bool	m_dominated_computed
	True if the dominated set has been computed from the domination graph.
bitset_t	m_dominated
	The sources of the domination graph minus a few representatives.

Detailed Description

Set of inferior cells.

Definition at line 84 of file InferiorCells.hpp.

Constructor & Destructor Documentation

InferiorCells::InferiorCells ( )

Constructs empty inferior cell set.

Definition at line 21 of file InferiorCells.cpp.

Member Function Documentation

void InferiorCells::AddCaptured	(	HexColor	color,
		HexPoint	captured
	)

Definition at line 90 of file InferiorCells.cpp.

References AddCaptured(), and benzene_bitset< _Nb >::set().

void InferiorCells::AddCaptured	(	HexColor	color,
		const bitset_t &	captured
	)

Definition at line 97 of file InferiorCells.cpp.

References AssertPairwiseDisjoint(), m_captured, RemoveDominated(), RemoveReversible(), and RemoveVulnerable().

Referenced by AddCaptured(), ICEngine::ComputeDeadCaptured(), ICEngine::FillInVulnerable(), HexBoard::HandleVCDecomposition(), and IceUtil::Update().

void InferiorCells::AddDead ( HexPoint dead )

Definition at line 72 of file InferiorCells.cpp.

References AddDead(), and benzene_bitset< _Nb >::set().

void InferiorCells::AddDead ( const bitset_t & dead )

Definition at line 79 of file InferiorCells.cpp.

References AssertPairwiseDisjoint(), m_dead, RemoveDominated(), RemoveReversible(), and RemoveVulnerable().

Referenced by AddDead(), ICEngine::CliqueCutsetDead(), ICEngine::ComputeDeadCaptured(), and IceUtil::Update().

void InferiorCells::AddDominated	(	HexPoint	cell,
		const std::set< HexPoint > &	dom
	)

Definition at line 152 of file InferiorCells.cpp.

References Digraph< T >::AddEdges(), m_dom_graph, and m_dominated_computed.

void InferiorCells::AddDominated	(	HexPoint	cell,
		HexPoint	dominator
	)

Definition at line 160 of file InferiorCells.cpp.

References Digraph< T >::AddEdge(), m_dom_graph, and m_dominated_computed.

Referenced by AddDominatedFrom(), ICEngine::CheckHandCodedDominates(), and ICEngine::FindDominated().

void InferiorCells::AddDominatedFrom ( const InferiorCells & other )

Definition at line 284 of file InferiorCells.cpp.

References AddDominated(), m_dom_graph, Digraph< T >::OutSet(), BitsetUtil::SetToBitset(), and Digraph< T >::Vertices().

Referenced by IceUtil::Update().

void InferiorCells::AddMutualFillin	(	HexColor	color,
		HexPoint	cell,
		const bitset_t &	carrier
	)

Definition at line 144 of file InferiorCells.cpp.

References AddMutualFillin(), and benzene_bitset< _Nb >::set().

void InferiorCells::AddMutualFillin	(	HexColor	color,
		const bitset_t &	cells,
		const bitset_t &	carrier
	)

Definition at line 130 of file InferiorCells.cpp.

References AssertPairwiseDisjoint(), m_mutual_fillin, m_mutual_fillin_carrier, RemoveDominated(), RemoveReversible(), and RemoveVulnerable().

Referenced by AddMutualFillin(), and ICEngine::FillInMutualFillin().

void InferiorCells::AddMutualFillinFrom	(	HexColor	color,
		const InferiorCells &	other
	)

Definition at line 318 of file InferiorCells.cpp.

References AssertPairwiseDisjoint(), m_mutual_fillin, and m_mutual_fillin_carrier.

Referenced by IceUtil::Update().

void InferiorCells::AddPermInf	(	HexColor	color,
		HexPoint	cell,
		const bitset_t &	carrier
	)

Definition at line 122 of file InferiorCells.cpp.

References AddPermInf(), and benzene_bitset< _Nb >::set().

void InferiorCells::AddPermInf	(	HexColor	color,
		const bitset_t &	cells,
		const bitset_t &	carrier
	)

Definition at line 108 of file InferiorCells.cpp.

References AssertPairwiseDisjoint(), m_perm_inf, m_perm_inf_carrier, RemoveDominated(), RemoveReversible(), and RemoveVulnerable().

Referenced by AddPermInf(), and ICEngine::FillinPermanentlyInferior().

void InferiorCells::AddPermInfFrom	(	HexColor	color,
		const InferiorCells &	other
	)

Definition at line 311 of file InferiorCells.cpp.

References AssertPairwiseDisjoint(), m_perm_inf, and m_perm_inf_carrier.

Referenced by IceUtil::Update().

void InferiorCells::AddReversible	(	HexPoint	cell,
		bitset_t	carrier,
		const std::set< HexPoint > &	reversers
	)

Definition at line 246 of file InferiorCells.cpp.

References AssertPairwiseDisjoint(), m_allReversers, m_allReversibleCarriers, m_dominated_computed, m_reversers, m_reversible, m_vulnerable, benzene_bitset< _Nb >::set(), and benzene_bitset< _Nb >::test().

void InferiorCells::AddReversible	(	HexPoint	cell,
		bitset_t	carrier,
		HexPoint	reverser
	)

Definition at line 217 of file InferiorCells.cpp.

References AssertPairwiseDisjoint(), m_allReversers, m_allReversibleCarriers, m_dominated_computed, m_reversers, m_reversible, m_vulnerable, benzene_bitset< _Nb >::set(), and benzene_bitset< _Nb >::test().

Referenced by AddReversibleFrom(), and ICEngine::FindReversible().

void InferiorCells::AddReversibleFrom ( const InferiorCells & other )

Definition at line 301 of file InferiorCells.cpp.

References AddReversible(), AllReversers(), AllReversibleCarriers(), AssertPairwiseDisjoint(), EMPTY_BITSET, m_allReversers, m_allReversibleCarriers, m_reversers, and Reversible().

Referenced by IceUtil::Update().

void InferiorCells::AddVulnerable	(	HexPoint	cell,
		const std::set< VulnerableKiller > &	dom
	)

Definition at line 186 of file InferiorCells.cpp.

References AssertPairwiseDisjoint(), m_dominated_computed, m_killers, m_vulnerable, RemoveReversible(), and benzene_bitset< _Nb >::set().

void InferiorCells::AddVulnerable	(	HexPoint	cell,
		const VulnerableKiller &	killer
	)

Definition at line 207 of file InferiorCells.cpp.

References AssertPairwiseDisjoint(), m_dominated_computed, m_killers, m_vulnerable, RemoveReversible(), and benzene_bitset< _Nb >::set().

void InferiorCells::AddVulnerable	(	HexPoint	cell,
		const std::set< HexPoint > &	killers
	)

Definition at line 168 of file InferiorCells.cpp.

References AssertPairwiseDisjoint(), m_dominated_computed, m_killers, m_vulnerable, RemoveReversible(), and benzene_bitset< _Nb >::set().

void InferiorCells::AddVulnerable	(	HexPoint	cell,
		HexPoint	killer
	)

Definition at line 197 of file InferiorCells.cpp.

References AssertPairwiseDisjoint(), m_dominated_computed, m_killers, m_vulnerable, RemoveReversible(), and benzene_bitset< _Nb >::set().

Referenced by AddVulnerableFrom(), ICEngine::BackupOpponentDead(), and ICEngine::FindVulnerable().

void InferiorCells::AddVulnerableFrom ( const InferiorCells & other )

Definition at line 293 of file InferiorCells.cpp.

References AddVulnerable(), AssertPairwiseDisjoint(), m_killers, and Vulnerable().

Referenced by IceUtil::Update().

bitset_t InferiorCells::All ( ) const

Definition at line 54 of file InferiorCells.cpp.

References BLACK, Captured(), Dead(), Dominated(), MutualFillin(), PermInf(), Reversible(), Vulnerable(), and WHITE.

Referenced by VCCommands::CmdBuildIncremental(), VCCommands::CmdBuildStatic(), and DfsSolver::SolveInteriorState().

bitset_t InferiorCells::AllReversers ( ) const [inline]

Definition at line 318 of file InferiorCells.hpp.

References m_allReversers.

Referenced by AddReversibleFrom().

bitset_t InferiorCells::AllReversibleCarriers ( ) const [inline]

Definition at line 323 of file InferiorCells.hpp.

References m_allReversibleCarriers.

Referenced by AddReversibleFrom().

void InferiorCells::AssertPairwiseDisjoint ( ) const [private]

Definition at line 423 of file InferiorCells.cpp.

References HexAssert, m_allReversers, m_allReversibleCarriers, m_captured, m_dead, m_dominated, m_dominated_computed, m_mutual_fillin, m_perm_inf, m_reversible, and m_vulnerable.

Referenced by AddCaptured(), AddDead(), AddMutualFillin(), AddMutualFillinFrom(), AddPermInf(), AddPermInfFrom(), AddReversible(), AddReversibleFrom(), AddVulnerable(), and AddVulnerableFrom().

bitset_t InferiorCells::Captured ( HexColor color ) const [inline]

Definition at line 281 of file InferiorCells.hpp.

References m_captured.

Referenced by All(), DeductionSet(), Fillin(), GuiOutput(), HexBoard::PopHistory(), PerfectPlayer::Search(), and IceUtil::Update().

void InferiorCells::Clear ( )

Definition at line 328 of file InferiorCells.cpp.

References ClearCaptured(), ClearDead(), ClearDominated(), ClearMutualFillin(), ClearPermInf(), ClearReversible(), and ClearVulnerable().

Referenced by HexBoard::ComputeAll(), and ICEngine::ComputeFillin().

void InferiorCells::ClearCaptured ( HexColor color )

Definition at line 346 of file InferiorCells.cpp.

References m_captured, and benzene_bitset< _Nb >::reset().

Referenced by Clear().

void InferiorCells::ClearDead ( )

Definition at line 341 of file InferiorCells.cpp.

References m_dead, and benzene_bitset< _Nb >::reset().

Referenced by Clear().

void InferiorCells::ClearDominated ( )

Definition at line 377 of file InferiorCells.cpp.

References Digraph< T >::Clear(), m_dom_graph, and m_dominated_computed.

Referenced by Clear(), and IceUtil::Update().

void InferiorCells::ClearMutualFillin ( HexColor color )

Definition at line 357 of file InferiorCells.cpp.

References m_mutual_fillin, m_mutual_fillin_carrier, and benzene_bitset< _Nb >::reset().

Referenced by Clear().

void InferiorCells::ClearPermInf ( HexColor color )

Definition at line 351 of file InferiorCells.cpp.

References m_perm_inf, m_perm_inf_carrier, and benzene_bitset< _Nb >::reset().

Referenced by Clear().

void InferiorCells::ClearReversible ( )

Definition at line 369 of file InferiorCells.cpp.

References m_allReversers, m_allReversibleCarriers, m_dominated_computed, m_reversible, RemoveReversible(), and benzene_bitset< _Nb >::reset().

Referenced by Clear(), and IceUtil::Update().

void InferiorCells::ClearVulnerable ( )

Definition at line 363 of file InferiorCells.cpp.

References m_dominated_computed, m_vulnerable, and RemoveVulnerable().

Referenced by Clear(), ICEngine::FillInVulnerable(), and IceUtil::Update().

bitset_t InferiorCells::Dead ( ) const [inline]

Definition at line 266 of file InferiorCells.hpp.

References m_dead.

Referenced by All(), ICEngine::BackupOpponentDead(), Fillin(), ICEngine::FillInVulnerable(), HexBoard::GetDead(), GuiOutput(), HexBoard::PopHistory(), and IceUtil::Update().

bitset_t InferiorCells::DeductionSet ( HexColor color ) const

Uses the inferior cell information to compute the deduction set.

This is the part of the proof set used to derive the equivalent ICE-reduced board. The proof set is composed of this, the played stones, and (some subset of) the empty cells on the ICE-reduced board. Note: it is assumed the color passed in is the player for whom the pruning (vulnerable, reversible, dominated) was computed, so these are not used... just the fillin.

Definition at line 513 of file InferiorCells.cpp.

References Captured(), MutualFillin(), MutualFillinCarrier(), PermInf(), and PermInfCarrier().

Referenced by ProofUtil::InitialProofForOpponent(), and ProofUtil::MaximumProofSet().

bitset_t InferiorCells::Dominated ( ) const

Returns the set of dominated cells.

This is not the same as the set of all cells dominated by some other cell. The returned is a maximal set of dominated cells that can be ignored during move

Note:: A cell can be both dominated (have an outgoing arc in the domination graph), and be vulnerable (have an outgoing arc in the vulnerable graph) and/or reversible. In such a case, the cell will never appear in the cells returned by Dominated().

Todo:: ensure m_dominated is disjoint from all others.

Definition at line 28 of file InferiorCells.cpp.

References InferiorCellsUtil::FindDominationCaptains(), HexAssert, m_dom_graph, m_dominated, m_dominated_computed, Digraph< T >::RemoveVertex(), Reversible(), BitsetUtil::SetToBitset(), Digraph< T >::Vertices(), and Vulnerable().

Referenced by All(), ICEngine::BackupOpponentDead(), and GuiOutput().

bitset_t InferiorCells::Fillin ( HexColor color ) const

Definition at line 63 of file InferiorCells.cpp.

References Captured(), Dead(), DEAD_COLOR, MutualFillin(), and PermInf().

Referenced by ICEngine::BackupOpponentDead().

bitset_t InferiorCells::FindPresimplicialPairs ( ) const

Examines the vulnerable cells; returns the set of presimplicial cells on the cells they kill.

Todo:: Handle vulnerable cycles larger than length 2? If they occur, they are extrememly rare, so it is probably not worth it.

Definition at line 466 of file InferiorCells.cpp.

References m_killers, m_vulnerable, benzene_bitset< _Nb >::set(), and benzene_bitset< _Nb >::test().

Referenced by ICEngine::FillInVulnerable().

std::string InferiorCells::GuiOutput ( ) const

Returns a string representation of its internal state.

The format is as follows: 1) First character is either f (for fill-in) or i (for ignorable) 2a) If fill-in, 2nd character is c/d/p/u (captured/dead/perminf/mutual) and 3rd character is b/w (black/white fill-in colour) 2b) If ignorable, 2nd character is v/r/d (vulnerable/reversible/domin) and 3rd entry is list of killers/reversers/dominators

Definition at line 526 of file InferiorCells.cpp.

References BLACK, Captured(), Dead(), DEAD_COLOR, Dominated(), FIRST_INVALID, m_dom_graph, m_killers, m_reversers, MutualFillin(), Digraph< T >::out_begin(), Digraph< T >::out_end(), PermInf(), Reversible(), benzene_bitset< _Nb >::test(), Vulnerable(), and WHITE.

Referenced by VCCommands::CmdBuildIncremental(), VCCommands::CmdBuildStatic(), and DfsSolver::SolveInteriorState().

const std::set< VulnerableKiller > & InferiorCells::Killers ( HexPoint p ) const [inline]

Definition at line 307 of file InferiorCells.hpp.

References m_killers.

Referenced by ProofUtil::InitialProofForOpponent().

bitset_t InferiorCells::MutualFillin ( HexColor color ) const [inline]

Definition at line 296 of file InferiorCells.hpp.

References m_mutual_fillin.

Referenced by All(), DeductionSet(), Fillin(), and GuiOutput().

bitset_t InferiorCells::MutualFillinCarrier ( HexColor color ) const [inline]

Definition at line 301 of file InferiorCells.hpp.

References m_mutual_fillin_carrier.

Referenced by DeductionSet().

bitset_t InferiorCells::PermInf ( HexColor color ) const [inline]

Definition at line 286 of file InferiorCells.hpp.

References m_perm_inf.

Referenced by All(), DeductionSet(), Fillin(), and GuiOutput().

bitset_t InferiorCells::PermInfCarrier ( HexColor color ) const [inline]

Definition at line 291 of file InferiorCells.hpp.

References m_perm_inf_carrier.

Referenced by DeductionSet().

void InferiorCells::RemoveCaptured	(	HexColor	color,
		const bitset_t &	captured
	)

void InferiorCells::RemoveDead ( const bitset_t & dead )

void InferiorCells::RemoveDominated ( const bitset_t & dominated )

Definition at line 385 of file InferiorCells.cpp.

References m_dom_graph, m_dominated_computed, Digraph< T >::RemoveVertex(), BitsetUtil::SetToBitset(), and Digraph< T >::Vertices().

Referenced by AddCaptured(), AddDead(), AddMutualFillin(), and AddPermInf().

void InferiorCells::RemoveMutualFillin	(	HexColor	color,
		const bitset_t &	mutual
	)

void InferiorCells::RemovePermInf	(	HexColor	color,
		const bitset_t &	perminf
	)

void InferiorCells::RemoveReversible ( HexPoint reversible )

Definition at line 412 of file InferiorCells.cpp.

References m_dominated_computed, m_reversers, m_reversible, benzene_bitset< _Nb >::reset(), and benzene_bitset< _Nb >::test().

void InferiorCells::RemoveReversible ( const bitset_t & reversible )

Definition at line 403 of file InferiorCells.cpp.

References m_dominated_computed, m_reversers, and m_reversible.

Referenced by AddCaptured(), AddDead(), AddMutualFillin(), AddPermInf(), AddVulnerable(), and ClearReversible().

void InferiorCells::RemoveVulnerable ( const bitset_t & vulnerable )

Definition at line 394 of file InferiorCells.cpp.

References m_dominated_computed, m_killers, and m_vulnerable.

Referenced by AddCaptured(), AddDead(), AddMutualFillin(), AddPermInf(), and ClearVulnerable().

const std::set< HexPoint > & InferiorCells::Reversers ( HexPoint p ) const [inline]

Definition at line 313 of file InferiorCells.hpp.

References m_reversers.

Referenced by ProofUtil::InitialProofForOpponent().

bitset_t InferiorCells::Reversible ( ) const [inline]

Returns the set of reversible cells.

Note:: An empty cell can be both reversible and vulnerable. In this case it will be vulnerable and not appear in the cells returned by Reversible().

Definition at line 276 of file InferiorCells.hpp.

References m_reversible.

Referenced by AddReversibleFrom(), All(), ICEngine::BackupOpponentDead(), ICEngine::ComputeInferiorCells(), Dominated(), GuiOutput(), and ProofUtil::InitialProofForOpponent().

bitset_t InferiorCells::Vulnerable ( ) const [inline]

Returns the set of vulnerable cells.

Definition at line 271 of file InferiorCells.hpp.

References m_vulnerable.

Referenced by AddVulnerableFrom(), All(), ICEngine::BackupOpponentDead(), ICEngine::ComputeInferiorCells(), Dominated(), GuiOutput(), and ProofUtil::InitialProofForOpponent().