Árbol de Juegos: Del Algoritmo Minimax con Poda α-β al Algoritmo Montecarlo Tree Search. Fuerza Bruta vs Aleatoriedad

Abstract

En este artículo, para juegos como el 3-en-raya (Tic-Tac-Toe), Conecta4, L, Damas, Othello, Ajedrez y Go entre otros, se discutirán dos famosos algoritmos de búsqueda en árboles llamados Minimax y Montecarlo Tree Search (abreviado como MCTS). Se tratará de descubrir la intuición detrás de los algoritmos de búsqueda en árboles. Después de eso, veremos cómo Minimax (con poda α-β) y MCTS se pueden usar en implementaciones de juegos clásicos y modernos para construir IA de juegos sofisticados. En dichos algoritmos se manifiestan dos formas de pensamiento computacional: en el Minimax la fuerza bruta con adecuadas funciones de evaluación, en el MCTS la aleatoriedad. El Ajedrez, según Herbert Simon, la Drosophila de la IA, ha sido superado por la máquina, caso de DeepBlue con sus entrañas de Minimax α-β, caso de AlphaZero con MCTS en sus venas.

In this article, for games like 3-in-a-row (Tic-Tac-Toe), Conecta4, L, Checkers, Othello, Chess and Go among others, two famous tree search algorithms called Minimax and Montecarlo Tree Search (abbreviated MCTS) will be discussed. The intuition behind the tree search algorithms will be commented. After that, we will see how Minimax (with α-β pruning) and MCTS can be used in both classic and modern game implementations to build sophisticated game AI. In these algorithms, two forms of computational thinking are manifested: in the Minimax, brute force with adequate evaluation functions, in the MCTS, randomness. Chess, according to Herbert Simon, the Drosophila of AI, has been overtaken by the machine, the case of DeepBlue with its guts of Minimax α-β, the case of AlphaZero with MCTS in its veins.