Humans Hold Off the Machines... For Now

Murr writes "The six game match between Gary Kasparov and the Deep Junior program ended in a draw today. Kasparov won game 1 and lost game 3 to a blunder, while the other 4 games were drawn. While the quality of play was not outstanding, after the recent matches of Kramnik and Kasparov against commercial programs running on (high end) commodity hardware, it's becoming apparent that chess programs are getting quite competitive with top human players."

Comments

mandatory go plug

[dollargonzo]

chess is nice, but most progresses in chess have been due to speed increases in hardware and optimizations, hence allowing the computer to overpower the human with depth of search. On top of that, the evaluation functions are rather primitive, with lots of factors, but fail rather miserably without a great depth of search. New developments such as Logistello's statistical forward alpha cutoff called multiprobcut is the interesting development, IMHO

Explanation

[br00tus]

For those of you who are unfamiliar with chess or computer chess, I'll explain how this works...

A chess game can be broken into three parts, the opening, the middle game, and the endgame.

Computers play the endgame *perfectly*. They do not make mistakes, they play perfectly. And they keep getting better. Originally, they played perfectly when 3 pieces were left on the board. Then 4. Then 5. Then 6. Their pefect playing keeps heading more and more towards the middle of the game.

Then we get to what they play second-best - openings. Computers play the opening as well as any opening ever played. They have every opening ever played by a top player in a "book", and with the generally agreed opinions of the top players what the best opening moves are. One advantage of the computer is it has all of this "memorized" in it's book within massive databases, whereas for a human it's difficult to retain this all, especially in an up-to-date manner. The one advantage a human player has here is he can discover a NEW opening variation, while the computer can't, or at least it won't under these circumstances. But finding new good variations is very difficult, and once one is played, the cat is out of the bag so to speak. So it's a very time-consuming thing to search for which can only be used once to great effect because it's a surprise.

The middle game is where the human player, if he or she is very good, has the most advantage over a computer. Tactically, the computer can wipe the floor with any human player. But human's can strategize better than computers. It's to the human's advantage to play in certain ways against the computer - such as to keep the game "closed up", to advance pawns towards the queening square and so forth. In this case, the computer often can't see the forest for the trees, what would be obvious to even a lower-rated human the computer can not comprehend.

So middle game strategy (and to a lesser extent, new opening variations) is where humans still have the advantage. Kasparov has always used this to the hilt. There are some grandmasters like Yasser Seirawan who make a specialty out of beating computers as well (one mark against Seirawan is thar his books on chess are printed by Microsoft Press...yech). There is material out there on the net on how to beat computers as well. But you have to be a really good player to even get near that level - it takes a lot of study before you could even begin approaching that.

Re:Explanation

[SamBeckett]

1. They suck at openings as soon as they are out of book. See every match with Garry vs. DJ. See game 1 in particular.

2. They suck at middle game. They are tactically perfect, true. But at and above the expert level, tactics aren't that important. Strategy is, and a computer, AFAIK, does not know A. How to make a plan B. make moves according to a plan.

3. They suck at the end game. Badly. Unless there are only 6 or less pieces left on the board.
As such, a six man tablebase is the only thing feasible right now b/c of the massive size involved.

Re:Explanation

[Old Wolf]

The endgame is only played perfectly for positions that the computer has tablebases for (all 3, 4, or 5 piece positions, and only some 6 piece positions). However the endgame can be reached with 20 or more pieces on the board.

Computers have a reputation for being bad at endgames that aren't in their tablebase (or nearly in it). If you have watched a Grandmaster analyse an ending then this will be clear. The way the human thinks is: "Given that the pawns are like they are, I want my King here (points to square), my Rook here (points) ... and I want to stop my opponent getting his King to here (points)".

The human knows from experience and study that if the pieces are in those positions then the game is won. The computer does not know this (it is a heuristic quality that the computer may be programmed with, but humans have an advantage of being able to recognize when the position is one that these rules apply, and what the exceptions are).

The human then begins to look at sequences of moves which will end up in the pieces getting to where he wants them (and prevent the opponent's pieces getting to where the opponent wants them).

On the other hand, the computer is just exploring almost completely by brute force (positional factors mean much less, or absolutely nothing, in endgames. Computers will often rate a position as +2.5 , or even +4, when humans can see that it is clearly drawn. This even happened in the Kasparov - DJ match where the computer had a passed pawn in a rook ending and thought it was +2.5, but Kasparov knew he was safe).
The computer will only win the ending if its brute force tree is big enough that it stumbles into a tactic, or into its tablebase.

Ending play is also a good gauge of a human's strength: great players are great endgame players.

Now, onto the openings. The computer's opening book is not necessarily an advantage. Sure, the book has moves, but are they the best moves? In the Kramnik - Deep Fritz match, Kramnik analysed the book before the match and found positions that were in the book but where the book's evaluation was wrong (that is to say, the book's programmers gave a line saying "this is good for me", but the line was actually good for the opponent and the programmers hasn't realised).

Human grandmasters follow the latest developments in opening theory and are able to steer the openings into ones that they know well. The human also has the great advantage of knowing what sort of opening moves translate to what sort of middlegame positions.

Consider the last game of Kasparov - DJ. That surely was in the computer's opening book for some time. But Kasparov knew that once the opening book ran out, the computer would not have a clue what to do because the position was one in which both players have to shuffle their pieces around behind their ranks preparing for the right moment to strike. The only way to know a good move is to have experience in the positions and know what squares will turn out to be good ones once the action begins. This was reflected in the match play, the computer mucked around horribly until Kasparov was nice enough to offer it a draw.

Saw the match on ESPN 2

[humblecoder]

Here in the US, the sixth and final match was televised on the cable channel ESPN 2. I was channel surfing and I happened to stumble across it. To my surprise, it was actually quite interesting to watch on TV.

I am not a big chess freak, so I would have guessed that watching chess would be a lot like watching paint dry. However, it was made interesting by the "play-by-play" analysts who were chess masters themselves. They did a good job of explaining the moves, and also the psychology and strategy of chess at the grand master level. It really gave me a lot of insight into what goes on at when chess is played at such a high level.

After the match ended in a draw, they interviewed Kasparov. It was interesting to get his reaction to the match. Basically, his goal for the game was to "not lose", which is why he offered a draw from a very strong position. He didn't want to take a chance of making a blunder like he did in the third game of the match.

It seemed like the key advantage that the computer has in this situation is the fact that it doesn't have an ego to deal with. After losing to Deep Blue in 1997, it seemed like Kasparov was very afraid of losing to another computer in such a high-profile match. That definitely affect the way he approached the game.

The computer, on the other hand, is just calculating moves, so psychology doesn't factor into how it plays. To me, this seems like the biggest advantage that a computer has over a human player.

Also, he seemed to have more respect for this computer program than he did for Deep Blue. Apparently, he had a lot of problems with Deep Blue and how the 1997 match was handled. It could be sour grapes, of course, so I took his comments with a grain of salt.

well understood problem

[Jayson]

Game tree search is a very well understood problem and most top programs use some version of a null-window negascout (ID-DFS) with opening and closing databases. The most black magic in these systems is in their heuristic evaluation functions.

Backgammon programs used to compete at only a moderate level until Gerald Tesauro's TD-gammon (and predecessors). I wonder if there will ever be a breakthrough of equal proportions in chess? If so, humans would have very little change against computers (I hate to say never, because of absolute freaks like Marion "I am programmed by God" Tinsley).

Re:Why wasn't it made 7 games?

[pez]

It's considered slightly advantageous to play with the white pieces, so an even number of games is almost required in order to have a fair match.

Also, an odd number of games does not guarantee to not result in a tie, since all of the games could be draws.

More Information

[Resseguie]

Here are more links I collected when submitting this story...

• World Chess Federation
• WCF coverage of match
• Yahoo News - coverage in non-chess expert terms
• Wired News article - why chess isn't as good a measure of intelligence as some make it out to be
• X3D Technology - provided 2D and 3D coverage of the match
• Coverage of games and press conferences by X3D
• How X3D works

Does anyone have a good link describing the programmers behind Deep Junior? All I could find were news articles and press releases. I'd like to read more information about their strategy, search algorithms, etc.

David

Re:Go?

[tpengster]

I think computer vs human Go matches would be much more interesting now,

Computer Go isn't advanced enough to make the matches interesting. Not too long ago a professional 1-dan (9-dan being the highest rank) played against a computer program giving it a 25 stone advantage. The human still won. (For those of you who haven't played go, 25 stones is HUGE. That would be like giving up a queen, two rooks, and both bishops)

Anonymous Karma Whoring

[Anonymous Coward]

Check this link:
http://www.intelligentgo.org/en/computer-go/overvi ew.html

Re:Go?

[harlows_monkeys]

That said, can someone venture an explanation why Go is so difficult to program?

For most of the game, there are many more moves available than in chess, and it usually takes many more moves for a bad move to have an obvious affect.

In Chess, a positional mistake can usually be converted to a material loss in 10 or 15 moves. In Go, a positional mistake can take much much longer to lead to a territory loss.

Re:Go?

[Phs2501]

For most of the game, there are many more moves available than in chess, and it usually takes many more moves for a bad move to have an obvious affect.

Also, an evaluation function for a board position in Go is very complicated, depending on the life or death of stone groups on the board. The only way to determine life or death is to effectively know how to best play out the remainder of that area and see who comes out alive. This is very difficult for a computer, since the evaluation function is what makes your min/max algorithm work.