Chess: Computers vs. Humans

[Bubba Ray]

Has a computer ever beaten a human Chessmaster (I'm thinking of people like Karparov and Karpov, not some braindead one like me who has never even managed to beat his C64;)), in a series of games.

[Johnny Angel]

Yes. But so what?

They played it up like a big deal when Kasparov got beat by Big Blue a couple of years ago, as though this meant that computers were suddenly smarter than people. Computers crunch through algorithms better than people, and there's nothing particularly intelligent about being able to do so. We've been accustomed to overrate the intelligence it takes to play chess for centuries, and I think what we're finally finding out is that it's a game so stupid, a computer can beat it.

[sailor]

I disagree. Playing chess is not only a matter of computing thousands or millions of moves, it is a matter of trying higher level strategies, of weeding out moves that lead nowhere and pursuing paths that look promising. It was *very* difficult for IBM to build a computer that could beat the human masters and they had to do it by using more than brute force.

[jcgmoi]

sailor and Johnny Angel:

You're both right. Deep Blue could generate around 200 million positions per second, if memory serves. But programmers built in plenty of expert knowledge so DB could evaluate those positions under time constraints of an actual game. A great achievement for IBM coders but I think a bigger one for those who wired up the circuits.

[Ashtar]

I for one am going to start planning for the day when the Cyber-insurrection arrives! Those programmers are going to be the first against the wall when the revolution comes! It'll be just like the board game 'Paranoia'!



-Ashley (Who will be spared the assimilation when he devotes his service to the Computer. The Computer is your friend. Do you trust Friend Computer?)

[Chronos]

Also, it's important to note that even though Deep Blue beat Kasparov, Kasparov is still considered the better player. Most analysts say that Kasparov was just having a bad week, that week (that happens to humans, sometimes), and further, the match (sponsored by IBM) was set to a very grueling schedule, tiring to a human. The consensus is that, had K been playing up to his usual standards, he would have beaten the computer, and he's agreed to a rematch at any time, provided that it's sponsored by a neutral third party (i.e., not IBM). So far, no sponsors have stepped forward.

[LazarusLong42]

Ashtar:

Happiness is mandatory. Are you happy?

:)

LL

[malaka]

Any WAGs on what would happen if Big Blue were to play...Big Blue in chess? A draw?

[AWB]

Originally posted by malaka
Any WAGs on what would happen if Big Blue were to play...Big Blue in chess? A draw?


In college, my roommate and I used to play our different computers at Othello (Reversi). The software was different as well.

We would set them at various levels and start one first. IIRC, one of them beat the other on most level settings if the levels were set the same (1-8) and it went first. Mixed results if the other went first. Also IIRC, if one was set at one higher level, it would almost always beat the other. (Variation of strategy, I imagine.) But of course, for any particular level settings and first moves, the outcome was the same. The games had no randomizer for starting the game. Even if they did, there're only 4 opening moves in Othello, so the results would probably just be mirror/flipped results.

[barbitu8]

Most of the top chess players have been either mathematicians or engineers. I think there is a correlation between those vocations or interests or aptitudes (whatever) and chess. Both require the ability to envision spatial relationships not actually presently existing.

In so far as persons with those aptitudes are also intelligent, there certainly is a correlation between chess and intelligence. However, Robert Fischer was and is an idiot (idiot savant, if you will). He is also insane, a paranoid schizophrenic. Many great chess players have gone insane. I wonder about that correlation.

[MadHatter]

I thought that Kasparov did actually beat Deep Blue, he just didn't win the series. He won 1 or 2 games I think but DB won more. Is this correct?

[barbitu8]

Originally posted by MadHatter
I thought that Kasparov did actually beat Deep Blue, he just didn't win the series. He won 1 or 2 games I think but DB won more. Is this correct?

Yes, you are correct. Kasparav won some of the games, but did not win the match. However, as pointed out, he was off during the match, lost some games he should have drawn or even won, and overlooked things he normally doesn't.

[hawthorne]

IIRC Kasparov was also criticised for failing to exploit the machine's weaknesses. Although much better than common programmes the top level ones still look for obvious advantages like "in three moves I can win a pawn". The way the top players beat them is to get involved in a deep subtle middlegame and exploit the machine's lack of positional "feel".

picmr

[labdude]

Also, Deep Blue was specifically programmed to beat Kasparov. The programmers had inserted many Kasparov games into deep blue's memory. There was an article in Slate mag about this around the time it occured. (if you want to search for it)

[bpaulsen]

I spent my senior project in college writing a chess program, so I hope I have some idea of what I'm talking about...

1) Chess skill = intelligence? No, obviously this is not true. However, when computer scientists first started talking about artificial intelligence, one of the goals was to build a computer that could beat a player at chess. This was, at the time, viewed as a reasonably complex game that required some native intelligence to play. Also, the number of permuations of positions was viewed to be overwhelming to just crunch through. Of course, at the time, they didn't have a gigahertz pentium chip just sitting around.

2) A computer's chess skill is almost directly proportional to processing power. Big Blue's hardware was built specifically for playing chess and therefore could compute positions many, many times faster than a general processor could. IIRC, the best computer's chess rating has gone up almost linearly since computers have started playing. I know that some early predictions were made on when a computer would beat the world champion and I wouldn't be surprised if the predictions were off by only a year or two.

3) Kasparov is the better player? That may have been true at the time. However, I'll assume that development on Big Blue has waned a bit (what's the point anymore?) and they haven't worked on building an even faster Big Blue. If they had, Big Blue would probably have a chess rating of about 200 points more than Kasparov. Under the formulas that FIDE uses, this means that Big Blue would probably win about 3 out of 4 games.

4) Big Blue was programmed to specifically beat Kasparov? While there were probably openings programmed in for Kasparov, I think it's somewhat obvious that Big Blue could beat any player you threw at it.

5) Kasparov didn't take advantage of Big Blue's weaknesses? Possibly when he first played, but not after the first loss. The types of mistakes that you mention occur when playing the crappy computers that we have on our PC's. Suffice it to say that a computer with over a 3000 rating isn't making too many positional mistakes. Let's remember that this rating was derived by playing actual people (and other computers that played actual people) It seems difficult for me to believe that every person involved didn't try to exploit the computer's "weakness."

Finally, I agree that beating the world champion amounts to "so what?" It's pretty easy to show that the more positions a computer can evaluate in a given time, the better it's going to be. All Big Blue did was throw the monster of all computers at a chess board and let it do it's thing.

What I think will be interesting is that in about ten years, you will probably be able to buy a program for your computer that will also beat Kasparov.

[Whack-a-Mole]

BPaulsen wrote:
Big Blue was programmed to specifically beat Kasparov? While there were probably openings programmed in for Kasparov, I think it's somewhat obvious that Big Blue could beat any player you threw at it.

I don't think this is obvious at all. At least not if the players you are throwing at the machine are also Grandmaster caliber players.

Just like in football (or any sport) players study their opponents past games to see what they do. Remember, when Kasparov lost to Big Blue it was a re-match. A year or so earlier Kasparov beat Big Blue. IBM then hired some high-powered chess players to consult on the re-programming of Big Blue. The result was a program specifically geared to play Kasparov. I do not think it is by any means certain that another player could automatically expect to lose. In fact, at that level of play, I'd expect Big Blue to lose to any other grandmaster chess player.

As for number crunching IIRC there are 12 billion possible board combinations after the first ten moves (by both sides) in chess. Even for Big Blue this is a monumental task (it has to evaluate each move for desirability as well). If the machine expects to play a Grand Master under time constraints the chess algorithm is at least as imporatant as the hardware it runs on.

[bpaulsen]

My memory on this is at least a few years old...

In general, a chess computer can be broken down into 2 parts:

1) Move generation. In other words, crank out every possible combination of moves.

2) Position calculation. In other words, after step 1 is done, take all of those positions, score them, and then select the move that gives you the best score.

Now, alpha-beta pruning of the position tree cuts down the number of positions that you have to generate by a LARGE factor - this is what makes it possible for a computer such as Big Blue to look 10+ moves ahead.

What was special about Big Blue was that they had processors that were geared specifically to taking a position (that was generated by other processors) and score them. And, they had a bunch of these processors so that everything could run in parallel. This is where they got the huge speed improvement.

As far as the algorithm (for scoring purposes) being important, it is. However, it's not the primary factor - speed is. If I have a computer that can look 12 moves ahead, and you have one that can only look 5 moves ahead, I'm probably going to win every game even with the most basic scoring algorithm. Plus, the studies have shown that the skill of a machine is almost directly correlated to its speed. Granted, a faster machine probably means that you can use a more sophisticated scoring algorithm...

As far as Big Blue not being able to beat any other grandmaster, I just think that's absurd. First, Big Blue won the right to play Kasparov by beating many other grandmasters. Second, are you trying to convince me that Kasparov is so set in his style of play that he couldn't change it one iota? After all, if it was so geared to beat only Kasparov, surely if he deviated from "standard Kasparov" he would've been able to beat Big Blue, right?

You are correct about the huge number of moves available at the beginning of the game and this is why virtually every chess computer has a giant book of standard (and non-standard) openings stored in memory so that it doesn't have to wade through those computations. Yes, you can deviate from those standards, but you would do so at your peril, since usually deviations from them are sub-optimal plays.

Brian

[barbitu8]

Originally posted by bpaulsen
My memory on this is at least a few years old...

You are correct about the huge number of moves available at the beginning of the game and this is why virtually every chess computer has a giant book of standard (and non-standard) openings stored in memory so that it doesn't have to wade through those computations. Yes, you can deviate from those standards, but you would do so at your peril, since usually deviations from them are sub-optimal plays.

Brian

Actually, new "theoretical novelties" are being discovered all the time by the GM's. That's why you cannot rely upon an opening book that is dated, and that is why there is a volume put out every year by a Yugoslavia company devoted to recent games and noting new moves. New in Chess does something similar.

And chess masters who play computers try to make moves that would tend to "befuddle" computers. Since a machine lacks instinct, it will compute the variations flowing from the move, but in doing so it will discount variations at the outset which appear unfavorable to it, based upon its early mathematical count. That's what these masters rely upon.

[panamajack]

There are computer vs. computer Chess tournaments. I don't know if Deep Blue has entered any, it wasn't originally designed for that but could probably be modified. Sometimes the programs that do very well in those tournaments are notoriously weak against human opponents.

[hijack]
On the subject of computers playing old strategy games, does anyone know if computer programs work well enough to beat good human players in similar games (like Shogi, or better yet, Go)?

Shogi is a Japanese game very much like Chess, on a 9x9 board, with the important addition that when you capture a piece, you hold it and can put it back into play on your side. This makes it difficult to search ahead more than a few moves; also the game doesn't really speed up since there aren't fewer and fewer pieces on the board. Even I can beat GNUshogi (based, unfortunately, mostly on GNUCHess) about half the time. I'm sure there are better versions out there somewhere.

Go would seem to be a challenge just to program a game that could play sensibly, let alone beat good human players.

panama jack

________________

http://www.coolsig.com -- look for one about chess, or computer programming, or something. I'm too lazy to do it.

[bpaulsen]

Actually, new "theoretical novelties" are being discovered all the time by the GM's. That's why you cannot rely upon an opening book that is dated, and that is why there is a volume put out every year by a Yugoslavia company devoted to recent games and noting new moves. New in Chess does something similar.

Let's not forget that the computer helps the GM come up with these new novelties...

And chess masters who play computers try to make moves that would tend to "befuddle" computers. Since a machine lacks instinct, it will compute the variations flowing from the move, but in doing so it will discount variations at the outset which appear unfavorable to it, based upon its early mathematical count. That's what these masters rely upon.

Maybe that's why some masters lose to inferior machines. It's been shown that the best plan of attack for the computer is to generate positions as far out as it can (and the exact number of moves depends on the speed of the computer) and then score those positions. It doesn't score intermediate positions, because if it did, it would never get a chance to see if sacrifices worked.

Basically, making unorthodox moves to "confuse" the computer usually backfire.

Humans have the advantage in two areas:
1) Pruning. A human can look many, many moves deep into a line that he/she finds interesting and disregard the others. The computer has to go through all of those other combinations. Now, alpha-beta pruning cuts out a lot of the positions that a computer has to generate, but there's still a ton left over.

Why is this an advantage? Well, if the computer can only look 5 moves deep, and you offer a sacrifice that results in checkmate in 6 moves, the computer will think it has the advantage after those 5 moves and happily take the sacrifice. Of course, if it could only recognize that it should look one move deeper.... The answer that has worked for chess programmers has been to build a faster machine that can look 6 moves deep. The ones that try to stop some lines early have nearly always failed.

2) Positional instinct. Basically, if you aren't swapping pieces and finding tactical holes to exploit, the computer has a hard time at trying to find the right move. This is because the effects of good positional play might manifest itself after 10-15 moves. For the most part, this is outside the realm of most ordinary computers.

Brian

[bpaulsen]

Go would seem to be a challenge just to program a game that could play sensibly, let alone beat good human players.

Last I read (and this was within the last year) there isn't a computer that can play a good game of Go yet.

Checkers computers, however, can pretty much always beat human players. AFAIK, there is only one human who can beat the best checkers computers, and that may not even be true anymore.

Brian

[DSYoungEsq]

Chess is a game with a finite number of moves. Given sufficient computational power, a computer will eventually 'solve' chess, that is, compute what the inevitable result is of all possible move combinations, determining once and for all whether White, moving first, obtains sufficient advantage to guarantee a win.

At present, no computer can manage this, nor do they attempt to do so in computer versus human games.

[Chronos]

Last I heard, the best Go programs could reliably beat human players... Provided those players were six years old, or so. Meanwhile, the top checkers computer is so good that it has to be given its opening move randomly for there to be any chance of a human beating it (at least, if the computer moves first).

Absolutely solving chess is impossible for any computer as we now know them (it's one of those things that even with a thousand times the computing power of the entire world would still take many times longer than the lifetime of the Universe), but it may actually be possible for a quantum computer, when those are sufficiently developed.

[kunilou]

Many, many years ago, Dad Kunilou had worked his way up to the rank of "Master" in chess (a skill he could not pass along to me, alas) and he used to pick up a few bucks by playing exhibitions.

He once played the West Point chess club. He beat the instructors, but lost to the students. His explanation? The instructors were playing by-the-book games which he was familiar with and well-prepared for. The students, on the other hand, threw all sorts of unconventional openings and tactics at him, catching him off guard.

He died before Kasparov and Big Blue, but his opinion of computerized chess before that was, it's fine for keeping your skills sharp, but there's no competition like a really good human player.

[Bubba Ray]

First: Thanks for all the replies!

Second: Can anyone provide to me an explanation what happened as Deep Blue beat Kasparov. (Not play by play of course, but something on the line of how many games and who won, draw?)

[bpaulsen]

Try the following:
http://www.siam.org/siamnews/bookrevs/chesside.htm

[Bubba Ray]

Thanks that is just what i've been looking for

[bpaulsen]

Another one (even better) is http://www.cs.vu.nl/~aske/db.html

Or better yet, go to http://www.yahoo.com and type "Big Blue Kasparov" and it will give you what you are looking for.

[astro]

Originally posted by barbitu8
However, Robert Fischer was and is an idiot (idiot savant, if you will). He is also insane, a paranoid schizophrenic. Many great chess players have gone insane. I wonder about that correlation.

I remember Fischer was considered a surly oddball 10-20 years ago but I didn't realize he had gone totally bonkers. Is he institutionalized? What happened?

[barbitu8]

He's not institutionalized, but living in a country in which Americans have been forbidden to go.

He's more than an "oddball." Remember his last official match, when he won the crown? He accused the Russians of all sorts of psychic maneuvers. He almost did not even show up due to his paranoia. It took a lot of coaxing from members of the USCF to get him to play in the first place. He hasn't played since officially and some of his ressons have merit, but some don't.

Besides the chess aspect, he has accused the Jews - Nazi-like - of being responsible for the world's woes. After he won the Title, he moved to California and lived like a Bohemian, altho he was rich, winning all that money, and never played in another official match or tournament. A match recently was being arranged in Yugoslavia, but it fell through; however, Fischer has remained there.

I say he's a paranoid schizophrenic due to his life-long views, statements, and activities. I don't think I'm over-reacting or exaggerting. Altho I'm not a psychologist or psychiatrist, it is obvious to even a layperson that that is what he is.

[hawthorne]

Besides the chess aspect, he has accused the Jews - Nazi-like - of being responsible for the world's woes. This is a good enough sign of insanity normally, but Fischer is himself Jewish.

[barbitu8]

Wrong. Fischer is not Jewish, except insofar as he was born Jewish. However, he converted to some other religion, the name of which escapes me, but is one of those fanatic religions.

[DRY]

Originally posted by barbitu8
After he won the Title, he moved to California and lived like a Bohemian, altho he was rich, winning all that money, and never played in another official match or tournament

It may not have been "official", but he played Boris Spassky in 1992 in an exhibition match (a rematch, 20 years later, of the 1972 Championship).

[barbitu8]

Right. That was the match in Yugoslavia, and I believed he won that match, although my memory fails me. It's a real tribute to his chess abilities that he can win a match with Spassky after not playing in a recognized match or tourney in 20 years. He's still a paranoid schizophrenic, por at least has a paranoid personality disorder. However, he has shown that he has lost touch with reality on many occasions, as witness the bizarre allegations at Iceland and his attack on Jews.