Author: Ingo Lindam
Date: 12:11:14 12/05/02
Go up one level in this thread
On December 05, 2002 at 12:34:23, José Carlos wrote: Hello Jose, perhaps it got a bit confusing because there are several thing mixed up in a single discussion. I will try to clear it up and if something keeps unclear don't hesitate to ask me about this point again. > I missed the previous discussion, maybe you explained this before (sorry in >that case), but how can I possibly know anything about the second best move >without knowing which one is the best? My main aim is to obtain a N-best-tree as a result of my search process. To make it easy let us just speak of a 2-best-tree, first. A 2-best-tree shall contain for each node the 2 best moves and their exact evaluation. So in a full 2-best-tree of depth 3 has 8 variation, of depth 5 you 32...and so on...in general in a full 2-best-tree of depth d you have 2^d variations. Ofcourse it makes a lot of sense not to store the two best moves not in all cases, but e.g. only in that cases where the score a) is not more than DELTA1 weaker than best move in current node and/or b) is not more than DELTA2 weaker than root/PV. Now the first point to discuss is how much more effort does it take to obtain this tree than doing a normal alpha-beta search for the single-best score. We don't assume a MP-system here. That is just another point to discuss later. We just doing a modified alpha-beta-search, where in each node I search as long as I know the exact scores of the two best moves (or fail with DELTA1 or DELTA2, see above). It is clear that it takes more effort to obtain the 2-best tree, but how much more? I am atleast sure it should be a constant factor with a constant N (here 2, because 2-best). It should be no additional effort compared with the case that your move ordering gives you the second best move always before the best move! The second point to discuss is, what is it worth to take this more effort obtaining a 2-best-tree? Here I mentioned that we get a better analysis by the computer because the output/result (the 2-best-tree) is a kind of argumentation why playing this in this position and not the second best move... and what is the difference in score between best and second best move. Another value we get with a 2-best tree is that I am able to reevaluate the decision between best and second best move for all nodes again with a more complex evaluation function, this time on a very simplyfied search space. And having an N-best-tree you should have a good starting point to create a N+1-best-tree. Then search for the 3 best moves I already have the two best moves for a lot of nodes and I also have the scores, which tell me whether I am near enough to PV score. The Multi Processor suggestion are because if you have a 2-best-tree of ply P than onother processor or maschne can do completly different things with it (expand it to a tree-best-tree or rescore it) which all is completly independent from the search of the first processor/maschine for the next ply. Are the question getting a little clearer now? Internette Gruesse, Ingo > Let's see: I'm at the root at, say, iteration 10. I search the first move and >get a score back. Then I search the other moves with a null window, researching >at fail highs, etc. After that, I have the best move, and its score. Now I >remove it from the list and repeat the process, getting the second best one and >its score. They're inner-related in this case. > Now let's suppose I have two processors. Processor 1 searches best move from >previous iteration. Processor 2 searches the second best. The first move is >finshed and that processor starts doing null searches with the other moves. If >now the second processor fails low, all those searches are wasted, and you need >to do them again with a different window. If two of them fail high, you've >wasted all the time processor 2 was searching... It seems quite messy; depending >on what each processor is doing and what move is failing high or low, there seem >to be a lot of cases. > > José C.
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.