Author: Vincent Diepeveen
Date: 17:14:19 09/02/02
Go up one level in this thread
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. 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. That's slowing down things, so another value for the window you can really miss. That's the reason and nothing else. 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. The important thing was that he lost a value. Simple as that. >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.