Juego del gato (tic-tac-toe) vía algoritmo minimax.

Me dejaron el ejercicio de hacer un juego de gato y escogí el camino de la inteligencia artificial de la vieja escuela. Pensé que era algo trivial pero si me costó varios días. Planeo hacer en vacaciones un video sobre el algoritmo minimax en mi canal porque los que hay tienen códigos que ahora me parecen innecesariamente complejos. La verdad es que, aunque mis amigos creen que lo digo sólo por modestia, soy muy pendejo para entender las cosas a la primera y más aún si no me explican paso a paso. Ya que vi claro todo el proceso recursivo me acordé del final de la película War Games. Les debo el video pero por ahora pueden consultar mi reporte aquí. La implementación que hice hace uso de la siguiente clase para instanciar los estados posibles del juego:

Contiene un método que verifica si el tablero ya esta lleno y otro que verifica si es el turno del jugador X. El pseudocódigo es el siguiente:

[click para agrandar]

La función evaluación() retorna +10 si 'X' gana la partida, -10 si 'O' gana y 0 si hay empate o si aún no hay ganador en ese estado. El código completo en Python lo pueden encontrar aquí. Este programa sólo tiene el fin de ayudar a entender el algoritmo minimax. No es una implementación eficiente ya que resuelve el problema por fuerza bruta repitiendo incluso el paso por varios estados ya visitados. Pueden mejorarlo añadiendo estrategias como poda alfa-beta o memorizando estados ya visitados.