ÁRBOL DE JUEGOS: DEL ALGORITMO MINIMAX CON PODA α-β AL ALGORITMO MONTECARLO TREE SEARCH. FUERZA BRUTA VS ALEATORIEDAD

Resumen

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.