Author: Robert Hyatt
Date: 19:03:43 10/13/02
Go up one level in this thread
On October 13, 2002 at 10:36:15, Uri Blass wrote: >On October 13, 2002 at 10:11:13, Robert Hyatt wrote: > >>On October 13, 2002 at 02:52:12, Uri Blass wrote: >> >>>On October 12, 2002 at 22:42:28, Robert Hyatt wrote: >>> >>>>On October 12, 2002 at 10:33:29, Omid David wrote: >>>> >>>>>On October 12, 2002 at 09:53:42, Robert Hyatt wrote: >>>>> >>>>>>On October 12, 2002 at 08:29:24, Omid David wrote: >>>>>> >>>>>>>On October 11, 2002 at 21:57:34, Robert Hyatt wrote: >>>>>>> >>>>>>>>On October 11, 2002 at 17:51:27, Omid David wrote: >>>>>>>> >>>>>>>>>On October 11, 2002 at 11:51:13, Robert Hyatt wrote: >>>>>>>>> >>>>>>>>>>On October 11, 2002 at 07:43:40, Uri Blass wrote: >>>>>>>>>> >>>>>>>>>>>On October 11, 2002 at 07:12:34, Vincent Diepeveen wrote: >>>>>>>>>>> >>>>>>>>>>>>On October 11, 2002 at 04:08:49, Uri Blass wrote: >>>>>>>>>>>> >>>>>>>>>>>>Isn't his article clear enough yet? >>>>>>>>>>> >>>>>>>>>>>Bob Hyatt still claims that it was 12 plies software and 6 plies hardware >>>>>>>>>>>so I prefer to hear an answer directly from Hsu. >>>>>>>>>> >>>>>>>>>>I agree. But _I_ don't claiam _anything_ except that members of the DB team >>>>>>>>>>specifically told me that 12(6) means 12 plies in hardware, 6 in software. I >>>>>>>>>>even posted the excerpt from the email that specifically said this... >>>>>>>>>> >>>>>>>>>>That is _all_ I have said about it... >>>>>>>>>> >>>>>>>>> >>>>>>>>>No matter what they say, even under extreme theoretical conditions it is >>>>>>>>>*impossible* to search 18 plies of brute force in chess, without any type of >>>>>>>>>forward pruning whatsoever, and no hash tables. >>>>>>>> >>>>>>>> >>>>>>>>However, they have _never_ said they didn't use forward pruning. They have only >>>>>>>>said "we don't use null-move for forward pruning" and nothing else. And they >>>>>>>>have >>>>>>>>slowly leaked details. But they pretty much had to since I had gone over their >>>>>>>>log >>>>>>>>files and discovered that theyt had a _very_ good branching factor, too good for >>>>>>>>pure >>>>>>>>alpha/beta alone... >>>>>>>> >>>>>>> >>>>>>>Interesting... What was the average branching factor based on the logs you >>>>>>>reviewed? >>>>>>> >>>>>>> >>>>>> >>>>>> >>>>>>I don't remember the _exact_ number although I posted it here in CCC and several >>>>>>were involved >>>>>>in a long discussion about it.. but the number was something less than 4.0 I >>>>>>believe, which is >>>>>>_way_ below what a pure alpha/beta program can produce. >>>>>> >>>>>> >>>>> >>>>>I can't imagine a way for brute force alpha-beta to come up with a branching >>>>>factor of anything even close to that number (esp. without hash tables). With >>>>>regard to the branching factor, it seems that some kind of forward pruning was >>>>>indeed in place... >>>>> >>>> >>>>Remember, Deep Blue _did_ have hash tables. Only the last few plies (done in >>>>hardware) >>>>didn't have hashing. The first N plies hashed just like the rest of us... >>>> >>>>And you are right, of course. There are details they have not completely >>>>revealed about >>>>whatever forward pruning they did to reach that BF... >>> >>>I understood that they were afraid of pruning based on Hsu's paper. >> >>Not if you read his papers. He didn't like "nujll-move pruning". And he was >>quite vocal >>about that. But that doesn't mean he didn't like/do some other sorts of >>pruning. And in >>fact, we now know that he did... >> >> >> >>> >>>Hsu considered the depth of Deeper blue in the games against kasparov as 12 and >>>said that they sacrificed 2 plies to implement their selective search >>>algorithms. >> >>Yes... the SE stuff. That was what we saw in Cray Blitz, generally. 1 ply all >>the time, >>2 plies in some cases.. >> >> >>> >>>If they really did 18 plies in the match against kasparov(if 12(6) means 18) >>>then I see no reason not to make it clear in a public article. >>> >>>Possible reasons not to say it can be: >>> >>>1)if the last 6 plies are something like qsearch and not something similiar to >>>what programs consider as plies. >>> >> >> >>The hardware does things differently. (1) not a traditional alpha/beta search, >>but a one-sided >>windowing search. (2) no hashing. (3) not particularly great move ordering. >>(4) some sorts >>of forward pruning. He mentioned futility as one thing, speeding them up by at >>least a factor >>of 10. >> >>Who knows what else was different in the last version of the processor since we >>were not >>having ACM events to get together and talk about the machine... >> >> >> >> >>>2)The 6 plies are not additional plies to the 12 plies and they have another >>>meaning. >> >>12 plies on a 30 procesor SP2 seems quite normal, IMHO, not counting the chess >>hardware at all. >> >> >> >>> >>>All their extensions(of singular and even in cases of 2 moves that are good >>>should make it harder to search 18 plies). >>> >>>The logfiles also suggest that they clearly did not use hash tables in an >>>effective way and the proof is the fact that the depth is not significantly >>>bigger in endgames. >>> >>>Uri >> >>We didn't see any simple endgames in the match... > >I remember that I could see difference of some plies in the depth of Fritz when >I compared depth before trading queens in game 1 and depth some moves after >trading queens in game 1 > >I did not see a difference of some plies in the depth of deep blue. > >It is not a proof and a better test may be to compare depth of programs without >null move pruning. > >Uri Deep Blue seems to follow the sort of pattern I recall from Cray Blitz days. We didn't see huge depth increases. IE remove the queens and we would get another ply, sometimes 2, max... Sometimes none at all. Ken Thompson noticed that his hardware search had the most trouble with "bare rooks and pawns" because the rooks have so much mobility and can check so wildly...
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.