Author: Christophe Theron
Date: 11:11:56 04/25/01
Go up one level in this thread
On April 25, 2001 at 10:31:43, Robert Hyatt wrote:
>On April 24, 2001 at 23:56:26, Christophe Theron wrote:
>
>>On April 24, 2001 at 20:38:49, Robert Hyatt wrote:
>>
>>>On April 24, 2001 at 15:12:03, Christophe Theron wrote:
>>>
>>>>On April 24, 2001 at 10:13:29, Albert Silver wrote:
>>>>
>>>>>On April 24, 2001 at 10:01:04, Robert Hyatt wrote:
>>>>>
>>>>>>On April 24, 2001 at 05:06:40, Amir Ban wrote:
>>>>>>
>>>>>>>On April 24, 2001 at 03:47:15, Uri Blass wrote:
>>>>>>>
>>>>>>>>the best software that is not IBM.
>>>>>>>>
>>>>>>>>Suppose there is a match of 20 games at tournament time control
>>>>>>>>
>>>>>>>>I am interested to know how many people expect 20-0 for IBM
>>>>>>>>How many people expect 19.5-.5?....
>>>>>>>>
>>>>>>>>If IBM expect to do better result then the average result that the public expect
>>>>>>>>then they can earn something from playing a match of 20 games with Deep Blue.
>>>>>>>>
>>>>>>>>I believe that a part of the public who read the claim that kasparov played like
>>>>>>>>an IM are not going to expect good result for IBM.
>>>>>>>>
>>>>>>>>Uri
>>>>>>>
>>>>>>>I expect DB ('97 version) to lose 8-12.
>>>>>>>
>>>>>>>Amir
>>>>>>
>>>>>>
>>>>>>Based on what specific facts? How many games did they lose from their debut
>>>>>>in 1987 through 1995 the last event they played in with other computers? Let
>>>>>>me see.. that would be... _one_ game. So what suggests they would do worse
>>>>>>today? we are all 100x slower (or more).
>>>>>
>>>>>Yes, and another thing that is being seriously overlooked is just how important
>>>>>speed and a ply make in comp-comp matches. One thing that time and SSDF has
>>>>>CLEARLY taught is that that one ply in a comp-comp match makes a world of
>>>>>difference. I think pitting a PC program against DB would be a massacre, even if
>>>>>I don't think humans (a very top GM) would do that much worse against DB
>>>>>(compared to DB vs. PC) as opposed to an 8-way server run PC program as will be
>>>>>the case here. Provided the conditions were the same, and that both matches had
>>>>>equal preparation of course.
>>>>>
>>>>> Albert
>>>>
>>>>
>>>>
>>>>I'm not sure I would agree with you.
>>>>
>>>>Yes, Deep Blue is way faster than PC programs (even on today's PCs) in NPS, but
>>>>there is something you should not forget.
>>>>
>>>>Due to Hsu's beliefs, as pointed out by Bob several times, Deep Blue is
>>>>essentially a brute force searcher.
>>>>
>>>>But after 3 decades of chess programming on microcomputers we all know that
>>>>brute force search is extremely inefficient.
>>>>
>>>>Actually brute force is increasingly inefficient as ply depth increases. Or if
>>>>you prefer the difference between brute force and selective searches in terms of
>>>>nodes to compute to reach a given ply depth growth exponentially with ply depth.
>>>>
>>>>Today, good selective programs can achieve a "branching factor" which is under 3
>>>>(and that includes the extra work induced by extensions). A well designed brute
>>>>force alpha beta searcher, without extensions, achieves a BF between 4 and 5.
>>>>
>>>>Some time ago I have found that a good brute force alpha beta implementation has
>>>>a BF of 4.3.
>>>>
>>>>I think current top programs have a BF which is close to 2.5, but let's say it's
>>>>2.8 to keep some margin.
>>>>
>>>>
>>>>You can compute the ratio of nodes to search by brute force divide by nodes to
>>>>search by selective search by:
>>>>
>>>> ratio = 4.3^depth / 2.8^depth (^ mean "power")
>>>>
>>>>
>>>>Now about the NPS. Deep Blue is supposed to be able to compute 200 million NPS
>>>>(nodes per second). Current top PC programs on fastest hardware (single CPU) can
>>>>compute up to 800.000 NPS, that's 1/250 of what DB can do.
>>>>
>>>>
>>>>At what depth the "ratio" starts to be above 250?
>>>>
>>>>Answer: at ply depth 13.
>>>>
>>>>So I suspect that Deep Blue and current top programs on top hardware (single
>>>>CPU) can reach ply depth 13 in the same time.
>>>
>>>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.
>>
>
>So do I. Hsu did mention "futility" in the chess processors, but for some
>reason I concluded he meant in the quiescence search.
Futility as a minor impact on BF, as it can be done only near the horizon.
> Maybe that was something
>I concluded rather than something he said. I will try to find the original
>email and read it again carefully...
>
>I did specifically ask about "null-move" and got an absolute "no" from
>everybody.
So here we have a real mystery, something more interesting than SE IMO.
>>>>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.
>>
>>
>>
>
>
>It was a monster, as I have often said. Of course, I got to see what it
>was doing on more than one occasion. It was enough to make me dream of 20
>years from now of course. :)
>
>
>
>>
>>
>>>>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.
>>
>>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.
>
>partially. Don't forget that their NPS was a product of their very fast
>hardware. And that if they wanted to do something we consider time-consuming,
>they simply built hardware for it. IE king safety. They know how many pieces
>attack squares near their king, how many pieces are in battery behind the front
>attacker, etc. I did this in Cray Blitz as the vector hardware made it pretty
>efficient. I don't do it in Crafty yet. It is expensive enough that it makes
>me think about the depth loss vs the knowledge gain...
>
>So their NPS _was_ all-important. They could keep it up at > 200M nodes per
>second, while adding evaluation feature after feature... as the hardware could
>do most anything at no additional cost. That was the main reason Hsu redesigned
>the chip before the 1997 match. Benjamin convinced him that more evaluation
>was needed...
>
>He reported that they used less than 1/2 of the evaluation hardware in the
>chip for the 1997 match as they didn't have time to include more although
>it was in the hardware chips...
I'm not really sure that evaluation makes such a big difference.
I'm also not sure their evaluation was so much better than ours. Remember that
our evaluations are more flexible (we can change the terms and add new terms,
when all they can do once the chip is designed is change the weights of their
terms), and we have been able, for some of us, to work on our evaluations for a
longer time.
Maybe their evaluation was better, but I'm not sure. Maybe it could have been
much better due to their hardware wired eval, but they would have needed more
time.
>>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.
>>
>
>Certainly not. It used tried-and-true techniques. But carried out in hardware
>so that they were orders of magnitude faster. I never said anything different.
>Neither did Hsu, et. al... They used some search extensions most of us don't.
>They used lots of eval terms that we don't/can't... but the overall framework
>was the same as the original chess 4.x basically, just like most every other
>program around. Except for no real selective forward pruning that we know of.
>
>Null-move might have been _really_ interesting on that hardware...
Of course. It is a nonsense IMO to have ignored null move.
You can say they did not need it, but it is so simple to implement that I cannot
find a valid excuse for them.
Christophe
This page took 0.01 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.