How can a computer learn Go by playing random games?

By playing a position out to the very end, many times, with random moves, and counting which moves tend to win. This method, Monte Carlo tree search, then spends more of its effort on the moves that won most often, so its search tree grows unevenly toward the promising branches; that is why it beats classical search in games with many possible moves at each turn, like Go. Google DeepMind's AlphaGo paired it with neural networks that judge moves and positions, and in October 2015 became the first program to beat a professional Go player on a full 19x19 board without a handicap.

The idea traces back further than Go. In 1987, Bruce Abramson combined classic game-tree search with an expected-outcome model based on random game playouts instead of a static scoring formula. In 1992, B. Brügmann first used this random-playout idea in a Go-playing program. In 2006, Rémi Coulom formally named the technique Monte Carlo tree search, and the same year Kocsis and Szepesvári introduced UCT, a formula that balances moves with a high win rate against moves that have barely been tried.

Each round of the search follows four steps: selection, where the algorithm walks down the tree picking promising child positions; expansion, where it adds a new position to explore; simulation, where it plays a random game out to the very end from that new position; and backpropagation, where the result updates the win counts for every position along the path. Positions that won more often get revisited more often, so the search naturally spends its effort on the moves that look best, without ever needing to fully analyze the entire game.

In March 2016, AlphaGo was awarded an honorary 9-dan master rank after defeating champion Lee Sedol four games to one. What made AlphaGo a genuine milestone was combining Monte Carlo tree search with neural networks, letting the program judge which moves and positions were promising far more efficiently than random playouts alone ever could.