Author: Stuart Cracraft
Date: 14:23:48 09/23/04
Go up one level in this thread
On September 23, 2004 at 13:25:46, Robert Hyatt wrote: >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 When I scaled this up for more than just ply == 0, e.g. ply < 2, ply < 3, the sorting impacted things predictably. Truly -- there is no silver bullet. After a decent move ordering and the major methods implemented, it's all uphill from there. 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.