Author: Vincent Diepeveen
Date: 08:12:49 01/30/02
Go up one level in this thread
as posted in rgcc: On 30 Jan 2002 15:17:53 GMT, Robert Hyatt <hyatt@crafty.cis.uab.edu> wrote: >Vincent Diepeveen <diep@xs4all.nl> wrote: >> Hello, > >> I would like to adress some major nonsense about search depth >> deep blue. > >> First of all, we know that deep blue was doing only fullwidth >> with loads of extensions. > >We don't know this. We do know that they used some form of futility >pruning from things Hsu has written in the past. We do know that they futility pruning is something that only happens in qsearch it doesn't happen in the normal search. 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. 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. >had a branching factor of around 4.0 from going through the logs of their 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. >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. > >> 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. The theoretical math is not refuted. Only a period is placed here. That shows how hard the proof is from mathematical viewpoint. > > > > > >> 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. >> 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. >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. >> 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. > >> 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. >> 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.