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)
This story appeared 8 hours ago here...
If you ask a Korean, you'll be told that it's Korean (he might call it "baduk" though). Anyway, the point is that we are still years from seeing a machine that can beat a human with a few years of experience (not to mention a professional). The game has much more combinations than chess. The numbers I remember is something of the order of 10^720 distinct games that you can play in go vs. 10^120 in chess - they may be off by a bit but that's roughly the order of magnitude. On top of it, it is not that easy to prune unreasonable moves - in chess you can in most cases easily go down to a few moves to consider while in go it is easily 20 or more in the opening game. You cannot just rely on the brute force but rather on hard to formalize concepts of "shape" and "influence". That's what also makes the game fun.
I believe that this is just a conjecture. That is, no one knows whether or not is possible to force a draw, or whether it is possible to force a win. To really know this answer, one would have to know the game tree (or some equivalent).
Go does have a much bigger game tree, due to its much large branching factor. It was Chinese by origin.
4096R/EF7BAFA6 79E1 DF98 D09D 898F 9A11 F6F0 DDDC 23FA EF7B AFA6
They have a picture on their website.
I keep hearing about how go is much more difficult for a computer to play than is chess. The number of possible moves in go has nothing to do with its difficulty. Computer scientists have been trying to teach computers to play chess for at least half a century and it is only now that computers have become powerful enough and for the theory to advance enough that computers can hold the world chess champion to a tie. Go has not been analyzed and picked apart enough for us to say that it us much more difficult than chess.
Go has the advantage that you start with a bare board. In chess, the game always starts the same way. A computer that has in its memory a century's worth of master games should be at a distinct advantage. The fact that chess engines with million game databases can only manage a tie against a good human champion means computers have barely scratched the surface of chess. When a computer can beat Kasparov at fischer-random chess, I will concede.
Perhaps with the belief among computer chess researchers that chess has been solved will Go soon undergo the same nitpicking that chess has. My bet is that it will prove to be even easier than chess.
Here's why I think so.
"Junior" is world champion for computers.
Kasparov is (still) the best player in the world.
Kasparov will have to reduce the heat on the board. He does it successfully against human players but computers are more accurate in complicated positions.
I think that Kasparov has a good chance to win.
"Go pieces, once placed on the board, cannot move anymore. Chess pieces can still move from one place to the other. This means that as more and more Go pieces are placed on the board, there are less and less positions the computer has to consider."
"Go requires the ability to look at patterns rather than combinations. Sure, the Go board is larger and the possible positions are greater but then there are only three possible ``cells'' to consider: the first player's stone, the second player's stone and an empty cell. That should be easier to manage than the job we are asking computer's nowadays to do: recognize people from their faces. I believe computers can match fingerprints easily today. Go should be a walk in the park."
Ok, I think you've got the right theory, however you missed a few items in your assesment of Go.
- Randomness:
In the begining two-thirds of a game of Go most of the stone placements are "random". Yes some players attempt to mark out a territory but that can be self-defeating, reason being: when all the stones are played the game is over and the player with the largest total areas under his control wins. Sure, you're right that as the game progresses randomness drops. However, how does a computer deal with a human player who decides to give up on an area that is contested? And how will a computer decide when a contested area needs to be given up on?- Patterns:
In Go there are only a few "true" patterns to worry about. The Line (easy to deal with if you know the rules). The Box (a way to control an area). And The Spiral, when a contested area "spirals" out of control. The Go game becomes a miniture Mandlebrodt set that can loop off into infinity, if we had infinite stones to play with on an infinitely large 2D surface. Past that, all "patterns" should be treated as forms with a tactical value. One method of playing Go is to work your opponent into a corner that he cannot leave, a pattern and strategy that he cannot give up or he loses (or thinks he'll lose), which in the end will make him lose.- The Stones:
The player actually has more than 3 states to consider with his game peices. For each of his solitary pieces there are 4 possible ways that it can be surrounded and taken. If there are pieces in contiguous strings or blocks the player must see how many sides are open to attack from an enemy. And if he happens to have a hole in the middle of his string (shape) or block, the player has to consider if that hole is large enough to allow an enemy to capture his pieces.IMHO Go will be harder to program than chess. Even considering the exponentially decreasing randomness there is still that first random placement, and as we all know... there is no true random-number generator program yet devised.
Once more into the birch deer fiends!
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."
This point comes up a lot, and is true but misleading. To solve chess using a minimax tree, the storage space required is proportional to the length of the longest game (which is bounded above by 4050 due to the 50-move rule), and which is likely to be on the order of log of the number of games. It is the *time* that is proportional to the number of games. Still not in sight, but not impossible.
Free Java games for your phone: Tontie, Sokoban
http://www.therockalltimes.co.uk/2002/10/21/chess- excitement.html has more details.