Author: Robert Hyatt
Date: 06:42:31 09/29/99
Go up one level in this thread
On September 29, 1999 at 05:16:40, Bas Hamstra wrote: >On September 28, 1999 at 09:25:58, Robert Hyatt wrote: > >>On September 28, 1999 at 08:13:47, Bas Hamstra wrote: >> >>>Hello, >>> >>>A while ago it was posted here that movesorting near the root was much more >>>important than near the leafs. >>> >>>- Is that true? >>>- If so, how much more important? >> >> >>Think about this for a minute. If you get the wrong move first near the >>leaves, how much work does it take to search the wrong move and then get the >>right one to get that cutoff? Compare this to positions near the root. So >>yes, it is _exponentially_ more important to get the move ordering right >>nearer to the root than nearer to the leaves. > >Like James I didn't think this was immediately obvious. Because nearly all nodes >are near the root and if moveordering is bad there, it is bad for nearly all >nodes. So it can't be *unimportant* as I saw somebody write here (not you). > not quite. An error in ordering at the root doesn't mean that ordering every- where below that node will be wrong. But based on simple math, an error closer to the root produces a huge number of extra nodes to search. An error near the tips produces a much smaller number of extra nodes, but does so many more times assuming that the probability of making an error is uniform across all nodes searched. But the obvious point is that you can't spend a lot of time ordering near the tips, because the cost is too high, but near the root, ordering time is free as there aren't so many nodes to apply it to. And since the danger is blowing the order near the root, we spend the time. IE this is why we us the last PV to sort the next iteration. If you blow the root ordering, you just produce a massive number of extra nodes, each with the usual move ordering problems. If you get the root right, you get far fewer leaf nodes, even though they still have the same ordering problems... >>>For instance Crafty has a FH FirstMove/FH rate of 94%. Now most nodes are near >>>the leafs, on average 94%, so near the root it is probably a good bit better. >>>Say 98%. Many moves come from hash, there. >>> >>>Now what if it went from 98% to 99%? What would be the impact on total nodes? >>>Any ideas? >> >>again, that 1% is an exponential improvement in the search, not linear... >>That last (missing) 6% would make the tree 2x smaller if I could get it... >> >>> >>>If sorting near the root is more important, isn't it an idea to try to improve >>>sorting for the first couple of plies (say 3) by Enhanced Transp Cutoffs? >>> >>>Some reported rootsorting by failsoftvalue gave good results. Why not the >>>first plies try something similar? >> >>this doesn't work. for positions where you have to search _all_ moves, >>ordering is totally unimportant. And even with failsoft, you do _not_ >>discover the best move. Alpha/beta simply won't do it. > >I guess what you are saying that there is no room for improvement of movesorting >near the root. But I am not quite convincend fail soft values are worthless. I >mean we try captures/killers/history. Are you sure we should do *nothing* with a >hashmove in case of UPPER? You are sure it is *evil* to put them between >captures and killers? Or between killers and rest? I am saying that a hash move with UPPER is worthless. Because there is no way to figure out which move is best when every one returns a bound <= alpha. > >Though a UPPER move is not best, it has some probability it is best. That >probability is too bad for playing this move first, as anyone can test. But how >do you explain moveordering by failsoft values at the root works? No big >improvement, maybe, but it clearly doesn't worsen...? > yes, there is a probability. this probability that your UPPER move is the best move there is 1/N where there are N moves to try. :) IE in such positions, you get a random move to try first. Not a good idea... this was what Ed was doing, but isn't doing any longer... > >Regards, >Bas Hamstra. > > > > > > > > > > > > > > > > > > > > > > > > > ETC is certainly worth a try. When I >>tried it it made the tree smaller, but it was no faster due to the extra >>overhead it entails. Trying it near the root is something I didn't try, so you >>ought to give that a test.. >> >> >>> >>>Regards, >>>Bas Hamstra.
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.