Author: Robert Hyatt
Date: 13:02:46 09/06/03
Go up one level in this thread
On September 06, 2003 at 04:40:26, Tony Werten wrote: >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. Notice that I didn't suggest test positions. The "Crafty goes deep" was _game_ positions. Not problem (tactical) positions... > >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. \ If you do it right, it means _both_. I split at the root when it appears I won't change my mind. That is pretty accurately predicted. I don't split at the root when it looks like I will change my mind. My tests are time-based. How long does it take to play a move in a real game position. There are three possibilities: (1) 5/6 of the time I don't change my mind at the root. Splitting at the root will _definitely_ be faster for those positions, no question at all, because the tree will be smaller. (2) for the remaining 1/6 of the searches done, there are two possibilities: (2a) The tree for a non-first root move grows significantly compared to the trees for the first move. This suggests that this move might eventually replace the current best. I catch this case and search root moves one at a time, using all processors for each of the suspected new best moves. (2b) (2a) fails. Now I end up searching the real best move with only one processor. I will _still_ find this move, but it will take more time. But I won't give up until I search that move. In all the tests I have run, the time saved in (1) and (2a) way more than compensates for the time lost in (2b) over the course of a real game. That was my point. It does work. > >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.