Author: Robert Hyatt
Date: 08:08:21 06/25/01
Go up one level in this thread
On June 25, 2001 at 06:27:06, Vincent Diepeveen wrote: >On June 24, 2001 at 10:43:06, Rafael Andrist wrote: > >Paper of Hsu is indeed very clear describing what he did: > IEEE99 > I have explained this several times, although it seems to do little good. But here goes, again. Hsu _always_ reported only the software search depth when he talked about the program. Because that was the part of the search that was "complete" and used all the extensions, and tricks he knew of. The last few plies are fairly simplistic since they do not do anything except for normal extensions like out of check and recapture. And the q-search is dead simply although it does recognize mates. But in reality, if he says "I did a 10 ply search" you can pretty well do the math and figure out that a 10 ply search is not going to take 180* 200 million nodes. At least not for any program I have ever owned. So where do the _extra_ nodes go? That is the only question you have to answer. They have already answered this question. So give me the math that shows how it would take 180*200M to 180*1000M nodes to search to only 10 plies in 3 minutes time... BTW I _know_ how big the 10 ply tree is. I have already ran this experiment when you asked the last time. It is _not_ in the billions. >In those years it still was said that Deep Blue searched 12 ply >but fullwidth which would kick butt of the same if searched with >nullmove, as well as that some amazing singular extensions which >were too expensive to use, that those would improve the level. > >Only the problem was that around that year (1999) also micro's >started searching 12+ ply (some of them, mine still doesn't do that >too many times), so then the lies about deep blue became bigger. > >Now most not only search deeper, but also extend at more depths, >so now the thing had to look better, so then it was said that 11(6) >means 17 ply. > >However there is a small theoretical problem here. > >The last 6 plies the average number of legal moves in a position >(not the check positions counted as those get extended anyway >which only increases overhead) is 40 or more in middlegame. > >That means that with a perfect evaluation and perfect >move ordering Deep Blue would need: > > 40 * 40 * 40 nodes to search 6 ply. More assumptions? Suppose they do some sort of pruning? We know they did some futility pruning in the hardware, Hsu said that directly. We don't know whether it was only done in the q-search or in the last 4-7 plies as well. How can you make up math not knowing exactly what they were doing? > Add to that factor 2 for qsearch (as each 50% of all > nodes you need to try evaluation and opponent might want > to answer at that too, so 2 nodes for every 50% positions > added is at least factor 2) and extensions. > > So a theoretical minimum starts with > > 2 * 40 * 40 * 40 = 128000 nodes for the last 6 ply. > >Now 200M nodes / 128k = 1562.5 of those searches a second >*theoretical*. > >You can't search 10 to 12 ply fullwidth with 1562.5 nodes >a second, even with hashtable because using Bobs own statement >that b.f. is lineair (i do not believe this when loading >factor of hashtable is not too big and you use a lot of probes) > >that means that you need for the first 11 ply: > >40 (first ply) >4.5 (branching factor all other plies) First, DB's branching factor was lower. As per the logs. > >40 * 4.5^10 = 136,202,515 That is poor math. Why not 4.5^11 which is what Knuth's formula actually uses, or else why not 40 * 40 * 4.5^9, or 40 * 40 * 40 * 4.5^8, etc??? Your formula assumes every move at ply=1 is searched without any knowledge about the alpha value computed from the first (best) move. IE it assumes that the root moves are ordered in worst-first order, which is an unrealistic assumption. nodes = W^floor(d/2) + W^ceil(d/2) not the formula you gave. for D=10, this is 160M nodes, assuming W=38. But we know they did better because of their effective branching factor. If you massage the formula to use their 3.8 rather than sqrt(38) then this becomes (for 10 plies) 600K. Which is also unrealistic. And it points out that we do _not_ know enough about their search to go around proving things with insufficient data. With a BF of 4.0 (which is higher than what I calculated last year using the log files from the 1997 match) 14 plies would take 268M nodes. You can pick any BF estimate you want. But it has to match the log files to be reasonable. And since the logfile BF is lower than what anyone expected (myself included) I assume that they were doing something we don't know about. Rather than assuming their numbers are simply "impossible". > >Now that's *without* extensions and WITH perfect move ordering >and an evaluation which doesn't modify next ply. > >in 180 seconds you don't even get *close* to that theoretical >minimum of 17 ply search, not to mention 18 ply. Even a factor 100 >isn't going to save ass here. Is this like your pronouncement "I can proof it is impossible to get a good speedup on a 10mbit/second networked cluster" even though Phoenix (and others) had done so??? > >So the whole discussion is completely nonsense that deep blue >ever searched 16 to 18 ply fullwidth. > >It's invented *after* the PC programs progressed bigtime. So they "make up numbers" is what you are saying? > >Of course things are different if you design a program right *now* >in hardware. > >First of all the hardware tools have been improved, secondly >you can use both nullmove and if you're a good designer also hashtables >inside a cpu (even though this is going to slow down the cpu itself >by a factor of 20 at least). It won't slow the chess processor one iota. If you only knew how hardware design worked... DB97 _had_ hardware hash table support. Just no memory to implement it at the time, due to insufficient time to get it done. If you would only do the math, you would realize that the chess processors were only running at 24mhz max. Memory can keep up with that with no problem what ever. Even without the trick of doing the memory read _before_ you need the data, memory is fast enough to keep up. Otherwise how do you think a Cray can keep up with a processor needing a pair of data values every two nanoseconds? Yet it does...
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.