Author: Don Dailey
Date: 14:12:48 01/24/98
Go up one level in this thread
Hi Rickard, MTD(f) is identical on the serial, parallel with 1 processor or parallel with more than 1, the implementation has nothing to do with parallelism although I'm sure it interacts. A 1 processor parallel search is about 5% slower but searches the exact same tree (right to the node) as a serial search. MTD(f) in a nutshell: Essentially MTD(f) is a sequence of zero width window probes done to the whole search. Many searches return extremely quickly because most of tree is already known to the search (via the hash table.) Each search gains more information about the true score but a search is never returned that does not fail either high or low. The way you determine the "goal" of each probe determines what type of search it is. Essentially it's best to do your test searches with scores as close to the correct score as possible. That's why a binary search of this space is a poor attempt. I have my own driver that's based on MTD(f) but with my own enhancements. I am discouraging most people from using MTD(f). Look at the posts on the problems with it. I hate MTD(f) and there is only 1 reason I am forced to keep it in my program, its far better than nega-scout in terms of speed. I never thought anything would ever prove to be significantly better than nega-scout but at least for me it was. As I discussed with Bob and others, my program may be one of the few that can benefit from it, it's benefit is very much tied to the kind of program you have and all the ugly hacks you use in the name of speed! The parallel algorithm is extremely simple, and completely recursive. So parallelism can happen anywhere. The cilk language was designed around chess and huge effort went into it to make it extremely efficient and powerful at the same time. The scheduling algorithm is automatic and makes good decisions. When a processor steals work from another processor it steals the oldest work that was posted so most of the "sharing" will get done near the root of the tree. A lot of our parallel searches look at LESS nodes than a serial search. This can happen because if you are looking at a bunch of sibling moves in parallel one may just happen to give you a very fast cutoff (like a mate sequence) and return quickly where the serial program may not get to that move for a while. In general of course any parallel program tends to do more work on the average. There are things we do to try to avoid extra work, if we think a cutoff will happen we do not try to search siblings in parallel, but wait for the result of the search. I usually quote numbers like 20% more work than a serial job but in fact this is nonsense. The work climbs very gradually with number of processors and drops with depth of search. If we had 1 billion processors we would have to search for a long time to get the full benefit. Our program does not play speed chess well with a lot of slow processors etc. One intersting phenomemon we had with our 1800 processor Socrates program is that the iteration times looked linear! It took a second per iteration until we were over 10 or something. The branching factor was so low. But this was because the deeper we went, the more parallelism we got. Obviously, you cannot use 1836 processors to efficiently do a 1 ply search! It's like getting 1000 people together to mow a small yard or garden! Move ordering may be even more important for a parallel program than for a serial program for this reason. One algorithm we use is to always search the first move at any node and get back a result before we search the rest in parallel. This is a big benefit for us. The processors are not wasted because the algorithm is recursive and all the processors will quickly get activated further up the tree. score = search the first_move; if cutoff then return search rest of moves at same time. if any one of these is a cutoff then abort all work in progress Most of this stuff is a bookkeeping nightmare. But with Cilk they are very high level commands and the language keeps up with all the detail. You can still control a lot of the details if you want to and I have experiemented a lot with various scheduling algorithms but this simple one get's almost all the benefit. - Don On January 24, 1998 at 02:29:19, Rickard Björklund wrote: >On January 22, 1998 at 21:59:57, Don Dailey wrote: > >> >>I have problems with PV's. In Cilkchess 1, I implemented MTD(f) and >>Aske Plaat improved the driver (I was doing it wrong and still getting >>a small speedup over PVS.) > >In Cilkchess, how is MTD(f) used when running on a parallel machine ? > >Is the root searched with different windows in order to cut down the >number >of re-searches or is parallelism used at interior nodes ? > >/Rickard
This page took 0.01 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.