Slashdot Mirror
Humankind Makes Last Stand Against Machine
MrZeebo writes "According to this Financial Times story, Garry Kasparov has begun another match against a computer chess program on Sunday, this time playing against the Israeli-developed Deep Junior. Kasparov is the highest-rated chess player of all time, and lost to Deep Blue in 1997. According to the article, Deep Junior, despite evaluating less moves per minute than Deep Blue, is considered to be a superior chess player. The match will span 6 games, the last one being February 7th." Kasparov has won the first game.
they do exactly that: they put computers against each other. and it typically doesn't take an hour, a microsecond, or the end of time. they usually abide by the same rules governing FIDE world championships. and yes, these tournaments typically result in the creation of better chess software.
look at the development of fritz, and deep junior, for example. or hell, why not try looking something up on google? it can't be that difficult, can it?
deep blue was dismantled after its rematch with kasparov. deep junior has been winning all the computer chess tournaments for the past three years.
had the editors of the almighty slashdot bothered to read my infinitely more entertaining and informative story submission on this match, they might have had this interesting link included in their story, amongst other informative and titillating urls. this particular link will show the replay of today's game, as well as live broadcasts of future games.
boo to the editors.
yay to herrd0kt0r.
herrd0kt0r for prez.
How can they really tell which computer plays better chess?
Read the second to last paragraph of this. Or just read "Deep Junior is a three-time world champion and won the last official world chess championship for computers in July".
Yes, but what the computer can do is calculate the probability of all of Kasparov's moves, then only explore the options that are most probable. Although the computer cannot correctly predict the exact move Kasparov is going to make, it can probably narrow it down to 2 or 3 likely moves. It can pretty much ignore all the other moves, because Kasparov is not going to make a bad play. Kasparov's move is either going to be the best move for the situation, or at least the second or third best move. Although the 'best move' for any given chess scenario is debatable, the way the computer plays is to quantify the relative strengths of different positions and try to get into the strongest position. It is something that they are quite good at and I only expect them to get better as they get more raw power coutesy of Moore's Law.
Enigma
Deep blue was the first computer to play a world champion. It played with huge advantages, and the match was poorly run. The result was questionable, but it did mean one thing: computers are here, and they're not going to get run over, even by the best of the best.
The next major match was Kramnik vs. Deep Fritz. Deep Fritz was the highest rated computer program, and Kramnik the second highest rated human and world champion. Kramnik blew the computer away at first, then mysteriously lost a few games to draw the match.
This is Kasparov (highest rated human, NOT WORLD CHAMPION), vs. Deep Junior (I forget its rating, but it's up there, and it's world champion {for computers}). Kasparov won the first game. The matche conditions heavily favor Gary, he even got to play with a version of the program pretty similar to what he saw today on his home computer for the last six months!
So, who's stronger than who, what's stronger than what, and who's stronger than what? Here's the breakdown:
Deep Blue is the weakest of the competitors. It looked at an ungodly number of positions, but mainly because it HAD to if it was to have a chance. It ran custom hardware and software. It was dismantled immediately after the competition. Most of the work put into it is lost.
Deep Fritz is a strong program. It employs modern techniques and runs within the windows operating system. It is a commercial program available for a reasonable price from chessbase (chessbase.com). It consistantly maintains the highest rating for computers, but this could be because of its ability to beat up on weaker computers consistantly. Deep Junior seems to beat it when it comes to the championships.
Deep Junior is the computer world champion. It is very similar to deep fritz: it runs under windows, can be bought from chessbase, and is very strong. It wins championships consistantly, but its rating is always a bit behind fritzy's -- again this could be because of its inability to play decisively against weaker programs.
Vladamir Kramnik is the current world champion and second highest rated player. He won the championship title from Kasparov and has held it since without rematch (the chess world is in shambles -- at least three people claim to be world champion and none defend their titles. Kramnik has the most legitimate claim, as shown by his rating and the conditions of his competition). He is a far superior chess player in comparison to Deep Fritz -- this was shown in their match. His second half problems were possibly exhaustion, boredom, or caused by less noble factors, but they are essentially meaningless. When he was at his best, he was destroying the computer handily.
Gary Kasparov is the current highest rated player in the world, by a large margin. He is an absolute terror over the board, few players even in the top 100 in the world stand a chance against him (even those in the top 10 do not necessarily fair well!). He is considered by many the strongest chess player of all time.
This match is an official FIDE (Federation International des echecs or International Chess Federation) Man vs. Machine world championship. Hopefully the first annual of such.
As to who's going to win: Kasparov won today, and I expect him to continue. He has the ability to adjust to all his opponents (except Kramnik), and the computer is very rigid in its style. Strength varies based on the type of position, and Kasparov will give the computer no oppurtunity to play "its game." I made a similar "human lots, machine little" prediction before Kramnik's match, though, and he collapsed in the second half. Much is still to be decided.
I don't remember where I read this, but I think I remember seeing that the programming team for Deep Blue had the option of not doing what Deep Blue asked. This even happened in one of the games Deep Blue won in. Deep Blue made a blunder early on, but the programmer made a more sensible move instead.
Anyway, it seems that computer+human does better than human, not necessary computer by itself.
Engineering and the Ultimate
There was a good attendance and a great deal of media coverage today for game one, particularly considering it was a national holiday in the USA. (Well, almost.) Kasparov had the white pieces in game one, which is an advantage. (Interestingly, the Deep Junior team won the drawing of lots and could pick which color to have in game one (and 3 and 5), and chose to start with black.)
He completely dominated the game, it was a total stomp. He played 'real' chess instead of the dubious anti-computer style he used against Deep Blue in the 1997 match. Anti-computer chess involves trying to reach positions that computers don't play well instead of just making what you think are the best moves. Deep Blue showed that computers are pretty much beyond being vulnerable to these tricks nowadays, although every once in a while you'll see a strong program play like an idiot in a position it doesn't understand.
Kasparov prosecuted his advantage very quickly. In the press conference afterward he showed how much he had learned about playing computers. One key, he said, is that a computer doesn't understand results or practical chances, it only understands the evaluation of the current position. So instead of trying to swindle a way out of a bad position like a human Grandmaster would, by creating maximum chaos and hoping the other guy makes a mistake, a computer just tries to find the 'least-worst' move all the time. This is the only effective way for computers to play chess, but in inferior positions it often makes them look completely docile, if not pathetic.
He won't be able to do this in all six games, of course, and he'll probably lose one just because a human can't play error-free chess for so long against a strong opponent and computers punish errors ruthlessly. But game one showed he's prepared to the gills, as usual, and along with the fact that he's the strongest player in history should give him a decisive edge.
You can watch the games live with my commentary (and that of other commentators on-site as I relay their words) at many places on the web. Most of it is directed toward the level of the casual fan, not the chess expert. The company I'm working with, ChessBase, publishes Deep Junior and just about every other top chess program. (The program Fritz just drew an eight-game match against the world's #2 rated player and current world champion, Kramnik, in October 2001 in Bahrain. I was the webmaster and commentator on that match as well. I think I prefer the cold here at home in NY to the Bahraini humidity.)
As for the Deep Blue versus the current micros debate, that will be eternal as long as Deep Blue is in pieces. It was obviously much more powerful, but that doesn't mean it was a better chessplayer. We only have six games as evidence of its strength. They were good, but they weren't godlike and Kasparov said at the opening press conference that when you go over those games with Deep Junior it's clear that it plays better in just about every moment. (Except for two, which are the moves Kasparov has always suspected were the result of human interference. But that's another kettle of conspiracy.) Deep Blue was far, far ahead of its competitors in 1997, but computer chess programming has not stood still for the past six years.
It's also worth noting that what constitutes a huge advantage in computer-computer competition does not always translate into play against humans. A processing power advantage of just 10% between two identical programs will cause a lopsided score, but even a fourfold increase in processing power usually only means an extra 30-40 rating point gain against open competition. That is, one more win out of ten games.
I've spoken with Deep Blue's architect and other members of the IBM team on several occasions. Their egos are almost as big as Garry's! Hsu's book on the building of Deep Blue is almost as partisan as Kasparov's comments. They are both very competetive people. Personally I don't think there was any human interference in the DB match, but IBM's secretive and heavy-handed behavior needlesssly created a great deal of circumstantial evidence and suspicion.
You can follow my reports and photos on Kasparov-Deep Junior at ChessBase.com and I'll also be posting bits and ends at my site ChessNinja.com.
A chessboard is 8x8, meaning 64 spaces. However, each space can contain a pawn, a rook, a bishop, a knight, a king or a queen of either colour. The best estimate for the number of states the board can be in is 2.99x1041.
A naive encoding is 96 bytes per state. Let's say a tighter, or compressed encoding is 48 bytes per state. So a rough estimate as to the total storage space it would require is 1.44x1043 bytes.
In words, that's about 14 million billion billion gigabytes of data. I'm not going to say it'd be impossible to build such a storage mechanism in the forseable future, but I will say it's incredibly unlikely, and would be mindbogglingly expensive. And with modern technology, would require more matter than is actually on the planet. So no, dynamic programming wouldn't be useful in chess at all. Proving once again that if it were as simple as that, somebody would have thought of it already.
Out of interest, consider Go. This is a board where dynamic programming really would be useless. With around 10750 possible states, it would require significantly more atoms than are actually in the entire universe.
Given enough time, my old 486 could do it too.
There is a story I remember reading in a computer magazine once (about 10 years ago) that seemed to me to be at best anecdotal but more likely urban myth. Anyhow, it was in a respected publication, and it wasn't the April issue, so I just filed it away in my brain in the "stranger things have happened" category.
Umm, it was in Mad.It was on a spoof of computer gaming where they presented games that we are certain to see.
Anthropomorphism.
I used to get crushed by level 1 on most chest programs for years... until sometime a couple years ago I actually (more for general/novelty interest) picked up a "beginner"-style book on chess openings. You can't believe how much it helps to know how to properly open the first four or five moves in a game. You can bet the chess programs probably do, and if you don't know the most proper responses, then it seems to me that you've basically thrown away most any chance you have at the whole game, since the program is way ahead with a strong board position. (Turns out, there are reasons why there are so many thick tomes on openings. ;-)
Actually pitting a chess computer to a chess computer is really only good for double-checking and testing the software for any obvious weaknesses. You never want to use one chess computer to teach another AI/learning chess computer because you'll just be reenforcing the bad habbits (weaknesses/flaws) that computer chess has.
My human chessmasters tend to poke and prod a computer's technique to find a weakness/hole. A human opponent would recognize this "testing of defenses" strategy and compensate. A giant chess computer is rarely, if ever setup to recognize that someone is probing it for weaknesses.
Anyways the matches are rarely fair, since it's usually dozens or more programmers, engineers and chessmasters on the side of the computer nudging it along before and after a match (acting like a giant team of super-coaches) versus one man.
Perhaps we should refer to this as. 'Many men and a machine versus man." instead of "man vs. machine". This might explain why the media and general population does not care about these tests. I know I'm only interested when the Man wins, since I know the deck is stacked against him. Cheer for the underdog I say:)
They did change the parameters. It is allowed under the rules, and common practice. If they ever stated "that they would not", please provide a citation.
Accurate, but irrelevant since Deep Blue had played in no previous matches. DB's precursors *had* played in matches, and those transcripts are public record. If Kasparov didn't have them it was because he didn't look.
The thing that GK complains so much about is that they refused to provide the evaluation logs. Big difference! The logs describe the *reasons* that DB played or rejected certain moves. Kasparov is no more entitled to them than any human player is to have his opponent sit down after the match and descript why he played each move. No professional player would ever give *or ask for* such a thing.
Frankly, I think this is why IBM disassembled Deep Blue and will never sponsor or play in another such match. Kasparov poisoned the well. The payoff for IBM is in the public relations, and for GK to accuse them of cheating seriously detracts from the PR value. And there's no way to disprove the charges. (BTW, the match jury *was* given the logs, and after examing them they cleared the Deep Blue team of any wrongdoing.)
You can't take the sky from me!