Conference 7.286::digital

    Its a R&D processor that is solely for playing chess.  No commercial
    applications are available.  
    
    Is chess  the compelling application that will establish Deep Blue 
    architecture as (another) industry standard? 
    

    
    I had heard what IBM did was take many Grand Masters styles and squish
    them all together into this machine.  Seems to me, that Kasparov has
    beaten them all many times before, so putting them all together won't
    give them an advantage.  Also this machine doesn't purport to have
    artificial intelligence, it just checks all the best combinations
    against some preset "best" move, or so I was led to believe.
    Kasparov can discard 95% of the bogus moves in an instant, the computer
    takes X cycles to do this.
    
    I'm putting my money of Kasparov, he's probably the most creative
    chess player ever.  Ten years on top with no serious challengers.
    
    /art

>>    Could we port their s/w, then go head-to-head with a TruCluster ?
>>    (head-to head with Deep Blue that is). Can we write better Chess
>>    software ? Would T/L vs SP2 at chess be mind bogglingly boring ? 
    
I have been interested in such a project for some years now. 
IBM's approach is parallel processing, custom software, and custom
hardware.

I would really like to be involved in a comptetition between a multi-
million dollar custom hardware solution versus an off-the-shelf solution.
While the OTS solution might lose, the cost would have to be less.
And maybe it could win.

This is no minor undertaking.  It would have to be funded by some group,
for the hardware, even if all the software types donated their time.

I have considered this project for my Master's thesis, and would be interested
in more input, if anyone else is intersted.  There are chess-specific parts,
database parts, parallel/distributed processing parts, hardware/networking
parts...

Bear in mind that at least one IBM Phd makes Deep Blue his life's work,
presumably under salary.

JPB

    
    	How fast can a "real" computer play a game of chess?
    
    	I ask this because I had a chess game ["Battle Chess"] on my
    	8-bit Nintendo deck and at the highest skill level the system
    	could take 1-2 hours to make the next move.
    
    	And why does it take so long?  My guess is that the system
    	plays out every possible move combination, starting with the
    	current layout and ending with 1 player losing ... and then
    	picks the move towards the best outcome.
    

    
    rep -1
    
    Battle chess is not a good yardstick to measure chess on a computer.
    It is very slow, and not a very good player.
    
    Get yourself ChessMaster 4000, I had ChessMaster 3000 until a year ago,
    and on Expert, I'd beat it about 33% of the time.  Since upgrading to
    ChessMaster 4000, and staying at the Expert level (which is one level
    from the top - Championship), I haven't won a game, haven't drawn a
    game, I have to admit, I've lost each and every game.  Most of them go
    25+ moves, before I drop a pawn and decide it's hopeless and resign, 
    a few games have gone 40+ moves before the computer finds the
    advantage and gains the lead.
    
    Or maybe my brain isn't what it used to be.
    
    Or maybe my brain isn't what it used to be.
    
    Or maybe my brain isn't what it used to be.
    
    Yeah, what he said!  :>)  /art

Didn't I hear that the current score in the 6 game match was 
	Kasparov  1
	Deep Blue 1
Deep Blue won the first game.  Kasparov won the second in a 72 move 
tactical marathon.

Jim

    Last I heard they'd gone three games -- third game was a draw.

    
    	4 games, 1-1 and 2 draws.
    

This match is also being discussed in 

GRIM::CHESS_DISCUSSION

KP7 to add to your notebook...

JPB

>    	And why does it take so long?  My guess is that the system
>    	plays out every possible move combination, starting with the
>    	current layout and ending with 1 player losing ... and then
>    	picks the move towards the best outcome.
    
I would think the impossibility of doing this in any reasonable time,
especially early in a game, is what makes developing chess-playing systems a
continuing challange. Horsepower is nice, but isn't the challange that there's
nowhere near enough speed to search the entire space of move possibilities? 
The challange is then to do something smarter than a blind search.

According to what I heard on NPR: the machine tries every possible combination
that can happen and also takes that several moves out. The human thinks out
the most likely combinations and goes for it. Sooner or later the machine will
win. If not this time then the next one. But our "intuition" makes us act faster
and probably also much more unpredictably. liesl

RE: <<< Note 4425.10 by UNXA::ZASLAW >>>

>I would think the impossibility of doing this in any reasonable time,
>especially early in a game, is what makes developing chess-playing systems a
>continuing challange. Horsepower is nice, but isn't the challange that there's
>nowhere near enough speed to search the entire space of move possibilities? 
>The challange is then to do something smarter than a blind search.

Yes, you've got it -- the challenge (on anything like a conventional computer)
is to figure out which board positions to evaluate -- to prune the tree of
possible moves and responses to those worth evaluating. I worked a little on a
chess-playing program many years ago, and that was a key aspect of the
chess-specific part of it (in addition to the definition of a board position's
value). 
						-- Tom

  If I remember the report correctly, Deep Blue is reported as being
  able to evalute 3,000,000,000 (3 Thousand Million) positions per
  second. It does this by using an array of custom hardware under
  the control of the general-purpose workstations. This rate of
  evaluating psoitions is sufficiently fast that the machine as-
  a-whole can look ahead 12 to 13 "plies" (half turns; that is, a
  white move or a black move) in a reasonable amount of time.

  During the opening, chess-playing programs begin with well-known
  openings, just like the Grand Masters do. But once the game is
  afoot, the computers start to play simply by looking ahead as far
  as they can in the alloted time and picking the positions that give
  them some advantage in either materiel or position.

  Kasparov said something along the lines of "If I play a perfect
  game, then there's no problem. But the instant I make a mistake,
  the computer" (and its thorough look-ahead to future positions)
  "relentlessly exploits the mistake."

                                   Atlant

    
    	3 thousand million?
    
    	[You call it maize, we call it corn.  8^)]
    
    	How about 3 billion?
    

A chess program in Silicon is pretty boring, however, Sun's rumored Java 
processor has raised lots of interest and speculation.


							-Paul

But Hot Java and a game of chess frequently go together...

re: .14
    
>    	3 thousand million?
    
>    	How about 3 billion?
    
In some parts of the world, three billion would be three million million, 
not three thousand million.

Ray

    Ok, to the real theme..
    
    *if* Deep Blue wins (or probably even if it loses), you can bet your
    Digital stock options that IBM Marketing will ruthlessly exploit this.
    
    Now, what I am told, is that this is 'an SP2' (dunno how custom or
    whatever it is). If the key is performance (moves munched per minute?),
    what kind of horsepower (ints Fps flops, whatever) does this SP2 beasty
    have ? 
    
    If I can lash together a TL config to beat the ass off of every SP2
    I've ever had to benchmark against for customer apps  (and I have, and I
    ain't lost yet!), what 'raw' horsepower could I assemble (Cluster, 96 CPU,
    EV56 ?) to go one -on -one with this 'SP2' ? Could be a boring game
    though.
    
    Anyone up for this in Marketing ? [come on Pat ;-)  ]. Where is Nasser
    ?
    
    enjoy,
    
    
    AW
    
    
    
    

    I think I read once that Kasparov said he would loose to a computer
    before he lost to a woman, so maybe he lost one game to wind things up
    a bit.
    
    Is there any chance that Judit Polgar will be ready to take him on
    sometime? Her achievements as a child prodigy were better than
    Kasparovs, I believe. Any chess buffs know about this.
    
    I'll be rooting for her if she plays him... 

I dunno why the term billion was devalued to cover 1000 million, when there 
was already a perfectly good term for that value in existance (a `milliard')

Chris.

>I dunno why the term billion was devalued to cover 1000 million, when there 
>was already a perfectly good term for that value in existance (a `milliard')
    
    Must've been an American marketeer, who decided that to be a good
    way to sell less while giving the impression that it was more. ;-)
    
    ...petri

    
    <rathole on>
    
    RE: .20, .22, .23
    
    I think we must all be very careful when talking of such large numbers,
    because the world is not made only of English-speaking countries, and
    words that sound similar may have different meanings in different
    languages.
    
    For example, in Italian 1.000.000.000 is called "miliardo"; for the
    term "bilione" there is some confusion: originally it meant
    1.000.000.000.000, but now several educated people who can speak
    English use this term with the meaning of 1.000.000.000 (and in my
    opinion they are wrong).
    
    Writing actual numbers instead of words is the only way we can be sure
    we are correctly understood all around the world.
    
    <rathole off>
    
    - Maurizio
    

RE: The rathole:

  I wrote "thousand million" because that's the way the BBC does it.
  It avoids the ambiguity around "billion" and people's ignorance
  of the word "milliard". And just to prove that *I* knew the
  word, somewhere in this conference (I think), you can find a
  pun I wrote once about the Maynard Milliard. :-)


RE: "Deep Blue" versus the TurboLasers:

  As I understand the IBM system, the actual evaluation of each
  potential chess-board position is done by dedicated silicon.
  That is (roughly speaking), there's a whole mess of chips whose
  inputs are chess boards and whose outputs are "Value of White's
  position" versus "Value of Black's position". This operation
  would require a lot of computation, but can be done fairly well
  in dedicated, highly-parallel hardware. It's those chips that
  allow "Deep Blue" to evaluate 3,000,000,000 positions per
  second.

  The SP2's "merely" act to compose the positions, determine strat-
  egy,  create the user interface, etc.

  Without the specialized hardware, you'd need quite a passel of
  TurboLasers to do the work. Consider: 3,000,000,000 positions
  per second is 0.33 ns per position. How many Alpha CPU cycles
  does it take to evaluate a position? 10,000 @ 3ns/cycle? (to
  just grab a reasonable number out of the air) That's 30,000
  ns. At that rate, you'll only need 100K TurboLaser CPUs.
  'Better start filling out the Capital Requests now! :-)

                                   Atlant

    Just to continue the rathole,
    in Germany, milliard is our billion.
    

RE: <<< Note 4425.20 by SMARIO::BARKER "Cracking Toast, Gromit !" >>>

Well, now it's my turn to start a rat-hole:

>...we can say that the EV5 Alpha Chip is a 1.2 BIP chip.

That should be BIPS, not BIP. The 's' is not a suffix indicating plurality, but
rather stands for 'second'. A "1.2 BIP" chip would be a "1.2 Billion
Instructions Per chip," which is not a very useful description.
						-- Tom

	Does this all make Bill Gates a "Thousand Millionaire" now??

							mike

>	Does this all make Bill Gates a "Thousand Millionaire" now??

no, it makes him a- oh forget it, I got moderated last time I said that in a 
conference!  :)

Chris.

  In an earlier reply, I said that "Deep Blue" could evaluate
  3,000,000,000 positions per second. This morning's "Boston
  Globe" reported 200,000,000, that is 15 times fewer. So:

> At that rate, you'll only need 100K TurboLaser CPUs.
> 'Better start filling out the Capital Requests now! :-)

  Better make the order for just 6666 TurboLaser CPUs. Your
  job just got 15 times easier!

                                   Atlant

    
    Now that Deep Blue has been Deep Sixed... 
    
    Lets have a "Digital Computer" WEB Site game with 1000 people
    playing. The move that most people pick will be 
    the real game move with Mr Kasparov.
    
    Who wants to put-up the $400K for the game ?
    ($400 per person). Winner(s) take all (you get your mony back).  

    "Now that Kasparov has beaten the computer at Chess he faces his
    sternest challenge yet, getting the #$%&^** thing to print!"
    
    (Spitting Image 18/2/96)

> Lets have a "Digital Computer" WEB Site game with 1000 people
> playing. The move that most people pick will be 
> the real game move with Mr Kasparov.

  I think this would be a strategy certain to ensure defeat.


  Ours.

  He's the world reigning champion exactly because he *DOESN'T*
  think like the majority of the herd. That's one of the things
  that makes designing a winning algorithm so tough -- he can
  radically change strategy away from the "accepted truth" as he
  apparently did in his sixth-and-final game.

                                   Atlant

    
    rep .32
    
    I like Garry, but I don't want to give him $400.
    
    He's "Simply the best!"
    
    /art

    Re: last few
    
    Boris did change his strategy after the computer beat him.  According
    to Paul Harvey this AM, he change to playing for position, not pieces
    and that seems to have confused "blue" just a bit.

    Bill

    
    	So, how's the Kasparov match going?
    

    It's over;
    
    Kasparov - 3 wins
    Deep Blue - 1 win
    with two draw games
    

  Kasparov won, 3 wins, 1 loss, 2 draws. (L-W-D-D-W-W)
  The match is over.

                                   Atlant

    
    rep .36
    
    "Boris did change..."
    
    
    Is this a flashback to the Spasky/Fisher match, or a non-PC correct
    term for a Russian male.
    
    /art

Win, loose, or draw, IBM still benefits from all the free advertizing.


						-Paul

RE: .41 -< IBM wins no matter >-

In one sense you are right, Paul, such that you believe that "they can
print anything they want about me as long as they spell my name right".

But in another sense I believe IBM got hurt here.  Today's (19-Feb) USA
Today article on page B-5 was a litany of errors by Team IBM which led 
to the losses, including not correctly configuring the software and data
files on the system, making moves that the system didn't order, and an
actual software crash in the middle of the game.  So the vaunted perfection
of the people at IBM was not helped here.

In addition there were all the problems people had getting into the WWW
site.  I am not even a Network Specialist, and I have copies of the USA
Today articles detailing how many hits per day their site took, and how
woefully unprepared they were for that call volume, and the fact that
they had to quickly bring in many other SP2 systems, and even then they
still had problems.  I am planning on making sure our customers know about
their problems, and contrast them with AltaVista and the Sports Illustrated
WWW site which holds the swim-suit issue, and the ease with which Digital
handles that load.

So I din't think it is all happiness over at Big Blue...

-- Ken Moreau

        Re: .40

    My ever nimble mind at work.  I meant Kasparov changed his play after
    his loss.

    (Young son and I had been discussing the philosophy of Rocky the
    Flying Squirrel at 3AM this morning).

Wasn't the key accomplishment that a computer beat a sitting World Champion for
the first time? 

Jim

    
    I've been rethinking this a bit.
    
    Doesn't Kasparov have a vested interest in the world believing that
    a computer is getting close to beating the world champion.  Like a 
    rematch, etc.  For $400,000 I'd say lots of nice things about my
    inanimate opponent.
    
    Not that I don't think he's the best or that Deep Blue is all that
    bad, but maybe Kasparov threw the first game, so interest would
    pick up.  From the last 3 games, it's clear to me that Kasparov
    has Deep Blues number.
    
    /art

    re .45                                         
    
    well, that was my theory in .21. 
    
    >I think I read once that Kasparov said he would loose to a computer
    >before he lost to a woman, so maybe he lost one game to wind things
    >up a bit.
    
    I think he had the joint cased thouroughly before he started. He is
    always immaculately prepared. But there is no story if you win 6-0 is
    there? 
    
    We should sign up Judith Polgar and get her to program an alpha. Then
    we could challenge Deep Blue to a game, obviously with a dollar limit
    on computing power. I don't know what the limiting factor is in this,
    but wouldn't a VLM application be appropriate for checking out the
    database of known games and critical situations?
    
    Someone pick this up please. I want to live to see it!
    
    Kevin

That's Judit - no "h".  Why do you think that a good chess player would
necessarily make a good programmer?  I would guess that most of the top-notch
players couldn't describe for you their method of analysis.

If we want to sponsor some university team to come up with an Alpha-based
chess playing system, fine, but I think we'd be wasting money to try to
do IBM "one better" here.

				Steve

    re -1.
    
    Steve,
    if we did 'one better' on IBM, in this space, it is unlikely to be
    money wasted. 
    
    If the silicon monster that they nailed together *isn't* SP/2 (ish),
    but is mainly custom stuff, then let's forget it. If it  *is* the
    'same' kind of silicon that they try to flog (sorry, american=sell) to
    customers, then why wouldn't we be game ? 
    
    Anyone actually know what this Deep Blue system is made of (I only get
    UK press reports - no-one believes the UK press about much at all) ?.
    
    If it *is* mainly SP2, then maybe we can have fun. Our (sellable)
    technology stuffs IBMs (sellable) technology. Maybe it can play chess too.
    :-).
    
    But boy, do *they* know how to market their kit....
    
    
    (..sound of soap box being pushed away..)
    
    
    
    AW
                  

    
    	The problem is, in order to get the exposure we'd want out of
    	this proposed showdown, we'd have to make sure EVERYONE knew
    	what was about to happen ... namely a chess match between IBM
    	and Digital.
    
    	And in order for us to get the RIGHT exposure, we'd have to be
    	sure we would win.  Are we that sure?
    
    	This is much different from putting our name on a race car,
    	especially since this would be a venture directly related to
    	what we do ... mainly, build computers.  In this case, a loss
    	would be bad publicity.
    

Re: .48

"Deep Blue" contained a lot of custom silicon.

			Steve

I understand that the chess match caused so much traffic into IBM's web site
that response times degraded.  It was my first time to hit the IBM page.  
Whenever you can get people to visit your hope page, you have an opportunity 
to present your company and your products.  

Jim

    re .49
    
    And the only way IBM would do it, is if THEY were sure THEY'D win. 
    Both companies have too much as stake... I doubt something like this
    would ever happen.
    
    -Steve
    

> Wasn't the key accomplishment that a computer beat a sitting World
> Champion for the first time? 

  Yes.

                                   Atlant

If we were going to try to beat IBM, we'd have to bring /nasser
back!

I bet he could set up a decent chess program...

    re .47
    
    Steve, I was not really being serious. I don't think that a good chess
    player would make a good programmer, but it would be good to have a top
    flight one in a team of programmers wouldn't it? Only a top player can
    really understand the subtleties of the information map. I think Judit
    Polgar (thanks for the correction) plays a very creative kind of chess,
    and the public interest would be hugh, given Kasparov's comments. It
    would be possible to find other joint sponsors to generate finance.
    
    I still don't think it was a straight fight between Deep Blue and
    Kasparov. Who put up the money ? Wasn't it IBM ? Kasparov had an
    interest in not killing the goose. Those who say, YES,  IBM have achieved a
    win against a sitting world champion must address this.
    
    The other question is, would we win, would we lose ?  That would be the
    same for them. But why do we lack self-confidence at Digital nowadays?
    Our technology is our strength. In certain areas we have a clear lead. 
    "Can we win? -> Why not? -> Yes!" would be the chain of thought to
    follow. Sure we have been through some bad times, but we came through
    them. Others didn't. So let's not undersell ourselves.
    
    Kevin 

Why is everybody so hung up about winning. If the objective is to 
get the company's name into newspapers then an IBM-Digital chess 
tournement could have only one outcome: we both win. SUN, SGI, HP 
etc are the losers.

The strategy would be to hype the FUN side of thing and never 
pretend that its serious. Fortunately, most people don't take 
computers too seriously anyway. (Long memories of $100,000,000 gas 
bills?)

Perhaps, the spin should be IBM with their very expensive, purpose 
built monstrosity vs, a little, cheap (sorry marketeers, I meant 
cost-effective) turbo-laser cluster. Its a David and Goliath story 
we can't lose.

Mike.

    re .56
    
    ok I'll buy that, but David did win against Goliath, that is the story,
    and we should certainly go for it.

... is what humans have over computers. Most people have no idea how computers
play chess and how many moves they need to consider to play a reasonable game.
You kind of get the idea when you consider the chess board as a 64 "digit"
number ... where almost each "digit" can be a white or black pawn, white or
black rook , king, queen, ...  

Humans see structures and patterns of pieces ... they do not evaluate a zillion
board positions.

To beat a computer, you need to have a plan that extends past the depth the
computer can search to in a reasonable amount of time. This is easier said 
than done though.

  Just so I'm clear on this, why does anyone believe that a
  (reasonably-sized) collection of TurboLasers would beat the
  custom hardware of "Deep Blue"?

  Do you have some new game-playing algorithm that will remove
  the need for the computer to do the exhaustive evaluation of
  positions? Or a new tree-pruning algorithm that limits the
  number of positions that need to be considered? Failing either
  of those, we'd be toast without similar custom silicon.

                                   Atlant

Re .59 (why do people expect Turbolaser to beat Deep Blue)

Because IBM has managed to convince people that Deep Blue
is a near-standard SP2 system built around RS6000 processors.
The IBM materials make little or no mention of the custom
hardware that is doing the real work.  Thus, it leaves the
impression that "you, too, could buy the supercomputer that
beat Garry Kasparov."  Pretty clever, to my way of thinking.

When all is said and done, the world will remember that it was an IBM 
computer that first beat a sitting World Chess Champion.  THAT was the 
feat that was accomplished in this match.  Just beating the World Chess
Champion in one game is no longer the standard - that has now been done.
The next step is to beat the sitting World Chess Champion in a match
amd given Kasparov's performance, that is not going to be easy.

Jim

    
    I firmly believe we can build a computer that will lose just as
    impressively as IBMs.  No matter what, the computer is only as
    good as the algorithm it is using, and with 5 or so GrandMasters 
    helping to program Deep Blue, all of who have lost or would lose to 
    Garry, Deep Blue is destined to lose.  Unless Garry throws the game, 
    or isn't feeling very creative that day.
    
    Computers can always win or tie at Tic Tac Toe, if they go first.
    And always tie if they go second.
    
    With checkers, until the Kings appear there is only a finite number
    of moves.  And I'd bet that because the strength of one's kings is the
    same as any other kings, that even after kings appear there are only 
    a finite number of moves.  Hence, a brute force machine should be able
    to always at least draw in checkers, and most times win, if it's
    opponent doesn't play a "perfect" game. 
    
    Chess is not the same.  A bishop and a knight have the same values,
    maybe.  A queen has the same value as two rooks, maybe.  And there 
    is no such thing as artificial intelligence, at least in my opinion.
    Machines don't have an Id, they don't branch off on unexpected tangents, 
    they are not a creative lot.
    
    And Garry K. is the "best" chess player the world has ever had.
    Perhaps not unbeatable, but as of today, he is "Simply the best!".
    And $400,000 richer.  Go Garry!
    
    /art

>    Machines don't have an Id, they don't branch off on unexpected tangents, 
>    they are not a creative lot.

... although, to a programmer, this isn't how they *seem*, oftimes ...

I leave the building for a few days, and the dam busts on this one...

There are standard approaches to building a chess program in a single-
processor evironment, general-purpose computer.  You use Minimax, pruning,
static evaluation.

Changes need to be made if you have multiple processors or custom, special
purpose processors.  There is academic work on this, some of it on the web. 
The IBM group has also published, I believe.

The more you approach loosely-coupled parallel processing, the more you get
into uncharted space.  This is where PVM or some such technology could pay
off.

Position caching is also a win, so a VLM-like approach could also help. 
But there has to be some point where you spend too much time searching
cache... What size is that?

I don't believe that today we could build an Alpha farm that could beat
Deep Blue, because of its custom hardware.  But we could build an Alpha
farm that plays grandmaster chess and has a part number, with no custom
hardware.  If we play our cards right, we could demonstrate openness,
standards, communication, internetworking -- several of our strengths.

I would be very interested in working on a pilot to see what the
possibilities are.  As I said earlier, I am looking for a Master's thesis
topic, and I was already thinking along these lines.

Please contact me via Mail at SLBLUZ::BROCKUS if

1)  you are also interested in working on this (technical) or
2)  if you want to provide hardware/software resources for this or
3)  you want to use the results of this effort.
4)  you're just interested in following this...

A couple of points:  I am billable to customers and will be gone to
training for a couple of weeks, so don't expect quick turnaround.
And I think the DIGITAL notes conference has taken enough of a hit with
this.  I will establish a distribution list of people who respond.
If this takes off, we can open a NOTES conference for the project. 

JPB

re: my previous about a Digital chess program:

>I would be very interested in working on a pilot to see what the
>possibilities are.  As I said earlier, I am looking for a Master's thesis
>topic, and I was already thinking along these lines.

Things have changed.

In order to increase my personal marketability, I have doubled the pace
of my Master's degree program.  I have changed from the thesis program to
non-thesis, and have no free time left.

There was insufficient interest shown to pursue this, anyway.  A
hard-driving person needs to head such an effort, and at some point it
would need corporate support.

Since this is a software project, it is likely it would not get that
support.

I would still love to see this done, but I can no longer be a major player

Perhaps someone else will pick up the reins on this one, but I don't have
the time.

JPB