Author: Robert Hyatt
Date: 14:26:58 09/05/03
Go up one level in this thread
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. > >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.