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

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