Slashdot Mirror
Kramnik and Deep Fritz Draw, Tied Before Final Game
iskander writes "Man and Machine were content to draw in game 7 of the Brains in Bahrain match. Now it's all down to the final game, in which Kramnik will enjoy the advantage of playing with white. It is worth noting that game 6, in which Kramnik may have resigned too early, was found to be a probable draw with best play, and that Kasparov lost to Deep Blue by tossing a drawable game. However, whereas Kasparov could only excuse himself (unconvincingly) by claiming that Deep Blue had been assisted by a human during play, Kramnik could simply request the adjudication of game 6 on the grounds of infractions committed by Deep Fritz, who is rumored to have heckled Kramnik with its Shakespearean chatter througout the game. :) So, will Dirty Fritz win it all or will Humanity's champion "rise above the chatter" and win back the crown for us? If you think you know, you may want to place a bet or register your opinion on the ChessLines survey soon, because the match ends tomorrow."
Kramnik vs Deep Fritz match summary:
October 04, Game 1: Draw ----------- Article
October 06, Game 2: Kramnik wins --- Article
October 08, Game 3: Kramnik wins --- Article Analysis
October 10, Game 4: Draw ----------- Article Analysis
October 13, Game 5: Fritz wins ----- Article
October 15, Game 6: Fritz wins ----- Article Analysis
October 17, Game 7: Draw ----------- Article
October 19, Game 8: ?
I am in no way a chess master (or even a decent player) but even I know that there is an advantage to playing white. I had always thought that chess tournaments featured an even number of games, so each player have equal shots at playing black and white.
Can anyone back me up or correct me? Thanks.
It is worth noting that game 6, in which Kramnik may have resigned too early, was found to be a probable draw with best play It is also worth noting that Kramnik didn't have much time left on his clock, and it would have been difficult for him to come up with the right moves given the amount of time he had left on his clock.
AccountKiller
It is possible in principle (just as the traveling salesman problem always is solvable in principle), but you have to enumerate each board - and there are too many possible boards to express in practice - ever.
Trust the Computer. The Computer is your friend.
Server... is... slowing... so here's the text:
Did Deep Fritz use Shakespeare to heckle the World Champion?
It is an interesting theory: the Fritz team installed the latest chatter files during the Man vs Machine event in Bahrain, causing the machine to talk to the world champion in authentic Shakespearean verse during the game. The historical chatter drove Kramnik to distraction and prompted his ill-fated Morphy-esque knight sacrifice. That, in any case, ist how Schakespearean scholar and chess addict Michael Fischer tells it in his special report.
Kramnik versus Deep Fritz, match game 6
While the reports have not been confirmed, there has been some talk of the Fritz team having employed a clever diversionary tactic in Game Six to unsettle the World Champion, Vladimir Kramnik. Before the game, programmer Frans Morsch and the notorious - some might say nefarious - Fred Friedel apparently tinkered with the Deep Fritz program, installing the Shakespearean Chatter Files slated to appear with a future release of Fritz. Morsch thought it would give the computer better odds. Fred thought it would be funny to see Kramnik turn red and talk to himself.
The conspirators rigged up several speakers around Kramnik's chair and set them at volumes low enough that only Kramnik might hear the computer's chatter. That the computer was talking to him doubtless distracted Kramnik; that Fritz was speaking entirely in Shakespearean verse surely drove Kramnik mad, prompting the questionable, Morphy-esque Knight sacrifice at f7.
Our reports go on to say that a Bahraini match official managed to extract a full transcript from the Deep Fritz computer after the game. This transcript he then e-mailed to the chatter-file designer, S. Michael Fisher, in the USA. In a fit of good conscience, this same Mr. Fisher (no relation of Bobby Fischer) then decided to make public the entire sordid affair.
What follows is a copy of that transcript.
[long transcript follows... one excerpt below:] Fritz: "Now is it time to arm: come, shall we about it?"Fritz: "The game's afoot."
Fritz: "What, the sword and the word! do you study them both, master parson?"
Fritz: "You are a villain; I jest not: I will make it good how you dare, with what you dare, and when you dare. Do me right, or I will protest your cowardice."
[ etc... ]
Traditionally the way the best players defeat good computer opponents is to observe the play and look for limitations of the algorithm/search depth. During Kasparov's match, the machine was tuned extensively between games, which invalidated some of his observations. This made the match much harder for Kasparov, than Kramnick's match seems to be (if I remember correctly, they disallow tuning of the software during the match).
Story about Kramnik's blunder costing him a game found here...
There are 20 possibilities for a first move:
Now there are also 20 possibilities for a response, that's already 400 possibilities for the first move and answer.
If you disregard the fact that the first moves may open new possibilities and keep calculating with 20 possibilities then the third move has already 8000 possibilities, the next one 160.000
After only 10 moves (5 on each side) this number alredy grows to 104.900.000.000.000.000.000.000.000 and the game has just started.
You would need a big Beowulf Cluster to build such a tree.
For those who aren't familiar with big numbers, it would take a modern processor (at around 10^12 moves per second) somewhere around 3^61 years to complete that game tree. How long is 3^61 years? Well... the sun will explode at 5^9 years, long before the computer ever finished searching the tree.
A Flash 6 Linux Player, beta to watch the final match on www.brainsinbahrain.com is available here
@de_machina
Oops. Should have used preview.
Sun explodes: 5 x 10^9
Computer finishes chess game tree: 3 x 10^61
The Week In Chess (TWIC) is the news center for chess players, as far as I'm concerned. They have good reports about the match as well, including an interview with Kramnik from a week before the match, here.
My karma is maxed, I'm not just whoring, I just hate people linking to an article on CNN or Yahoo or so when it's about chess. Though this submission was clearly a lot better than the previous ones.
And about the match - it's interesting that after Kramnik exploited the computer's weaknesses (endgame, strategy, etc), the computer followed up by exploiting the human's weaknesses - emotion in game 5 (Kramnik realized he was facing a long hard defence, didn't like this, maybe he was a bit nervy), and vanity in game 6 (Kramnik went for the flashy tactics, he wanted "the best game in his life". Admittedly he didn't see the refutation so it seemed a good move, but it certainly wasn't good anti-computer strategy.)
And now it's 3.5-3.5 with one game to go. Kramnik has to choose between playing for a win (which may involve risk), or take no risks (leading to a probable draw). This may lead to doubts in his mind. Something Fritz doesn't have to deal with, although his operators may have the same problem choosing an opening repertoire.
Let's hope they don't let Fritz go down because of their humans flaws.
I believe posters are recognized by their sig. So I made one.
For those who don't seem to get it:
;)
The Shakespeare quotes article was humor, not fact. Or maybe wishful thinking...
But in any case, Deep Fritz is not clever enough (or blessed with a complex enough *ahem* 'chatter file') to actually use Shakespeare to such great effect... It did not really happen.
Sheesh.
STOP . AMERICA . NOW
A few things I've noticed:
1) The quotes are all remarkably apt for the moves--in other words, they reflect the emotion and the mental state of Kramnik and the game itself. A computer would not be able to understand the underlying meanings of the Shakespearean quotes, let alone choose the appropriate quote for each moment.
2) It played the words just loud enough for Kramnik alone to hear. How then is it that we have a full and complete transcript of what Fritz said? Never mind -- I just read the transcript again and it looks like an official got the transcript from Fritz. But I still say it's fishy.
3) It hummed the theme from Midsummer's Nights Dream? It whistled. While recordings of these could be made, and I suppose loaded in and played on command, I still find it hard to believe that this would happen.
4) Considering that Krimnik could easily, and without drawing criticism on himself, point out this clear breach, wasn't it way too much of a concern for the people developing the Fritz program? Did they really want to risk disqualification?
I was able to read the transcript once (it's
All right, all right, folks -- read to the end of the transcript. This line gives it away: It's a practical joke placed upon us by, surprise surprise, a "Shakespearean scholar and chess addict" Michael Fischer.
Karma: Chevy Kavalierma.
The article was on the chessbase site. www.chessbase.com
Not too many human players do. Deep Blue was probably within the top 10 human players, and at blitz speeds better than any human.
The comment about not learning is most definately not true. The computer uses its ability to "brute force" as an advantage, but the technology which is being used in computers like Deep Blue and Fritz are not just game trees. Modern day AI most definatley can "learn" and adapt.
Most notable are artificial neural networks which mimic the human brain structure and constantly adapt the weight system by comparing inputs and outputs with what is expected.
Think about it.. if the code was completely determnistic, as soon as Kramnik won one match he could just play the exact same set of moves and win again.
-ashot
Pretty slow due to /. right now, but you can get it here
I suspect you have misunderstood the meaning of my remark; perhaps you are not aware of the literal content of statements made by Kasparov during and after that match. Kasparov did in fact say (repeatedly) that some moves made (ostensibly) by Deep Blue during actual game play (with clocks a-ticking) were in fact chosen by a human; that is, IMO, he basically claimed that the Deep Blue team had cheated. In particular, after game 6 (the final game) of his match against Deep Blue, in which (in an eerie parallel with Kramnik's game 6) he played black and resigned early, he blamed the loss on the intervention of a "human hand". Perhaps someone else here can dig up a link to a transcript of his statements from the depths of her bookmarks file; thanks in advance, etcetera. In any case, I think that his meaning was quite clear and that my statement is thus scrupulously fair.
Excuse me for my lack of knowledge on the subject, but why can't a game tree for chess be made?
You are absolutely right - this is basically how chess programs work. As many other have pointed out, it is impossible to calculate all the moves for a game. But contrary to some posts, the strategy is not meaningless. The computer will make a game tree say 5 moves ahead, then discard all of the inplausible moves, and go down another couple of levels (there is, of course, a lot of thinking that goes into specifying exactly which paths should be discarded and a lot of other details)
And wouldn't it be a matter of time before it is impossible to beat a computer at chess?
Yes, this is exactly what has happened. Only a few people in the world can deal with a computer that evaluates all possible moves 5 or more steps ahead.
Tor
Chess cannot be completely solved by brute force, not unless it's a lot of brute force. The difficulty of chess comes from anticipating moves that will happen any number of moves in the future. This sort of computation grows logarithmically more difficult with the number of moves. Furthermore it must anticipate the opponent's moves.
Chess requires sacrifice, a difficult concept to use in a raw computational method. The set of "rules" for each computational step is dependant on all preceding steps. While this play tree is evaluated (depth first or breadth first) some measure of "goodness" must be evaluated for all future board positions. They must be stored and compared. A brute force evaluation must assess the likelyhood that any future board position will lead to other favorable board positions further into the game. I'm sure that very good chess simulators are very aware of strategies and methods that tallented chess players are aware of. If it were just a brute force method, they'd be running deap fritz on a thousand processor monster.
Go is a difficult and interesting problem also, yet the fundamental problems are similar. (How to define and compare the relative "goodness" of future possible boards, how to elinimiate unnessesary computation, how to store previously made calculations and search them effectively.) The higher number of board positions just makes it all that much harder.
Okay, RM, that's good. But what we are talking about here is an academic disipline called AI. It is a branch of computer science. Certain problem domains and techniques are acknowledged by much of mainstream academia to fall within the bounds of AI. Playing chess at grandmaster level is generally acknowledged as a worthy test of some of those techniques.
This is not to be confused with science fiction and popular usage, where AI has an entirely different meaning, which is why most AI researchers have been sprinting as fast as they can away from the term.
And in terms of waiting on Wintermute to start ringing the row of payphones in the airport just once as I walk by, well, I agree with you we aren't going to get there for a while and probably with much different tools than we are currently using. But that is a fantasy future and not the reality of the situation today.
7. What we cannot speak about we must pass over in silence.
This is absolutely correct. To reply to all the other posters on this thread: time is a very important part of all competitive chess. There are strict rules about the chess clock and its use. International chess specifies 2 hours for the first 40 moves and then another two hours to reach move 60, for example (IIRC). Losing on time is a very common occurrence - especially on the Internet servers. Nothing like a quick game of 2 minutes blitz to make you appreciate time to think :)
If you want to see some game played by grandmasters when in "time trouble", I'd suggest picking up the Mammoth Book of Chess by Graham Burgess for some excellent - and amusing - examples. You don't have all the time in the world - chess is a balance between concentration and speed.
--- Hot Shot City is particularly good.
Gotta disagree here. A lot of programs look at positions more than 5 moves deep, even programs on the palm pilot can do this, and they are certainly beatable by a decent player (turn on evaluations in GNUChess). I find the same principles apply at the lower level, i.e. avoid complexities and the positional play is weak.
The point is, most humans can look 5 moves ahead in the few variations that matter in a given position, but the advantage is that the general pattern of the resulting position is easier for a human to value, because we can do this at a glance from pattern recognition. The value of a position is of course dependent on the moves that can be played after it, but if the computer is not looking any further ahead, the valuation of the position is generally not as accurate as human perception. Human evaluation is also effectively looking at future moves, its just we take a big shortcut.
The reason why computers beat humans regularly are that they generally look much deeper than 5 moves, especially in important lines (they discard some lines they don't think matter at the point of 'quiescence' and concentrate on important ones), and thus are trying to value a final position that is more developed than the position a human player would be evaluating.
If Deep Fritz works along the same lines as Deep Blue, it can easily learn from its mistakes. Consider a simple point-system(imperfect, but widely used), in which each piece position contributes to a numeric value of the board. Let's say moving a piece to a particular square under a particular set of conditions is initially rated very highly - it's a "good move." Then, two moves later, because of that move, the computer is in mate. Obviously not a good move. If this mistake is left in how the machine "thinks," the human can just exploit this weakness. If the machine DOESN'T learn from it's mistakes, it will fail miserably.
Imagine it as a tree by which you want to get to a specific goal. If following a specific branch doesn't get you to the goal, would you ever want to follow it again?
AI isn't actually that state-of-the-art. Most of the concepts behind AI are, strangely enough, very intuitive, and the reason that AI is appearing to get better is because computational power is increasing quite rapidly. If you have the speed and memory to explore EVERY possible move in the rest of the game, why not do it? Can we do this now? No. Will we be able to down the line? Yes.
-agent oranje.