Kramnik Ties Fritz; Machines Not Yet Our Masters 241
Maltov writes "World Chess Champion V. Kramnik ties his match against the software Fritz. Details here.
You can also check out a picture gallery and a short history of computer chess."
We can at best hope a tie.. (Score:4, Interesting)
Machines Not Yet Our Masters? (Score:4, Interesting)
First Chess machine (Score:5, Interesting)
Mainly it was used by con artists selling the machine to the rich (without the midget inside).
Thankfully things have come a little way since then...
Too bad... (Score:4, Interesting)
Re:We can at best hope a tie.. (Score:5, Interesting)
Here's an interesting quote from MSNBC:
Friedel pointed to two weaknesses in Kramnik's play characteristic of humans. "Once in 200 moves a human will make a blunder, and that's all Fritz needs. And [Kramnik] was seduced by beauty." He added that Kramnik "understands 100 times more about chess than any computer, but tactically Fritz is a monster."
Re:We can at best hope a tie.. (Score:3, Interesting)
I wouldn't hold my breath for the "guaranteed tie" level of gameplay to come any time soon...
Re:We can at best hope a tie.. (Score:5, Interesting)
Computers are strong in tactical play, humans in positional; people have argued for ages, which is better, so far both styles have their proponents among grandmasters.
And we can't really find an answer to this question unless we compute the entire game tree of chess, but this is impossible, even if you used all the atoms in the Universe to track the nodes in your tree.
Btw, the concern that chess as a game will exhaust itself and in the future grandmasters will always tie, has been expressed many times in the past. So far they have all been proven wrong, usually when some prodigy (Tal, Fischer, Kasparov) has come forward and brought new innovations with him. Computer chess is in a similar position, bringing many new ideas to the chess world, and countless new chess theories have been created by analyzing how computers play.
So I am quite optimistic about the future of chess, there is certainly no end in sight for now.
Re:First Chess machine (Score:4, Interesting)
Pretty cool hoax.
What's the big deal? (Score:2, Interesting)
Just as people carry on competing against each other to see who is the fastest runner, despite of the fact that even a 50cc motorbike would beat them hands down, they will carry on competing at chess - despite the fact that machines are already probably better at it. The time has come to put chess where it belongs: a more or less interesting game, but very, very far from the pinnacle of human intellectual achievement.
Re:We can at best hope a tie.. (Score:1, Interesting)
More realistically, "man" will stay more or less the same strength, and "machine" will continue improving. We'll see machines either winning or tieing, never losing. Actually if man doesn't improve at all we will start to see *less* drawn games as the ELO gap widens between man and machine.
Actually, he's right (Score:1, Interesting)
If White can force a win, then, in a match of 8 games, each side will have four wins. If Black can force a draw, then in a match of 8 games there will be eight draws.
But as other people have said, determining whether a draw or win can be forced is computationally infeasible. So the game will be interesting for a while.
Was the match 'fair' this time? (Score:5, Interesting)
Anyone know if this was ever an issue in this current tournament?
Hardware and OS it was running on? (Score:3, Interesting)
I know that Fritz is supposed to be much more intelligent in its search-tree pruning than Deep Blue was, and not require so much computational power.
Computers playing with humans (Score:3, Interesting)
The average slashdotter seems pretty certain of the day when programs, these unbeatable machines, will be able to simply trounce the best humans in one on one competition. But what about a future match with the best chess computer against a top notch grandmaster with his own pc, even a weaker program? Do you people honestly think that human knowledge will simply be obviated by brute force processing power?
Re:We can at best hope a tie.. (Score:4, Interesting)
On the average chess has a branching factor of about 40 (or 35--reports vary). This means that on average for each players turn there are that many possible moves. So to build a game tree, that's how fast the tree will grow.
Go on the other hand as you state, starts with an empty board, and so even if you're playing on a child sized board of 9x9 (standard sized boards are a good bit bigger than this, I forget the size, at least 13x13 i believe) you have 81 possible moves at first. And you do make a good point that this branching factor drops dramatically as the game advances.
there's nothing inherent to Go that makes it a better game, "harder", or anything of the sort--no magic reason for why computer AI's suck. It's simply a ton less energy being put into Go (when was the last time you heard of a MASSIVE super computer being built for Go?) and the massive branching factor.
My personal feeling is that within 20 years Go AI with be at a similiar level as we are at with chess today--just my own guess.
Not correct (Score:3, Interesting)
Westerner alert! (Score:5, Interesting)
Perhaps with the belief among computer chess researchers that chess has been solved will Go soon undergo the same nitpicking that chess has
This game is much more popular than chess in China, Japan, and Korea. Somehow, you seem to assume that these regions are all completely deviod of any programming, AI, or mathematical talent.
These people are obviously just sitting around waiting for us Westerners to solve chess so we can move onto their little problem.
As for your 'points'... they cry of a lack of deep understanding of both Go, and AI
1. Go pieces can be removed from the board, by capturing. Thus opening up more combinations
2. Even if it weren't possible, and a stone was plunked down each time, you'd still have (19x19)! possible moves (a lot, as stated earlier)
3. When chess pieces are removed from the board, it collapses the search tree. On a Go board, it expands it.
4. There are 4 'cells' Remember, in a Ko battle, a space can be empty, but unplayable.
5. The whole cells argument is pretty nonsensical anyway? You are basically discussing bit-depth... in which case, would a black and white face be easier for a computer to recognize than a grayscale, how about color?
6. Facial recognition really has nothing to do with Go in a practical sense. Facial recognition is categorization based on large differences. In go, you have to select the best move based on extremely small differences in extremely similiar layouts.
7. As far as the "million game database" This just will not work, as playing against a human, they'll just do a profitable, but nonsensical move. It is the same thing that happens when studying Joseki. People will know the Joseki, but without an understanding of the principles behind it, it will be useless to them as they will not be able to respond to non-standard moves (GNU Go has a Joseki database I believe).
---Lane
Re:We can at best hope a tie.. (Score:5, Interesting)
You need to learn more about the game, I think, before you try to explain it to others.
Re:Kramnik shoulda asked for a tiebreaker... (Score:5, Interesting)
Chess vs. Magic.... (Score:3, Interesting)
Games like backgammon and poker have unknowns - you may know what is in your hand, but you don't know what is next up, nor do you know what the other player has. As a result, given the state you can see, you CANNOT compute a single optimal set of moves - all you can do is probablistically state "most of the time, this would be the best move".
Add to that bluffing - in poker you can bluff the other guy into losing when he should have won.
Now, consider card games like Magic: The Gathering . Not only do you not know what the other guy's next draw is, nor what he has in his hand, you cannot even for certain limit the set of what he can draw very much - "Does he have a Force Of Nature? He might, or he might not."
In addtion, since each card can change the behavior of the other cards, the combinatorial growth of the game state is extremely large. You might be winning, then the other guy plays a card that completely changes how your cards act.
Given the above, much of the game is decided before you even sit at the table - how you construct your deck may decide the game, even before you see your opponent. AND you might change your deck, based on what you observe of the opponent's strategy.
Given the above, what I would like to see would be a computer program that could, given a set of N cards, compose a deck of M card (where M < N), play that deck against an opponent, then compose a new deck from the same N cards that answers the strategy of the opposing player.
When we can do that, THEN I'll believe we have real A.I.
Re:Westerner alert! (Score:2, Interesting)
It is the factorial. See, the first stone has 19x19 = 361 possible places, the second has one less (because of the previous stone occupied that) so two moves has 361*360. Repeat this until the board is full and you get 361! possible plays (this assuming that no pieces are removed and no positions are unplayable). For calculating large factorials just remember that
x! = exp(sum(i=1,x)ln(i))
so the above number is about exp(1768.75) is about 1.438e768 which means that we need a quantum computer with 2552 qubits to represent all the possible states of Go. Now imagine a Beowulf cluster of those ...
Re:First Chess machine (Score:3, Interesting)
And all because of some lying toe-rag... we get the clothes we stand up in today.
Go and Chess programs: its the branching factor (Score:5, Interesting)
Anyway, the other posts concerning the search branching factor difference in the two games are right on.
Typically, there are a few hundred possible legal moves in any Go position. It is simple to write an alpha-beta search that does well in chess because of the relatively small branching factor (the free Java AI web book on my site has an example).
Really, Go is an ideal testbed for AI, but currently the best Go programs are good engineering projects, but not really good AI projects. I would consider a great Go project to include these features:
-Mark
Re:Actually, he's right (Score:2, Interesting)
Perhaps I was being sloppy. I was thinking that since the board is roughly symmetrical, if either could win, it would be the one with the first move.
In any case, it doesn't matter. As long as the outcome is always one of the following possibilities, any fair match of an even number of games will ultimately result in a draw:
Even allowing for a strange state of affairs where Black can force a win, the above three possibilities absolutely limit any deterministic board game like chess, go, tic-tac-toe, etc. Either one of the sides can force a win, or both sides can force a draw. If e.g. Black can't force a draw, then either Black or White can force a win.
If White can always force a win, then every match of eight games will end 4-4. If Black can force a win, it will also be the case that every match of 8 games will end 4-4. If either side can force a draw, then every match of 8 games will end in 8 draws.
Realizing this is very simple if you just imagine that chess was as easy as tic-tac-toe. Adults don't play tic-tac-toe because they know a game played perfectly on both sides always results in a draw, and the perfect game is really easy to play.