Author: Robert Hyatt
Date: 21:30:50 09/02/02
Go up one level in this thread
On September 02, 2002 at 20:14:19, Vincent Diepeveen wrote: >On September 02, 2002 at 04:29:46, Ricardo Gibert wrote: > >there really was only 1 reason to use MTD and it is very CLEARLY >expressed in his paper. He needed it because in hardware things >work different than in software. > >if you use alphabeta you need TWO values > alpha > beta > >which you need to receive from the software. > >Using one bound (note he doesn't call it MTD) you receive one value >less which is EASIER in hardware search. Every value is a waste of your >time simply. > >You want to cutoff or not in hardware search, that's quicker. > Maybe or maybe not. Belle didn't do that. That was something Hsu modified later. He claimed it was to reduce the number of data paths on the chess chip. His book claims that the first chips were _very_ close to max capacity already, so this was probably the reason... >Look in theory he could do 2 - 2.5 mln nodes a second at hardwareprocessors >ranging from 20Mhz to 25Mhz. > >That means you have ONLY 10 clocks for each node, *everything* >included. > >If he needs a slow eval he already needed like 9 clocks in hardware. >to pick a move by a very primitive move ordering he would need another >clock etcetera. > However, if you would _read_ his stuff, you would see your explanation is bad. When he makes a move, he starts a slow eval. And a fast eval. And he can choose to wait for the full slow eval, if needed, or take the fast eval and act on that instead. And the slow eval is done in parallel with the next move generation, etc... so that it takes 10 cycles, period... He could have made it 20 or 5, depending on his intentions... The clock cycle is not the big issue. It is the number of gates that stack up in any one stage of the finite state machine, as the clock cycle has to be long enough to allow them all to sequentially settle... >That's slowing down things, so another value for the window you can really >miss. > >That's the reason and nothing else. The reason was space and nothing else... his paper says that... > >Further the cpu's were already very inefficient by doing things like >not having even a KILLER move list. > >So who cares if you waste again nodes to the processors by using a single >bound instead of PVS or whatever nice & neat. > >I completely agree with Hsu here. He wanted 1 bound, search depth was >simply *not* the issue. There is a very simple proof for why >search depth was NOT the issue. > >If it would have been, then Hsu would have used nullmove. Simple as that. >He didn't. It's still amazing he got 12.2 ply with it. > >IBM paid him to get 100+ million nodes a second. He got estimated 126 >million nodes a second with it. > >So he did what he was hired for. He kept his promise. He did what IBM >advertized with. So he was a briliant guy in that sense. > >He kept his promise. > >Not many keep their promise. > >Actually he did too much. Kasparov again played his usual unpredictable >kids chess against programs and even managed to lose from it. > >Without that 6th game the world would see deep blue as the machine that >lost 'again' against kasparov. now it has eternal fame. > >But to talk about search efficiency. Everyone who has toyed more than >zero times with MTD will know very well how important hashtable is for >it. the whole MTD idea is completely hashtable based. However, part of >that problem DB didn't feel, because the first few ply were in software, >and there already pretty soon a good bound was established by using >NORMAL alphabeta (no other enhancements. no pvs, no negascout or whatever). > >So the real hashtable problem of MTD needing hashtables badly because of >the many searches in the root, the deep blue usage didn't suffer that much >from it there. > >The loss wasn't big in fact. There was a loss, 100% sureness of that. >But it was small. everyone agrees with that... > >The important thing was that he lost a value. Simple as that. Actually he lost a data path, required to stream two values thru the engine... That was a design issue. It might not be the same today with smaller pathways... > >>On September 02, 2002 at 03:28:54, Gian-Carlo Pascutto wrote: >> >>>On September 02, 2002 at 02:19:08, Ricardo Gibert wrote: >>> >>>>This isn't clear. Remember the hardware is not searching near the root. It is >>>>only searching near the leaves. The vast majority of the time, all you may want >>>>to show near the leaves is if all the "relevant" positions in the subtree are >>>>greater or less than a certain bound. For this mtd(f) would fit the bill just >>>>fine despite the absence of a hash table as long as a research does not need to >>>>be performed. >>> >>>But *if* a research needs to be performed, you're looking at an average of >>>about 10-15 iterations to converge on a new value (true MTD, their bisection >>>approach is less efficient). Because of the lack of hash, thats a tenfold >>>overhead. If we assume they have move ordering comparable to current programs, >>>they needed a research about 1/10 of the time. >>> >>>Very very roughly, this means that their searches would take about double the >>>nodes than they would have with a normal search. >> >>In comparison with alpha-beta, with no research, you examine 50% as many nodes. >>With one research you about break even. With 2 researches, 150% as many, etc. >>Hsu may be making a good bet by using mtd(f). I don't know the details to know >>for sure, but the fact that the hardware search is only done near the leaves is >>significant. Depending on the details, it may be possible to arrange for mtd(f) >>to almost never perform a research. This I would think depends on the software >>portion of the search and how it harnesses the hardware portion of the search. >> >>> >>>-- >>>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.