¿Alguna vez has jugado al ajedrez contra el ordenador y te has preguntado cómo es capaz de jugar sin fallos? 

La respuesta es sencilla, los ordenadores siguen unos algoritmos, es decir, una serie de reglas con la que determina qué movimiento realizar, uno de estos algoritmos es el minimax.

Este algoritmo es muy popular en la teoría de juegos y consiste en buscar el movimiento que más ventaja te da suponiendo que tu contrincante realiza un movimiento que te deja en desventaja. Para ello el ordenador construye un árbol con todos los posibles movimientos y busca el más ventajoso.

Para entender mejor este algoritmo trabajaremos sobre el juego del 3 en raya y programaremos el juego para jugar unas partidas contra nuestro ordenador. Partiendo de un estado inicial como puede ser el de la figura, el algoritmo realizará los siguientes pasos.

PASO 1.

Primero el ordenador realiza todos los posibles movimientos que se realizan para acabar la partida.

PASO 2.

Después atribuimos un valor a los estados finales, este valor depende de si el ordenador gana, pierde o empata. En este caso asignamos el valor 1 si X gana, siendo X el ordenador. Por otra parte asignamos el valor -1 si el ordenador pierde, es decir, cuando gana O. En caso de empate asignamos a estos estados el valor 0.

PASO 3.

Finalmente el algoritmo lo que hace es partir desde las hojas del árbol maximizando el valor de la jugada cuando le toque jugar al ordenador y minimizando cuando juega el ordenador.

En el siguiente vídeo se explica el algoritmo : https://www.youtube.com/watch?v=QJjM7EKDRuc

Para desarrollar este algoritmo en el lenguaje python usaremos Google Colaboratory o más comúnmente conocida como Colab. Además de desarrollar nuestro código Python desde la nube podremos añadir notas y cuadros de texto como si fuera un cuaderno. Es muy utilizado en el ámbito de la ciencia de datos y machine learning ya que no requiere configuración y proporciona GPU’s de manera gratuita.

A continuación realizaremos un cuaderno de introducción al colab mediante el siguiente enlace:

Una vez acabado el cuaderno comencemos a programar el algoritmo:

Existen versiones más complejas del algoritmo como la que podemos ver el siguiente notebook que lo complica añadiéndole una penalización por tiempo:

https://colab.research.google.com/drive/1-4juncrgfqwA1gCdMMSi6lTji9CbKy82?usp=sharing

Y para profundizar podemos ver en que consiste el algoritmo de poda alfa beta que es más eficiente que el minimax

profundizar en el algoritmo con poda alfa beta https://www.youtube.com/watch?v=I0y-TGehf-4

Este tutorial ha sido desarrollado por Óscar Cabrera, graduado en matemáticas e informática, durante el programa de becas de formación práctica en 2021 del cabildo de Fuerteventura.