Author: Richard Pijl
Date: 05:31:27 12/03/02
Go up one level in this thread
On December 02, 2002 at 22:33:14, Robert Hyatt wrote:
>On December 02, 2002 at 18:01:00, Bob Durrett wrote:
>
>>
>>Fritz will display second best, third best, etc. moves and give a line for each.
>> But the Fritz manual says doing so requires extra computation when compared to
>>calculating only one move and displaying a line for it.
>>
>>I do not know what other chess-playing programs have to offer insofar as display
>>of alternate moves with there lines is concerned.
>>
>>A few questions:
>>
>>(1) If other programs offer this same feature, how do these chess engines
>>produce the alternate moves and lines? Differently from the way the first move
>>and it's line is produced?
>
>There are two ways to do this.
>
>1. Search all legal moves and get the best and display it. Delete this from
>the list of legal movs and search again for the best. This will take about
>as long as the first search. Total cost to find two moves is 2x the cost.
When looking at the PV's develop during multi PV search it seems like Junior is
doing it this way.
But I think you can do this in one go by using smart A-B boundaries
I just wrote the pseudo code below, so there may very well be some errors in it:
PV_t PV[]; // Sorted array 1..max_pv where index=1 is the best PV
int nr_pv=0;
alpha=-INFINITE;
beta=+INFINITE;
iterate over all moves {
score=search(move,alpha,beta); //regular mono PV search
if (score>alpha) {
insert_PV_in_PV_array();
nr_pv++;
if (nr_pv>=max_pv) {
nr_pv=max_pv;
alpha=PV[nr_pv].score;
}
}
}
Of course this can be extended with PVS, aspiration search or whatever although
implementation may be a bit more difficult than usual because you will have to
fail low or high when less than max_pv PV's are found.
But you cannot escape the fact that you will have to search for the
second..max_pv PV's with a wider window than you would have to when only
searching for one PV.
I don't think it will be twice as expensive for two lines though as you are
saving yourself some trouble in researching the same moves each time with a
lower alpha.
Richard.
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.