Alpha-beta search. More...

#include <SgSearch.h>

Public Member Functions
	SgSearch (SgSearchHashTable *hash)
	Constructor.
virtual	~SgSearch ()
virtual bool	CheckDepthLimitReached () const =0
	Stop search if depth limit was not reached in current iteration.
const SgSearchHashTable *	HashTable () const
void	SetHashTable (SgSearchHashTable *hashtable)
const SgSearchControl *	SearchControl () const
void	SetSearchControl (SgSearchControl *control)
	Search control.
void	SetProbCut (SgProbCut *probcut)
	ProbCut.
virtual std::string	MoveString (SgMove move) const =0
	Convert move to string (game dependent).
virtual void	SetToPlay (SgBlackWhite toPlay)=0
virtual void	OnStartSearch ()
	Hook function called at the beginning of a search.
int	DepthFirstSearch (int depthLimit, int boundLo, int boundHi, SgVector< SgMove > sequence, bool clearHash=true, SgNode traceNode=0)
	Looks 'depthLimit' moves ahead to find the value of the current position and the optimal sequence.
int	DepthFirstSearch (int depthLimit, SgVector< SgMove > sequence, bool clearHash=true, SgNode traceNode=0)
	Call DepthFirstSearch with window [-SG_INFINITY,+SG_INFINITY].
int	IteratedSearch (int depthMin, int depthMax, int boundLo, int boundHi, SgVector< SgMove > sequence, bool clearHash=true, SgNode traceNode=0)
	Calls DepthFirstSearch repeatedly with the depth limit starting at 'depthMin' and increasing with each iteration.
int	IteratedSearch (int depthMin, int depthMax, SgVector< SgMove > sequence, bool clearHash=true, SgNode traceNode=0)
	Call IteratedSearch with window [-SG_INFINITY,+SG_INFINITY].
int	IteratedSearchDepthLimit () const
	During IteratedSearch or CombinedSearch, this returns the current depth that's being searched to.
virtual void	StartOfDepth (int depthLimit)
	Called at start of each depth level of IteratedSearch.
bool	Aborted () const
	Return whether the search was aborted.
void	SetAbortSearch (bool fAborted=true)
	Mark this search as aborted.
void	SetScout (bool flag=true)
void	SetKillers (bool flag=true)
void	SetOpponentBest (bool flag=true)
void	SetNullMove (bool flag=true)
void	SetNullMoveDepth (int depth)
void	GetStatistics (SgSearchStatistics *stat)
	Get the current statistics.
const SgSearchStatistics &	Statistics () const
void	StartTime ()
	Starts the clock and clears the statistics.
void	StopTime ()
	Stops the clock and clears the statistics.
virtual void	Generate (SgVector< SgMove > *moves, int depth)=0
	Generate moves.
virtual int	Evaluate (bool *isExact, int depth)=0
	The returned value reflects the value of the position, with positive values being good for the current player (ToPlay).
virtual bool	Execute (SgMove move, int *delta, int depth)=0
	Return true if the move was executed, false if it was illegal and could not be played.
virtual void	TakeBack ()=0
	Takes back the most recent move successfully executed by Execute.
virtual SgBlackWhite	GetToPlay () const =0
	Return the current player.
virtual bool	AbortSearch ()
	Test whether search should be aborted.
virtual SgHashCode	GetHashCode () const =0
	Return the hash code for the current position.
int	CurrentDepth () const
	The current depth of the search, incremented by 1 for each move that's played.
SgMove	PrevMove () const
	Indicates which move in the movelist at the previous level was executed.
SgMove	PrevMove2 () const
	The move prior to the previous move.
virtual bool	EndOfGame () const =0
	Is the game over?
void	InitSearch (int startDepth=0)
	Initialize PrevMove, CurrentDepth and other variables so that they can be accessed when move generation/evaluation are called directly, not as part of a search.
bool	TraceIsOn () const
	Is tracing currently active?
virtual void	CreateTracer ()
	Default creates a SgSearchTracer; override for specific traces.
void	SetTracer (SgSearchTracer *tracer)
	Set tracer object.
SgSearchTracer *	Tracer () const
void	SetAbortFrequency (int value)
int	SearchEngine (int depth, int alpha, int beta, SgSearchStack &stack, bool *isExactValue, bool lastNullMove=false)
	Core Alpha-beta search.
Static Public Attributes
static const int	DEPTH_UNIT = 100
	One DEPTH_UNIT corresponds to the default search depth for one move, in the internal representation of search.
static const int	MAX_DEPTH = 256
	Remark: could make it 512 if deep ladder search a problem.
static const int	SG_INFINITY = numeric_limits<int>::max()
	Infinity for windowed searches.
Private Member Functions
int	DFS (int startDepth, int depthLimit, int boundLo, int boundHi, SgVector< SgMove > sequence, bool isExactValue)
	Depth-first search (see implementation).
bool	LookupHash (SgSearchHashData &data) const
	Try to find current position in m_hash.
bool	NullMovePrune (int depth, int delta, int beta)
void	StoreHash (int depth, int value, SgMove move, bool isUpperBound, bool isLowerBound, bool isExact)
	Store current position in hash table.
void	AddSequenceToHash (const SgVector< SgMove > &sequence, int depth)
	Seed the hash table with the given sequence.
int	CallEvaluate (int depth, bool *isExact)
	Evaluate current position; possibly write debug output.
bool	CallExecute (SgMove move, int *delta, int depth)
	Execute move; update m_moveStack, m_currentDepth and statistics.
void	CallGenerate (SgVector< SgMove > *moves, int depth)
	Generate moves; possibly write debug output.
void	CallTakeBack ()
	Take back move; update m_moveStack and m_currentDepth.
bool	TryMove (SgMove move, const SgVector< SgMove > &specialMoves, const int depth, const int alpha, const int beta, int &loValue, int &hiValue, SgSearchStack &stack, bool &allExact, bool &isCutoff)
bool	TrySpecialMove (SgMove move, SgVector< SgMove > &specialMoves, const int depth, const int alpha, const int beta, int &loValue, int &hiValue, SgSearchStack &stack, bool &allExact, bool &isCutoff)
	SgSearch (const SgSearch &)
	Not implemented.
SgSearch &	operator= (const SgSearch &)
	Not implemented.
Private Attributes
SgSearchHashTable *	m_hash
	Hash table.
SgSearchTracer *	m_tracer
	Used to build a trace tree of the search for debugging.
int	m_currentDepth
	The depth of the current position - number of moves from start.
int	m_depthLimit
SgVector< SgMove >	m_moveStack
	Stack of all moves executed in search.
bool	m_useScout
bool	m_useKillers
bool	m_useOpponentBest
	Move best move from parent to front.
bool	m_useNullMove
	Use null move heuristic for forward pruning.
int	m_nullMoveDepth
	How much less deep to search during null move pruning.
bool	m_aborted
	True if search is in the process of being aborted.
bool	m_foundNewBest
	Flag that new best move was found in current iteration.
bool	m_reachedDepthLimit
	Keeps track of whether the depth limit was reached.
SgSearchStatistics	m_stat
SgTimer	m_timer
int	m_timerLevel
int	m_prevValue
	The search result from the previous iteration.
SgVector< SgMove >	m_prevSequence
	The PV from the previous search iteration.
SgArray< SgKiller, MAX_KILLER_DEPTH+1 >	m_killers
	Killer heuristic.
SgSearchControl *	m_control
SgProbCut *	m_probcut
int	m_abortFrequency
Static Private Attributes
static const int	MAX_KILLER_DEPTH = 10

Detailed Description

Alpha-beta search.

The problem-specific part of the search is isolated in five methods: move generation, position evaluation, executing and taking back moves, and time control. These need to be overridden for each kind of search. The evaluation may employ lookahead or a quiescence search to find the value. If so, the sequence from the current position to the position where that value is really reached is returned, otherwise the empty list is returned.

Todo:

Why does AmaSearch::Evaluate need the hash table, shouldn't that be done in SgSearch?

Remove m_depth, pass as argument to Evaluate instead

Use best-response as move ordering heuristic

Definition at line 239 of file SgSearch.h.

Constructor & Destructor Documentation

SgSearch::SgSearch ( SgSearchHashTable * hash )

Constructor.

Parameters:

hash

Hash table to use or 0, if no hash table should be used.

Definition at line 127 of file SgSearch.cpp.

References InitSearch().

SgSearch::~SgSearch ( ) [virtual]

Definition at line 148 of file SgSearch.cpp.

SgSearch::SgSearch ( const SgSearch & ) [private]

Not implemented.

Member Function Documentation

bool SgSearch::Aborted ( ) const

Return whether the search was aborted.

Definition at line 572 of file SgSearch.h.

References m_aborted.

bool SgSearch::AbortSearch ( ) [virtual]

Test whether search should be aborted.

Return true to abort search. Default implementation checks Abort() of the installed search control.

Definition at line 224 of file SgSearch.cpp.

References SgSearchControl::Abort(), SgTimer::GetTime(), m_aborted, m_abortFrequency, m_control, m_stat, m_timer, m_tracer, SgSearchStatistics::NumNodes(), SgUserAbort(), SgSearchTracer::TraceComment(), and TraceIsOn().

Referenced by SearchEngine().

void SgSearch::AddSequenceToHash	(	const SgVector< SgMove > &	sequence,
		int	depth
	)			`[private]`

Seed the hash table with the given sequence.

Definition at line 332 of file SgSearch.cpp.

References CallExecute(), CallTakeBack(), DEPTH_UNIT, GetHashCode(), m_hash, MoveString(), SG_ASSERT, SG_NULLMOVE, SgDebug(), and SgHashTable< DATA >::Store().

Referenced by DepthFirstSearch(), and IteratedSearch().

int SgSearch::CallEvaluate	(	int	depth,
		bool *	isExact
	)			`[private]`

Evaluate current position; possibly write debug output.

Definition at line 286 of file SgSearch.cpp.

References Evaluate(), and SgDebug().

Referenced by SearchEngine().

bool SgSearch::CallExecute	(	SgMove	move,
		int *	delta,
		int	depth
	)			`[private]`

Execute move; update m_moveStack, m_currentDepth and statistics.

Definition at line 296 of file SgSearch.cpp.

References SgSearchTracer::AddTraceNode(), Execute(), GetToPlay(), SgSearchStatistics::IncNumMoves(), SgSearchStatistics::IncNumPassMoves(), m_currentDepth, m_moveStack, m_stat, m_tracer, MoveString(), SgVector< T >::PushBack(), SG_PASS, SgBW(), SgDebug(), and TraceIsOn().

Referenced by AddSequenceToHash(), NullMovePrune(), SearchEngine(), and TryMove().

void SgSearch::CallGenerate	(	SgVector< SgMove > *	moves,
		int	depth
	)			`[private]`

Generate moves; possibly write debug output.

Definition at line 152 of file SgSearch.cpp.

References Generate(), and SgDebug().

Referenced by SearchEngine().

void SgSearch::CallTakeBack ( ) [private]

Take back move; update m_moveStack and m_currentDepth.

Definition at line 316 of file SgSearch.cpp.

References m_currentDepth, m_moveStack, m_tracer, SgVector< T >::PopBack(), SgDebug(), TakeBack(), SgSearchTracer::TakeBackTraceNode(), and TraceIsOn().

Referenced by AddSequenceToHash(), NullMovePrune(), SearchEngine(), and TryMove().

virtual bool SgSearch::CheckDepthLimitReached ( ) const [pure virtual]

Stop search if depth limit was not reached in current iteration.

Usually this should return true, but it depends on the move generation in the subclass. For example, if the move generation prunes some moves at lower depths, because the goal cannot be reached at the current depth, this function has to return false.

Referenced by IteratedSearch().

void SgSearch::CreateTracer ( ) [virtual]

Default creates a SgSearchTracer; override for specific traces.

Definition at line 327 of file SgSearch.cpp.

References m_tracer.

int SgSearch::CurrentDepth ( ) const

The current depth of the search, incremented by 1 for each move that's played.

Value is 0 at root level of search.

Definition at line 577 of file SgSearch.h.

References m_currentDepth.

int SgSearch::DepthFirstSearch	(	int	depthLimit,
		int	boundLo,
		int	boundHi,
		SgVector< SgMove > *	sequence,
		bool	clearHash = `true`,
		SgNode *	traceNode = `0`
	)

Looks 'depthLimit' moves ahead to find the value of the current position and the optimal sequence.

No values outside the range ['boundLo'..'boundHi'] are expected; if values outside that range are encountered, a value <= 'boundLo' or >= 'boundHi' will be returned, and the search should be repeated with new bounds. If node is not 0, then add the whole search tree below '*node'. The hash table is seeded with the sequence passed in, so that partial results from a previous search can speed up a re-search.

Definition at line 387 of file SgSearch.cpp.

References AddSequenceToHash(), SgSearchTracer::AppendTrace(), SgHashTable< DATA >::Clear(), DFS(), SgSearchTracer::InitTracing(), m_depthLimit, m_hash, m_tracer, OnStartSearch(), SG_ASSERT, StartTime(), StopTime(), SgSearchTracer::TraceIsOn(), and SgSearchTracer::TraceNode().

Referenced by DepthFirstSearch().

int SgSearch::DepthFirstSearch	(	int	depthLimit,
		SgVector< SgMove > *	sequence,
		bool	clearHash = `true`,
		SgNode *	traceNode = `0`
	)

Call DepthFirstSearch with window [-SG_INFINITY,+SG_INFINITY].

Definition at line 582 of file SgSearch.h.

References DepthFirstSearch(), and SG_INFINITY.

int SgSearch::DFS	(	int	startDepth,
		int	depthLimit,
		int	boundLo,
		int	boundHi,
		SgVector< SgMove > *	sequence,
		bool *	isExactValue
	)			`[private]`

Depth-first search (see implementation).

Definition at line 369 of file SgSearch.cpp.

References DEPTH_UNIT, InitSearch(), m_aborted, m_currentDepth, m_foundNewBest, SearchEngine(), and SG_ASSERT.

Referenced by DepthFirstSearch(), and IteratedSearch().

virtual bool SgSearch::EndOfGame ( ) const [pure virtual]

Is the game over?

Referenced by SearchEngine().

virtual int SgSearch::Evaluate	(	bool *	isExact,
		int	depth
	)			`[pure virtual]`

The returned value reflects the value of the position, with positive values being good for the current player (ToPlay).

Parameters:

	isExact	Return value, if set, the value is exact, even if it is not a terminal positions and Generate would generate moves.
	depth	See SgSearch::Generate()

Returns:: The evaluation of the current position.

Referenced by CallEvaluate().

virtual bool SgSearch::Execute	(	SgMove	move,
		int *	delta,
		int	depth
	)			`[pure virtual]`

Return true if the move was executed, false if it was illegal and could not be played.

Parameters:

	move
	delta	The amount by which that move shall decrement the current depth. Normal is DEPTH_UNIT, but forcing moves may return a delta of zero to look deeper into one variation.
	depth	See SgSearch::Generate() (Execute could need to know the depth to reject moves depending on the depth that were originally generated, e.g. used in ExCaptureTask::Execute)

Referenced by CallExecute().

virtual void SgSearch::Generate	(	SgVector< SgMove > *	moves,
		int	depth
	)			`[pure virtual]`

Generate moves.

Parameters:

	moves	The returned list is the set of moves to be tried. These moves will be tested for legality, so illegal moves can also be included if that speeds up move generation. If the empty list is returned, the evaluation function will be called with the same position right away (thus an evaluation done during move generation can be saved and returned from the move evaluation).
	depth	The remaining depth until a terminal node is reached (height > 0). Note that this is a fractional value: each move may be counted as less than one full move to look deeper in some variations. The value is expressed in DEPTH_UNIT rather than using float to be stored compactly in the hash table.

Referenced by CallGenerate().

virtual SgHashCode SgSearch::GetHashCode ( ) const [pure virtual]

Return the hash code for the current position.

Referenced by AddSequenceToHash(), LookupHash(), and StoreHash().

void SgSearch::GetStatistics ( SgSearchStatistics * stat )

Get the current statistics.

Can be called during search.

Definition at line 265 of file SgSearch.cpp.

References SgTimer::GetTime(), m_stat, m_timer, and SgSearchStatistics::SetTimeUsed().

virtual SgBlackWhite SgSearch::GetToPlay ( ) const [pure virtual]

Return the current player.

Referenced by CallExecute(), and SearchEngine().

const SgSearchHashTable * SgSearch::HashTable ( ) const

Definition at line 590 of file SgSearch.h.

References m_hash.

void SgSearch::InitSearch ( int startDepth = 0 )

Initialize PrevMove, CurrentDepth and other variables so that they can be accessed when move generation/evaluation are called directly, not as part of a search.

Definition at line 163 of file SgSearch.cpp.

References SgVector< T >::Clear(), m_currentDepth, m_killers, m_moveStack, m_useKillers, MAX_KILLER_DEPTH, SgVector< T >::PushBack(), and SG_NULLMOVE.

Referenced by DFS(), and SgSearch().

int SgSearch::IteratedSearch	(	int	depthMin,
		int	depthMax,
		int	boundLo,
		int	boundHi,
		SgVector< SgMove > *	sequence,
		bool	clearHash = `true`,
		SgNode *	traceNode = `0`
	)

Calls DepthFirstSearch repeatedly with the depth limit starting at 'depthMin' and increasing with each iteration.

Stops when the problem is solved, meaning that a result that is definitely good for one of the players is reached, or when 'depthMax' is reached. The bound parameters are just passed to DepthFirstSearch. If node is not 0, then add the whole search tree below '*node'. The hash table is seeded with the sequence passed in, so that partial results from a previous search can speed up a re-search.

Definition at line 414 of file SgSearch.cpp.

References AddSequenceToHash(), SgSearchTracer::AppendTrace(), CheckDepthLimitReached(), SgVector< T >::Clear(), SgHashTable< DATA >::Clear(), DFS(), SgTimer::GetTime(), SgSearchTracer::InitTracing(), m_aborted, m_control, m_depthLimit, m_foundNewBest, m_hash, m_prevSequence, m_prevValue, m_reachedDepthLimit, m_stat, m_timer, m_tracer, SgVector< T >::NonEmpty(), SgSearchStatistics::NumNodes(), OnStartSearch(), SetAbortSearch(), SgSearchStatistics::SetDepthReached(), SG_ASSERT, SgSearchControl::StartNextIteration(), StartOfDepth(), StartTime(), StopTime(), SgSearchTracer::TraceIsOn(), and SgSearchTracer::TraceNode().

Referenced by IteratedSearch().

int SgSearch::IteratedSearch	(	int	depthMin,
		int	depthMax,
		SgVector< SgMove > *	sequence,
		bool	clearHash = `true`,
		SgNode *	traceNode = `0`
	)

Call IteratedSearch with window [-SG_INFINITY,+SG_INFINITY].

Definition at line 605 of file SgSearch.h.

References IteratedSearch(), and SG_INFINITY.

int SgSearch::IteratedSearchDepthLimit ( ) const

During IteratedSearch or CombinedSearch, this returns the current depth that's being searched to.

Definition at line 600 of file SgSearch.h.

References m_depthLimit.

bool SgSearch::LookupHash ( SgSearchHashData & data ) const [private]

Try to find current position in m_hash.

Definition at line 176 of file SgSearch.cpp.

References GetHashCode(), SgSearchHashData::IsValid(), SgHashTable< DATA >::Lookup(), m_hash, SG_ASSERT, and SgDebug().

Referenced by SearchEngine().

virtual std::string SgSearch::MoveString ( SgMove move ) const [pure virtual]

Convert move to string (game dependent).

Referenced by AddSequenceToHash(), and CallExecute().

bool SgSearch::NullMovePrune	(	int	depth,
		int	delta,
		int	beta
	)			`[private]`

Definition at line 243 of file SgSearch.cpp.

References CallExecute(), CallTakeBack(), m_tracer, SearchEngine(), SG_INFINITY, SG_PASS, SgSearchTracer::TraceComment(), and TraceIsOn().

Referenced by SearchEngine().

void SgSearch::OnStartSearch ( ) [virtual]

Hook function called at the beginning of a search.

Default implementation does nothing.

Definition at line 189 of file SgSearch.cpp.

Referenced by DepthFirstSearch(), and IteratedSearch().

SgSearch& SgSearch::operator= ( const SgSearch & ) [private]

Not implemented.

SgMove SgSearch::PrevMove ( ) const

Indicates which move in the movelist at the previous level was executed.

This may be necessary if the value or moves at a position depend on the sequence leading to that position.

Definition at line 614 of file SgSearch.h.

References SgVector< T >::Back(), and m_moveStack.

SgMove SgSearch::PrevMove2 ( ) const

The move prior to the previous move.

Knowing both the last two moves is necessary to decide whether the current position is a seki, where it's best for both players to pass.

Definition at line 619 of file SgSearch.h.

References m_moveStack, and SgVector< T >::TopNth().

const SgSearchControl * SgSearch::SearchControl ( ) const

Definition at line 624 of file SgSearch.h.

References m_control.

int SgSearch::SearchEngine	(	int	depth,
		int	alpha,
		int	beta,
		SgSearchStack &	stack,
		bool *	isExactValue,
		bool	lastNullMove = `false`
	)

Core Alpha-beta search.

Usually not called directly - call DepthFirstSearch or IteratedSearch instead.

Definition at line 588 of file SgSearch.cpp.

References AbortSearch(), SgSearchHashData::AdjustBounds(), SgSearchHashData::BestMove(), CallEvaluate(), CallExecute(), CallGenerate(), CallTakeBack(), SgStack< T, SIZE >::Clear(), SgVector< T >::Contains(), SgSearchHashData::Depth(), DEPTH_UNIT, EndOfGame(), GetToPlay(), SgSearchStatistics::IncNumEvals(), SgSearchStatistics::IncNumNodes(), SgStack< T, SIZE >::IsEmpty(), SgProbCut::IsEnabled(), SgSearchHashData::IsExactValue(), SgSearchValue::IsSolved(), SgSearchHashData::IsValid(), LookupHash(), m_aborted, m_currentDepth, m_hash, m_killers, m_nullMoveDepth, m_probcut, m_reachedDepthLimit, m_stat, m_tracer, m_useKillers, m_useNullMove, m_useOpponentBest, m_useScout, MAX_KILLER_DEPTH, SgStack< T, SIZE >::NonEmpty(), NullMovePrune(), SgProbCut::ProbCut(), SgStack< T, SIZE >::Push(), SgVector< T >::PushBack(), SG_ASSERT, SG_INFINITY, SG_NULLMOVE, StoreHash(), SgStack< T, SIZE >::Top(), SgSearchTracer::TraceComment(), TraceIsOn(), SgSearchTracer::TraceValue(), TryMove(), TrySpecialMove(), and SgSearchHashData::Value().

Referenced by DFS(), NullMovePrune(), SgProbCut::ProbCut(), and TryMove().

void SgSearch::SetAbortFrequency ( int value )

Definition at line 629 of file SgSearch.h.

References m_abortFrequency.

void SgSearch::SetAbortSearch ( bool fAborted = true )

Mark this search as aborted.

Will terminate next time AbortSearch gets called. Or mark search as not having been aborted (e.g. when minimizing area and first search succeeds but second one doesn't have enough time to complete).

Definition at line 634 of file SgSearch.h.

References m_aborted.

Referenced by IteratedSearch().

void SgSearch::SetHashTable ( SgSearchHashTable * hashtable )

Definition at line 595 of file SgSearch.h.

References m_hash.

void SgSearch::SetKillers ( bool flag = true )

Definition at line 639 of file SgSearch.h.

References m_useKillers.

void SgSearch::SetNullMove ( bool flag = true )

Definition at line 644 of file SgSearch.h.

References m_useNullMove.

void SgSearch::SetNullMoveDepth ( int depth )

Definition at line 649 of file SgSearch.h.

References m_nullMoveDepth.

void SgSearch::SetOpponentBest ( bool flag = true )

Definition at line 654 of file SgSearch.h.

References m_useOpponentBest.

void SgSearch::SetProbCut ( SgProbCut * probcut )

ProbCut.

Set the ProbCut bounds; pass 0 to disable ProbCut. Caller keeps ownership of probcut.

Definition at line 199 of file SgSearch.cpp.

References m_probcut.

void SgSearch::SetScout ( bool flag = true )

Definition at line 659 of file SgSearch.h.

References m_useScout.

void SgSearch::SetSearchControl ( SgSearchControl * control )

Search control.

Set the abort checking function; pass 0 to disable abort checking. Caller keeps ownership of control.

Definition at line 194 of file SgSearch.cpp.

References m_control.

virtual void SgSearch::SetToPlay ( SgBlackWhite toPlay ) [pure virtual]

void SgSearch::SetTracer ( SgSearchTracer * tracer )

Set tracer object.

Search object assumes ownership

Definition at line 664 of file SgSearch.h.

References m_tracer, and SG_ASSERT.

void SgSearch::StartOfDepth ( int depthLimit ) [virtual]

Called at start of each depth level of IteratedSearch.

Can be overridden to adapt search (or instrumentation) to current depth. Must call inherited.

Definition at line 880 of file SgSearch.cpp.

References m_aborted, m_tracer, SgDebug(), and SgSearchTracer::StartOfDepth().

Referenced by IteratedSearch().

void SgSearch::StartTime ( )

Starts the clock and clears the statistics.

Can be nested; only the outermost call actually does anything.

Definition at line 271 of file SgSearch.cpp.

References SgSearchStatistics::Clear(), m_stat, m_timer, m_timerLevel, and SgTimer::Start().

Referenced by DepthFirstSearch(), and IteratedSearch().

const SgSearchStatistics& SgSearch::Statistics ( ) const

Definition at line 360 of file SgSearch.h.

References m_stat.

void SgSearch::StopTime ( )

Stops the clock and clears the statistics.

Can be nested; only the outermost call actually does anything.

Definition at line 280 of file SgSearch.cpp.

References SgTimer::IsStopped(), m_timer, m_timerLevel, and SgTimer::Stop().

Referenced by DepthFirstSearch(), and IteratedSearch().

void SgSearch::StoreHash	(	int	depth,
		int	value,
		SgMove	move,
		bool	isUpperBound,
		bool	isLowerBound,
		bool	isExact
	)			`[private]`

Store current position in hash table.

Definition at line 204 of file SgSearch.cpp.

References GetHashCode(), m_hash, SG_ASSERT, SgDebug(), and SgHashTable< DATA >::Store().

Referenced by SearchEngine().

virtual void SgSearch::TakeBack ( ) [pure virtual]

Takes back the most recent move successfully executed by Execute.

Referenced by CallTakeBack().

bool SgSearch::TraceIsOn ( ) const

Is tracing currently active?

Definition at line 219 of file SgSearch.cpp.

References m_tracer, and SgSearchTracer::TraceIsOn().

Referenced by AbortSearch(), CallExecute(), CallTakeBack(), NullMovePrune(), SearchEngine(), and TryMove().

SgSearchTracer * SgSearch::Tracer ( ) const

Definition at line 672 of file SgSearch.h.

References m_tracer.

bool SgSearch::TryMove	(	SgMove	move,
		const SgVector< SgMove > &	specialMoves,
		const int	depth,
		const int	alpha,
		const int	beta,
		int &	loValue,
		int &	hiValue,
		SgSearchStack &	stack,
		bool &	allExact,
		bool &	isCutoff
	)			`[private]`

Definition at line 504 of file SgSearch.cpp.

References CallExecute(), CallTakeBack(), SgVector< T >::Contains(), SgStack< T, SIZE >::CopyFrom(), DEPTH_UNIT, m_aborted, m_currentDepth, m_foundNewBest, m_killers, m_tracer, m_useKillers, m_useScout, MAX_KILLER_DEPTH, SgStack< T, SIZE >::Push(), SearchEngine(), SG_ASSERT, SG_NULLMOVE, SgSearchTracer::TraceComment(), and TraceIsOn().

Referenced by SearchEngine(), and TrySpecialMove().

bool SgSearch::TrySpecialMove	(	SgMove	move,
		SgVector< SgMove > &	specialMoves,
		const int	depth,
		const int	alpha,
		const int	beta,
		int &	loValue,
		int &	hiValue,
		SgSearchStack &	stack,
		bool &	allExact,
		bool &	isCutoff
	)			`[private]`

Definition at line 569 of file SgSearch.cpp.

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

Referenced by SearchEngine().

Member Data Documentation

const int SgSearch::DEPTH_UNIT = 100 [static]

One DEPTH_UNIT corresponds to the default search depth for one move, in the internal representation of search.

Used for fractional ply extensions. E.g. extending from atari in Go may count as only 1/8 ply = DEPTH_UNIT/8. This way forced lines can be searched much deeper at a low nominal search depth.

Definition at line 247 of file SgSearch.h.

Referenced by AddSequenceToHash(), DFS(), SgProbCut::ProbCut(), SearchEngine(), and TryMove().