So last month Go was officially conquered by AI. That means all of the classic board games are now dominated by computers.
How did AlphaGo do it?
The short answer is ... Monte-Carlo Tree Search + DeepLearning + More DeepLearning + Lots of Hardware.
Let's go through these elements in detail.
Start with the concept of a game. One way to look at it is like this: A game is a series of moves made in tandem with an opposing player. We want to make the best decisions. We want a machine that can tell us which decisions to make.
Go: Given a board state, tell me where to put the next stone.
So Go can be thought of as a sequence of board states and moves. Every move creates a new state which prompts a new move which leads to a new state and so on ... With Go (and most board games) the moves alternate between players so from the perspective of one player it's move creates new board state which leads to the opponent moving which leads to a new board state which leads to my next move ...
We can think about this in terms of a simpler game, Tic-Tac-Toe.
Thinking about games in this way means we can treat it as a search problem. Ideally, if we could expand the tree completely (i.e. try out every possible move until each possible end) we could easily pick our next move just by seeing where it leads. We could play "perfectly".
Of course, expanding the tree completely is not feasible for any normal game because the tree grows exponentially. For games with moderate or high branch factor, brute-force expansion of the tree is completely impossible. Even for tic-tac-toe it is unnecessary, because there exist obvious ways to reduce the complexity of the tree. For example, we don't have to consider board positions which are equivalent through rotation of mirroring.
In the next part I will try to write down what I know about the basic minimax algorithm.
