DfpnSolver Class Reference
[Depth-First Proof Number Search]

Hex solver using DFPN search. More...

#include <DfpnSolver.hpp>

Classes
class	GuiFx
	Handles guifx output. More...
Public Member Functions
	DfpnSolver ()
	~DfpnSolver ()
HexColor	StartSearch (const HexState &state, HexBoard &brd, DfpnStates &positions, PointSequence &pv)
	Solves the given state using the given hashtable.
HexColor	StartSearch (const HexState &state, HexBoard &brd, DfpnStates &positions, PointSequence &pv, const DfpnBounds &maxBounds)
void	AddListener (DfpnListener &listener)
std::string	EvaluationInfo () const
	Returns various histograms pertaining to the evaluation function from the last search.
void	PropagateBackwards (const Game &game, DfpnStates &pos)
	Updates bounds from this state to start of game or a state is not in position set.
Parameters

bool	UseGuiFx () const
	Dumps output about root state what gui can display.
void	SetUseGuiFx (bool enable)
	See UseGuiFx().
double	Timelimit () const
	Maximum time search is allowed to run before aborting.
void	SetTimelimit (double timelimit)
	See Timelimit().
int	WideningBase () const
	Widening base affects what number of the moves to consider are always looked at by the dfpn search (omitting losing moves), regardless of branching factor.
void	SetWideningBase (int wideningBase)
	See WideningBase().
float	WideningFactor () const
	Widening factor affects what fraction of the moves to consider are looked at by the dfpn search (omitting losing moves).
void	SetWideningFactor (float wideningFactor)
	See WideningFactor().
Private Member Functions
size_t	MID (const DfpnBounds &n, DfpnHistory &history)
void	SelectChild (int &bestMove, DfpnBoundType &delta2, const std::vector< DfpnData > &childrenDfpnBounds, size_t maxChildIndex) const
void	UpdateBounds (DfpnBounds &bounds, const std::vector< DfpnData > &childBounds, size_t maxChildIndex) const
bool	CheckAbort ()
void	LookupData (DfpnData &data, const DfpnChildren &children, int childIndex, HexState &state)
bool	TTRead (const HexState &state, DfpnData &data)
void	TTWrite (const HexState &state, const DfpnData &data)
void	DumpGuiFx (const std::vector< HexPoint > &children, const std::vector< DfpnBounds > &childBounds) const
void	PrintStatistics (HexColor winner, const PointSequence &p) const
size_t	ComputeMaxChildIndex (const std::vector< DfpnData > &childrenData) const
void	DeleteChildren (DfpnChildren &children, std::vector< DfpnData > &childrenData, bitset_t deleteChildren) const
void	NotifyListeners (const DfpnHistory &history, const DfpnData &data)
Private Attributes
boost::scoped_ptr< HexState >	m_state
HexBoard *	m_workBoard
DfpnStates *	m_positions
std::vector< DfpnListener * >	m_listener
SgTimer	m_timer
bool	m_useGuiFx
	See UseGuiFx().
double	m_timelimit
	See TimeLimit().
int	m_wideningBase
	See WideningBase().
float	m_wideningFactor
	See WideningFactor().
size_t	m_checkTimerAbortCalls
	Number of calls to CheckAbort() before we check the timer.
bool	m_aborted
GuiFx	m_guiFx
size_t	m_numTerminal
size_t	m_numMIDcalls
size_t	m_numVCbuilds
SgStatisticsExt< float, std::size_t >	m_prunedSiblingStats
SgStatisticsExt< float, std::size_t >	m_moveOrderingPercent
SgStatisticsExt< float, std::size_t >	m_moveOrderingIndex
SgStatisticsExt< float, std::size_t >	m_considerSetSize
SgStatisticsExt< float, std::size_t >	m_deltaIncrease
size_t	m_totalWastedWork
SgHistogram< float, std::size_t >	m_allEvaluation
SgHistogram< float, std::size_t >	m_allSolvedEvaluation
SgHistogram< float, std::size_t >	m_winningEvaluation
SgHistogram< float, std::size_t >	m_losingEvaluation

Detailed Description

Hex solver using DFPN search.

Definition at line 420 of file DfpnSolver.hpp.

Constructor & Destructor Documentation

DfpnSolver::DfpnSolver ( )

Definition at line 246 of file DfpnSolver.cpp.

DfpnSolver::~DfpnSolver ( )

Definition at line 260 of file DfpnSolver.cpp.

Member Function Documentation

void DfpnSolver::AddListener ( DfpnListener & listener ) [inline]

Definition at line 618 of file DfpnSolver.hpp.

References m_listener.

bool DfpnSolver::CheckAbort ( ) [private]

Definition at line 379 of file DfpnSolver.cpp.

References LogInfo(), m_aborted, m_checkTimerAbortCalls, m_numMIDcalls, m_timelimit, and m_timer.

Referenced by MID().

size_t DfpnSolver::ComputeMaxChildIndex ( const std::vector< DfpnData > & childrenData ) const [private]

Definition at line 652 of file DfpnSolver.cpp.

References HexAssert, WideningBase(), and WideningFactor().

Referenced by MID(), and PropagateBackwards().

void DfpnSolver::DeleteChildren	(	DfpnChildren &	children,
		std::vector< DfpnData > &	childrenData,
		bitset_t	deleteChildren
	)			const `[private]`

Definition at line 681 of file DfpnSolver.cpp.

References HexAssert, DfpnChildren::m_children, DfpnChildren::Size(), and benzene_bitset< _Nb >::test().

Referenced by MID().

void DfpnSolver::DumpGuiFx	(	const std::vector< HexPoint > &	children,
		const std::vector< DfpnBounds > &	childBounds
	)			const `[private]`

std::string DfpnSolver::EvaluationInfo ( ) const

Returns various histograms pertaining to the evaluation function from the last search.

Definition at line 304 of file DfpnSolver.cpp.

References m_allEvaluation, m_allSolvedEvaluation, m_losingEvaluation, and m_winningEvaluation.

Referenced by DfpnCommands::CmdEvaluationInfo().

void DfpnSolver::LookupData	(	DfpnData &	data,
		const DfpnChildren &	children,
		int	childIndex,
		HexState &	state
	)			`[private]`

Definition at line 769 of file DfpnSolver.cpp.

References DfpnBounds::delta, DfpnData::m_bounds, DfpnData::m_work, DfpnBounds::phi, DfpnChildren::PlayMove(), TTRead(), and DfpnChildren::UndoMove().

Referenced by MID(), and PropagateBackwards().

size_t DfpnSolver::MID	(	const DfpnBounds &	n,
		DfpnHistory &	history
	)			`[private]`

Definition at line 418 of file DfpnSolver.cpp.

References BLACK, CheckAbort(), DfpnBounds::CheckConsistency(), HexBoard::ComputeAll(), ComputeMaxChildIndex(), benzene_bitset< _Nb >::count(), DeleteChildren(), DfpnBounds::delta, DfpnHistory::Depth(), Resistance::Evaluate(), DfpnChildren::FirstMove(), HexBoard::GetPosition(), DfpnBounds::GreaterThan(), hash_t, HexAssert, HexEval, DfpnBounds::INFTY, INVALID_POINT, EndgameUtils::IsDeterminedState(), DfpnBounds::IsLosing(), DfpnBounds::IsSolved(), EndgameUtils::IsWonGame(), LookupData(), m_allEvaluation, m_allSolvedEvaluation, DfpnData::m_bounds, DfpnChildren::m_children, DfpnData::m_children, m_considerSetSize, m_deltaIncrease, DfpnData::m_evaluationScore, m_guiFx, m_losingEvaluation, DfpnData::m_maxProofSet, m_moveOrderingIndex, m_moveOrderingPercent, m_numMIDcalls, m_numTerminal, m_numVCbuilds, m_prunedSiblingStats, m_state, m_totalWastedWork, m_useGuiFx, m_winningEvaluation, DfpnData::m_work, m_workBoard, ProofUtil::MaximumProofSet(), EndgameUtils::MovesToConsider(), NotifyListeners(), DfpnBounds::phi, DfpnChildren::PlayMove(), DfpnSolver::GuiFx::PlayMove(), DfpnHistory::Pop(), DfpnHistory::Push(), benzene_bitset< _Nb >::reset(), Resistance::Score(), SelectChild(), benzene_bitset< _Nb >::set(), DfpnSolver::GuiFx::SetChildren(), DfpnChildren::SetChildren(), StoneBoard::SetPosition(), DfpnBounds::SetToLosing(), DfpnBounds::SetToWinning(), DfpnChildren::Size(), TTRead(), TTWrite(), DfpnSolver::GuiFx::UndoMove(), DfpnChildren::UndoMove(), UpdateBounds(), DfpnSolver::GuiFx::UpdateCurrentBounds(), DfpnSolver::GuiFx::Write(), and DfpnSolver::GuiFx::WriteForced().

Referenced by StartSearch().

void DfpnSolver::NotifyListeners	(	const DfpnHistory &	history,
		const DfpnData &	data
	)			`[private]`

Definition at line 710 of file DfpnSolver.cpp.

References m_listener.

Referenced by MID().

void DfpnSolver::PrintStatistics	(	HexColor	winner,
		const PointSequence &	p
	)			const `[private]`

Definition at line 264 of file DfpnSolver.cpp.

References SolverDB< HASH, DB, DATA >::Database(), StateDB< T >::GetStatistics(), SolverDB< HASH, DB, DATA >::HashTable(), LogInfo(), m_considerSetSize, m_deltaIncrease, m_moveOrderingIndex, m_moveOrderingPercent, m_numMIDcalls, m_numTerminal, m_numVCbuilds, m_positions, m_prunedSiblingStats, m_timer, m_totalWastedWork, TransTable< T >::Stats(), and HexPointUtil::ToString().

Referenced by StartSearch().

void DfpnSolver::PropagateBackwards	(	const Game &	game,
		DfpnStates &	pos
	)

Updates bounds from this state to start of game or a state is not in position set.

Definition at line 795 of file DfpnSolver.cpp.

References BLACK, Game::Board(), ComputeMaxChildIndex(), SolverDB< HASH, DB, DATA >::Get(), Game::History(), DfpnBounds::IsSolved(), LookupData(), DfpnData::m_bounds, DfpnData::m_children, SolverDB< HASH, DB, DATA >::Put(), DfpnChildren::Size(), and UpdateBounds().

Referenced by PerfectPlayer::Search().

void DfpnSolver::SelectChild	(	int &	bestMove,
		DfpnBoundType &	delta2,
		const std::vector< DfpnData > &	childrenDfpnBounds,
		size_t	maxChildIndex
	)			const `[private]`

Definition at line 717 of file DfpnSolver.cpp.

References DfpnBounds::delta, HexAssert, DfpnBounds::INFTY, and DfpnBounds::IsLosing().

Referenced by MID().

void DfpnSolver::SetTimelimit ( double timelimit ) [inline]

See Timelimit().

Definition at line 640 of file DfpnSolver.hpp.

References m_timelimit.

Referenced by DfpnCommands::CmdParam(), and PerfectPlayer::Search().

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

See UseGuiFx().

Definition at line 630 of file DfpnSolver.hpp.

References m_useGuiFx.

Referenced by DfpnCommands::CmdParam().

void DfpnSolver::SetWideningBase ( int wideningBase ) [inline]

See WideningBase().

Definition at line 650 of file DfpnSolver.hpp.

References m_wideningBase.

Referenced by DfpnCommands::CmdParam().

void DfpnSolver::SetWideningFactor ( float wideningFactor ) [inline]

See WideningFactor().

Definition at line 660 of file DfpnSolver.hpp.

References m_wideningFactor.

Referenced by DfpnCommands::CmdParam().

HexColor DfpnSolver::StartSearch	(	const HexState &	state,
		HexBoard &	brd,
		DfpnStates &	positions,
		PointSequence &	pv,
		const DfpnBounds &	maxBounds
	)

HexColor DfpnSolver::StartSearch	(	const HexState &	state,
		HexBoard &	brd,
		DfpnStates &	positions,
		PointSequence &	pv
	)

Solves the given state using the given hashtable.

Returns the color of the winning player (EMPTY if it could not determine a winner in time).

Definition at line 318 of file DfpnSolver.cpp.

References DfpnBounds::MAX_WORK.

Referenced by DfpnCommands::CmdFindWinning(), DfpnCommands::CmdSolveState(), PlayAndSolve::SolverThread::operator()(), and PerfectPlayer::Search().

double DfpnSolver::Timelimit ( ) const [inline]

Maximum time search is allowed to run before aborting.

Set to 0 for no timelimit.

Definition at line 635 of file DfpnSolver.hpp.

References m_timelimit.

Referenced by DfpnCommands::CmdParam(), and PerfectPlayer::Search().

bool DfpnSolver::TTRead	(	const HexState &	state,
		DfpnData &	data
	)			`[private]`

Definition at line 782 of file DfpnSolver.cpp.

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

Referenced by LookupData(), MID(), and StartSearch().

void DfpnSolver::TTWrite	(	const HexState &	state,
		const DfpnData &	data
	)			`[private]`

Definition at line 787 of file DfpnSolver.cpp.

References DfpnBounds::CheckConsistency(), DfpnData::m_bounds, m_positions, and SolverDB< HASH, DB, DATA >::Put().

Referenced by MID().

void DfpnSolver::UpdateBounds	(	DfpnBounds &	bounds,
		const std::vector< DfpnData > &	childBounds,
		size_t	maxChildIndex
	)			const `[private]`

Definition at line 747 of file DfpnSolver.cpp.

References DfpnBounds::delta, HexAssert, DfpnBounds::INFTY, DfpnBounds::IsLosing(), DfpnBounds::phi, and DfpnBounds::SetToWinning().

Referenced by MID(), and PropagateBackwards().

bool DfpnSolver::UseGuiFx ( ) const [inline]

Dumps output about root state what gui can display.

Definition at line 625 of file DfpnSolver.hpp.

References m_useGuiFx.

Referenced by DfpnCommands::CmdParam().

int DfpnSolver::WideningBase ( ) const [inline]

Widening base affects what number of the moves to consider are always looked at by the dfpn search (omitting losing moves), regardless of branching factor.

This amount is added to the proportion computed by the WideningFactor (see below). The base must be set to at least 1.

Definition at line 645 of file DfpnSolver.hpp.

References m_wideningBase.

Referenced by DfpnCommands::CmdParam(), and ComputeMaxChildIndex().

float DfpnSolver::WideningFactor ( ) const [inline]

Widening factor affects what fraction of the moves to consider are looked at by the dfpn search (omitting losing moves).

Must be in the range (0, 1], where 1 ensures no pruning.

Definition at line 655 of file DfpnSolver.hpp.

References m_wideningFactor.

Referenced by DfpnCommands::CmdParam(), and ComputeMaxChildIndex().