Author: Dan Newman
Date: 01:43:54 01/17/00
Go up one level in this thread
On January 16, 2000 at 23:20:49, Sanjiv Karnataki wrote:
>Hi All,
>
>I am writing an amateur program and I just finished implementing the negamax
>procedure with a simple eval function. The proc works correctly and returns the
>correct eval but I cannot figure out when to record the nodes being searched as
>part of the PV. I tried recording them whenever a new alpha gets assigned but
>that does not seem to work.
>
>any help or pointers to web-sites that discuss this topic would be greatly
>appreciated.
>
>Thank you.
The usual way of recording the PV is to maintain a 2-d square array of
moves. (You only need a triangular array, but it's easier to implement
using a simple square array.) This array should be wide enough so that
a row can accommodate the maximum complete PV. Each row is for a
different ply.
move_t pv[ MAX_PLY+1][ MAX_PLY+1];
You also need an array to keep track of how long the PV is, with an
entry for each ply (or you could use sentinels in the PV's themselves):
int len_pv[ MAX_PLY+1];
You also must have a ply number variable passed into your search function
so that you know which ply you are in:
int search( int alpha, int beta, int depth, int ply, ....)
{
.....
int score = -search( -beta, -alpha, depth-1, ply+1, ....);
.....
}
The idea is that when you find a best move at a node (score greater than
alpha and less than beta) you copy the next ply's row into the current ply's
row and also record the current best move into it:
len_pv[ply] = len_pv[ply+1];
for( int i = ply+1; i < len_pv[ply]; i++ ) pv[ply][i] = pv[ply+1][i];
pv[ply][ply] = best_move;
Since you've been doing this all along at any node where you get a best move
you will have copied the chain of best moves leading from this node out
to the leaf node from which the score came. In other words a partial
(potential) PV.
len_pv[ply] gets set as above and also when we get to a leaf node or a node
with a game theoretical value or a node from which we get an exact score
from a transposition table probe, i.e., any from which we return without
further search and which may be the last node reached by a PV:
len_pv[ply] = ply;
When you get back to the root (and also get a best move there) you end up
with an array, pv[0], containing the new PV with a length of len_pv[0].
All that being said, I don't do it that way. I use an array of pointers
to PV's and swap PV's when I get a new best move. I also stick a sentinel
value (0) into the PV to indicate its end. I do all this with the idea of
getting better performance. But the above copying technique doesn't cost
much because most of the time you don't get a (new) best move but are busily
failing high or low. If I were to start over again, I might well do it with
the copying technique as it seems to have fewer associated headaches.
-Dan
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.