Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: "Deep Blue ..." in 1995

Author: Vincent Diepeveen

Date: 09:00:09 10/14/02

Go up one level in this thread


On October 14, 2002 at 11:46:15, Uri Blass wrote:

>On October 14, 2002 at 11:19:28, Vincent Diepeveen wrote:
>
>>On October 14, 2002 at 10:51:18, Uri Blass wrote:
>>
>>>On October 14, 2002 at 09:32:42, Vincent Diepeveen wrote:
>>>
>>>>On October 14, 2002 at 09:13:43, Uri Blass wrote:
>>>>
>>>>>On October 14, 2002 at 06:03:53, Vincent Diepeveen wrote:
>>>>>
>>>>>>On October 14, 2002 at 04:19:46, Odd Gunnar Malin wrote:
>>>>>>
>>>>>>>On October 14, 2002 at 04:04:30, Ingo Althofer wrote:
>>>>>>>
>>>>>>>>In the log-files of the ICC hour with Feng Hsiung Hsu
>>>>>>>>the following passages can be found:
>>>>>>>>
>>>>>>>>> EeEk(* DM) kibitzes: I heard that Fritz did
>>>>>>>>> play a match against Deep Blue in Hong Kong
>>>>>>>>> 1995,according to one of the Fritz programmers,
>>>>>>>>> is this not true?
>>>>>>>>> CrazyBird(DM) kibitzes:
>>>>>>>>> false advertisement. deep blue does not exist
>>>>>>>>> until 1996. the new chip was not completed
>>>>>>>>> until january 1996...
>>>>>>>>>
>>>>>>>>> ...
>>>>>>>>>
>>>>>>>>> EeEk(* DM) kibitzes: question from oddg: Back to
>>>>>>>>> the WC 1995, There was an entry with the name
>>>>>>>>> Deep Blue (Fritz won against DB), did it not have
>>>>>>>>> any relations to your Deep Blue? (EeEk: any idea
>>>>>>>>> how Deep Blue's name got in there, is this
>>>>>>>>> completely false?)
>>>>>>>>> CrazyBird(DM) kibitzes: deep blue did not play in
>>>>>>>>> 1995, since it did not exist yet.
>>>>>>>>> it was just deliberate relabeling on the part of
>>>>>>>>> commercial vendors, for obvious reasons.
>>>>>>>>
>>>>>>>
>>>>>>>You cliped a bit to early, here are the rest of his answer:
>>>>>>
>>>>>>But he said it wasn't deep blue. that's nonsense it was deep blue.
>>>>>>whether it was the old dtii is logical. every year you
>>>>>>have new versions of your thing of course. 95,96,97 each year new
>>>>>>chips. but it WAS called deep blue. calling it something else now
>>>>>>is not nice. If it had won, it would be said different: "deep blue
>>>>>>dominated always and also against kasparov". That the level of the
>>>>>>games played by computers in 1995-1997 was still very low, the audience
>>>>>>has forgotten of course.
>>>>>>
>>>>>>Relevant is that it was called deep blue. Not deep shit.
>>>>>>
>>>>>>>"
>>>>>>>CrazyBird(DM) kibitzes: the program played was deep thought ii. which
>>>>>>>was vastly inferior to deep blue in chess knowledge as well search
>>>>>>>speed (1000 to 1 ratio in effective speed, 100 to 1 in raw speed)
>>>>>>>CrazyBird(DM) kibitzes: and we were as unlucky as kramnik is today:).
>>>>>>>"
>>>>>>
>>>>>>the speed projections are not interesting. The number of nodes is not
>>>>>>the important factor here basically. There is so many things where you
>>>>>>lose to that the number of nodes a second is irrelevant.
>>>>>>
>>>>>>Relevant is that the 1997 version got 12.2 ply on average. This was
>>>>>>WITH no progress pruning and WITH very dubious pruning last plies
>>>>>>(which however tactically doesn't miss something soon).
>>>>>
>>>>>I do not believe that Deep blue did pruning in the first plies.
>>>>>I know that they were afraid of pruning and it means that if they searched 12
>>>>>plies forward they did no pruning in the first 12 plies.
>>>>>
>>>>>I believe that pruning later on the tree was done but you can look it as lack of
>>>>>extension in some branches and not as pruning.
>>>>
>>>>There is hard statement from Hsu at the microsoft meeting a few days
>>>>ago that he is forward pruning last few plies in hardware, other
>>>>than no progress pruning.
>>>>
>>>>Basically it is some form of what i described and what Heinz also
>>>>described (though it is not the 100% same method). Heinz calls it
>>>>futility pruning in fullwidth search.
>>>>
>>>>Of course they definitely needed that pruning as they just were
>>>>extending, extending, extending otherwise.
>>>>
>>>>If you just extend without ever doing a nullmove, then the explosion
>>>>of the tree is like the big bang.
>>>>
>>>>the word 'believing' has nothing to do with this here. It is a hard
>>>>statement of Hsu and i do not see why he should lie about this.
>>>>
>>>>It is no good marketing for him to tell that he forward pruned last
>>>>few plies, so he definitely would not have said it when he didn't do
>>>>it.
>>>
>>>The question is if the last few plies that are pruned can at distance of not
>>>more than 12 plies from the root.
>>
>>it was only pruning in hardware last few plies. So that's like 1,2, or 3
>>plies.
>>
>>Most likely number is 2 ply.
>>
>>>It is possible that he used forward pruning only when there were more than 12
>>>plies from the root position so pruning was done only in case that an extension
>>>was done earlier.
>>
>>forget the 12 ply pruning. It was doing only some forward pruning last
>>few plies in hardware. Not in software.
>>
>>>In that case you can look at pruning as not extending.
>>
>>No it is wrong. At a 12 ply line they also forward pruned of course.
>>No way to tell the hardware processors what depth in terms of real plies
>>you are searching at. In fact the values it gave to the hardwareprocessors
>>was already limited. Instead of alfa + beta, that was too much, so
>>it only gave 1 value (we call that MTD, but MTD really isn't using
>>binary jumps, so it wasn't MTD at all).
>>
>>You really think it also gives a real ply then? Another software value.
>>
>>That makes the chip dead dead slow.
>>
>>Suppose you must check in hardware another RAM value. That's another
>>extra sequential clock extra.
>>
>>That loses another 200k nodes a second at a chip. It only had 10 clocks
>>a node on average. No way to lose another clock. too expensive in hardware.
>>
>>You realize that?
>>
>>>For example it is possible that he extended a line like 2.Qxh5 Rxh5(after 1.e4
>>>h5) but later pruned the line because of that futility pruning so the extension
>>>had no effect.
>>
>>don't compare it with software pruning please. You can't do it like
>>that in hardware.
>>
>>Everything that goes in parallel you get for free in hardware, everything
>>that is sequential, like conditions to prune, that is costing
>>extra clocks.
>>
>
>I understand the point.
>It seems based on it that the 12 plies brute force of deep blue was not at least
>12 plies in every line.
>
>It seems that deep blue simply has inferior hardware in some meaning.
>
>All the 126M nodes are clearly misleading and the number of nodes in a
>normal machine to get the same result is clearly smaller.
>
>Uri

But still 12 ply was good in 1997 and getting 126 million nodes a second
was what the marketing department of IBM could do something with.

In fact it was design criterium 1: get more nodes a second than
others. The rest was irrelevant.

The best proof for maximizing number of nodes a second we can find in all
kind of idiot conclusions they drew.

For example:
  - normal alfabeta is just as good as other forms of alfabeta
    (IEEE99)
  - processors get timed out after a while and other processors
    resplit then and more processors get joined in
    (2001 document)
  - nullmove is not useful

In short everything was done to get as much as possible processors
running without worrying about efficiency.

Even in 1997 everyone on this planet who had a reasonable chessprogram
realized that normal alfabeta was inferior to for example pvs, aspiration
search, and all kind of other forms.

They wasted no time in algorithmic optimizations of say 10-20% even.

Incredible, but real true.

Nullmove was not used of course because it was brandnew in 1997 and
some said it was dubious even. In fact the popular testset in 1997
was if i remember well a testset with some zugzwangs in it. Of course
completely anti-nullmove...

But more important is that when you use nullmove, that your nodes a second
goes down. fullwidth you can do *much* faster.

The resplitting of the processors is the real sick thing it did.
It is a pathetic design issue. If you let the hardware processors
search a bigger depth, say 4 ply instead of 2 or 3, then of course
you get less communication between the slow 100Mhz RS6000 processors
and the hardware processors. So you get more nodes a second. However
it is very inefficient to do searches bigger than 2 ply with hardware
processors.

In fact a statement from Chrilly was that the move ordering in hardware
is so bad, that he could not believe deep blue doing 4 to 6 ply
in hardware processors unless they were just out for nodes a second.

The move ordering gets real horrible, comparable with a random move
ordering. No killermoves, no hashtable info to use etcetera!

Brutus is doing 2 ply searches in hardware and in endgame 3 ply. That's
WITH nullmove.

They did 4 to 6 ply. No nullmove. Fullwidth even. Just some forward pruning
last few plies. Most likely 1 to 2 ply.

There are another load of design issues taken to get a bigger nps.

Take for example the slow eval and quick eval.

That's a form of lazy evaluation. It won't be long before all commercial
programs will not use lazy eval anymore. I do not want to mention names
here but i know from 2 more commercials who stopped doing lazy evaluation.

there is a big difference between forward pruning last few plies and
lazy evaluation for correctness in the search tree.

you can see forward pruning as something that you do not see now, but
which you see in a later stadium perhaps. So you weaken your search
with it, but you should get in the end the same moves getting played.

On the other hand lazy evaluation CHANGES the evaluation and limits
its capabilities.

there is no difference between lazy evaluation and calling it a quick
evaluation. the principle is the same.

In fact i only experimented with a quick evaluation which can approach
the big evaluation with an accuracy of 3 pawns in 99% of the positions.

It's horrible if i use it.

Deep Blue did use it. Of course. It would be 2 times slower if it didn't.

For interesting to see about deep blue is why it is hardly changing its
best move. If it locks into a certain move it most likely is going to
play it. Usually that happens only if you search very dubiously, and
even then only when also the evaluation is very consequent.

Best regards,
Vincent



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.