DfsSolver Class Reference

Determines the winner of a gamestate. More...

#include <DfsSolver.hpp>

Classes
struct	GlobalStatistics
	Globabl statistics for the current solver run. More...
Public Member Functions
	DfsSolver ()
	~DfsSolver ()
HexColor	Solve (const HexState &state, HexBoard &board, DfsSolutionSet &solution, DfsStates &positions, int depthLimit=-1, double timeLimit=-1.0)
	Solves state using the given previously solved positions.
void	DumpStats (const DfsSolutionSet &solution) const
	Dumps the stats on # of states, branching factors, etc, for the last run.
DfsHistogram	Histogram () const
	Returns histogram of last search.
Parameters

bool	UseDecompositions () const
	Controls whether gamestates decomposible into separate components have each side solved separately and the proofs combined as necessary.
void	SetUseDecompositions (bool enable)
	See UseDecompositions().
int	ProgressDepth () const
	Depth from root in which the current variation is printed.
void	SetProgressDepth (int depth)
	See ProgressDepth().
int	UpdateDepth () const
	Depth at which the current state is dumped to the log.
void	SetUpdateDepth (int depth)
	See UpdateDepth().
bool	ShrinkProofs () const
	Whether ICE is used to provably shrink proofs.
void	SetShrinkProofs (bool enable)
	See ShrinkProofs().
bool	BackupIceInfo () const
	Use newly acquired ICE-info after the move ordering stage to prune the moves to consider.
void	SetBackupIceInfo (bool enable)
	See BackupIceInfo().
bool	UseGuiFx () const
void	SetUseGuiFx (bool enable)
	See UseGuiFx().
int	MoveOrdering () const
	Returns the move order flags.
void	SetMoveOrdering (int flags)
	See MoveOrdering().
Private Member Functions
void	PlayMove (HexPoint cell)
	Plays the move; updates the board.
void	UndoMove (HexPoint cell)
	Takes back the move played.
bool	CheckTransposition (DfsData &state) const
void	StoreState (const DfsData &state, const bitset_t &proof)
bool	CheckAbort ()
	Checks timelimit and SgUserAbort().
bool	HandleLeafNode (DfsData &state, bitset_t &proof) const
	Returns true if current data is a terminal node (win/loss), or a DB/TT hit.
bool	HandleTerminalNode (DfsData &state, bitset_t &proof) const
	Returns true if node is terminal.
bool	OrderMoves (bitset_t &mustplay, DfsSolutionSet &solution, std::vector< HexMoveValue > &moves)
	Orders the moves in mustplay using several heuristics.
bool	SolveState (PointSequence &variation, DfsSolutionSet &solution)
	Solves the current state.
bool	SolveDecomposition (PointSequence &variation, DfsSolutionSet &solution, HexPoint group)
	Solves each side of the decompsosition; combines proofs if necessary.
bool	SolveInteriorState (PointSequence &variation, DfsSolutionSet &solution)
	Does the recursive mustplay search.
void	HandleProof (const PointSequence &variation, bool winning_state, DfsSolutionSet &solution)
	Shrinks/verifies proof then stores it.
Private Attributes
DfsStates *	m_positions
HexBoard *	m_workBrd
double	m_start_time
double	m_end_time
std::vector< std::pair< int, int > >	m_completed
bool	m_aborted
DfsHistogram	m_histogram
GlobalStatistics	m_statistics
boost::scoped_ptr< HexState >	m_state
bool	m_use_decompositions
	See UseDecompositions().
int	m_update_depth
	See UpdateDepth().
bool	m_shrink_proofs
	See ShrinkProofs().
bool	m_backup_ice_info
	See BackupIceInfo().
bool	m_use_guifx
	See UseGuiFx().
int	m_move_ordering
	See MoveOrdering().
unsigned	m_last_histogram_dump
int	m_depthLimit
double	m_timeLimit

Detailed Description

Determines the winner of a gamestate.

DfsSolver uses a mustplay driven depth-first search to determine the winner in the given state.

Definition at line 226 of file DfsSolver.hpp.

Constructor & Destructor Documentation

DfsSolver::DfsSolver ( )

Definition at line 39 of file DfsSolver.cpp.

DfsSolver::~DfsSolver ( )

Definition at line 52 of file DfsSolver.cpp.

Member Function Documentation

bool DfsSolver::BackupIceInfo ( ) const [inline]

Use newly acquired ICE-info after the move ordering stage to prune the moves to consider.

Definition at line 426 of file DfsSolver.hpp.

References m_backup_ice_info.

Referenced by DfsCommands::CmdParamSolver().

bool DfsSolver::CheckAbort ( ) [private]

Checks timelimit and SgUserAbort().

Sets m_aborted if necessary, aborting the search. Returns true if search should be aborted, false otherwise.

Definition at line 136 of file DfsSolver.cpp.

References Time::Get(), LogInfo(), m_aborted, m_start_time, and m_timeLimit.

Referenced by SolveState().

bool DfsSolver::CheckTransposition ( DfsData & state ) const [private]

Definition at line 108 of file DfsSolver.cpp.

References SolverDB< HASH, DB, DATA >::Get(), m_positions, and m_state.

Referenced by HandleLeafNode(), OrderMoves(), and Solve().

void DfsSolver::DumpStats ( const DfsSolutionSet & solution ) const

Dumps the stats on # of states, branching factors, etc, for the last run.

Definition at line 856 of file DfsSolver.cpp.

Referenced by DfsCommands::CmdSolverFindWinning(), and DfsCommands::CmdSolveState().

bool DfsSolver::HandleLeafNode	(	DfsData &	data,
		bitset_t &	proof
	)			const `[private]`

Returns true if current data is a terminal node (win/loss), or a DB/TT hit.

If so, info is stored in data.

Definition at line 182 of file DfsSolver.cpp.

References CheckTransposition(), HandleTerminalNode(), m_state, DfsData::m_win, m_workBrd, and ProofUtil::MaximumProofSet().

Referenced by SolveState().

void DfsSolver::HandleProof	(	const PointSequence &	variation,
		bool	winning_state,
		DfsSolutionSet &	solution
	)			`[private]`

Shrinks/verifies proof then stores it.

Todo:: HANDLE BEST MOVES PROPERLY! This can only happen if the mustplay goes empty in an internal state that wasn't determined initially, or in a decomp state where the fillin causes a terminal state.

Definition at line 462 of file DfsSolver.cpp.

References DfsBranchStatistics::cells_removed, HexPointUtil::colorEdge1(), HexPointUtil::colorEdge2(), BoardUtils::ConnectedOnBitset(), HexBoard::Const(), benzene_bitset< _Nb >::count(), EMPTY_BITSET, StoneBoard::GetColor(), HexBoard::GetDead(), HexBoard::GetPosition(), HexBoard::ICE(), INVALID_POINT, m_aborted, DfsSolutionSet::m_numMoves, m_shrink_proofs, m_state, m_workBrd, DfsSolutionSet::proof, DfsSolutionSet::pv, BoardUtils::ReachableOnBitset(), ProofUtil::ShrinkProof(), DfsBranchStatistics::shrunk, DfsSolutionSet::stats, StoreState(), HexPointUtil::ToString(), DfsBranchStatistics::total_states, and HexBoard::Write().

Referenced by SolveState().

bool DfsSolver::HandleTerminalNode	(	DfsData &	data,
		bitset_t &	proof
	)			const `[private]`

Returns true if node is terminal.

Fills in data if terminal. Data's bestmove field is not specified here.

Definition at line 158 of file DfsSolver.cpp.

References EndgameUtils::IsLostGame(), EndgameUtils::IsWonGame(), m_histogram, DfsData::m_numMoves, DfsData::m_numStates, m_state, DfsData::m_win, m_workBrd, and DfsHistogram::terminal.

Referenced by HandleLeafNode(), OrderMoves(), and SolveDecomposition().

DfsHistogram DfsSolver::Histogram ( ) const [inline]

Returns histogram of last search.

Definition at line 456 of file DfsSolver.hpp.

References m_histogram.

Referenced by DfsCommands::CmdHistogram().

int DfsSolver::MoveOrdering ( ) const [inline]

Returns the move order flags.

Definition at line 446 of file DfsSolver.hpp.

References m_move_ordering.

Referenced by DfsCommands::CmdParamSolver().

bool DfsSolver::OrderMoves	(	bitset_t &	mustplay,
		DfsSolutionSet &	solution,
		std::vector< HexMoveValue > &	moves
	)			`[private]`

Orders the moves in mustplay using several heuristics.

Aborts move ordering early if it finds a TT win: winning move is put to the front.

Will shrink the mustplay if it encounters TT losses: losing moves are not added to the list of sorted moves.

Returns true if it found a TT win, false otherwise.

The TT/DB checks are done as a single 1-ply sweep prior to any move ordering, since computing the VCs for any solved states is pointless, plus these may resolve the current state immediately.

Definition at line 570 of file DfsSolver.cpp.

References CheckTransposition(), HexPointUtil::colorEdge1(), HexPointUtil::colorEdge2(), HexBoard::Cons(), HexBoard::Const(), benzene_bitset< _Nb >::count(), DfsSolverUtil::DistanceFromCenter(), VCSet::Exists(), DfsBranchStatistics::explored_states, DfsMoveOrderFlags::FROM_CENTER, VCUtils::GetMustplay(), HexBoard::GetPosition(), HandleTerminalNode(), HexAssert, ProofUtil::InitialProofForOpponent(), BitsetUtil::IsSubsetOf(), LogFine(), m_backup_ice_info, m_move_ordering, DfsData::m_numMoves, DfsSolutionSet::m_numMoves, DfsData::m_numStates, m_state, DfsData::m_win, m_workBrd, ProofUtil::MaximumProofSet(), DfsBranchStatistics::minimal_explored, EndgameUtils::MovesToConsider(), PlayMove(), StoneBoard::PlayMove(), DfsSolutionSet::proof, VC::SEMI, benzene_bitset< _Nb >::set(), DfsSolutionSet::SetPV(), DfsSolutionSet::stats, benzene_bitset< _Nb >::test(), DfsBranchStatistics::total_states, UndoMove(), StoneBoard::UndoMove(), DfsMoveOrderFlags::WITH_MUSTPLAY, DfsMoveOrderFlags::WITH_RESIST, and HexBoard::Write().

Referenced by SolveInteriorState().

void DfsSolver::PlayMove ( HexPoint cell ) [private]

Plays the move; updates the board.

Definition at line 544 of file DfsSolver.cpp.

References m_state, m_statistics, m_workBrd, DfsSolver::GlobalStatistics::played, and HexBoard::PlayMove().

Referenced by OrderMoves(), and SolveInteriorState().

int DfsSolver::ProgressDepth ( ) const

Depth from root in which the current variation is printed.

void DfsSolver::SetBackupIceInfo ( bool enable ) [inline]

See BackupIceInfo().

Definition at line 431 of file DfsSolver.hpp.

References m_backup_ice_info.

Referenced by DfsCommands::CmdParamSolver().

void DfsSolver::SetMoveOrdering ( int flags ) [inline]

See MoveOrdering().

Definition at line 451 of file DfsSolver.hpp.

References m_move_ordering.

Referenced by DfsCommands::CmdParamSolver().

void DfsSolver::SetProgressDepth ( int depth )

See ProgressDepth().

void DfsSolver::SetShrinkProofs ( bool enable ) [inline]

See ShrinkProofs().

Definition at line 421 of file DfsSolver.hpp.

References m_shrink_proofs.

Referenced by DfsCommands::CmdParamSolver().

void DfsSolver::SetUpdateDepth ( int depth ) [inline]

See UpdateDepth().

Definition at line 411 of file DfsSolver.hpp.

References m_update_depth.

Referenced by DfsCommands::CmdParamSolver().

void DfsSolver::SetUseDecompositions ( bool enable ) [inline]

See UseDecompositions().

Definition at line 401 of file DfsSolver.hpp.

References m_use_decompositions.

Referenced by DfsCommands::CmdParamSolver().

void DfsSolver::SetUseGuiFx ( bool enable ) [inline]

See UseGuiFx().

Definition at line 441 of file DfsSolver.hpp.

References m_use_guifx.

Referenced by DfsCommands::CmdParamSolver().

bool DfsSolver::ShrinkProofs ( ) const [inline]

Whether ICE is used to provably shrink proofs.

Definition at line 416 of file DfsSolver.hpp.

References m_shrink_proofs.

Referenced by DfsCommands::CmdParamSolver().

HexColor DfsSolver::Solve	(	const HexState &	state,
		HexBoard &	board,
		DfsSolutionSet &	solution,
		DfsStates &	positions,
		int	depthLimit = `-1`,
		double	timeLimit = `-1.0`
	)