Re: [computer-go] question regarding Hydra Chess Supercomputer

[Vincent Diepeveen <diep@xxxxxxxxx>]

then let someone from the anti box state some facts:

a) both chrilly and hsu say their evaluation is sophisticated

My impression is they have no idea about chess at all. It's like me
shouting my go program has a lot of go knowledge. I know the edges are more
important and i have mobility in the program (as described once by Mark
Boon in a paper) and i have it implemented incremental in go program.

Further i know nothing of go other than a few rules and threads like
super-ko are already hard to read for me.

Let's quote facts on deep blue:
  a) it searched 10-12 ply (including hardware searches)
     and had forward pruning in hardware (last 4 ply of that 10-12 ply)
  b) random move sorting is branching factor 10 or so (in 1997 and before
     this was a NORMAL branching factor with a few exceptional thin searching
     programs from which crafty and junior are an example). Nowadays
     it is more or less 2.8
  c) deep blue had no hashtables in hardware, which is a severe handicap
  d) deep blues nodes a second has been overestimated by some authors,
     from which hyatt is best example. I remember hyatt quoting a theoretical
     1 billion nps. Well there is no measurements here. Chrilly *measures*
     with hydra how many software searches he's doing. Deep Blue 
     hasn't measured anything. They just optimistically estimated it at
     an average of more or less 120 million nodes a second. Not the quoted
     1 billion by hyatt (again hyatt).
  e) the parallel efficiency was quoted as 15% or so. This was however
extrapolated from 1 cpu with 16/32 at 1 node. 

The reality is however that if you already have such a poor speedup at
16-32 processors at 1 node, that of course the CLUSTER efficiency loss will
be way bigger when moving up to 30 nodes with each 16 hardware cpu's.

Especially for 2 reasons this was the case:
  a) deep blue used aphid which is known to scale bad (see original authors
     paper on this from Jonathan Schaeffer)
  b) they used singular extensions

With diep there is already problems using singular extensions at 4
processors, so i had to write a lot of special code to fix that. At 16
processors it was already horror & co. 

That's why for 460 processors i had turned it off completely.

Now again, they do not show any output or proof anywhere about their
efficiency. So we're talking about
 
  1) statistical insignificant measurements, probably they had 1 position
     with 15% speedup and used that as a reference, however gameplaying
     is a worst case game. Not an average or best case game. They just use
     best case
  2) their comparision is flawed. They compare a very inefficient 1 cpu
hardware search with a 16-32 hardwareprocessor search.
  3) they do not show *anywhere* how many nodes a second their thing
searched when using 480 processors, so we can safely assume their 100+
million average includes a big piece of guessing too.

The reason their branching factor is seemingly 4.0, is because their
parallel search was so inefficient SCALING that it simply needed quite some
time to scale. When effectively more cpu's start helping, it's easy to
predict that you can get away without showing the real branching factor you
burned.

I need to note that when searching IN SOFTWARE, very EFFICIENTLY fullwidth
with singular extensions, it's very hard to get to 10 ply for DIEP after
hours and hours of search it is hardly 11-12 ply.

And even then i'm not extending so much tactics like deep blue (i don't do
recaptures for example). 

A good comparision is in go. Fullwidth, branching factor = 60
With nullmove branching factor = 10.0 (for my silly go program using
nullmove).

Around 1997 so many even very strong software programs searched
inefficiently. Deep Blue just was the exponent of it. 

Even then we can easily judge its play. That was about 2200 level.

That kasparov lost from it has nothing to do with good play from Deep Blue.
It didn't play well. Kasparov just played some moves and didn't care. He
made a mistake in assuming he would get a rematch. The idiot. 

So it was good for Kasparov's ego.

In other posting here Chrilly already explained that it is not in the
interest of companies who sponsor GM's, to let them play for a win. GM's
won't show up then.

I'm not so sure whether hydra is better than humans.

Just organize a world champ against the computer and winner of it wins $500k.

If qualified GM gets knocked out first round, he gets $100 for showing up.

They will come, oh sure. All few hundreds of GM's alive will show up.

No company nor sheikh has any interest in organizing such an event. They
just want to look good. They just give GM's some money and those are happy
to for once in their life not fight hard to earn money. Kasparov was no
exception to that. Even blindfolded he can play better than that.

I'm sure in one of his many statements he said that.

Yet again we remember fritz-kasparov of 2 years ago and there we can see in
1 game the real strength of mankind.

kasparov played some *gambits* against computer there and kasparov
basically didn't do much.

Then kasparov is down 1 point and this time kasparov is not so stupid to
lose match so he *had* to win the next game in order to not lose the match.
Kasparov then played 1 game where fritz was shreddered into dust without
having a chance. In fact fritz said it was WINNING where it was losing
bigtime.

So when kasparov *had* to win to not lose the match, he had zero problems
to without losing much time, to just shredder it. 

This where fritz at the time already was a very agressive program.

then last game kasparov again played quietly and drew and match was a tie.

Everybody happy including kasparov. 

Nevertheless the level of those games was hundreds or rating points higher
than in 1997.

That's a very objective fact which every strong player will be able to
clearly show you.

Where we must not believe the nonsense a certain professor Hyatt spreads.

Basically i'm just disbelieving some nonsense from a, his chess rating is
in go comparable to 30 kyu rank or so, that todays chess software is
stronger than mankind.

Nevertheless it's clear that the software has made big jumps past few years.

I am very amazed the go-software isn't making similar jumps.

Probably it's a money question. Too little go-engine authors that work hard
when compared to chess where there is about 500 engines now.

At 19:13 24-10-2004 -0400, Don Dailey wrote:
>
>I agree  with you, but  according to Bob  Deep-Blue had none  of these
>issues, he  claimed there were  *no* compromises, that even  given the
>same numer of nodes Deep Blue would blow everything else away.
>
>My feeling was that the top  PC programs would probably beat Deep Blue
>if you waited for a computer fast  enough to be able to MATCH the same
>number  of nodes per  second.  I  made a  statement something  to that
>effect which started the discussion (ok,  argument.)
>
>I eventually  shut up  for 2  reasons.  Bob could  yell louder  than I
>could but the  other reason was that I was starting  to come across as
>anti-Deep Blue even  though I wasn't.  When you  end up in discussions
>like this  people try to push you  into a box.  In  this case, several
>were into  Deep Blue  hero worship  and I was  too, but  evidently not
>enough so I got placed into the anit-blue box and I couldn't get out.
>
>- Don
>
>
>
>
>
>   From: "chrilly" <chrilly@xxxxxxxxxxxxxxxxx>
>   Date: Mon, 25 Oct 2004 01:06:41 +0100
>   X-Priority: 3
>   X-MSMail-Priority: Normal
>   X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3
>   X-AntiSpam: Checked for restricted content by Gordano's AntiSpam Software
>   X-Scanned-By: MIMEDefang 2.42
>
>   >
>   >You say  hardware search  is less efficient  than software  search.
>   >
>   It is much more difficult to implement. Implementing a recursive function
>   with a Finite-State-Matchine is not easy. Especially getting all the
timing
>   right. A lot of things run in parallel, some operations take 1, some 2
some
>   3 cycles. The Hydra FSM is simply a nightmare.
>   The Deep-Blue Hardware search was particulary simple. E.g. They had not
even
>   a killer-heuristic (Hydra has). Such things like History-Heuristic can
>   principially not be implemented (at least in the Deep-Blue and Hydra
>   design). Has to do with move-masking.
>   Additionally there is no reasonable way to implement a hashtabelle.
Even if
>   one has RAM on the FPGA-cards, one can not distribute the hashtables in a
>   massivly parallel system.
>   DB had also not null-move. Hydra has.
>   Additionally the software part of the search gets only a few bits of
>   information from the hardware part. In Hydra its 32-Bits.If everything
is in
>   software, one can use the full information of this search also for the
other
>   parts of the tree.
>
>   This points can all be solved, but not within the Deep-Blue and Hydra
>   architecture. Besides using FPGA Hydra is from the architecture quite
>   similar to DB.
>
>   > computer chess  group and got heavily criticized  by Bob Hyatt who
>   >defended Deep Blue on this issue.
>   >
>   There is no need to defend DB on the search-issue. Feng Hsu openly
discussed
>   this problems in his publications and never claimed that his search is
more
>   effective than the best software-searches. He only claimed that his method
>   is more effective than that of the other hardware-engines Hitech and of
>   Belle. I claim that the Hydra search is better than the DB-one.
>   >
>   >I couldn't figure how the  hash table implementation would be as good,
>   >
>   There are no hashtables in the hardware part of DB.
>   >
>   >or  how the  evaluation  could be  as  good because  it's  so easy  to
>   >engineer software code  than hardware code.
>   >
>   The evaluation is a different story. I think one can make a better
>   evaluation in hardware than in software. Especially in the
>   middle-game the Hydra evaluation is even now better than the eval of Fritz
>   or
>   Shredder. In the endgame the software programms have still an edge..
>   There is no speed-knowledge tradeoff. Additional knowledge needs more
logic,
>   is cumbersome to implement,  but there is only little slowdown. Everything
>   can be made in parallel. The main part of the Hydra-Evaluation is a
>   super-move-generator. This move-generator generates for both sides the
>   attack information and a quite accurate evaluation of attacks/defenses
plus
>   pins is done. This is in software very expensive, in Hardware it takes 3
>   cycels. What is hard to implement are e.g. some special cases in the
>   endgame.
>   The main problem is in hardware, that the evaluation is so cheap. One
has a
>   lot of terms and tuning is very complicated/work intensive. Also the
>   turnaround times for a new version is even in FPGAs much longer than in
>   software.
>   >
>   >Bob was  so strong in  his opinion  that I just  had to shut  up.
>   >
>   Sounds familar.
>
>   Chrilly
>
>
>
>_______________________________________________
>computer-go mailing list
>computer-go@xxxxxxxxxxxxxxxxx
>http://www.computer-go.org/mailman/listinfo/computer-go/
>
>
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/