Computer Chess Club Archives


Search

Terms

Messages

Subject: Basic alpha-beta question

Author: John Scalo

Date: 23:42:07 01/05/98


I have a search algorithm that looks something like this (with lots of
stuff

omitted) -



Search(alpha, beta, depth, *bestPath, ...)

{

	if (...deep enough...)

	{

		return Eval();

	}

	GenerateMoves(successors, &succIndex);

	for (i=0; i<succIndex; i++)

	{

		newMove = SelectMove();

		MakeMove(newMove);

		if (KingInCheck())

		{

			UnmakeMove();

			goto end;

		}

		//null move stuff omitted

		score = -Search(-beta, -alpha, depth+1, movePath, ...);

		UnmakeMove(newMove);

		if (score > alpha)

		{

			alpha = score;

			*bestPath = movePath;

		}

		if (alpha >= beta)

		{

			AddKiller();

			AddHistoryMove();

			AddToHash(...);

			return alpha;

		}

		end:;

	}

	AddHistoryMove();

	AddToHash(...);

	return alpha;

}



The question is, if the search goes through every move and never gets a
score >

alpha, what's the appropriate action? Is this what is referred to as a
"fail low"?



The problem of course is that a best move (or path in my case) hasn't
been

established and the alpha that's getting returned isn't accurate. I
assume that

the search needs to be redone with an infinite alpha-beta window but I'm

wondering if there's a preferred way of "notifying" the calling Search()
that the

window was inadequate.



Thanks,

John



P.S. Apologies in advance if Internet Explorer contorts the text as it's
done in the past when posting to this board...



This page took 0.02 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.