Author: Tony Werten
Date: 01:40:26 09/06/03
Go up one level in this thread
On September 05, 2003 at 17:26:58, Robert Hyatt wrote: >On September 04, 2003 at 18:01:14, Gian-Carlo Pascutto wrote: > >>On September 04, 2003 at 17:10:26, Robert Hyatt wrote: >> >>>Knuth and Moore _know_ that splitting at the root is the right thing to do. >> >>...assuming perfect move ordering. >> >>>After you have searched the first move in parallel, of course... >>> >>>I do both. >> >>This is simply about getting a good splitpoint. Ideal splitpoints >>are ALL nodes, that have high certainty, are close to the root, and >>don't have any moves searched yet. >> >>The root itself doesn't fit that criteria as far as I'm concerned, >>and you messing around with 'exceptions' is an evidence of that. >>The root doesn't have a particularly high certainty and you're forced >>to serialize some moves often. > >Think about the "Crafty goes Deep" experiment. in 1/6 of the cases, Crafty >finds a better move at the root. In 5/6 of the cases, it doesn't. So for >5/6 of the cases, the root is the _perfect_ place to split for zero search >overhead. > >Now, what about that 1/6? It turns out that it is possible to predict with >some reliability when this is happening, by looking at the node count for >each root move. And when it appears to be a possibility, those moves that >appear to have larger-than-usual node counts can be searched one at a time >with a parallel search, > >This is a win-win that is very important for overall search efficiency. > >> >>Something funny is that you serialize if there's multiple big >>subtrees. You don't serialize when one tree is much bigger than >>the others. You're effectively getting exactly the opposite from >>what you'd like to have (big trees to search in parallel). That's >>a PV node for you. > >Not a problem. I search that one big tree in parallel, then search the >rest of the root moves in parallel. Note that the root sub-trees are >the _biggest_ trees available to search in parallel. Searching them one >at a time with all processors is going to be (a) less efficient due to >extra splitting overhead; (b) less efficient because move ordering isn't >perfect and this introduces search overhead. You can see the difference >by telling Crafty to not split at the root and running a test set, then >running it in normal mode and using the same test set. The results are >often significant. Testpositions won't work since they are biased for a change in first move. If, at the ply you find the best move, the bestmove is at position 3, the following will happen: Not splitting at root: You finish move 1 and 2 first then find move 3. Splitting: You finish move 1,search 2 and 3. Effort is only move 1 + half move 2 (or less dependig how fast the fh is found) ( I discard the effort for move 3 since a) a fail high is found fast and b) It's a bad move to search parallel since all assumptions are wrong ) Splitting at the root will always look better. It doesn't mean the search is better. Tony > >> >>You preferably want to use splitpoints from ALL nodes >>with a high certainty. But there's a tradeoff between more splits >>and more overhead from that and the risk of wrong ordering at PV nodes >>generating wasted effort. >> >>Note that I'm working on the assumption that classifying nodes >>works more accurately than ordering moves. This should be true >>given some testing of the appropriate heuristics. >> >>I've been wondering why Crafty alledgedly goes so much faster when >>you split at the root. I'd assume it's because your simple design >>doesn't leave you much choice in getting a good splitpoint, i.e. you >>take the first thing that looks like an ALL node that you come by. >>Because of the same reason, you don't care much if you get a PV or >>an ALL node, since you don't split until you've serialized the first >>two moves anyway. > >Correct. The DTS algorithm in Cray Blitz was much better in this regard. >However, I can adjust the "ALL node detection" so that it has to search >more than one branch at a node before assuming it is an ALL. However, this >just adds more wait time and doesn't help overall search time get smaller, >because the move ordering is already pretty good. > >> >>I've looked what you wrote about this from Cray Blitz, and apparently >>it allowed split at the root also. I'm interested if you have performance >>results with and without splitting in the root (also for Crafty). By the >>nature of DTS, CB might have ended up not actually splitting in the root >>(in some cases) because there were simply better split points available. > >I haven't run the root/non-root test recently. however, the command >"smproot=0" disables splitting at the root, "smproot=1" (the default) >enables it. So it is easy to test. > >But for CB, the root would _always_ look like the best place in most >positions. But it could detect that things were changing deeper in >the tree and that the change might be on the way back to the root, so >that it might avoid it. Crafty does this in a much cruder fashion, based >only on the size of the tree. > > > > >> >>-- >>GCP
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.