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."

Comments

Re:We can at best hope a tie..

[wwwojtek]

(I've been told that the Japanese (or is it Chinese) game of Go is one such game)

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..

[Nigel Stepp]

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.

Fritz runs on an eight-processor Compaq machine

[Anonymous Coward]

They have a picture on their website.

Re:We can at best hope a tie..

[yeOldeSkeptic]

I've been told that the Japanese (or is it Chinese) game of Go is one such game.

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.

• 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.

Re:We can at best hope a tie..

[crulx]

While I personally would love harder Go opponents to play against on the computer, I don't feel that Go will get anywhere near the level of Chess for a long time. Jay Burmeister wrote an excellent paper on the topic of computational Go and I'll use some of his points to show why many Computer Scientists feel that Go will take significantly more work than Chess to acheieve a grandmaster level of play.

Features | Chess | Go
# moves in a game | ~80 | ~300
Branching factor | ~35 | ~200
Horizion effect | Applies basically at Grandmaster level | Applies at beginner level
End of game | Strictly defined checkmate | Loosely defined territory conquest(see seki and ko fights)
Evaluation of board position | Correlates to number and quality of pieces on board | Poor correlation with either pieces or territory

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

Re:We can at best hope a tie..

[legLess]

Blockquothe the poster:

My bet is that [go] will prove to be even easier than chess.

Yowza. I believe you're sincere, but you should do much more research before spouting off. You're flat-out wrong.

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.

Chess has at most 40 legal moves possible for the first move; go has 361. The average chess game has 40 moves; the average go game has 6 to 8 times that.

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.

Go requires the ability to look at patterns rather than combinations.

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 ... sometimes all the other stones.

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.

Um ... this is a sad series of non-sequiturs. Computers are stunningly bad at facial recognition, even in best-case scenarios. Humans, on the other hand, can recognize someone they haven't seen for 20 years based on a casual glance. Being social animals, there's literally nothing humans do better than pattern recognition, and go is all about pattern recognition.

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.