Orego: Artificial Intelligence and the Game of Go

How can we devise an artificially intelligent program to defeat top human players at the classical Asian game of Go?

Project Abstract

Go (Weiqi), the oldest strategy game in the world, was invented in China thousands of years ago. Its rules are simpler than those of Chess, but its strategies more subtle and profound. Top human Go players, unlike Chess players, can still easily defeat the most powerful computers. The space of possible board configurations is unfathomably vast, many orders of magnitude larger than the number of electrons in the universe. We suspect that human Go strength depends on the ability to decompose the game into local subproblems that are largely, but not quite, independent.
Orego and other Go programs have made huge strides in the last decade thanks to a surprising algorithm called Monte Carlo tree search. To decide on a move, the program plays thousands of simulated games against itself. After completing the simulations, the program chooses the move that most often led to a win. The moves in the simulated games are random, but biased by the results of previous simulations. A major challenge is determining when a configuration is "similar to" a previously-encountered one.
Techniques developed in this research will be applicable to a wide variety of difficult problems, from power plant management to transportation planning.

This is a unique website which will require a more modern browser to work! Please upgrade today!