Author: Robert Hyatt
Date: 07:51:35 04/25/01
Go up one level in this thread
On April 25, 2001 at 00:59:51, Eugene Nalimov wrote: >On April 24, 2001 at 23:56:26, Christophe Theron wrote: > >>On April 24, 2001 at 20:38:49, Robert Hyatt wrote: >>> >>> [...] >>> >>>You _are_ aware that DB's branching factor was well below 5? I posted the >>>analysis here a year ago (Ed probably still has it as he was interested). I >>>took the 1997 logs and just computed the ratio using time. They were nowhere >>>near 5... not even near 4... >> >> >> >> >>I was not aware of that. >> >>But given that Deep Blue reached ply depths higher than what I have written >>above, I have good reasons to believe that their BF was indeed well below 4. >> >>So they were using a selective algorithm. >> >>I wonder what it was. > >Bob mentioned that they used futility pruning in their hardware search. But I >believe that they can have more-or-less same branching factor even without it. >Today's micro program (e.g. some-Tiger) prunes a lot using null move and >undoubtely a lot of other secret heuristics. Deep Blue does not prune; instead >it extends some lines like crazy. Net result is the same -- both programs have >highly unbalanced trees, so I don't see why their branching factor cannot be >(roughly) the same. The difference is number of nodes in the trees, but of >course Deep Blue team can allow it to be orders higher than micro developer... >And of course with their approach search results are much more reliable; their >N-plies search is really N-plies search. > > >>>>And it turns out that ply depth 13 can be routinely reached by today's PC >>>>programs at standard time controls. >>> >>>Yes.. but don't forget DB was reaching depths of 15-18 in the middlegame, >>>as their logs from 1997 clearly show... >> >> >> >>Yes, it looks like I was badly informed. >> >>Knowing that, I now believe that no micro program of today would have any >>reasonnable chance against Deep Blue. >> >>Against a single chip maybe, not against the whole thing. >> >> >> >> >> >>>>But there are 2 things I'm not really taking into account here: >>>>1) selective search is less reliable than brute force search >>>>2) Deep Blue uses something called "Singular extensions" which increases its >>>>branching factor dramatically over the BF of a simple alpha beta brute force >>>>algorithm. >>>> >>>> >>>>Point 1 is hard to evaluate. >>>> >>>>About point 2 we have some data suggesting that "singular extensions" is an >>>>extremely expensive algorithm: while PC programs have no problem to reach ply >>>>depth 13 on current hardware, Deep Blue could not go beyond ply depths 11-12 in >>>>the 1997 match. Of course in some lines it was computing much deeper. >>> >>>Not again. Look at the logs. 11(6) is a +seventeen+ ply search. >>> >>> >>> >>> >>>> >>>>It remains to be seen if "Singular extensions" is such an improvement. So far I >>>>think that nobody has managed to prove that it is. Some people speculate it >>>>could be effective only if you have a very fast computer, but only the Deep Blue >>>>experiment suggests this, without further scientific proof. >>> >>>No. I used them in later cray blitz versions. HiTech used them as well. >>>They have their good and bad points. Some micro programs have/do use them >>>as well... >> >> >> >>I'm sorry but I still have to read a study about the success of this extension. > >There was article in the ICCA journal (in 1989?). Later they changed their mind >about it, but later they changed it once again. During his last lecture at MS >Hsu told that this extension is very important one. Their first conclusion seemed to be based on test suites, comparing SE with no SE. Later they used a match of games and concluded the difference was far less. Then later they found that against really strong opponents the idea was more important than they had been thinking as the Kasparovs of the world do look quite deeply at some points... >>Anyway, if it is such a small improvement that it is not even clear by now clear >>if it is good or not, then in my opinion the main (and maybe only) strength of >>Deep Blue is its huge NPS. >> >>But that's not new. >> >>That's why I see Deep Blue as a technical and financial success, and just that, >>certainly not as a breakthrough in computer chess. > >Then Moon landing also was not a breakthrough. In principle everything was >doable (and even simple), USA need only to create the organization (I believe >Apollo was the 2nd complex program in the human history), put a lot of money >into it, develop the technology, and go forward. Nevertheless I believe Apollo >*was* a breakthrough (it results were not used, but that's another story). >Exactly the same is Deep Blue -- when you are putting together a lot of money >and very competent team, results usually are very good. > >Eugene > >> >> >> Christophe
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.