Author: Robert Hyatt
Date: 12:16:28 01/31/02
Go up one level in this thread
On January 30, 2002 at 11:12:49, Vincent Diepeveen wrote: >as posted in rgcc: > > >futility pruning is something that only happens in qsearch it >doesn't happen in the normal search. Who says? Several have experimented with futility pruning and it is _not_ just a capture search issue. > >We know from 1998 postings from you, quoting the same sources as you >did for that 12(6) statement, that they only did fullwidth and were >not a byte forward pruning. So the truth from these 1998 postings and >1999 postings are IMHO not more or less relevant than the 12(6) >statement as far as i am concerned. It is hard to modify statements >from around these times in 2002. I'm not trying to modify _anything_. They said "the hardware chips had futility pruning disabled for the matches against the micros..." That doesn't say nor imply that futility pruning was only done in the q-search (as I do it) or in the normal search as Heinz's group did it... There is simply no information about that and I haven't talked with them recently to ask about it. I therefore conclude _nothing_ except they had some sort of "futility pruning" in the hardware, and I stop there... > >Note the only one that *ever* said they searched 12(6) = 18 ply >was you, not a single official statment by Hsu published it like >this, instead he uses 12 ply in IEEE99. Again note that two members of the DB team, including Hsu, said that X(Y) means X plies in software plus Y more plies in hardware. they told me that in 1987 when I sat behind them running deep thought and asked about it. They confirmed that this had not changed with the new Deep Blue stuff... What more can anyone say? _I_ didn't say that 12(6) means 18 plies. _they_ said it in the email I posted here. _I_ didn't say they always searched to 12(6) either. You are implying that. According to the logs, 10(6) was more common thru the opening and early middlegame... and the search went deeper as the game progressed, just like it does for me. > >this is not relevant as we both know when using 480 chessprocessors >it takes a bit of time before they all have work to do and they borrow >in software some plies from previous moves. We are simply >speaking from math point here. I miss a factor million simply from >theoretical viewpoint. I have no idea what you are talking about here. If I run _my_ program on a 480 node machine, there is not any "bit of time before they all have work to do." My speedups for .1 second searches are just as good as they are for 100 second searches. We've been over this in the past. Just because you have some sort of "start-up" problems does not mean _everybody_ has them... You do realize that each chess processor board sits on a bus that has a _high_ bandwidth between the chess processor board and the CPU it is connected to? Bandwidth that makes the PC bus look like a soda straw?? > >>games played in the 1997 match (anyone can compute this for themselves if >>they want, I published an analysis of this on CCC a couple of years ago >>as I was personally surprised). >> >>A program with a branching factor of 4 can go quite deeply when searching >>up to one billion nodes per second... > >You are ignoring the theoretical math. Good try to only zoom in into >something which for non-parallel searching persons is hard to >understand. What are you talking about? Looking at actual game logs to determine data is far better than some theoretical model that doesn't even include transpositions, or variable-depth search. DB's logs show their branching factor. Or is this another case like a few years ago when you continually argued over and over that Cray Blitz couldn't possibly be producing the kind of 4-cpu speedup I had reported, even when you saw the real data? > >> >>> a) 12(6) doesn't mean they searched 18 ply. It means they searched >>> 12 plies fullwidth from which 6 ply in hardware >> >>It does not. I just posted excerpts from two emails from the DB team >>that were _very_ specific about this. It means 12 plies in software >>and 6 plies in hardware. There was no ambiguity in the statements they >>made, period. > >They also stated they searched fullwidth by the same sources and that >they did singular extensions also when there were 2 moves forced. > And then later they mentioned the "futility pruning in the hardware chips" which has not yet been fully discussed by them, other than to say that turning it off slowed things down by a factor of 10x, which is "interesting" if nothing else... >The theoretical math is not refuted. Only a period is placed here. >That shows how hard the proof is from mathematical viewpoint. > > We don't need any "theory" here since we have real data.. >> >> >> >> >> >>> Nevertheless Bob (Robert Hyatt acting as IBM defense), again claims it >>> is 18 ply fullwidth. Note that he bases his claim on an EMAILED and >>> not PUBLISHED statement from a non-programmer who said it was Deep >>> Thought printing stuff out like that. Note that the only published >>> depth is 12 ply in advances of AI : IEEE99, an OFFICIAL document. >> >>"non-programmer"? One email was from a programming member of the team. >>The second email was from the same programmer, _after_ he specifically asked >>Hsu and he relayed Hsu's answer to me. (CB is the "knickname" for Hsu if >>you didn't know, it came from CMU and a reference to "Crazy Bird".) > >You are th eonly one who publishes this nonsense then. He doesn't dare >to publish it in an official statement as he know he is going to >falsify statements. You are someone whose postings are getting well >read, so obviously i see this as a kind of PR attempt from the persons >in question. As we know IBM lied bigtime with PR, saying for example >that their new generation of processors is based upon deep blue >technology (which is 0.60 micron native chessprocessors) and during >the match the PR department said in a 10 piece ending that deep blue >was playing perfect chess as all these positions were in endgame >databases. Secondly they also said before the match that this was >the last match kasparov-deep blue (who needed 3-3 obviously >and failed to do so by a mistake in game 6 in opening, an opening he >never plays otherwise, so this is no big deal) and that deep blue >after this would be put on the internet. > >Then later when they had won, they suddenly said the chessprocessors >would do 'moleculair' research, which is impossible as the processors >can play chess only. So saying 12(6) = 18 ply is a small lie in this >sense, and Hsu never says it himself, only by your mouth! > >>I would think that (a) someone that worked directly on the project, and >>(b) the prime architect of the project, would know what they are talking >>about with respect to _their_ project... > >Their chessprocessors is converted into a 0.6 micron (that's 486 >technology) moleculair research, and the new 0.18 and 0.13 micron >processors are still so called 'based' upon deep blue technology... >..so compared to that statement i would not believe a word what they >post to someone from which we can never proof they stated it in an >official paper. > You are simply misquoting the article. They _never_ said "the chess processors are doing molecular research". They said the SP2 is doing so, and the marketing folks simply pointed out the link between the SP2 used by DB2 and the SP2 they were talking about, to "piggyback" on the reputation of DB's hardware. Most of us _here_ understood what was going on. And nobody _here_ was fooled for a second by that. And the DB team had _nothing_ to do with that marketing hype... >>> Let's assume Bob as only defender from IBM is right, >>> let's do some math on the MINIMUM number of nodes >>> they would need for a 18 ply search. >> >>> Also we know they didn't use a hashtable in hardware. >> >>> It is not amazing to see that in the complex middlegame Deep Blue >>> searched >>> just as deep as in the far endgame, about 11(6) to 12(6). >> >>> That means Knuth's lemma is of course working for them, otherwise >>> they would have searched many plies deeper in endgames. >> >>> Knuths lemma says that you need about the square root of the average >>> number of moves for even depths. >> >>> Now everyone can easily figure out what the average number of legal >>> moves >>> is (considering they extend checks so these positions do not count) >> >>> This was measured by me at 40. There i am the only person here >>> who recently measured this, the previous measurement of 35 was >>> INCLUDING checks and is like 50 years old, and was just saying >>> something about positions in GM games, it is obviously logical that 40 >>> is pretty true in the middlegame. >> >>I measured this over hundreds of games and got 37, although I don't see what > >You never did do this. You never posted that result and never showed >any source code doing it, despite that all your other chessprojects >are open source. > There is no open source because there was no source code. I went thru the log by hand, using a calculator. I posted the numbers _here_ in CCC. Ed looked at them after I did and he reached the same conclusion I did: "Hmm their branching factor seems 'interesting' for a simple brute-force search" but we were unable to draw any other intersting conclusions without more info. >>this has to do with anything. Lower it to 36. Sqrt(36) is 6, yet they have >>a documented branching factor of _four_. How are you going to explain that >>away? > >You probably forgot to exclude positions in check as those get >extended anyway so they do NOT count. I didn't include or exclude anything here... just simple guestimate numbers... > >>> Note that >>> in this math we assume a PERFECT move ordering, we do not count >>> the huge number of nodes singular extensions need and we do forget >>> the fact that deep blue proved in the games tactical weaker than >>> crafty would be at 15 ply even, whereas the truth is that they DID >>> do some extensions of course, it's even mentionned that in the >>> software part they did do 'dangerous extensions'. >> >>It never proved "tactical weaker than crafty at 15 plies". The "Crafty goes >>deep" didn't refute anything DB played in the games at all... They disagreed >>on positional grounds in some cases. And DB saw more tactically in others. >>So what? > >Uri Blass has shown some great things from the output deep blue showed >versus the real truth. Deep Blue saw tactical nowhere more. He has also found no places where micros see tactical "more" either... so what? > >> >>> For a 18 ply fullwidth search: squareroot (40^18) = 40^9 >>> = 262,144,000,000,000 >> >>> Now we know Deep Blue ran at 200M nodes a second, which from >>> hardware viewpoint is an incredible achievement and the only >>> thing IBM cared for. IBM *never* said something about searching >>> deeper. >> >>> So for a 18 ply search the theoretical minimum would have been >>> (assuming 100% speedup from deep blue, whereas in reality they >>> wrote down they got 20% out of it this was published in IEEE99 >>> by Hsu): >> >>> 262144000000000 / 200,000,000 nodes a second = 1310720 seconds >>> needed to get 18 ply >> >>Change the numbers a bit, because we _know_ their branching factor was >>4. To go to 18 plies requires 4^9 or 2^18 times as much computing as > >no this is wrong assumption. You are fiddling with numbers instead of >Knuths lemma. Even your above statement of 6 you have forgotten. > >>doing 1 ply of search. If you assume one ply requires (say) 100 nodes, >>then they need to search 262K * 100 nodes. That takes about 100 seconds. >>It is _perfectly_ doable by the DB hardware. If you assume 1 ply takes >>200 nodes, then they need about 200 seconds. Still doable. 300 nodes? >>300 seconds. Still within reason. And not all searches were to depth >>12(6). There were some that didn't get that deep. As expected... > >You make your story too long to believe it. Just write 10 papers and >then conclude what they did is ok. > >The hard fact is that 40^9 is so much nodes that no one can imagine it >yet. Yes. But nobody is saying they _search_ that many nodes, either... > >>> We definitely need to note that in 1995 not a single program with >>> mobility did get *near* 11 or 12 ply at 3 minutes a move, not even >>> WITH nullmove. >> >>> Even in 1997 it was a pain to reach 11 to 12 ply with just nullmove >>> for programs with mobility. >> >>> Only years after that things happened soon and fast, but a single >>> email from a person who didn't make the chip is quoted by Bob and >>> believed by some persons who are bad in search math. >> >>One of the programmers, after talking to _the_ person that made the >>chip, explained the 12(6). Your statement is patently wrong for obvious >>reasons. > >My statement is still true. You use a very hard to be shown true >'branching factor' which is something entirely different than number >of nodes needed as there is a 6 ply overhead everywhere where Knuth's >lemma 100% sure is truth. Then add some factors to that for qsearch as >they appear to do quite a bit in qsearch (which is pretty smart as it >picks up many tactics) then add another factor 5 for having 20% >speedup at 480 processors. Then add another factor of 16 because they >would lose 4 ply to singular extensions at 18 ply. And so on and so >on. > >The only truth is that 40^9 is the theoretical PROVEN minimum, you try >to add some doubts at the math here and there, but it is not cloaking >the truth from 40^9 completely disproving their 18 ply search. > >>> 18 ply fullwidth without hashtable is unreachable CCC audience, with >>> nullmove things change rapid however. This is why nullmove earns the >>> nobel prize and the defense of deep blue must admit that in 2002 >>> it is hard to say that a program that just searched fullwidth and >>> which was promoted only by nodes a second, that it got 11 to 12 ply >>> and not 17 to 18. 12 ply is in fact already a real good search >>> depth fullwidth, if i let diep search fullwidth WITH hashtables and >>> singular extensions, then i don't even get over 10 ply in fact. >> >>> The reason is real easy. I do my singular extensions also 4 ply from >>> the leafs, whereas DB 'only' did it 7 ply from the leafs. If never >>> forward pruning is used (like nullmove R=3 as i use in DIEP) it is >>> simply impossible to explain the huge problems singular extensions >>> cause. >> >>> Best regards, >>> Vincent Diepeveen > >>-- >>Robert Hyatt Computer and Information Sciences >>hyatt@cis.uab.edu University of Alabama at Birmingham >>(205) 934-2213 115A Campbell Hall, UAB Station >>(205) 934-5473 FAX Birmingham, AL 35294-1170
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.