Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Computer Go

Expand Messages
  • Lance
    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
    Message 1 of 1 , Aug 10, 2009
    View Source
    • 0 Attachment
      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
    Your message has been successfully submitted and would be delivered to recipients shortly.