Towards AI – Monte Carlo Tree Search
Jan Novotny, Paul Bilokon, Aris Galiotos, Frédéric Délèze · 2019
This chapter focuses on elements of the machine learning literature leading to algorithms denoted as AI, or Artificial Intelligence. The key concept for the chapter is the distinction between exploration and exploitation. The machine learning methods introduced so far have been constructed such that they exploit the knowledge learnt from the training data set. The exploration steps, on the other hand, stand for actions made by the algorithm, which explores new paths. The chapter starts with a multi-armed bandit problem, which represents a textbook example of finding an optimal choice of slot machines in the casino without having prior knowledge about their performance. Then, it extends the introduced concepts and implements the Monte Carlo Tree Search algorithm, which is an algorithm behind many game engines. The chapter implements a particular method for tic-tac-toe. Further, it discusses the extension of the Monte Carlo Tree Search leading to AlphaGo engine.