Mogo and the UCT Go Algorithm
Mogo and the UCT algorithm first beat a Master-level human opponent in Go on March 22, 2008 in a tournament hosted by the French Go Federation.
The Game of Go
It is a game of Chinese origin played on a board called a goban, measuring 19 x 19 squares, but often reduced to 13 x 13 or 9 x 9 squares.
Players place white or black stones at the intersections of the board lines, the game takes turns, the goal is to surround the opponent's stones to score points.
In this historical duel against the computer, a reduced board measuring 9 by 9 squares was used.
The game of go is similar to Othello, played on an 8 x 8 square board. In Othello, surrounded figures take on the color of the figures surrounding them and therefore change possession. Reversi is a variant of Othello.
Othello-Reversi software with a computer as an opponent has existed for a long time and uses simple algorithms like alpha-beta to replace the human player.
Go has nothing to do with Gomoku, which is a derivative of the game Tic-Tac-Toe. This has 3x3 fields and the goal is to create a line or diagonal of three pawns of the same color.
Mogo and the CPU algorithm
In 1998, the Deeper Blue program at IBM beat chess master Gary Kasparov for the first time. However, the game of go is more difficult to program, since the number of predicted moves is practically unlimited.
The best currently available Go player software is Mogo, developed by INRIA, CNRS and Paris-Sud.
This program uses the UCT algorithm to traverse the tree of possible moves.
UCT, Upper Bound Confidence for Tree, is derived from UCB, Upper Confidence Bounds, and includes the use of Monte Carlo as an evaluation feature.
The tree passes starting from the root of the current pawn position and passes using the UTC algorithm until the final node is reached. At this point, a computational function called Monte Carlo is applied. UCT goes through the same branches several times, but each time they are evaluated, and therefore it will strive to run along the most promising branches.
An improved version of the UCT algorithm uses a Monte Carlo simulation, which consists in filling the game with counters in an uncalculated way and counting the points of each player to assign a value to this terminal node.
The name Monte Carlo refers to the casino of the principality, and thus to gambling, which is the basis of the method used.
References: Mogo, master of the game? Explanation of the algorithm and UCT and Monte Carlo, presentation of the Mogo program. (PDF)
Algorithms