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."
Related older link... (Score:3, Informative)
Re:We can at best hope a tie.. (Score:4, Informative)
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.
Re:We can at best hope a tie.. (Score:4, Informative)
Go does have a much bigger game tree, due to its much large branching factor. It was Chinese by origin.
Re:Yeah but Fritz isn't the best player (Score:3, Informative)
Here's the link [cnn.com], and here's the quote:
"Deep Fritz has previously beaten Deep Blue, Kasparov and World Chess Federation champion Vishwanathan Anand."
Re:Too bad... (Score:3, Informative)
The Comparison:
Deep Blue could analyze 200 million possible moves per second, while Deep Fritz looked at a paltry 3 million moves a second. However, programmers said Fritz was designed to look more intelligently at the moves ahead, rather than using Deep Blue's brute-force method.
And What happened to Deep Blue:
Back in 1997, IBM created Deep Blue specifically for the Kasparov challenge, using 200 special-purpose chess chips, 32 processors and a score of programmers. Since the system didn't have commercial value, it was broken down after the match. In contrast, Deep Fritz is a souped-up version of a commercially available product published by the German company Chessbase, running on eight 900mHz Pentium chips.
Re:Too bad... (Score:4, Informative)
Fritz is very easy to use but very difficult to beat. Since 1993 the program has been the enfant terrible of the chess scene. In Munich it won the strongest blitz tournament of all times, together with world champion Garry Kasparov; in 1995 it won the world computer chess championship in Hong Kong, ahead of Deep Blue; in July 1999 it won the super-strong Frankfurt Masters and thus qualified to play against the world champion next year. Fritz is used by all top players in the world and is the most popular chess program amongst tournament players.
Winning the world computer chess championship ahead of deep blue is not the same as playing against deep blue. It could easily be said that Fritz found a particular weakness in another program which found a particular weakness in Deep Blue. That Fritz might find that same weakness or another one against deep blue itself is unknown unless they did play against each other. But this is how most sporting games are held in modern times. Computers, however, are less susceptable to time, weather, and other variations humans are so subject to that make us play 'a bad game'.
-Adam
Re:Not masters, but equals (Score:3, Informative)
You seem to imply that eventually computers will equal human being's in life. Trying to say that a computer could ever equal a human being is silly and ignorant. The human brain is infinitely more complex than any computer could ever be; a single neuron is more complex than a computer could ever be.
You simply cannot do in the time that humans have, what took evolution over a billion years to accomplish.
Fritz runs on an eight-processor Compaq machine (Score:4, Informative)
Re:Not masters, but equals (Score:4, Informative)
Sure, a bacteria doesn't have trillions of individual parts. Neither do human beings; there are only 30,000 - 100,000 genes.
But E. coli are trillions of times more complex than our most complex computers, and human beings are trillions of times more complicated than E. coli.
E. coli may not have many different "working parts" in your layman terms, but the way in which those finite parts interact and are regulated and modulated are infinitely complex; far more complex than any computer system we have -- more complex than the entire internet, basically a set of interconnected computer systems.
Take a look at the 3D structure of one protein. It's pretty complicated; so complicated, in fact, that the most powerful computers we have can't accurately predict how a protein sequence will fold. That's just one protein. Proteins synthesis is regulated by both transcription (DNA -> RNA) and translation (RNA -> protein), as well as by post-translational factors, such as other proteins which bind to and modify the activity of your protein. A kinase is a protein which phosphorylates other proteins; depending on which cyclin a cyclin-dependant kinase is bound to, it may phosphorylate different proteins.
Sure, the number of parts of even the most complicated living systems (human beings) are very finite (100,000 genes max). But they way in which they interact and are regulated is infinitely complex.
Computers may be great, but they're simple -- very simple. Even a layman can, with a little bit of education, understand exactly how a computer works. But the most intelligent biologist alive isn't anywhere near understanding how a single cell works in its entirity.
Before you go about demeaning any form of life to being simpler than a computer, perhaps you should try to gain some understanding of the complexity of even the most "simple" life.
Re:We can at best hope a tie.. (Score:4, Informative)
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.
Soon: Kasparov vs "Junior" in Jerusalem (Score:2, Informative)
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.
Re:We can at best hope a tie.. (Score:3, Informative)
"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.
Re:Too bad... (Score:2, Informative)
An older slower machine. This match is a crock because the computer used is substantially slower and weaker than the one that beat Kasparov. They're jerking us around. Deep Blue type machines are now as strong as the strongest players. They're just milking this for all it's worth. Hyping it into something it can't be. The best chess playing machine has been disassembled. Do this for info about deep blue:
Go to Google groups, restrict your search to the *chess* newsgroups and type in "crazybird" for the search term. The 2nd and 3rd hits are interviews with the creator of deep blue. It's good stuff, read it.
These articles make me wonder how much misinformation goes into my head thru slashdot. I just don't know enough to discredit it in most other topics.
Re:We can at best hope a tie.. (Score:5, Informative)
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. [demon.co.uk] 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
Re:We can at best hope a tie.. (Score:5, Informative)
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 [anusha.com]
- AI-Depot article comparing chess and go. [ai-depot.com]
- Google cache of chess vs. go article (slightly fluffy and biased towards go) [216.239.33.100]
- The Sciences article [nyu.edu]
Note that I'm not saying go is better than chess. I think such arguments are foolish [slashdot.org]. But, to quote myself, from a computer's perspective go makes chess look like tic-tac-toe.Re:We can at best hope a tie.. (Score:3, Informative)
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.
More coverage here (Score:2, Informative)