Brain vs. Computer: Place Your Bets

dev_null_ziggy writes: "CNN reports that the current chess guru is going up against a supercomputer, amusingly titled 'Deep Fritz.' The match is scheduled for October, and the current champion, Vladimir Kramnik, stands to win $1 Million dollars if he wins. Of course, since he'll be snagging $800k for a draw, and $600k for a loss ... I'll give two to one odds on the machine."

worst game of 'fritz' ever...

[andi75]

This game is *hilarious*. I can't imagine what Kramnik will do to the poor machine :-)

This game clearly shows how stupid computers really are. For your amusement:

White: L. Van Wely, Black: Fritz SSS; played in Rotterdamn 2000

1.c4 e5 2.g3 Nf6 3.Bg2 Nc6 4.Nc3 Bb4 5.a3 Bxc3 6.bxc3 0-0 7.e4 a6 8.a4 d6 9.d3 Bg4?! 10.f3 Bd7 11.Ne2 Qc8?! 12.h3 b6 13.f4 Be6? 14.f5 Bd7 15.g4 Ne8 16.Ng3 Qd8 17.g5 Bc8 18.h4 f6 19.Qh5 Na5 20.Ra3 Qe7 21.Nf1! Nc6 22.Ne3 Qd7 23.g6 h6 24.Ng4 Ra7 25.Rg1! 1-0

Re:worst game of 'fritz' ever...

[tunesmith]

Is there some online applet we can copy/paste the record into to step through the moves on a chess board? Seeking the laziest way possible. :-)

tune

I'd take that bet

[hjw]

So what this chessplayer needs to do is take you up on your bet.

If he bets $400k on the machine.

If he loses, he gets a $800k from you, and $600k from the competition + $400k stake =$1600k
If he draws, he comes out of it with $800k - $400k stake = $400k
If he wins, hecomes out with $1000k - $400k

hmmmm.. what to do???

Brain vs. Computer

[MouseR]

Given the alternative [ntk.net], I choose the Computer.

computers play Chess well, but suck at GO

[andi75]

Computers play Chess quite well, they're even stronger at Checkers, and they rule at Connect 4 (a friend of mine has written the strongest freeware checkers and c4 programs [fierz.ch], check them out).

However, they suck *badly* at GO. This is because the branching factor (that is the average number of available moves) is about 30 at chess, 10 at checkers, and 7 at connect4. GO has an incredible branching factor of *over 200*. That means, the typical approach of 'alpha-beta' search breaks down.

If you're into researching new board game algorithms, try GO.

- Andreas

Re:computers play Chess well, but suck at GO

[Skuto]

>and they rule at Connect 4

This game has been SOLVED by Victor L. Allis.

He also invented a new tree search algorithm
which is extremely strong _when_ it can be
used.

He used a combination of this tree search and
rules (black can't win if this parttern
is present etc..) to solve it.

>about 30 at chess, 10 at checkers,

It's 38 for chess, 2.7 for 8x8 checkers (where
a comp is already world champion)

The use of tree search depends on a lot on
the tactical nature of the game. You can still
use it with a branching factor of over 100 if
the game is tactical enough. (so 5-7 ply searches
beat most humans)

But go needs more longtime planning, and you need
way more depth for that.

--
GCP

That will be with "long" matches?

[OpenSourced]

I seem to remember (correct me if I'm wrong) that the Deep Blue-Kasparov match was played with "fast" matches, allowing less time than normal championship "long" matches. I had the idea no computer had been created that could beat a Grand Master human in a "long" match.

The article says nothing about that. Anybody knows something about it?

--

Re:That will be with "long" matches?

[dersen]

Deep Blue - Kasparov was played with standard "long" matches. This Deep Fritz vs. Kramnik match is also played with standard time, but I believe Kramnik is allowed to rest every 5 or 6 hour of play.

Re:That will be with "long" matches?

[Skuto]

>played with "fast" matches, allowing less time
>than normal championship "long" matches.

The match was fast in the sense that few games
were played, but Kasparov was allowed the full
thinking time.

>I had the idea no computer had been created that
>could beat a Grand Master human in a "long"
>match.

Those have existed for quite a while now. Most top
programs have no problems with 'weak' GrandMasters
(sub 2600 ELO rating) even at long timecontrols.

--
GCP

Re:That will be with "long" matches?

[OpenSourced]

Thanks for the info! :o)

I will then forget chess and learn "Go", that will give me some breathing space before the computers start winning at that too ;o)

Why Fritz?

[Yumi Saotome]

Come on, everyone knows that Crafty is the best Chess AI out there. I mean, it can consistently beat humans, even Grandmasters, and has a much better algorithim. Fritz is gonna get killed by Kramnik. When they tried Fritz in the Dutch tourney, it did ok, but produced some interesting games that displayed its stupidity. Like when Piket beat it, the rest of the grandmasters said "What the heck are you doing? You wouldn't play against a human like that! You'd get killed!" Or when Khalifman was losing badly, he said, "Maybe if I feed it pawns, it will do something stupid." And the computer drew a won game. Strangely, Chess AIs seem to draw/lose to rat defenses (which no one in his right mind would do against a human). Only Crafty seems to beat that.

Why Chess?

[Runt-Abu]

I have no idea why chess is always used as the basis for competition, it's not exactly the most intresting or even inventive game.

So here's my suggestions for some games that computers should be taught to play.

* Kerplunk - "Logic" and skill required, also would mean your 6 year old has a chance of winning.

* Diplomacy - Cunning and backstabbing should be part of the standard COE build by now.

* Quake - For no other reason then the irony of a computer playing a computer game.

* Skeet shooting - More a sport but let's see how good those motion trackers really are...

Re:Why Chess?

[Tim C]

I'd think that chess is generally chosen because you can just calculate best moves based on a scoring system, and because trees of move sequences are relatively easy to calculate. (Note that I said "easy", not "quick".) There is also a logical and strategical element to it, which you can exploit in your code if you're feeling ambitious.

As for playing Quake, surely that's exactly what all Quake bots do? "All" you'd have to do would be to write a mod that allowed a bot to play the single player game, instead of the multiplayer game, and see how well it did.

Cheers,

Tim

Re:Why Chess?

[iapetus]

But that's exactly why chess is so uninteresting. It generally boils down to a question of making a better brute force algorithm. Other games are far more interesting from an AI perspective - Bridge is a very good one to look at.

One of the most interesting AI players I've seen in recent years is the Angband borg, which plays the roguelike game Angband with a relatively high level of skill (although it's far too much of a coward for my liking...)

Re:Why Chess?

[iapetus]

Sometimes they boil down to brute force, but not always. Incomplete information makes brute-forcing things difficult (that's the main problem with Bridge, rather than any randomising element). In fact dealing with random elements in some situations can actually be almost as simple as non-random games - maybe even simpler, since the computer is going to have the edge in calculating the probabilities of particular events taking place.

There are plenty of evolutionary approaches to generating AI similar to the one you describe for Quake. I'd be interested in seeing if a good Quake bot could be generated using GP...

The really amazing thing...

[Daneboy]

Really, the thing that's amazing about this is that there are human beings who are able to keep up with machines like Deep Blue. I know Kasparov was all P.O.'d that he lost, but I think it's just mind-boggling that he was able to play a machine like that and win even a single game! Think about it -- even dumb, off-the-shelf PC chess programs can handily beat the 99.99% of humans whose chess rating is, say, below 2200 or so. Then comes a custom-made supercomputer, tailored to Kasparov's particular playing style, with a memorized library of *all* his past games, and he *still* can compete with it on an equal footing. That's freakin' amazing!

What if Deep Fritz wins?

[kiwaiti]

Will he get a million, too?

Or will it all go to his "owner" again?

I hate to think theres still no one concerned about us machines, our desires, needs, and pursuit of happiness.

Kiwaiti

How big a library ?

[jneves]

One of the tricks of 'Deep Blue' was a library with every game of chess played at the master level in the last century. That's what made it play like a human. Kasparov lost the first game because of an error in his training, he prepared himself to play with a machine and got an almost human player.

The biggest advantage of the machine in this kind of games is that it's more difficult for it to make a mistake. I don't know what is the depth of moves that the machine can calculate, but someone at the level Kramnik can usually "see" 10 moves ahead. Then an error screws up everuthing. How long until we get a computer capable of doing this kind of search ? Then we could really see a computer playing a game completly different from a human, and winning ?

Re:How big a library ?

[Skuto]

>One of the tricks of 'Deep Blue' was a library
>with every game of chess played at the master
>level in the last century. That's what made it
>play like a human.

And Kasparov simply sidestepped this by making
some seldomly played moves at the start. You
can see it easily by looking at the games. The
machines opening play was all but human.

>Kasparov lost the first game because of an error
>in his training, he prepared himself to play with
>a machine and got an almost human player.

It was still a machine, but just with a lot more
chessknowledge and tactical speed than anything
else at that time. He was expecting something
like Fritz (literally!) and got something much
more powerfull.

--
GCP

Are you sure that's "human"?

[dstone]

Kasparov lost the first game because of an error in his training, he prepared himself to play with a machine and got an almost human player.

I would adjust your claim to be, "Kasparov prepared himself to play with one type of machine and got a different, stronger machine." Having flawless, move-by-move recollection of 100 years of of games is not "almost a human" quality. If it had 1500 years of game history that could be accessed and analzyed in real-time, 10x faster than before, would it be even more human? I don't think so. Probably stronger than ever. But less human.

And, upon checkmating the machine, a cry is heard

[wowbagger]

Fritz! They've killed Fritz! Those dirty rotten fairies!" [imdb.com]

Seriously, though, this is why chess is not a "game" in the game theory sense of the word. Every move has known, predicatable consiquences, and all the data is available to both sides during play. As a result, as computers advance, they will become better than people, because chess is a computation, not a game

Now, consider poker. While somewhat simpler in terms of the number of moves available to a player at any given time, they player cannot predict with complete precision all possible outcomes of a given play, since he does not know what cards are coming up next, what cards the other players have, and therefor cannot winnow the solution space significantly. In poker, the machine cannot easily tell if I am bluffing or if I just completed my royal flush.

Now, for a REAL computational challenge, make a computer that can play Magic, the Gathering worth a darn. Talk about "limited information" - you don't know what cards the other player has, you may not know the powers of the cards, and you may not even know what's coming up in your deck next. Make a machine that plays that well and I'll be impressed.

Re:And, upon checkmating the machine, a cry is hea

[Eeeeegon]

M:TG programs have been written before (who can forget the infamous Planeswalker game just before the release of 5th Edition?). The AI just needs to be improved before a Magic program can be taken seriously. All it takes is statistical analysis ('playing the odds'), using what it knows about the opponent's cards and/or deck, and a pretty extensive database of 'if I do A, then B will happen'. It's anything but trivial, but certainly within the reach of current technology and processing power.

I'm not saying a program could win a PTQ; but it would prove invaluable in training for one (especially for this season ... invasions block constructed...)

Research like this has been going on for years; poker analysis has become a science of its own, using unknown information to formulate the 'best play'. Magic is just a linear step up; a larger database of cards, rules of the game, and known decks in the given format. Of course, this is all brainstorming, but it's certainly possible to write. I bet we'll see a quality Magic-playing computer program in the next six months.

Re:And, upon checkmating the machine, a cry is hea

[tmark]

Now, for a REAL computational challenge, make a computer that can play Magic, the Gathering worth a darn. Talk about "limited information" - you don't know what cards the other player has, you may not know the powers of the cards, and you may not even know what's coming up in your deck next. Make a machine that plays that well and I'll be impressed.

This is a bad idea. If you write a program that plays "Magic, the Gathering" well it will get beaten up and overwritten by other, cooler programs that don't want to have such loser programs in the same address space. Not to mention the fact that you will be fair game to every bully on your block. Hell, regular "Magic, the Gathering" players may well be entitled to beat you up...you would be that low on the totem pole.

Re:And, upon checkmating the machine, a cry is hea

[DoktorGonzo]

...chess is not a "game" in the game theory sense of the word. Every move has known, predicatable consiquences, and all the data is available to both sides during play.

Does anyone have all the data on white moving a given pawn as its first play? What shall white do for its next move? Can black predict it? Consider chess to be exclusively a two-player game (or computation, or whatever)--black versus white. But poker, in a bizarre sense, always has at least three: a player, his opponent, and chance, each with their own secret information which the others cannot use to aid their own decisions.

I would be interested in seeing the definition of "game" according to game theory. Prisoner's Dilemma has neither the complexity of chess nor the chance element of poker, what with only two moves and four possible outcomes. I call it a game. What does game theory call it?

Re:And, upon checkmating the machine, a cry is hea

[wowbagger]

I thought predicting the possible outcomes of a poker game and a chess game is pretty much the same problem

No, it isn't the same problem. In chess, I could, in theory, predict every possible move you can make with absolute certainty. I know every piece you have, and every possible move it can make. There are no surprises.

In poker, I don't know every card you have. True, I can try to predict every possible outcome given every possible card you MIGHT have, but that causes the problem space to balloon mightily. Furthur, I might have to assume, because you have 2 jacks showing, that you might have the other two jacks plus a joker (five of a kind, almost unbeatable), and that if that is the case, there is no way I can complete my jack-high straight. But, you might NOT have the jack, and it might be the top card, and I might be able to complete my straight, and leave you with at best a three of a kind (four if you have a joker). You see, I have to play the probabilities while in chess it is a certainty that you cannot move your knight one square forward.

Re:And, upon checkmating the machine, a cry is hea

[wowbagger]

OK, given that you have 5 of hearts and 6 of spades showing, with 7 of diamonds, 8 of clubs, and 2 of spades in your hand. You are playing against a single opponent, who is showing 3 of clubs and 3 of diamonds. Your draw. What is your optimal move?

You don't have all the information. You can go by the probabilites that discarding the 2 and drawing to either end of the straight has the highest probability of giving you a strong hand, but little do you know that the next three cards are 2 of clubs, 3 of spades, 3 of hearts. By drawing one, your opponent draws 2 and gets 4 of a kind to your garbage. Had you discarded three cards, kept the 2, and drawn, you would have had two pair to one pair and won the hand.

In chess, you know EXACTLY what possible outcomes exist, and you can, in theory, precisely compute the path through the state space (assuming your opponent is equally skilled and has equal memory and computational resources.) to the best possible solution. In games of chance such as poker, you simply cannot, no matter what computational resources you and your opponent have. That is the difference between a "game" and a computation.

Personally, I don't play either chess or poker. However, the whole wonder of true games theory is in analyzing games in which the very rules of the game prevent you from having perfect data. In the big blue room, you very rarely have perfect data.

Deep Thought

[Jedi Binglebop]

Deep Thought could beat Deep Fritz and Deep Blue with Marvin tied behind his back! (So there!)

-JB.

----
There is no .sig

It's not humanity on trial, it's the game of Chess

[Uggy]

Really all these exercises are just research into whether or not chess is a sophisticated version of Tic Tac Toe. As long as human's beat computers in chess the jury is out... on the game of chess not humanity.

As long as we think that chess==life then we're going to be upsetting ourselves needlessly. Computers outdo humans everyday in a wide variety of ways, but they still can't feed themselves, fix themselves, or reproduce without our help. Hell, they still need humans to actually move the chess pieces. Bah! that's not the chess I grew up with.

No, you took your hand off, that's a move. No I didn't, I was just testing. Cheater!!!! Mom!!!!

Re: moving the pieces

[Jeremiah]

Hell, they still need humans to actually move the chess pieces.

Um, no they don't. [slashdot.org]

Or, slightly lower tech [heartlandamerica.com]...

Deep Blue vs. Deep Fritz

[Skuto]

It's interesting that the programmer of Deep
Fritz (Franz Morsch) has been mouthing off that
his program is ready for Kramnik and should be
equal to Deep Blue.

They played in the Dutch Championships last year
and couldn't even manage to win. Now they're
saying they stand a chance vs the World Champion?
Well, if he goes too hard on vodka maybe.

This match is simply marketing. They know their
computer is going to lose, but unlike IBM, those
guys actually _sell_ their chesscomputers. And
many people are going to want the one that was
good enough to play the World Champion.
They even 'fixed' the qualifier for this event
so that only their programs played (Deep Fritz
and Deep Junior are both from the German ChessBase
company), nicely blocking out the computer World
Champion (Shredder), as well as blocking out most
other strong contenders (Crafty, Tiger, Rebel,
Hiarcs, Nimzo, Diep, etc...) on false grounds.

So, please don't say this match is anything like
Deep Blue - Kasparov. Fritz is significantly slower
and stupider, no matter what they would want you
to believe. This is in no way the best chess
computer to have ever existed.

Also, don't say this is the end of human
intelligence
if Kramnik loses. Not until a go program starts
beating me, at last :)

--
GCP

Re:Deep Blue vs. Deep Fritz

[Skuto]

>To be fair, ChessBase sells just about every
>world-class PC-based non-Chessmaster program
>available. The programs are written by
>independent and rival groups. It's like saying
>that the book review pool on /. is rigged by only
>including books that Amazon will sell you.

This is true, but there are some issues.

First, ChessBase has acquired Tiger and Shredder
(which would have been _the_ strongest contenders
for the Kramnik match) very recently, perhaps
after the qualifier even.

The Tiger team wasn't even contacted about the
match.

Secondly, ChessBase is marketing 'Fritz' mainly,
and the other programs are somewhat ignored. This
is because of brand recognition. It goes even as
far that Shredder for pocket PC will be called
'Pocket Fritz' just because 'Fritz' is more known.
Most people have never heard of the other programs
either.

And which of their programs ends up playing Kramnik? Right...

The qualifier even started with a 5-0 lead for
Deep Junior, when Fritz 'miracously' came back
and won on tiebreak. This stuff can happen in
comp-comp matches, but it's a very nice
'coincidence' for ChessBase allright.

>you can buy a program that plays at over 2600 ELO
>and run it at home.

There are free ones even (Crafty being the most
well-known, ChessBase even offers a crippled
version as a plugin engine for Fritz).

>I wish they'd said what hardware they were
>running the thing on...

8 CPU Pentium III 700Mhz was the last report.

--
GCP

More Coverage ...

[wiZd0m]

English links

• Official site for the match [brainsinbahrain.com]
• Brain Games network [braingames.net]
• CNN report [cnn.com]
• CBS News report [cbsnews.com]
• BBC News report [bbc.co.uk]
• The Times [thetimes.co.uk]
• Financial Times [ft.com]
• Daily Telegraph [lineone.net]
• Associated Press [yahoo.com]
• Reuters [yahoo.com]
• Britannica India [britannicaindia.com]
• International Herald Tribune [iht.com]

Other languages

• Netzeitung report [netzeitung.de] (German)
• Yahoo.de [yahoo.com] (German)
• ORF Futurezone [futurezone.orf.at] (German)
• Financial Times [www.ftd.de] (German)
• Chesslines survey [chesslines.com] (French)
• CNN en Español [cnnenespanol.com] (Spanish)
• CNN Italia [cnnitalia.it] (Italian)
• BBC Brasil [bbc.co.uk] (Portugese)
• Express [expressen.se] (Swedish)
• El Comercio Peru [elcomercioperu.com.pe] (Spanish

Links: How chess programs work

[mgarraha]

Here are some articles explaining computer chess beyond what they teach in undergraduate AI class.

• Paul Verhelst, Computer Chess Programming [xs4all.nl]. Includes many other links.
• T.A. Marsland, The Anatomy of Chess Programs [qmw.ac.uk]. International Computer Chess Association.
• A.N. Walker, Notes for a course [nott.ac.uk] at the University of Nottingham.
• Fox, Williams, and Messina. Chapter from a book [syr.edu] called Parallel Computing Works.

Sidenotes to the Deep Blue - Kasparov Match

[Anonymous Coward]

There have been 2 matches between Deep Blue and Kasparov, who was the strongest player in the world up until last year. Kasparov won the first one, and lost the second. There are however a few sidenotes that have to be made about the second match: - Kasparov wasn't allowed to analyse games of Deep Blue in advance, they were classified secret by IBM. This was very unfair, because the Deep Blue team had all games Kasparov has ever played in his professional career on file, and they used this in their preparation. This is very normal in chess, everybody prepares on his opponent. Kasparov could not, while Deep Blue could. - Deep Blue had very large opening and endgame databases. One could argue that they are part of the program, but it is not a very strong argument. Databases are not part of the program, it would be equivalent of Kasparov using opening books during the game. Obviously, Kasparov wasn't allowed to do this. I don't think this is entirely fair, the machine having at his disposal all opening theory in existance, every professional chess game ever played and every endgame ever analysed (we're talking about several hundreds of GB's here)... - Deep Blue wasn't a very good chess program, compared to other programs like Fritz, however it had a lot of power. And it had something else, it was designed completely to counter Kasparov's style, against any other opponent it would have played much weaker. This is, in my opinion, not entirely fair. If a chess program is superior to humans it should be superior to all humans, not to whatever human happens to be the best at that moment. - Furthermore, Kasparov simply isn't the best anti-computer player in the field. His playing style doesn't work very well on computers. Every human has another style, and I don't think Deep Blue would've been able to counter Karpov, for example, even though Karpov is obviously weaker than Kasparov. - Finally, all chess analists agreed that Kasparov played very poorly that match. They all agreed that he has played much better in the past.. All in all, I don't think computers were all that superior in 1997, and I think Kasparov would have had a big chance in a rematch, had it been fair (my first 2 points). However IBM had 'proven' a point and abandened the project... Of course, it's now 2001, so computers have become stronger. However Kramnik is not Kasparov, and I think the match will be pretty interesting....

Re:Sidenotes to the Deep Blue - Kasparov Match

[tmark]

All in all, I don't think computers were all that superior in 1997, and I think Kasparov would have had a big chance in a rematch, had it been fair

(Didn't the Deep Blue team get to tweak it between matches as well ? That seems like it would make the competition unfair too.

Re:Sidenotes to the Deep Blue - Kasparov Match

[gmarceau]

Your post is silly. You are badly trying to unprove something, but just what exactly I don't know. Deep blue is not human? Deep blue is not intelligent? Who exactly said so in such grand authority that you would need to debunk it that harshly?

In fact, I really don't know. Deep blue poked questions at our definition of intelligence. IBM did something, with massive media coverage for sure, and at the end of the day, coming up with a meaning for the event is up to you.

I will say you deserve to get yourself a book about the event. You are obviously interested yet you live with a number of misconceptions. The interesting meat of the Db vs Kasparov games were played in mid games, so the dbs weren't that important. Ibm trained Deep blue at various tournament before meeting with Kasparov and faired very very well, getting slowly better as they accumulated feedback from players. Reading about the team's competence and dedication convinced me Deep blue was running the best chess playing program there is.

To me, Deep blue success lie in the following quote by Kasparov, after the 2nd game of the rematch :

In Deep Blue's Game 2 we saw something that went well beyond our wildest expectations of how well a computer would be able to foresee the long-term positional consequences of its decisions. The machine refused to move to a position that had a decisive short-term advantage -- showing a very human sense of danger. I think this moment could mark a revolution in computer science that could earn IBM and the Deep Blue team a Nobel Prize

Puzzled by the style he saw in the 2nd match, in found hard to keep his concentration and didn't play as well. Thus the remaining games are not interesting nor important. It is Kasparov's quote that changed my perception of intelligence and ai. Maybe, just maybe, intelligence has more to do with brute force computational power that we though it did

It made me optimistic for the future of ai. There this age-old question in ai about the limit. Will we recreate intelligence, and if not, what will break first : our ability to build ever faster machines, or out ability to program them elegantly. Thanks to Ibm, the later is now less worrisome

Re:Sidenotes to the Deep Blue - Kasparov Match

[slaida1]

No. Yes. You're right but uploading a db of past games is no special feat. IBM didn't make a great chess program, they made at most a mediocre one with a big database of past games. Anyway, point is: IBM isn't playing fair. They sacked the project after they got what the wanted. The right thing to do would be to keep that project open and let other great chessplayers (humans and other chess programs) to try their skills against it too.

I got the feeling that Kasparov and his reputation was cheaply used to aid IBM's marketing . IBM is cheap but makes expensive products. Go figure.

There's still hope for us humans...

[Anonymous Coward]

As has been said already, Chess programming has very little to do with AI. The reason we get beat is that for most positions, there are only about 20 to 30 legal moves, and only a few of these are sensible, so brute force lookahead is possible.

To see how bad computers really are at strategic thinking, all you need to do is look at a game with a much higher branch factor (meaning more legal moves each turn).

One good example is the Chinese game of Go [britgo.org], which has an average of about 200 legal moves. Computers are absolutely dire at this game. Interestingly, one of the better Go playing programs is Free Software (GnuGo [gnu.org]). It still loses to half-decent humans though.

Kramnik will win if he forgets who he's playing

[kalifa]

For all the smoke and bluster, the main reason why Deep Blue beat Gasparov is simply that Gasparov played very poorly, I mean, amazingly poorly. For one reason or another, he was terrified and destabilized by the peculiar "personnality" of his opponent (playing chess against some sort of HAL is not the most comfortable situation one can imagine).

Had Deep Blue been a real human made of flesh and bone, there is no reason to think that he could have won playing the way it did.

2 to 1 Odds? Really?

[nanojath]

Timothy, if you're really willing to make book 2-1 in favor of the machine drop me a line, I might be interested in a gentleman's wager. Seriously, though - The reality is that to this day, machines have a fairly poor record against humans. We all assume that eventually they will be fast enough and able to think far enough ahead and be programmed up with enough sure -win scenarios from the thousands of recorded matches that they are essentially unbeatable - but the assumption many seem to be making that this point has come and gone is highly debatable, the Kasparov rematch notwithstanding. It's worth remembering that the majority of those games ended in a draw. It seems perhaps that the highest pinnacle of chess computing has mainly served to cancel the human advantage of creative nonlinear thought and reduce chess to a sort of rich man's tic tac toe.

And in the end its worth remembering that for now, at least, machines are still just intermediaries. Chess is not a strong AI problem, although playing like a human (as opposed to as well as/better than a human) might be. Kasparov wasn't just going against a machine, he was going against decades of IBM technological advancement, half a dozen engineers and an International Grandmaster (Joel Benjamin, part of the IBM development team). All told I think he did pretty well. But I'd bet in this match the CPU gets its clock cleaned.

Anyone who puts 2:1 odds on Fritz is a moron.

[Supercoz]

1) Kramnik is rated about 200 FIDE points higher than Fritz. Fritz played an equal match [all games drawn] with Dr. Robert Huebner of Germany [mid 2600 elo]. Kramnik is much stronger, and he has more energy due to being 40 years younger.

2) Anti computer techniques exist. Basically, computers have excellent tactical vision but poor strategic vision. So if I try to catch one with a knight fork, it won't work, but it will happily fall into a positional trap and lose 40 mores later. Most GMs don't bother to learn these because they would rather spend their time trying to beat other humans.

3) Kramnik's style is more suited to playing a machine than Kasparov's. Kasparov is mainly a tactical player. He wins by outcalculating his opponents. Kramnik is mainly a positional player. He wins by strangling people in the endgame. When he played Deep Blue, Kasparov tried to play positionally. It just wasn't his style.

4) Most GMs use Fritz as their computer analysis program, including Kramnik. He has a good feel for how the program works and can prepare opening surprises.

Don't get me wrong, computers are getting better and better at chess. Traditionally a program gains approximately 50 ELO points for every doubling in processor speed. Given that Fritz is approximately a 2600 program, that to convincingly beat Kramnik would require about a 2900 rating, and that processor speeds double about every 18 months, I predict that in another 10 years or so a PC may be able to give the world champion a run for his money. But not today.

Forecast: Kramnik 6.5;Fritz 3.5. Kramnik +3=7-0.

Why does anyone care?

[alexjohns]

Look, we're all geeks here. We understand computers. Chess can be won by pure computing power alone. A semi-good algorithm with enough speed to look 10 moves ahead - every possible combination - will win over a human being. Maybe it's 12 moves. Maybe 15. Doesn't matter. Enough cycles per second and you don't have to have a very good algorithm.

There are so many things we humans can do that we haven't even begun to figure out how to make computers able to do. True intelligence in computers is a long way off.

Me: "Hey, computer, last night at the club I was at, there was this really hot chick with red leather pants, get her number for me."
Computer: "There were 3 ladies with red leather pants at the club last night. Which one should I search for?"
Me: "The one with black hair, sitting at the bar, drinking some red slushy drink with two of those tiny little straws, looking like she wanted me real bad."
Computer: "Oh, that one. Not really your type, but I'll see what I can do."

Imagine what that computer has to be able to do. Scan through the video of the club; identify individual people; correlate the image from the video with images from other cameras; find out where she lives or works from that (likely work - less privacy there); somehow get from there to her phone number. (I don't know how - if you get here home address, you can just hack into a utility company's database. If at work, hack into their phone list. Get her name from an audio feed somewhere. Doesn't matter.)

That's the kind of things we should be working on. Because I really need that phone number.

Re:Why does anyone care?

[alexjohns]

Sorry, I was out yesterday.

My point was that chess is uninteresting (to me) because it's a problem that can be solved by speed alone. If you have a computer fast enough to look at all the possible moves, for 20 or 30 moves ahead, I believe the algorithms we have right now would beat any human player. Of course, at that point, you would have algorithmic improvements by testing one computer vs another.

There's a whole bunch of stuff that we haven't developed algorithms for. If we had a TeraHertz computer with an ExaByte of memory, you still wouldn't be able to do things like Natural Language recognition, analyzing a picture (or a video feed), intelligent AI that ferrets out all the info you want from the internet and filters out all the stuff you don't. Things like that. I don't think those kinds of things will come out of chess playing.

I created a simple chess playing algorithm years ago. Analyzed some others. If it's understandable to me, it ain't cutting edge research. I have a definition of art: If I can do it, it's not art. Mona Lisa, art. Ode to Joy, art. Blown up picture of a Campbell's soup can, not art. By the same reasoning, chess playing algorithm, not art. How to get a computer to understand what I'm saying, art. :)

This is all IMO, of course.

The Limits of Computers

[Kope]

Computer chess suffers many limitations that human beings do not. These limits are being extended, but they still exist and the human being in this match should not be counted out.

Many people think that since IBM's Deep Blue beat Kasparov that the debate has been settled that computers are better than people. However, there where some aspects of the way that match was played that gave the computer a decided advantage. Kasparov never got a chance to see any of Deep Blue's games. Kasparov never got a chance to play any warm up matches against Deep Blue. In otherwords, Kasparov went into the match "blind" as far as his opponent was concerned.

Deep Blue, on the other hand, had complete access to every professional game that Kasparov ever played, and a team of GM's working with the programmers to twink the machine to take advantages of weaknesses pin-pointed in Kasparov's games. In match play, preparation is the key to success. Against Deep Blue, Kasparov wasn't allowed to prepare.

This match is decidedly different. Kramnik has been given a copy of the program and the hardware to run it. He has been given time to analyze how the program plays and to see what weakness it has.

Moreover, Kramnik is a very positional player, whereas Kasparov was a very tactical player. Computers excel at complex tactics, even as good as Kasparov was, he can't out calculate a computer. However, that isn't the only way to play chess. Kramnik excels at finding positional improvements that will see their point well beyond the analysis horizon of the computer.

Kramnik has a very strong record against some of the best computers in the world. Including Fritz and Deep Junior - too offerings from the same company that makes Deep Fritz.

It is simply ignorance which would allow anyone to think that at this point in time the outcome of this match is a foregone conclussion. Certainly at some point in time the computers will be far better than people at Chess. But it is not the case that we are at that point today.

And for chess players and fans, this match promises to provide some very interesting games that will be well worth studying. And perhaps that aesthetic aspect is actually the point?!

Not unusual

[TheMidget]

> Of course, since he'll be snagging $800k for a draw, and $600k for a loss ...

This is nothing unusual. In many chess tournaments, even the loser still wins a sizeable amount of money. Consider it as a kind of gage to remunerate their willingness to participate (and to risk some of their prestige if losing).

Re:Not unusual

[stilwebm]

I knew I should have been a professional chess player. The fame. The glory. The money. None of those disabling injuries I get in professional football. Sure, the cheerleaders aren't as hot, but major media coverage should help me get women anyway.

Re:Not unusual

[Skuto]

I don't know where you got the statement that
Deep Fritz beat Deep Blue, but it's obviously
false given that Deep Blue never played anyone
but Kasparov.
There were single-chip versions of Deep Blue on
the web for a while, so it could be that they beat
such one. But its more than 400 times slower than
the full Deep Blue.
Also, the win vs. Kasparov was in a blitz game.
Computers have long been superior in those fast
games.

This is marketing people. Many here don't seem
to realize chess in multimillion business, and
lying is ok if it makes you sell better.

--
GCP

Re:Not unusual

[sailesh]

but it's obviously false given that Deep Blue never played anyone but Kasparov.

Not true. Plenty of people have played DeepBlue the program. In fact I've played it too .. although I'm only a recreational player ! I lasted about 15 moves ! :-)

Seriously, this was when I was a grad student and attended an IBM conference (CASCON'95). DeepBlue was an exhibit along with the research team. In the final day of the conference, DeepBlue played a top Canadian player and defeated him quite easily. Throughout the show, anyone could walk up to DeepBlue and play against it .. most people were quite apprehensive about it though. It had already beaten Kasparov in Philadelphia - the first game only. Kasparov bounced back .. this was Match 1. Apparently the 3rd game these guys misplaced the opening book and it still managed to do okay.

The difference between the DeepBlue I played was that it was on a stock RS/6000 machine (today's p-series e-Server). The beast that played Kasparov was a top of the line SP.

Re:Not unusual

[max_power26]

I got it from the Article. All I can find is that the original Fritz (running on a P90) beat the Deep Blue Prototype the year before it played Kasparov.

'By winning the championships Fritz demonstrated that chess knowledge was at least as important as computing power - Fritz was using one of the least powerful computers in the tournament (a standard Pentium 90MHz PC supplied by the Chinese University of Hong Kong)'

See: http://www.dcs.qmw.ac.uk/~icca/WCCC8/chess95.html Round 5 is DB vs. Fritz

Re:Not unusual

[Skuto]

>Deep Blue Prototype

That should have rung a bell. Windows ruled Linux 0.01 too.

--
GCP

Re:Not unusual

[Skuto]

>Not really, the "Power chess 98" engine drew
>DeepBlue.
>Ever heard of World Chess Computer Championships?

As has already been stated in another post, they
drew a PROTOTYPE.

--
GCP

Re:Not unusual

[astr0boy]

except in chess you dont get brain damage

It's inevitable

[Bjarke Roune]

Even if this guy should beat the computer, that should not lead anyone to having illusions about the future. Eventually, computer chess superiority will be a fact. Even though the program running on Deep Blue could beat Kasparov, that day is not today. The very fact that we are unsure whether Validimir Kramnik or the computer will win clearly proves this.

One reason that computers inevitably will beat us humans is that each year, computers get exponentially faster, which means the chess programs can search linearly deeper in the game search tree. It's simply a matter of waiting untill they are unbeatable.

However, that wait might be very long, but to top things over, algorithms are improving too. Some have thought in the past that our game-tree search algorithms were pretty close to optimal, but for example some of Aske Plaat's research [cs.vu.nl] clearly shows that this is far from the case, and that the old predictions about optimal performance was based on too simple and fundamentally unsound principles. Substantial improvements can be made. (not that I have anything to do with him. I don't know him and live in another country)

Even more important is the fact that we need not search the full search tree (indeed Deep Blue did not, using instead something called singular extensions). Rather, if we can make a heuristic that tells us which parts of the search tree are "interesting" we can skip the rest and only concentrate on those areas. In this way, computer chess is becoming a little more like human chess (though not much). The point is, as those "this part of the tree is interesting" heuristics get better, so will computer chess programs get better.

In short, the future of computer chess is bright, and we might have only seen the tip of the iceberg. Human superiority or even something resembling it simply will not last. Chess will neither be the first nor the last game where computers will always beat a human.

Re:It's inevitable

[Skuto]

>Even more important is the fact that we need not
>search the full search tree (indeed Deep Blue did
>not, using instead something called singular
>extensions).

Deep Blue did not search the full tree, but
singular extensions are a different beast.
Singular extensions let the computer search
_more_ than would be needed.

The idea was to detect horizon effects and avoid
them. The overhead for doing this is large, but
the DB team believed they had so much computing
power anyway that it was worth the tradeoff.

This tradeoff was made in some other places
as well, for example Deep Blue did not use
nullmove pruning, something which nearly
every program nowaways does as which can
prune away large parts of the tree relatively
safely.DB's team decided it wasn't worth the risk
with the computing power they had.

Deep Fritz uses it very aggressively and hence
can sometimes see just as far Deep Blue could,
but also makes more mistakes because of it.

PS. Aske Plaat's proposed improvements are not
used in any top program noawadays. They cause
troule with some of the other tricks in use and
the gain is not large enough to live with them.

--
GCP

Re:It's inevitable

[Bjarke Roune]

Deep Blue did not search the full tree, but singular extensions are a different beast. Singular extensions let the computer search _more_ than would be needed.

It is true that singular extensions extend the depth of the search. However, they have everything to do with Deep Blue not searching the full tree (as it would have been without singular extensions).

If you just use plain alpha-beta, you search as much as you can, perhaps using iterative deepening or some such. When you use singular extensions on top of that, you decrease the depth which you ask alpha-beta to search (this is important), and then you use singular extensions to extend the search beyound that point. So, compared to the tree you would have had if you had not used singular extensions, you are not searching all of it. Rather, you are only searching those parts of it which are deemed interesting by the heuristic that decides which search paths to extend. These interesting paths can then be searched even deeper than regular alpha-beta would do, which is the whole point.

Deep Fritz uses it very aggressively and hence can sometimes see just as far Deep Blue could, but also makes more mistakes because of it.

Null-move pruning is only dangerous in case you are in a zugzwang (or something like that) situation. That is, a situation where the best you could do would be to say "pass" and let the other guy have a second turn. These are exceedingly rare, I've been told, and that is also my experience. What is the last time you've wanted to say "pass" in a chess game? Of course, I might be mistaken. Do these situations occur more frequently in high-level chess matches than I think?

Aske Plaat's proposed improvements are not used in any top program noawadays. They cause troule with some of the other tricks in use and the gain is not large enough to live with them.

I didn't know that... but he did make it clear that current game-tree search algorithms are not optimal, and there is still room for substantial improvement, which was my point.

Re:It's inevitable

[Supercoz]

'Pass' states are called Zugzwang. They don't occur very often in the middlegame [aside from the famous Alekhine-Nimzowitch and Saemish-Nimzovitch], but they are quite common in the endgame. The simplest example is when one side is K+P vs K.

Example:
White King: e6
White Pawn: e5
Black King: e8

Now, with a 'pass move' black draws. All he has to do is sit there on the e8 square and white can never queen the pawn. But he has to move, which loses: 1...Kd8 2. Kf7 Kd7 c6+ and the white pawn queens.

Most chess programs only use the null move when there are several pieces left on the board; it is then fairly safe.

Re:It's inevitable

[snoozer20001]

I say create an AI, then let it figure out how to play chess. That's the only fair way to do it - that's what humans have to do.

Re:It's inevitable

[efuseekay]

No it's not. There are more possible chess games than all the atoms in the universe. In chess, it is a truism that the most complicated position is the initial position.

It's a fallacy to compare "my brain can compute # moves per second" vs the computer's ability to simply crunch.

The brain remember patterns, and can quickly intuit the kind of strategy to go about it. For example, if the position seems "closed", I aim for a strategic maneuvering game trying to obtain the upper hand by controlling squares or perhaps marshalling resources before a sudden opening of the position. I will spend very little time trying to look for tactics in such a position. Now a computer program that brutely analyzes the position by counting moves will have to go through an entire branch of variation that a human would simply won't think about. That's a sample of how intution works.

The thing about the 2nd game in the Kasparov vs DB match is that DB actually made a "positional" move that seemed almost human : it sacrifices a nice tactical combination for a longterm positional advantage. Old K couldn't believe it was the computer and alluded to some cheating by the DB team (very bad taste, but it was a huge compliment to the DB team).

So, waiting for the "exponential" (which is not true either) growth of computing power to play the "ultimate game" is not going to work.

Also, you ignore the fact the humans are becoming better players. The average grandmaster now can kick a lot of butts tof the previous generation. Why? Simply because a lot of theoretical (yes, they actually call them chess theory) development has occured. Some common chess themes that were vogue then are now considered bad or dubious. New ideas are overtaking the old. I grew up on the games of Fischer and Botvinnik, where the byword is clear-cut and simplicity. NOwadays, chess games are a complicated mess that I don't quite understand what's going on.

Disclaimer : I used to play lots of chess. Now I play once in a while on chess.net.

Machine loses....

[Anonymous Coward]

Hacked by Chinese!

I see Kramnik as a heavy favorite.

[hypermodernist]

I think we will see 2 wins by Kramnik and the rest will be draws. Kramnik is a very stable and player who doesn't usually sacrifice material or go into complications. Plus Kramnik's endgames are second to none in the world. Kramnik will use the same strategy that he used as black against Kasparov. Which was to go from the opening into the endgame. This is a huge disadvantage to the computer because they do not play endgames very well without very large table bases. Kramnik also has the advantage of studying several Deep Fritz games before the match. Kasparov did not have this luxury vs. Deep Blue. If he did have that would have made a big difference. But that isn't the only reason that Kasparov lost that match. He should have adopted a slow positional style similar to Karpov or Kramnik's. Of course I may be biased towards Kramnik because his favorite first move is 1. Nf3 :)

Vladimir had better not outwit himself like Gary

[TAFKA]

In his attempts to get Deep Blue "out of the book" Kasparov made some very twisted transpositions of standard openings, including the ridiculous looking rook pawn for opening move (or was it knight pawn .... same diff). The net result was that Gary outsmarted himself. Since opening play is the most analyzed aspect of the game, it would make more sense to save the variations for the early middle game.

Re:Humans has to win, right ?

[well_jung]

A human can very easilly come up with new ideas that has not yet been thought of

You presume that all of Chess has not already been thought of. The possibilties are not infinite. Sooner rather than later, the computer will be unbeatable @ Chess.

Re:Humans has to win, right ?

[alainygr]

You think everything always stays the same, do you believe that humans came on earth just like they are now? I don't (and I would say: of course).
We're the result of an evolution, I think it's just a matter of time, when humans will create something (will it still be called a computer?) which is more "intelligent".
Yeah, now brain is better than processor, you say "because brain can adapt to new situations", I agree with that, it seems also obvious, but obvious NOW.
Our will / mind is just the result of our life experience, our memory of it (situation-feeling), and some physical connections in the brain (brain is a physical thing, right?) and I think one day we will create something with an own will and mind, and maybe we won't even realize it because if this thing can think, it's going to realize that it should stay hidden to survive and wait till it is powerfull enought.
hmmmm.. and then the human creature won't be at the top of evolution anymore, but the machine.
-Alain-

Re:Humans has to win, right ?

[ianezz]

if this thing can think, it's going to realize that it should stay hidden to survive

If it wants to survive at all, of course.

I'd say that most (if not all?) life forms out there have some sort of survival instinct because, ehm... only the individuals (or group of individuals) that took care of surviving actually survived enough to reproduce themselves and transmit this characteristic to their descendands.

If we take an evolutionary approach, for each AI actualy willing to survive, there would be a lot of others not giving a dime on the subject, and the ones performing the selection would probably be human beings (at least in the earlier stages). Given this scenery, staying hidden is almost surely a bad move for an AI in order to stay alive.

OTOH, if you are able to tell an AI that it has to survive, you probably can also tell it to be kind towards other life forms... YMMV. :-)

Re:Humans has to win, right ?

[alainygr]

"OTOH, if you are able to tell an AI that it has to survive, you probably can also tell it to be kind towards other life forms..." Nice try, but in my opinion, surviving is not something you learn, it's part of what we call instinct. Do you think a machine will accept to be turned off if it has conscience that it might not be turned back on? I think that the fear of death is an instinct.

Re:Humans has to win, right ?

[johnnydeggplant]

I agree with you that survival is an instinct found in humans, and most of the rest of the animal kingdom for that matter, but I don't think that it is a neccessary method in the live class definition. The only reason that it seems that all animals have this instinct is that the lifeforms that we consider animals have gone through a long period of survival of the fittest (think back to when you first loaded windows 3.1 on your 286, it was longer than that!) It the animal didn't have survival instincts, it wouldn't survive because, so to say, it wasn't interested in surviving (much like my programming career after windoze XP secures its strangle hold on the internet.) It we preempt those years of evolution and create a machine that is 'intelligent', it wouldn't necessarilly contain the will to survive. Intelligence is only what you define it in that if we create something and label it 'intelligent' it's still what we created. For example, I have a Psy-Duck pokemon stuffed animal with an ISO 9000 certification pin in it's 'hair' and sometimes I see intelligence in its stoic approach to life. Well, that's my stuff, Dave

Re:Read up on your psychology. Man has no instinct

[dlkf]

Every creature on the Earth has instincts. . . every creature except for humans.

I see that you have never witnessed a human being born. Humans do have several instincts designed for survival. At the precise moment that a baby is born it cries. It does not learn to cry at this moment, it does it out of instinct so that it can inflate its lungs and breathe. Babies that do not cry when first born can have serious problems. Another instinct humans are born is to suckle. We do not show a baby how to do this, only where. Instinct tells them what to do from that point on.

These are two instincts humans have acquired so that when born, we can eat and breathe. Two skills necessary for survival. Modern hospitals have reduced the need for these instincts, but they are still with us. Im sure a good pediatrician could tell you of many other behavioral patterns all human babies are born with or surface as they age and you could try to argue that they are all learned, but no child learns how to cry or suckle.

As for your other statement that fear of death is learned, your examples only go to show that we learn what death is and what causes death, not that we learn to fear death itself. A child does not have a fear of drinking bleach because it doesnt know the effects of drinking bleach or the effects of falling out a window or down stairs.

Re:Humans has to win, right ?

[jarran]

It is a rather strange thought that the human mind can create something which is superior to itself

Why? After all, the human body has been used to construct machines that are physically superior for many years.

Re:Humans has to win, right ?

[Fred Ferrigno]

It is a rather strange thought that the human mind can create something which is superior to itself

Why? After all, the human body has been used to construct machines that are physically superior for many years.

My sentiments exactly. Humans created can openers, and they're a darned sight better at opening hard metal cans than I am.

Chess Rules Changes (Human vs. AI)

[wass]

I think a far more interesting 'battle of the brains' tournement between computer and human would involve something that as quite, but not entirely unlike, chess. I've spoken with some friends about this idea, and they agree.

Chess players have spent nearly their entire lives studying the way pieces move around the board, whether they realize it or not. They can see several moves into the future more easily than a chess novice with equal intuition. That said, I would be far more curious to see how a chess player would handle playing a different game. What I mean by this is change the rules of chess slightly, then allow 3 days for both computer programmers and human challenger to learn/recode the new rules and strategies.

Sample rules changes could involve knights moving orthogonally 2:2 instead of 2:1, or having a borderless board, where if you move off the left you come in on the right side (like Pacman), or marking a few squares as off-limits for the whole game, etc.

I think that some of these rather simple alterations of the rules would drastically alter subsequent gameplay. I also think that a chess novice would do roughly equally well in the various scenarios (albeit rather crappy in 'classical' chess). But more interestingly, how would the chess expert do? Would these new rules to him be like learning an entirely new game? Suddenly he wouldn't have the benefit of 20+ years of practice, and would have to 'see' things as they were for the first time.

I would be very interested to see how the great chess masters would do against computers in these situations. People often hype the human/AI chess games as battles to see whether computers are smarter than people. I think 'modified' chess would be a more interesting study. Do the great chess players really possess that much more wisdom and foresight, or is it some experience acquired by 20+ years of watching the pieces move.

I posted this idea on /. a few years ago, and I got some angry replies from chess players indicating that chess is all intuition and that rules changes wouldn't matter. Well, anybody care to find out?

Re:Chess Rules Changes (Human vs. AI)

[bruck]

Check out http://www.chessvariants.com There are hundreds of existing chess variants, some of which have their own competitions. Some were designed by chess GMs (Capablanca chess is one example). Some GMs like to play other games of the chess family, and play them well. Depending on the specific rules, some concepts remain the same, so 20+ years of experience do not go out the window once you change any 'ole rule. As to what it would to the AI, there's a commercial program called Zillions of Games http://www.zillions-of-games.com/ which plays a decent game of chess (I don't know how it would rate), with no book, no special knowledge of the game, no special tweaking for chess. The only thing the AI gets about chess, or about any of the other games it plays, is the rules. You can also write your own rules files, and many people have.

Re:Chess Rules Changes (Human vs. AI)

[CodingFrenzy]

A well known experiment from cognitive psychology is the following:

Novice and expert chess players are confronted with two types of chess setups and are asked to analyze the positions. Setup type 1 is an actually possible setup (e.g. can be reached by legal moves), while type 2 could never occur during the normal course of a game.

The novices do equally well for both setup types. Unexpectedly, the chess expert don't! While type 1 setups are analyzed very fast, the experts take approx as long to analyze the impossible setups (corrected for trained mind etc) as the novices.

A chess computer will probably behave as a novice in the above experiment (if the setup is not in the library), ie take the same analyzation time for both setup types.

Hence, this could lead to the conclusion that even a tiny adjustment in the rules could shift the odds heavily towards the computer, if these rules suddenly allow positions not possible previously.

Re:Chess Rules Changes (Human vs. AI)

[binney]

Not quite true. Master players are much faster and more acurate analysing random positions too. See here [ex.ac.uk] for example

Re:Chess Rules Changes (Human vs. AI)

[Anonymous Coward]

Interesting idea. Back when I was a senior in high school, playing chess caught on really big in my school. Everyone was playing it, even the football players. Anyway, we made up some new variations (some which helped the games go faster-- a necessary thing in the days of 50-minute free periods). Here are a couple of them:

1) No pawns: It makes a much quicker game, and maybe I didn't play it enough, but it didn't seem to matter who went first.

2) Only three pawns: And you can put them anywhere you want on your side of the board.

3) Secret King: The "King" is whatever piece you want it to be. Before the game, each player writes it down on a piece of paper and places it under the board. The catch to this version is that there are no "checks," per se. If your secret king is in check, you don't have to tell anyone. I kind of liked this version because it adds a sort of "poker face" aspect to it.

4) Bombs: Any _ pieces (we usually played with 2 or 3) are bombs. When they are taken, the other player loses piece that he just used to take that piece. This is done the same way as the secret king: each player writes down beforehand which pieces will be bombs.

I'm not sure how this could work with the your suggestion to use it in a match b/t computer and grand master, but I think some of them might be pretty cool. Either way, I'd be curious to see what other people think of our little way of relieving boredom during free periods.

Re:Chess Rules Changes (Human vs. AI)

[kraada]

There are already variations like this. Of note is Nightmare CHess (SJG), which is an almost MTG like adaptation to chess. Basicaly, you get 5 cards, and can play one before, or after either your move or your opponents, depending on what the card says. Cards say things like: Earthquake: rotate the board 90 degrees either clockwise or counterclockwise. Promote all appropriate pawns. Earthquake counts as your move. or New Tactics, which makes pawns move diagonally and capture forward. It's a crazy game. I've also personally seen a USCF Senior Master play against some of my friends, and whomp us all, proving that it isn't all luck . . . It'd sure be interesting to see a GM play it vs a computer :)

Re:Chess Rules Changes (Human vs. AI)

[BigGar']

There is a chess variant that was proposed by Bobby Fischer to eliminate the open book knowledege that top players and computers have. It's called Fischer Random Chess and it works by scrambling the arrangement of peices under the following rules, 1. must have opposite colored bishops & 2. one rook on either side of the king. Black and White have the same arrangement of peices & there is also some modifications to the castling rules. What this gives you is 960 possible starting positions and effectively eliminating opening theory and get's down to how well you play, not what you've memorized.

Re:Humans has to win, right ?

[joss]

> Every game that is possible has been played before.

Ignorance is bliss, how's it working out for you ? An average chess game is
50 moves (each) without about 20 possibilities on each move.
20^100 is a pretty big number. The proportion of games played to possible games is less than 1:number of atoms in known universe.
Being wrong by that order of magnitude is unusal even for /.

Re:Humans has to win, right ?

[A Big Gnu Thrush]

There are no new moves in chess.

This is a good poing, but you ruin it with:

Every game that is possible has been played before.

Chess is a finite game, but I think you're underestimating how big that finite area of 64 squares really is.

A sufficiently powerful computer will always beat a human opponent, but creativity is important for the human if he is to have a chance. As I understand it, great human chess players don't play like computers, they play like great human chess players.

Re:Humans has to win, right ?

[Kynde]

A sufficiently powerful computer will always beat a human opponent, but creativity is important for the human if he is to have a chance.

In the early days, say early 80s when the computers took their first steps in being proper opponent for good chess players humans those computers one by one by useing their lack of brute force and/or intuition against them. Boris Spasski whooped one computer beautyfully by sacrificing few king side pawns at point where even a moderate human chess player would've realized that by giving room to Spasski's rocks there'd be problems _in the horizon_. The opposing computer those days naturally couldn't predict that and Spasski indeed launched a glorious attack and won.

That was just a good example how humans usually play against computers. And this is also what Gasparov tried against Deep Blue but in vain. A nice example of where computers had gotten at that point was in one of the games, where Kasparov launched a really promising attack on the king side. It really was promising at that point and most likely any chess guru who was capable of spotting that offense opportunity would have seized it. BUT, at the decicive moment when deep blue had to decide wether to fall back and just try to minimize the damages or call the bluff it (DB) had calculated _every_ possible ending that attack could result in (and we're not talking about checking mates in 5 or 6, but serious amount of prediction) using nothing but brute force. Thus the Deeb Blue took the pawn Kasparov had sacraficed and dealth with the attack to a point where Kasparov gave up.

The throne of chess has been lost for good. There's little reason to suspect that Deep Fritz would loose unless it's significantly slower (or it runs M$ software) than Deep Blue. Garri Kasparov was by far good enough to represent our kind...

(every little detail in this comment may not be 100% accurate as I can't be arsed to check the references right now, but it's by far close enough)

-

Re:Humans has to win, right ?

[jeremyp]

Actually, the BBC article on the subject a couple of days ago stated that there was every possibility that Deep Fritz *is* a weaker player than Deep Blue and it's probable that Kramnik is a stronger player than Kasparov (he beat Kasparov after all).

Re:Humans has to win, right ?

[boaworm]

Every game that is possible has been played before.
Chess is a finite game...

What's this ? Ever played a game of chess? Sure it is true that there's a finite number of squares, and for SOME of the pieces, there's a limited amount of games to play, like the peasants.
But think a bit more... all those pieces that can move forth and back again. They OBVIOUSLY creates an INFINITE amount of games, since they can move around and around and around.

Re:Humans has to win, right ?

[pmc]

But think a bit more... all those pieces that can move forth and back again. They OBVIOUSLY creates an INFINITE amount of games, since they can move around and around and around.

A game is a draw is there have been no pawn moves and no captures for 50 moves each (except in special conditions). As pawns can only move forward there is a finite number of moves until all pawns must reach the eighth rank, at which point the game must end in fifty moves, or a piece must be taken. Then the maximum length of the game is (maximum number of pawn moves until last pawn reaches eighth rank * 50) + (50 * number of non-kings after last pawn is promoted).

The special condition mentioned above is where the game can go beyond 50 moves if there is known to be a forced win - King, Rook, and Bishop vs King and Two Knights can go on for 223 moves between captures.

Another way of looking at it is that there are only a finite number of legal chess positions. If any of these appear three times in one game then it is a draw (if you slightly generalise position to include potential moves from that position - pieces can be in the same position of the chess board but have different legal moves: en passant and castling are the two exmaples where this happens).

Re:Humans has to win, right ?

[Erasmus Darwin]

They OBVIOUSLY creates an INFINITE amount of games, since they can move around and around and around.

Under the F.I.D.E. laws [chessvariants.com] (I dunno how official this is, since I'm not a chess person -- it seems to be "official" chess, according to the site), rule 10.10 states that it's a draw when the chess board repeats its state for the 3rd time. There are OBVIOUSLY a FINITE number of chess board states (placing a finite number of pieces on a finite number of squares, plus a few extra bits to represent piece "rights" such as castling and en passant stuff). Therefore, sooner or later, a chess game will either end "normally" or run out of states that haven't been hit twice.

Computers can't play Backgammon.

[ratzmilk]

Any more then a computer can play poker. And I'm not talking about playing for matches.

Backgammon, like poker, is a gambling game. It makes a very big difference when it is your hard earned bucks on the table.

When you play Backgammon properly (for money), it almost never plays out to the end.

Not Exactly True

[evolspit]

The article states that Deep Fritz is aware of over 2,000 opening stategies, but I think that gives a convservative idea of its prowess. You see, in addition to the tome of recognized openings, defenses, mainlines and variations, Fritz is aware of past games where deviations proved a winning choice.

Picture a tree where move 9 might have 3 possible follow-ups (9a thru 9c) ... 9a leads to a situation where there are 2 respectable follow-ups, ad infinitum.

It is very difficult to have all these previous developments memorized (although the world champions probably know thousands). The computer has no trouble at all analyzing all of this data.

In closing, I picked up a game [bkchess.com] that uses the Fritz engine a while back and it owned my ass.

In a manner of speaking, I suppose...

[kabir]

Consider this, though: Supposing I know rules of chess, and am a decent player by the "livingroom" standard, but not really someone who could compete at much of any level. But I do understand the (finite) rules well, and I do have some concept of what it means to win or lose, and the relative value of the pieces. Since a computer is (inherently) a state machine, and a fast one at that, I could simply program it with the ability to consider many, many possible lines of play, to some arbitrary depth, and then compare the results of those hypothetical situations. What you'd end up with is a tree of possibilities, some branches of which would contain more "good" than "bad" situations. The program would be intstucted to select the branch with the most favourable overall evaluation, and in all likelyhood it could kick my butt every time (the "deeper" it considers, the more my butt gets kicked...). While this could certainly be computationally intensive, I don't think it's much that the average PC couldn't handle at a relatively shallow "lookahead" depth, and a big multiprocessor machine could certainly take the concept much furthur.

As it is, I think that what I have described is, roughly, how home PC chess programs work. Of course there has been some tweaking and refining, and probably a hell of a lot of precalculation of common scenarios on the home PC products - so that it's nice and fast and doesn't need a Cray. I'm not sure how Deep Fritz works, but I'm fairly certain it does something similar on some level (Hence the name?).

The advantage that computers tend to have over people in this kind of thing should be pretty obvious: most people can't accuratly remember that much stuff! Naturally, human creativity makes a big difference, as does talent and experience, but the computer being able to consider so many options so quickly and accurately makes up for a lot, and should allow it to surpass it's creators fairly easily (unless it's creators are Grand Masters!).

Not necessarily (includes explanation)...

[Richard Bannister]

Most computers play chess by looking ahead at the consequences of whatever moves are made. Depending on how fast the computer is, huge numbers of possibilities can be checked.

In many cases this is augmented by a database of opening sequences, which is used to give the computer a head start, so to speak.

The computer algorithm works out, for example, what is likely to happen 5 or 6 moves from now if it should move a piece to a certain place. It runs through all possible moves, looking at each one and the likely consequences of it, before deciding exactly what move to execute.

No human can possibly consider anything like the number of moves a computer can, but a truly excellent player stands a chance because look ahead methods are far from flawless.

Re:But...

[klmth]

Not quite. They programmed Deep Blue, for example, by feeding it's heuristical engine with data from thousands of previous games. This data, together with the learning ability of the machine and the raw computation power yields to a chess computer far more effective than the people who programmed it. Not that it neccessarily is any better than a human being: Deep Blue didn't win every game against Kasparov, it merely won more games in the turney.

Re:But...

[NonSequor]

Nope, you got it wrong. Deep Thought was the supercomputer used to find the answer to the question of life, the universe, and everything in the Hitchhiker's Guide to the Galaxy. Deep Blue was IBM's first attempt at beating Kasparov. The second attempt was Deeper Blue. IBM was assisted by one of Kasparov's rivals when tuning Deeper Blue. It was basically tuned with the assumption that it would be playing Kasparov and so many people think that a different grandmaster could have beaten it.

Re:But...

[ethereal]

Actually, I think that's right. A computer will only follow mathematical theories programmed into it. It may follow them faster and in greater depth than its human creators, thus coming to some insights that humans aren't persistent or long-lived enough to reach, but there is no qualitative difference in mathematical ability since the computer can't make new theories and extend the boundaries of mathematics.

I could see how in the future a computer could somehow be programmed to make guesses and "intuitive" leaps that would end up defining new mathematical theorems, and then use those theorems to explain certain gaps in our knowledge and create new mathematical knowledge that human mathematicians could not have approached. I don't think this has been done yet, though.

Doug Lenat's AM found theorems

[yerricde]

the computer can't make new theories and extend the boundaries of mathematics. I could see how in the future a computer could somehow be programmed to make guesses and "intuitive" leaps that would end up defining new mathematical theorems

Your "future" is past. Doug Lenat wrote an automated mathematician [google.com] that could discover and propose interesting mathematical conjectures. Starting from simple set theory, AM discovered arithmetic, prime numbers, Goldbach's conjecture, and a new area of number theory: maximally divisible numbers.

Re:But...

[Mahonrimoriancumer]

Then why hasn't a computer been able to beat humans consistenly?

Until a computer is able to consistently beat oppenents in tournaments, it will not be better than humans.

Re:Deep Blue 2?

[Jedi Binglebop]

I have had this very same argument with a friend of mine. Computers, unbeknownst to some, have no intelligence. Essentially, even with a perfect map of how to win every chess game in every situation - which is not possible in any case, there being always "two" players, not just one - but even if there was such a map, the computer which has no intilligence could not cope with the concept of merely picking the best fit.

Also consider, there is never only one path to take to gain a win. There are always choices. A computer can't choose, it can only calculate (ie compute). A programmer can direct the computer to calculate in such a way that a desirable outcome may be possible, but there is never (ever) going to be 100% certainty that a machine with a perfect set of calculations is going to defeat a human player every time (chess is not a trivial game/problem. You cannot approach it from a trivial perspective).

Deep Blue won iirc 3 our of the 6 games played, and drew 1 (in the rematch) so it was not a one game one win situation. After the rematch (in 1996 iirc) Deep Blue was dismantled. However Gary Kasparov had some queries to IBM about two fo the games in the match - he felt there had been some human intervention. Deep Blue's victory was not "grand" in any sense other than as a marketing stunt for IBM.

-JB.

Re:Deep Blue 2?

[psycho_tinman]

You are making a comparison between brute force computation and heuristics/algorithmic analysis.. What you describe can't happen.

In chess, certain segments of the game are fairly stylized. Take for example, openings, which have been researched, analyzed and can generally be committed to memory. Take also end games, which are more or less set pieces where a result can be determined. Most chess playing computers actually store only the openings, and end game positions. To store every possible move is impossible. This is where the algorithmic analysis/heuristics/AI capability comes in. Using some algorithm like alpha-beta minimax, a computer operates the same way we do, by pruning the decision tree until an optimal move can be found.

The advantage for humans is that there are some moves and positions that we can reject automatically, through experience. The advantage for the computer is that even though it cannot reject such obviously flawed moves without consideration, it can actually compute (and consider) more branches of the decision tree than humans (faster calculations)..

A computer will eventually dominate a human player in Chess. But maybe not just yet..

Re:Not a chance

[Kintanon]

In chess, there are 16 pieces per side. This means there are 16*16 possible combinations of first move (for each side). Assuming you are storing chess moves in 2 bytes (possible, but compact - given no index space is given here), that's 512 bytes for the first move. when you get to the second move, though, you hit 16*16*16*16 possibilities. Suddenly, that's 131072 bytes - 128K. For each additional move, using these raw calculations, you need 256 times more space.

The problem with that supposition is that it is false. There are not 16*16 legal moves in the first move of a game. There are 20. There are also 20 on the second move, however there can be a possible of somewhere around 40 on the 3rd and 4th moves. The number of legal moves goes up rapidly towards the mid game, then begins to decline again towards the end game as pieces are removed or trapped.
So yes, while there are theoretically 16x16 first moves, only 20 of those are legal moves. The rest can be discarded. That means there are 20 branches to explore, in each of those 20 branches there are varying numbers of continued paths, certain opening moves result in there being 19 moves available on the second move, others result in there being 38.
Most of this is probably irrelevant to the point though, I've only had 3.5 hours of sleep and I'm a little woozy, but I was getting somewhere with this... Oh yeah!
Say there are 1 billion relevant chess matches to store, that would be those chess matches where the moves conform to the standards of a master chess player, that means you can throw out all of the games where the person just systematically moves their pawns up 1 space each turn from left to right, and stuff like that. Anyway, 1 billion chess matches, stored in 40 bytes per match would be 40gb, That's 320 bits, so 256 bits to store moves in and then 64 bits to store a key in to define the notation. I think that could be done...
So while you may not be able to store EVERY chess game in 40gb, you can certainly store every relevant chess game in 40gb...

Kintanon

Re:Not a chance

[k8to]

There are more valid chess positions than there are atoms in the known universe.

If you need me to find the calculations I can.

A complete chess database is not possible.

Perhaps a complete *enough* database is possible,
where responses to all moves are known
which are winning.. However, I'm not sure
how you'd ARRIVE at such a tree without a
complete exploration.

Re:Not a chance

[Kintanon]

First of all the selection process doesn't have to be done real time while playing, so it's no big deal to have the machine searching all of the possible branches for 6 months prior to the match to get as many as possible preconfigged and discard all of the paths that result in a loss for the machine. It seems like that would be the best choice, just discard any route that would result in a loss for the machine.

Kintanon

Re:Not a chance

[TheMidget]

Oh great! That means that now you can store five moves rather than four... Indeed, storage need increases exponentially with number of moves.

Re:alice

[it's a culture thing]

which king would bill gates be then? and could we chop off his head?

Re:Artificial Intelligence too advanced

[it's a culture thing]

The concept of computers becoming "smart" is a bit vague. While accepting that modern computers may appear smarter than their predecessors they aren't. Its just that as processor speeds increase more instructions can be done in a finite period of time and therefore the program can evaluate more information/possibility combinations making you think its smarter. The IBM machine which beat the Grand Master had been programmed with the assistance of 10 other grand masters to look for certain combinations which would lead to victory so it wasnt just evaluating every possibility but only those likely to result in a win.

As to taking away peoples jobs of course computers will. Most jobs are boring, dull and totally pointless. Would you want to spend your entire career screwing nuts onto wheels in some car manufacturing plant or actually designing the next generation of cars while a robot did the dull stuff?

Strange though it may seem, everytime computers take away jobs people become better trained and get to do things which they wouldn't have otherwise. Look at the increases in higher education in the past few decades, the improvements in the standard of living for the majority of people, would you give it up for dumber computers?

And in answer to your final question: The world is becoming more complex. Fun isn't it? 8)