Author: José Carlos
Date: 03:32:14 12/06/02
Go up one level in this thread
On December 05, 2002 at 15:11:14, Ingo Lindam wrote: >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! In the trivial approach, which is using Alpha-Beta to find the best move, remove it from the list and repeat the process for the second best, it should take about twice the time for every node that you search with an open window. So an upper (pessimistic) bound would be: Time(null window nodes) + N^(Time(open window nodes)) I suppose there must be a better algorithm, but it should be provided in order to calculate the time it takes. >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. From a human point of view, it isn't very useful unless we're talking about a wild tactical position, in which case we need N to be larger than 2. In most situation, a human wants to see refutation for some obvious (for the computer) moves, like "you can't take the knight because the pawn promotes" or "rook to seventh is bad because it gets trapped", and so on. >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. That's interesting for non-tactical positions. >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. I don't follow here. If you have two processors, and one of them is creating that N best tree, the other one is idle meanwhile. The, when the first proccessor jumps to the next ply, the second will need a fraction of a second to do whatever with the N-best tree, and then go idle again. Isn't it a waste of processor time? >Are the question getting a little clearer now? It is an interesting topic, thank you very much for your ideas. >Internette Gruesse, >Ingo 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.