Slashdot Mirror
Man Vs Machine In Chess - Who Is Winning?
FFriedel writes "In a few weeks, the world's strongest player Garry Kasparov will take
on X3D Fritz in a high-profile man-machine
chess match. Who is the statistical favourite? Since computers have been steadily
improving and are now holding their own against the very strongest human players,
one would think it may be Fritz. Not necessarily, says statistician Jeff Sonas,
who doesn't believe computers will inevitably surpass the top humans, and presents empirical evidence to support his claim as part of a series of articles for ChessBase."
If you think you know something about computer chess but haven't read Behind Deep Blue by the man largely responsible for creating it, you need to correct your error asap. Did you know, for instance, that in 1997 Deep Blue had 480 chips running its chess program _in silicon_ with 30 rs/6000 nodes controlling them? Moore's law isn't going to let a 2 (4?) cpu PC catch up THAT fast, let alone when it's pure software.
BTW, the Fritz people make a big deal about beating deep blue in 1995. That would have been a big deal, but the program they beat was Deep Thought II ("Deep Blue Prototype"), not deep blue, a weaker program running on weaker hardware. The match was in Hong Kong where DT2 had persistent problems with their data line to the USA where DT2 was physically located.
Anyone else think that once machines take over the Earth, all they will do is play chess against eachother?
Karma: SELECT `karma` FROM `users` WHERE `userid`=138474;
"brethren," eh?
:)
Hypocrite
Moxy Fruvous did an amusing take on the topic a few years ago at MIT on their U.S. tour. The discussion made it on their "Live Noise" album as "Kasparov vs. Deep Blue", and a transcript is available at http://www.fruvous.com/ln-lyr.html about 2/3 of the way down the page. (Warning, there are a few instances of adult language in the discussion)
I consider it's still humans competing with other humans playing chess. On one hand we have a chess-master using all the power of his brain, on the other some computer people using a high-powered computer.
When a computer can learn to play chess by itself and then beat the top players, then we have something to look at.
Part of the problem is that Kasparov is this generation's GM. Kasparov plays very emotional games. He's not just looking to beat you in his first match; he's looking to utterly destroy, smash and humiliate you with a dramatic and embarrassing win.
This is a great strategy against people, but it's not so effective against computers. Kasparov is probably the worst chess master to pit against a machine since Ruy Lopez (I think he's won with the Ruy Lopez opening a few times, case in point: it's a brutal and humiliating play for the losing opponent).
Kasparov knows that the computer can "think through" future moves better than he can. Computers, in fact, do the opposite of human chess players: we set goals and try to find ways to get there while computers search through various ways to find a satisfactory goal they can achieve. So, Kasparov plays it very conservative and keeps himself out of any situations that give the computer too much range of foresight, which is why the Kasparov/computer matches tend to look like Verdun (though he's been surprised a few times).
Personally I'd like to see some of the younger generation take on the big programs. They tend to play more technically and less passionately than Kasparov and his generation.
All's true that is mistrusted
Like when a player scores a touchdown? Or do the programmers wheel it around in circle chanting it's name? You gotta let them have a little fun. Better then making them mad and having them go Terminator on us.
MMORPG Fan? Prove your worth!
Not to get too off-topic, but there are also now several (increasing) prizes for beating top ranked players (well, rather, any professional player and occasionally there's a prize for beating a dan ranked amateur) in Go.
For those of you who are unfamiliar, there is an excellent, if somewhat dated, article that discusses some of the difficulties for getting a computer to play Go well. It also talks about Janice Kim, a 1 dan (professional) at the time (now a 3 dan), beating the then-best program when the computer had a 25 stone handicap. To give an idea, a 9 stone handicap in an experimental games between evenly matched professionals generates about 140 point advantage.
As I said, it is a bit dated (5 years old) and computers have improved, but we are still nowhere close to beating a professional.
Integrate Keynote and LaTeX
I notice that the question is "Man vs. Machine". You completely ignore the hundreds of grandmaster chess players that happen to be female.
Name a few.
Any in the top ten?
Didn't think so.
More importantly, the article mentions a match against Kasparov, most certainly a male. Thus, although we can philosophically ponder the bigger question of "human vs machine", the title has no sexism involved, without even resorting to a discussion on the use of the masculine neutral in English.
read rec.games.chess.computer. the search space is WAY the hell too big.
It is simply naive to say computers will never be able to outdo human thought, such as that required for chess or other logic/pattern-recognition based tasks. This is analogous to 19th century Royal Society scientists claiming one could never escape the Earth's gravity into space and beyond (and providing "proof," mind you). But I digress. Chess is not so much about logic and thought (in the normal sense) as it is for pattern recognition and "looking ahead." The best chess players in the world have nearly memorized all the possible combinations in all the possible scenarios, contrary to popular belief that their abilities are innate. I don't know if software has evolved enough to beat him this time around, but if the second math was any indication, my money's on the machine.
A blog like any other.
from the article:
"The red line is Garry Kasparov's rating over time, and the blue line is the rating of the top computers on the SSDF list. The blue line is creeping closer and closer to the red line. It seems just on the verge of crossing over. "
But then, further, down, he writes:
"Although computers obviously must be improving in recent years, the strongest humans seem to also be improving at about the same rate."
These two statements contradict each other, don't they? Either computers are improving faster than grand-masters, meaning the graph and its extraploations are true; or, computers and grand-masters are improving at the same rate, which would mean the percentage of human wins and draws would be generally the same as in previous years (something not indicated by the second graphic in the article)?
the coolest club on
Oh, yes indeed. Because emotion is such an important part of playing chess.
I had but a simple dream, to destroy all humans.
According to p. 45 of Russel & Norvig's AI book, a look up table for the game of chess (i.e. if you mapped every achievable permutation of chess pieces on a board) you would have 10^150 entries. Unfortunately, there are only 10^80 atoms in the observable universe. Even with excellent heuristics, I think these numbers show that a computer that capable of playing perfect chess will not be built in the foreseeable future.
Although the entire search space of moves obviously hasn't been explored, it's generally considered an advantage to be White (White moves first). With the first move, you automatically get the initiative, and at the highest levels of chess this can be a great advantage. My guess would be that if the entire search space could be enumerated, chess would either be a draw (more likely) or a win for White. I really doubt it would be a win for Black.
Use Ctrl-C instead of ESC in Vim!
Meanwhile, the fastest airplane ever built is still the SR-71A made in the 1960's. That doesn't mean aircraft technology has come to a standstill. It just means outrunning the SR-71A hasn't been a priority of aircraft builders since then. If they wanted to expend the resources to make a faster plane today, they could do it.
Deep Blue II was the SR-71A of chess computers. What's come afterwards has been a lot more economical and practical, but hasn't tried to match it in pure performance, and hasn't done so.
While the total number of states in Tic Tac Toe is a boringly small finite number, the total number of states in chess is rather amusingly large. And by "amusingly large", I should point out that I'm a large number theorist.
How large is "amusingly large"? Around 10^150, if I remember my AI class correctly. Discarding entirely the problem of how you'd create a game tree of that size (given the cosmos has about 10^77 particles), let's just address the energy required to compute the table.
It requires an absolute minimum of kT*ln2, or about 3*10^-26 Joules, of energy to set a bit. Each cell on a chess board requires a minimum of four bits to store its state (it has to store a three-bit enum { PAWN, ROOK, KNIGHT, BISHOP, QUEEN, KING } and a one-bit enum { BLACK, WHITE }). So for a 64-block chess grid, you're looking at 256 bits just to store state.
256 * 3*10^-26 = 7.7*10^-24
7.7 * 10^-24 * 10^150 = 7.7 * 10^126
Do you have any freaking clue how much energy 10^126 Joules is? It's frickin' huge. Like enough to cause a symmetry-breaking event which would propagate through the universe at the speed of light and utterly annihilate everything in its path, including the computer churning out the complete decision tree for chess.
I can see it now. When Judgment Day comes, it's all going to be because of a Slashdotter who thinks he knows a lot more about what computers can and can't do than he really does, and goes off to solve unsolvable problems without considering the thermodynamic consequences of his actions.
Typical for Slashdot.
Something the article doesn't touch on is that although chess grandmasters were caught off guard by the strength of chess computer's in the mid-90's, since then we have learned a tremendous amount about the computer's weak spots. The computer for example is very poor at playing in tight positions like some lines in the Caro-Kann and French defenses. Also many of the so-called hypermodern openings.
I imagine the new breed of young GM's like Ponmariov, Grischuk and Malakhov probably find the prospect of beating stock Fritz/Junior/Hiarcs rather boring. A few extra CPU's isn't going to make a big difference in terms of playing power. Much more effective is to spend time tuning the engine's opening book and that takes traditional GM's with novelties.
Kasparov should win this easily, though he did miss a trivial 2 move combination in a tournament recently so you never know...
This is the constant claim of the meaning of computers outpacing humans at chess, and it's complete BS.
Machines have been outpacing humans in various endeavours for years. Eventually computers will be powerful enough and well programmed enough that they'll never lose (although they certainly will still draw).
Big deal. Either show me the sprinter who can beat a formula 1 or show me the movement to claim there are no longer human champions in speed. I don't see either of those, so I don't see why it should matter for a mental game.
I see no reason why we should care if computers can someday see all possible positions 35 moves out. Chess isn't about that. Chess is a game of reason, of insight, of spacial perception, of memory, of stamina (you try concentrating on one thing for 6 hours), and of emotion. Seeing forcing variations a dozen moves out is rarely part of the game for humans, and plenty of players have risen to the top of the game almost never calculating beyond 2 or 3 moves out. Giving a machine an 800HP engine and wheels takes absolutely nothing away from the human accomplishment of mastering the game.
There has been a chess message board discussion where the author of the article mooted his ideas last week. I write for ChessBase and worked on both of the last big man-machine matches (Kramnik-Fritz 2002 and Kasparov-Junior 2003).
For those here who claiming obvious Deep Blue superiority over current micros because of how many chips it had and how many positions per second it looked at, some chess knowledge would help. Deep Blue only played six games and all have been analyzed to death. We know two things. One is that Deep Blue beat Kasparov and that's the only thing most people care about, the result. The other is that Deep Blue's play was far from perfect.
Years of human and computer analysis can about as close as you can to the truth in chess. With that knowledge we can compare Deep Blue's moves to those of the current top programs such as Fritz and Junior. And we have, extensively. The bottom line is that they play better in many places, the same in others, and worse only in very few. The overall level of play by the micros in the same positions from the Deep Blue games is better. With Deep Blue in pieces that is the only way to compare the quality of their chess. Positions per second is interesting and not irrelevant, but time marches on and knowledge is important too.
While the humans in these matches obviously have some interest in saying that the program they are playing is the strongest, hundreds of other analysts don't. And Kasparov and Kramnik aren't going to make fools of themselves by recommending moves that could be easily shown to be inferior.
Kasparov played some of the most inconsistent and nervous chess of his life in the pressure-cooker match against Deep Blue in 1997. He resigned in a drawn position for the only time in his career and Deep Blue's other win, in the final game, came in a total mental collapse by Kasparov and was the shortest loss of his career in a serious game. All credit to the Deep Blue team, mission accomplished and all that, but it wasn't the greatest chess.
Meanwhile, humans studied and learned. Kasparov's attempts to baffle Deep Blue by playing intentionally inferior moves was ill-advised. That era was over, he just didn't know it. But computers still have their weaknesses, as Kramnik showed in the first half of the Bahrain match.
The top programs today running on the fastest micro hardware available play better chess than Deep Blue '97. But the top humans play better, and smarter, against them than Kasparov did in 97.
However, noting that the state-space size is large isn't really a very useful observation, since chess programs these days don't try to map out the entire tree of possible outcomes. Instead, they operate on neurodynamic programming techniques, which basically try to extract which "features" of the game are important and weigh those features to decide which moves to make. This significantly reduces the complexity of the system, but requires that the person writing the program have some intuition about which "features" are important. In chess, for example, these include such things as material balance, piece mobility, king safety, and other positional factors. A period of training is usually required as well, where basically the computer goes over a lot of games that grandmasters have played and tries to "learn" how to weigh the different features in order to choose the optimal move.
For those who are interested in reading further about this (yeah, yeah, this is Slashdot, if people can't RTFA what are the odds they'll want to pick up a book? :) ) a good place to start would be Chapter 6 of Bertsekas' "Dynamic Programming and Optimal Control".
The bold print giveth, and the fine print taketh away