About a decode ago a computer finally beat the best chess mind on the planet. Computers can play nearly every game we've invented better than us. However, one game stands out as unbeaten. The ancient Chinese game of Go. The Times of London has an interesting article on why the computer still can't beat an average human Go player.
The computer can play chess because it can calculate the results of all possible moves and then pick the best one. In chess, there are usually 25-35 possible moves at any point. In Go, there are 250. This makes the brute force strategy a lot harder. Almost impossibly hard. The thinking goes that playing Go well is all about recognizing patterns--something computers are notoriously bad at. If so, being able to play Go well would be a breakthrough affecting lots of other areas of computing from vision to AI.
This reminds me, I still have to find the time to learn to play Go. It's one game I've never played yet.
Steve Rowe linked to an essay on why computers can't play Go well even though they've mastered
ReplyDeleteI highly suggest learning to play. There are only 6 or 7 rules (and most of them are corner cases). You can play on-line, such as at the KGS server, which automatically ranks you, so it's easy to play against people your level. It's frustrating at first because you'll suck a lot, though :p
ReplyDeletes/Computers/Computer Programmers/
ReplyDeleteThe immense size of the search space is, it must be admitted, a daunting problem. But it shouldn't be a killer; there are many problems with as large or bigger state spaces that have been solved.
Consider the following "game" similar to Go:
Two players; one with black stones, one with white stones. Black goes first.
The board is a 19x19 grid. Players take turns; a turn consists of placing a stone on a vacant spot on the grid.
There is no capturing. The game ends when the board is full. The last player to place a stone wins.
This state space is only slightly smaller than Go, but it is trivial to write a program that plays as well as the best human mind... because Black always wins!
Chess turned out to be tractable to computers, in part because computing power increased, but mostly because computer programmers figured out ways of encoding "chess wisdom" into heuristics; in other words, teaching the computer to /play chess/ rather than relying on calculating power.
I personally hold out hope that computer programmers may yet find a way to encode "Go wisdom" in a similar fashion. The article is sadly silent on why "Go wisdom" is so much harder to codify than "chess wisdom"; the wikipedia has some thoughts... the phrase "pattern recognition" is tantalizing in its essential ambiguity.
> the wikipedia has some thoughts
ReplyDeleteIn particular:
http://en.wikipedia.org/wiki/Computer_Go
Most people point out the difference in search space size between chess and Go, but few mention the difficulties in constructing a tolerably good evaluation function for Go. In chess, the evaluation function is quite simple, essentially weighted sum of pieces owned with some tactical considerations (like doubled pawns, isolated pawns, center control etc) thrown in, and very fast to calculate. In Go, evaluation is much more complex, and this is much harder on computer Go programmers than mere size of search space, because efficient minimax pruning algorithms on which Deep Blue relies become practically useless.
ReplyDeleteThe victory condition in chess (checkmate) is also simple to evaluate. Meanwhile, even writing a program which *scores* finished Go games accurately is quite a challenge, never mind determining whether a given game is actually finished.
As concerns master-level (or even strong amateur-level) computer Go programs, being both a programmer and a 2 dan amateur, I'm not holding my breath. Anecdotal evidence suggests that there is a "curse" on this problem, i.e. those programmers whose programs begin to approach about 6-7 kyu level, abandon their projects. By the way, the ranks awarded to programs are a joke, commonly 4-5 ranks stronger than the program actually plays.
I've tried to play GO, and actually, I can attest the rules are really simple. However, in some games I thought I was having an advantage in some area of the board, and the opposite player (who was an amateur) always told me: "See, this pattern here is really bad because...".
ReplyDeleteAlso, when I sa a game played by two strong players, I had no idea at all who was winning!