Computer Chess Club Archives




Subject: Re: Storing the PV in a search routine

Author: Bruce Moreland

Date: 12:09:16 06/09/98

Go up one level in this thread

On June 09, 1998 at 14:44:18, Scott Gasch wrote:

>Hi.  I'm a newbie at computer chess and am having some trouble storing
>the PV with my search routine.  I am using an alpha beta search with
>a depth identifier to moderate search depth.  Before I return from any
>invokation of search I store the best move it found in a move array at
>pv[depth].  I thought this would be the correct way to operate since
>the search is depth first.  However, when I look at the move array later
>it often makes no sense; for instance, the same piece is moved twice on
>successive turns or pieces get taken where they are not located in the
>deeper levels of the PV.  The first move in the array is always legal
>and is (usually) a sound move.  This leads me to believe the search
>routine is working but I am just missing some concept about how to store
>the PV.

I will invent some terminology first.

I'll call the root of the search "level 0".  When this instance of
search recurses, the recursed call is "level 1", when that recurses, you
get to "level 2", etc.  The deepest level you happen to get to in the
course of a line I'll call "level N", although "N" can change throughout
the tree.

Each possible level is going to need an array of moves, along with a
count of how many elements are currently in the array.

When you do a level N node, and the score comes back between alpha and
beta, this is a tip PV node.  When you encounter one of these, you set
your move element counter for this level of the search to zero, because
there wasn't actually a move made here, you just evaluated a position
and thought it was fine.

Anywhere else in the search, if you get a score back that is between
alpha and beta, you have to do something more complicated.  You take the
move that you just made, the one that you recursed on, and you stick it
at the head of this array.  You then take the array for the next deeper
level of the search, and you append it to this array.  The number of
elements in the array at this level is now the number of elements in the
deeper level's array, plus one.

When your search finishes, the PV is in the level zero array.

The memcpy doesn't kill you, because you'll only do it a few hundred
times per search, maybe.

This sounds complicated but it is maybe five lines of code.


This page took 0.04 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

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