The game of Go may have simple rules, but to play successfully requires enormous skill. Few computer programs are able to navigate through the unimaginable number of possible moves and find the best strategy. The solution, as shown by MoGo, is not even to attempt to look at all the possibilities. Instead, a randomised exploration of the options based on multi-arm bandits makes this problem more manageable. The secret behind the early success of MoGo was Upper Confidence Trees.	sampling is used to build an approximate picture of where the ships are on the grid. When applying Monte Carlo search to a game tree, this equates to evaluating many branches of the tree chosen randomly to see which player might eventually win or lose if those moves were followed, and then deciding on the best branch to follow. Traditional Monte Carlo methods might iteratively search the game tree, deeper and deeper, but they sampled each branch with a uniform probability. An even better approach, as introduced by researchers Levente Kocsis and Csaba Szepesvári in 2006, is to bias the random sampling of branches.
The idea of using machines to take the role of our opponent in a game arose even before computers had been created. Chess has long attracted the attention of designers of these machines. While the very earliest chess automata were frauds, by the 1950s the subject was being considered seriously. According to Claude Shannon in 1950, we should think of the game as an imaginary tree branching out from the current state of the board. Each possible move was another branch from the current state; follow a branch and you reach a new board state from which new branches grow. Chess has a lot pieces and a lot of possible moves by each piece, making the game tree vast. Even the most powerful supercomputers cannot search all of this tree. However by the late 1990s and early 2000s, our best computers were fast enough to search significant parts of the tree. Computers such as Deep Blue and later Deep Fritz were able to beat human chess grand masters using these brute-force approaches.
This project (or adventure...) has been really a wonderful collaborative work which has led to some advances not only in the field of Go, but also which has opened new perspectives in other fields as well.
But the game of Go was another matter entirely. Compared to chess, which may have around 37 legal moves possible each turn on average, Go has rarely fewer than 50 moves possible, and typically over 200 each turn. This means that the game tree for Go is considerably larger than the one for chess. So even with the very fastest supercomputers, a brute-force search for good moves simply doesn’t work for the game of Go. Monte Carlo search is one useful way to make vast search spaces more manageable. Instead of trying to exhaustively search the whole space, a Monte Carlo method randomly samples points in the space and then uses the results of that sampling to approximate the solution. It’s like the game of Battleship, where random