Author: Bruce Moreland
Date: 16:26:13 07/15/99
Go up one level in this thread
On July 15, 1999 at 00:33:00, Scott Gasch wrote: >Hi there, > >My question is this: how much time is lost maintaining some sort of data >structure to record the PV as you search? Wouldn't it be better just not to >worry about the thought process but rather just get the one move that the top >level search routine returns and make it? > >Along the same lines, what is the best data structure to store the PV as you >search? I am thinking of an array of stacks... but the algorithm seems like too >much overhead. Is there a better (i.e. simpler or faster) way to maintain the >PV as you recursively alpha-beta search? In order for a move to have anything to do with the PV, its score must be between alpha and beta. This turns out to be extremely rare, so you can do a lot of work when you find a move like this. One rational way of doing this involves an array of PV's. A PV will typically be an array of moves, so effectively you have a two dimensional array. You have one PV available per potential distance from the root. The number of moves per PV must be enough to contain the longest possible PV, although you can take advantage of the fact that if you further from the root, the maximum length of the PV is shorter. You can make a triangular array and save approximately half the space, if you are inclined to do so. When you enter "search" recursively, you clear out the PV array for this distance from the root. This typically involves assigning the number of moves in the PV to zero. When you encounter a move that is > alpha and < beta, you stick the move into the PV for this distance from the root, and you append the PV for the next greater distance from the root to this. This is just a couple of assignments and a memcpy, probably. When "search" completes at the root, the PV is sitting there in the top-most PV in the array. bruce
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.