Author: Dieter Buerssner
Date: 21:35:56 08/30/01
Go up one level in this thread
On August 30, 2001 at 18:53:56, Sune Fischer wrote:
>I see a lot of you printing principal variations (not the algorithm, but the
>best lines of play) found in the searches. How do one obtain that information,
>the alpha-beta only returns the score, not the moves?
Funny, exactly the same question was posted at rec.games.chess.programmer.
The following code is from a variant of Kalah that
I have written some years ago as a preperation for my chess program. It
uses fail soft alpha-beta.
It uses less data abstraction, than I would use now, but I hope it is
readable nevertheless.
The idea is just as Vincent said: While updating the score, also update
a pv-array.
Instead of using a local array, also a global two-dimensional array (indexed
by ply) could be used, or to save some space, even a tridiagonal data structure.
int absearch(int alpha, int beta, int side, int depth, int ply,
MOVELIST_T *pv)
{
int j, move, best, score, xside, nmoves;
POSITION save_pos;
MOVELIST_T mypv[MAXPLY+1], *mymp=mypv+1;
MS ms[6], *mp; /* At most 6 different moves are possible in this game.
MS: Move and Score */
move = (side==0) ? 0 : 6;
mp = ms;
/* generate and score moves (for move ordering) */
nmoves = generate_moves(move, mp);
if (nmoves)
{
/* Save the pos for easy UnmakeMove */
memcpy(&save_pos, &pos, sizeof(save_pos));
++ply;
--depth;
best = -INFSCORE;
xside = side^1;
--nmoves;
do
{
/* Check for user input once in a while */
if ((++nodes & CHECK_NODES) == 0 && search_interrupted())
return 0;
/* select best move. selectmove() is the inner loop of a selection sort.
*/
if (nmoves > 0)
move = selectmove(nmoves,mp);
else
move = mp->mv;
do_move(move, side);
/* leave_search is just about the same, but saves some
branches in the inner loop and adds only one branch here.
It is not a quiescence search, but rather a depth=1 only search. */
if (depth == 1)
score = -leave_search(-alpha, xside, ply, mymp);
#if (USE_ZERO_WINDOW & 2) == 0
else
score = -absearch(-beta, -alpha, xside, depth, ply, mymp);
#else
/* PVS. Here real NegaScout could be done to save some researches */
else if (best != -INFSCORE)
{
score = -absearch(-alpha-1, -alpha, xside, depth, ply, mymp);
if (score > alpha && score < beta)
score = -absearch(-beta, -score+1/*-alpha*/, xside, depth, ply, mymp);
}
else
score = -absearch(-beta, -alpha, xside, depth, ply, mymp);
#endif
/* undo move */
memcpy(&pos, &save_pos, sizeof(save_pos));
if (interrupted)
return 0;
if (score > best)
{
best = score;
if (score > alpha)
{
if (score >= beta)
return score;
alpha = score;
/* Update the PV */
pv[0] = move;
/* For chess and variable length PVs due to extensions/pruning
you need a marker at the end of the PV, instead of
assuming the last element will be mypv[depth] */
/* memcpy(pv+1, mypv+1, depth*sizeof(*pv)); */
for (j=1; j<=depth /* mypv[j] != END_LIST */; j++)
pv[j] = mypv[j];
/* pv[j] = END_LIST; */
}
}
mp++;
}
while(--nmoves >= 0);
}
else
{
/* No move -> the game is over. */
pv[0] = END_LIST;
EVAL_MATE(side, ply, best); /* best is assigned a value here */
}
return best;
}
Dieter
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.