Slashdot Mirror
Kramnik Ties Fritz; Machines Not Yet Our Masters
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."
← Back to Stories (view on slashdot.org)
or are we going to start getting The Onion inspired subject titles?
--
# Canmephians for a better Linux Kernel
$Stalag99{"URL"}="http://stalag99.net";
Chess is nothing. I'll be impressed when an A.I. chat bot can talk a girl into a date. This would be a tool every slashdotter could appreciate.
Linux. Because a 386 is a terrible thing to waste.
If two chess players play perfectly, then the game will always result in a tie
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."
-- Kircle
Alcohol and Calculus don't mix. Don't drink and derive.
The problem with this is that defining "perfect play" is next to impossible in chess. Different players have very different playing styles, and if player A is strong against player B, and B is strong against C then it doesn't necessarily mean that A could defeat C.
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.
When men used to be men
One oft-quoted complaint by Kasaarov, of the last man-vs-machine match against Deep Blue, was that Deep Blue was programmed with the moves of all of Kasparov's past championship games so it could ostensibly analyze the strategies used by Kasparov beforehand, while Kasparov was not allowed to look at Deep Blue's previous games.
Anyone know if this was ever an issue in this current tournament?
There's 10 types of people in this world, those who understand binary and those who don't.
There was a time when people put a lot of weight on a computer being able to play a high level of chess, but that was before the advent of a strategy that is best characterised as massive parallel brute force solution of a game with a very large tree of possible moves.
Nowadays, there really is very little point. You are comparing apples to oranges when you allow the one party a nearly infinite budget of cycles and power and allow the other party 18 cycles per second on a biological processor that is running on a couple of oranges for a whole games' worth of computation.
I we want to make this kind of competition interesting again I think there really should be limits on the power and cycle budget of the machine involved in order to get back to the essence of the whole game theory thing, which is not going flat out for the maximum number of ply you can look ahead but to try to quantify a strategic advantage.
Unfortunately that will not make for interesting press releases.
To me the current 'matches' look a little bit like sledgehammers being used to crack nuts. It does work, but there is no real output. All this stuff proves is that if you throw enough money at a problem you can force the outcome of something as trivial as a game of chess.
It does not advance the state of the art in computing at all.
MP3 Search Engine
...It's Man vs. Nature.
Kramnik and Kasparov are the best chess players that nature can produce. Meanwhile, humans have built Fritz and Deep Blue. We aren't in the process of losing to machines. We're in the process of beating nature.
There was a young Russian named Kramnick
Who at chess was just real frickin' slick,
He came back in a blitz
But could only tie Fritz
he exclaimed "just a tie, and my wallet's so thick!"
(sorry)
Cake or Death? Cake Please!
A quote from his paper may also help,
"3.3 Why Go Cannot be Programmed Like Chess
Chess programs typically use a heuristic search and evaluation technique. Search trees of board positions are generated to a fixed depth and are heuristically pruned according to an evaluation of the merit of the board positions. This approach works well in Chess because the board size is sufficiently small and the nature of Chess is more tactical than strategic.
Evaluation of a board position in Go presents problems not encountered in Chess. Go is a much more strategic game in comparison to Chess. Unlike Chess, Go does not focus around the capture of a single piece. Positional advantages are slowly built up in achieving the long term goal of acquiring more territory than the opponent. There are many direct and indirect ways to achieve this goal such as making territory, building influence, attacking weak enemy groups, securing friendly groups, destroying enemy territory etc. Due to the large size of the board, a Go game is comprised of many small local skirmishes. If a game of Chess were described as a battle, a game of Go could be described as a war. Many good tactical moves at the local level must all compete for selection in the context of strategic global considerations. Thus a player must balance resources to achieve local goals at many locations whilst trying to pursue an overall global objective."
Read more about computer Go at Mike's Computer Go. Sit down and try a game of Go for yourself and you will see why computers won't get to the same level anytime soon.
crulx
So yes, after each move there are fewer go positions, but after 80 stones have been placed (the average number of chess moves), there are still 281 moves possible. You have to play more than 200 moves into a go game before you have as few move possibilities as you do for your first move in chess. If by "combinations" you mean "tacics," you're incorrect. Tactics are crucial in go, and it's only by a solid understanding of tactics that strategic thinking is possible. It's true that the rules of chess tactics are more complex than go, but it's precisely this lack of rules and formulae that make go so hard for computers.
Go's not nearly as easily quantifiable. You can tell a chess computer that the king is worth 10,000,000 pawns, the queen 9, bishops and knights 3 or 3.5. In go, however, the only thing giving value to a stone is its position on the board and its relation to other stones
I think I realize what you're trying to say, though - that there are only three states for one position on a go board, while there are many more for a chess board. This is immaterial to the game. The problem computer programmers have with go is that there's no algorithm that will reliably determine if a group of stones is alive or dead without brute-forcing the entire game. Many groups can be correctly evaluated, and computers are good at scoring finished games, but computers will happily slog ahead (and lose horribly) in games that professionals would resign in disgust.
Read a few of these pages and then reconsider your viewpoint:
- NYT article (archived offsite - no pwd) from 1997
- AI-Depot article comparing chess and go.
- Google cache of chess vs. go article (slightly fluffy and biased towards go)
- The Sciences article
Note that I'm not saying go is better than chess. I think such arguments are foolish. But, to quote myself, from a computer's perspective go makes chess look like tic-tac-toe.This isn't as much "normalization" as it is "don't take so many drugs when you're designing tables."
Hello, sorry, but... Go has not been analyzed and picked apart enough for us to say that it us much more difficult than chess.
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
You need to learn more about the game, I think, before you try to explain it to others.
This isn't as much "normalization" as it is "don't take so many drugs when you're designing tables."
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