[Computational Complexity] Computer Go
- While we have computer programs that have solved Checkers (it's a tie) and beat the world's best chess players, but until recently Go programs played a very mediocre game.Computers playing these kinds of games have a rough similar structure: Do a search through the game tree for some number of levels, evaluate the resulting game boards and do mini-max through the game tree to pick the best move for the player. There are many tricks to speed up the search (allowing a larger depth) such as alpha-beta pruning, selectively extending the tree search and various other tools but the basics run the same.The problem in Go is two fold: A very large number of moves at every turn forcing a very shallow tree and game boards that are very hard to evaluate. Much faster computers has helped in a getting at least a reasonable depth in the search. But what about evaluation?Consider the following seemingly crazy way to evaluate a game board: Have each player play randomly and see who wins. Repeat a few hundred times and score the position by the percent of time that White won.Imagine that strategy for chess: Each player would often put their pieces in jeopardy and the opponent would fail to take them. Most randomly simulated games would end in a draw because no one would execute the checkmate.But for Go the random process to evaluate positions works. Combined with a very fast machine, a well-designed tree search and lots of fine tuning this process had led to Computer Go programs that can play good games against strong amateurs.We're a long way from having Computer Go programs as the top Go players in the world but when a simple idea takes the power of Go programs from lousy to not bad in a relatively short time one can hope.
Posted By Lance to Computational Complexity at 8/10/2009 05:17:00 AM