Author: Brian McKinley
Date: 11:59:19 05/14/98
Go up one level in this thread
On May 14, 1998 at 05:32:13, frank phillips wrote:
>Can anyone point me in the direction of explanations of the techniques
>used in chess programming. Having learnt a bit of C this year and with
>the help of articles found on the Net about search algorithms managed to
>write crude connect4 and othello programs, I would now appreciate some
>pointers to simple but thorough and complete explanations of bitboards
>and hashtables. Several articles I have found partially explain these
>topics but usually assume that the reader has more knowledge than I do,
>perhaps because they assume a basic programming background which I do
>not have. The source code to Crafty (thanks Bob) is well documented but
>beyond me at the moment. On a specific issue, I would be grateful for
>an explanation of how to get a pv out of the (alpha/beta negamax)
>search. Everything I have tried so far based on storing the best move
>in an array pv[depth] has failed, so I seem to be missing a fundamental
>point - or am just plain stupid :-/
Figuring out how the back up the principal variation was one
of the problems that gave me trouble when I started my chess
program. Then I realized that each value has a pv associated with
it, and that all you need to do is to back up the pv with the value.
I have tried to include some code to demonstrate this. Notice that
AlphaBeta returns a structure containing a value and a pv instead
of just a value. Good Luck.
// Structure to hold a pointer to a value and it's pv.
struct SResult
{
SResult() { m_value = -INT_MAX; m_pv = 0;}
SResult( int value, CMoveList * pv)
{ m_value = value; m_pv = pv;}
SResult & SResult::operator = (int i)
{m_value = i; m_pv = 0; return *this;}
operator int()
{ return m_value;}
SResult & operator - ()
{ m_value = -m_value; return *this; };
int m_value;
CMoveList * m_pv;
};
// Saves the principal variation in the storage area (CMoveList)
// for the current ply.
CMoveList * CPosition::SavePrincipalVariation()
{
int size = m_move - m_game->Position().MoveNumber();
CMoveList & pv = *(m_plyinfo->m_pv);
pv.Empty();
if (size > 0)
{
pv.Size(size);
SPlyInfo * plyinfo = m_plyinfo;
for (int i = size - 1; i >= 0; i--)
{
pv[i] = plyinfo->m_lastmove;
plyinfo = plyinfo->m_previous;
}
}
return m_plyinfo->m_pv;
}
// This function swaps the pv at the next
// ply with the pv at this ply so that the pv
// will not be overwritten by the next move.
void CPosition::BackUpPrincipalVariation()
{
CMoveList * pv = m_ply[m_nextplyinfo].m_pv;
m_ply[m_nextplyinfo].m_pv = m_plyinfo->m_pv;
m_plyinfo->m_pv = pv;
}
// Stripped down AlphaBeta to demonstrate how the pv is
// backed up with the value.
SResult CPosition::AlphaBeta( short depth, int alpha, int beta, int
positionbest)
{
SResult best, value;
CMove * move = 0;
CMove bestmove;
if (depth < 0 || GameOver())
{
best = Evaluate();
}
else
{
move = NextMove();
while (move)
{
MakeMove(*move);
if (best > alpha )
alpha = best;
value = -AlphaBeta( depth - 1, -beta, -alpha, best);
UnMakeMove();
if (value > best)
{
bestmove = *move;
best = value;
BackUpPrincipalVariation();
if ( best >= beta)
break;
}
move = NextMove();
}
}
// Saving the pv is expensive, so only do it
// if it will be backed up at the previous ply
if (!best.m_pv && best < -positionbest)
{
best.m_pv = SavePrincipalVariation();
if (!bestmove.IsEmpty())
best.m_pv->Add(bestmove);
}
return best;
}
This page took 0 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.