Author: Robert Hyatt
Date: 10:25:46 09/23/04
Go up one level in this thread
On September 23, 2004 at 12:23:23, Stuart Cracraft wrote: >On September 23, 2004 at 05:10:40, martin fierz wrote: > >>On September 23, 2004 at 04:14:15, Tony Werten wrote: >> >>>On September 23, 2004 at 04:10:18, martin fierz wrote: >>> >>>>[snip] >>>> >>>>>There is _no_ overhead. It is done only at the root, once per iteration. For a >>>>>12 ply search, a total of 12 times. That won't use measurable CPU time. The >>>>>point is that root move ordering is critical for efficiency.. >>>> >>>>exactly how critical for efficiency would you believe it to be? >>> >>>Depends on the bestmove. If that is constant, it's less important than after a >>>rootfaillow. >>> >>>Tony >> >>ha! what kind of an answer is that :-) >> >>seriously though: it's clear that there is some importance to it, but can >>anybody quantify it? e.g. like this: "ordering root moves by size of subtrees >>gains X elo compared to constant static ordering done at ply 1". >> >>cheers >> martin > >I would like to comment that I don't see what the point of ordering >by subtree size is. That subtree is already searched. There is no >flowover to other subtrees of brother moves at ply 0 to benefit those >brothers. The point is well-known. The _first_ move at the root takes over 50% of the total search nodes when you do not change your mind. The other moves take a fairly equal fraction of the remaining total nodes searched. When you reach a position where you are "almost" changing your mind, the size of that sub-tree will grow significantly with respect to the others. You might notice this if you print each root move as it is searched. The first takes forever, the rest rip by. Until on iteration N, suddenly move X seems to "hang" for a few seconds before move X+1 and so forth fly by. On the _next_ iteration it is possible, even probable, that that move X is going to take even longer to search and that it will become the new best move. Wouldn't it be nice if that move were searched _second_ rather than 30th (or whatever)? That is the point here. It particularly helps in games where you don't do full iterations. But even if you do, it will reduce the size of the search tree on positions where you change your mind, because after you find the new best move, the other moves get searched even faster than before since you now have a higher alpha (lower bound) thanks to the new best move's better score... > >That is why when I experimented today with a ply == 0 resort after each >move is searched that I resorted with the new history heuristic table. > >I got a very slight increase in problems solved (2 out of 300) with >a slight 2% drop in total nodes searched. > >Stuart
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.