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. 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.