Minimax con poda alfa-beta en Python

Ya a fines de la década de 1920, John Von Neumann estableció el problema principal en la teoría de juegos que sigue siendo relevante hoy en día: los jugadores s1, s2, ..., sn son pl...

Introducción

Allá por finales de la década de 1920 Juan Von Neumann estableció el principal problema de la teoría de juegos que sigue siendo relevante hoy en día:

Los jugadores s~1~, s~2~, ..., s~n~ están jugando un juego determinado G. ¿Qué movimientos debería hacer el jugador s~m~ para lograr el mejor resultado posible?

Poco tiempo después, problemas de este tipo se convirtieron en un desafío de gran importancia para el desarrollo de uno de los campos más populares de la informática en la actualidad: la inteligencia artificial. Algunos de los mayores logros en inteligencia artificial se logran en el tema de los juegos estratégicos: los campeones mundiales en varios juegos estratégicos ya han sido derrotados por computadoras, p. en ajedrez, damas, backgammon y, más recientemente (2016), incluso en go.

Aunque estos programas son muy exitosos, su forma de tomar decisiones es muy diferente a la de los humanos. La mayoría de estos programas se basan en algoritmos de búsqueda eficientes y, desde hace poco, también en aprendizaje automático.

El Algoritmo minimax es un algoritmo relativamente simple utilizado para la toma de decisiones óptimas en teoría de juegos e inteligencia artificial. Una vez más, dado que estos algoritmos se basan en gran medida en ser eficientes, el rendimiento del algoritmo vainilla se puede mejorar considerablemente mediante el uso de la poda alfa-beta; cubriremos ambos en este artículo.

Aunque no analizaremos cada juego individualmente, explicaremos brevemente algunos conceptos generales que son relevantes para dos jugadores [no cooperativo] (https://en.wikipedia.org/wiki/Non-cooperative_game_theory) resumen cero simétrico juegos con [información perfecta](https://en. wikipedia .org/wiki/Perfect_information) - Ajedrez, Go, Tic-Tac-Toe, Backgammon, Reversi, Damas, Mancala, 4 en raya, etc.

Como probablemente hayas notado, ninguno de estos juegos son aquellos en los que, p. un jugador no sabe qué cartas tiene el oponente, o dónde un jugador necesita adivinar cierta información.

Definición de términos

Las reglas de muchos de estos juegos están definidas por posiciones legales (o estados legales) y movimientos legales para cada posición legal. Para cada posición legal es posible determinar efectivamente todos los movimientos legales. Algunas de las posiciones legales son posiciones iniciales y otras son posiciones finales.

La mejor manera de describir estos términos es usando un gráfico de árbol cuyos nodos son posiciones legales y cuyos bordes son movimientos legales. El gráfico está dirigido ya que no necesariamente significa que podremos retroceder exactamente de donde vinimos en el movimiento anterior, p. en el ajedrez un peón solo puede avanzar. Este gráfico se llama árbol de juego. Desplazarse hacia abajo en el árbol del juego representa que uno de los jugadores realiza un movimiento y el estado del juego cambia de una posición legal a otra.

Aquí hay una ilustración de un árbol de juego para un juego de tres en raya:

Las cuadrículas de color azul son los turnos del jugador X, y las cuadrículas de color rojo son los turnos del jugador O. La posición final (hoja del árbol) es cualquier cuadrícula donde uno de los jugadores ganó o el tablero está lleno y no hay ganador.

El árbol de juego completo es un árbol de juego cuya raíz es la posición inicial y todas las hojas son las posiciones finales. Cada árbol de juego completo tiene tantos nodos como resultados posibles tiene el juego para cada movimiento legal realizado. Es fácil notar que incluso para juegos pequeños como tic-tac-toe, el árbol de juegos completo es enorme. Por esa razón, no es una buena práctica crear explícitamente un árbol de juego completo como estructura mientras se escribe un programa que se supone debe predecir el mejor movimiento en cualquier momento. Sin embargo, los nodos deben crearse implícitamente en el proceso de visita.

Definiremos complejidad de espacio de estado de un juego como una cantidad de posiciones de juego legales que se pueden alcanzar desde la posición inicial del juego, y factor de ramificación como la cantidad de niños en cada nodo (si ese número no es t constante, es una práctica común usar un promedio).

Para tres en raya, un límite superior para el tamaño del espacio de estado es 3^9^=19683. ¡Imagina ese número para juegos como el ajedrez! Por lo tanto, buscar en todo el árbol para averiguar cuál es nuestro mejor movimiento cada vez que nos turnamos sería muy ineficiente y lento.

Esta es la razón por la que Minimax tiene una importancia tan grande en la teoría de juegos.

Teoría detrás de Minimax

El algoritmo Minimax se basa en la búsqueda sistemática, o dicho con mayor precisión, en fuerza bruta y una función de evaluación simple. Supongamos que cada vez que decidimos el próximo movimiento buscamos a través de un árbol completo, hasta las hojas. Efectivamente, analizaríamos todos los resultados posibles y cada vez podríamos determinar el mejor movimiento posible.

Sin embargo, para juegos no triviales, esa práctica es inaplicable. Incluso buscar hasta cierta profundidad a veces lleva una cantidad de tiempo inaceptable. Por lo tanto, Minimax aplica la búsqueda a una profundidad de árbol bastante baja con la ayuda de [heurística] adecuada (https://en.wikipedia.org/wiki/Heuristic) y una función de evaluación bien diseñada pero simple.

Con este enfoque perdemos la certeza de encontrar el mejor movimiento posible, pero la mayoría de los casos la decisión que toma minimax es mucho mejor que la de cualquier humano.

Ahora, echemos un vistazo más de cerca a la función de evaluación que hemos mencionado anteriormente. Para determinar un buen movimiento (no necesariamente el mejor) para un determinado jugador, tenemos que evaluar de alguna manera los nodos (posiciones) para poder comparar uno con otro por calidad.

La función de evaluación es un número estático, que de acuerdo con las características del propio juego, se va asignando a cada nodo (posición).

Es importante mencionar que la función de evaluación no debe basarse en la búsqueda de nodos anteriores, ni de los siguientes. Simplemente debe analizar el estado del juego y las circunstancias en las que se encuentran ambos jugadores.

Es necesario que la función de evaluación contenga la mayor cantidad de información relevante posible, pero por otro lado, dado que se calcula muchas veces, debe ser simple.

Por lo general, mapea el conjunto de todas las posiciones posibles en un segmento simétrico:

$$
\mathcal{F} : \mathcal{P} \rightarrow [-M, M]
$$

El valor de ‘M’ se asigna solo a las hojas en las que el ganador es el primer jugador, y el valor de ‘-M’ a las hojas en las que el ganador es el segundo jugador.

En los juegos de suma cero, el valor de la función de evaluación tiene un significado opuesto: lo que es mejor para el primer jugador es peor para el segundo y viceversa. Por lo tanto, el valor de las posiciones simétricas (si los jugadores cambian de rol) debería ser diferente solo por el signo.

Una práctica común es modificar las evaluaciones de las hojas restando la profundidad de esa hoja exacta, de modo que, de todos los movimientos que conducen a la victoria, el algoritmo pueda elegir el que lo hace en el menor número de pasos (o elige el movimiento que pospone pérdida si es inevitable).

Aquí hay una ilustración simple de los pasos de Minimax. Estamos buscando el valor mínimo, en este caso.

La capa verde llama al método Max() en los nodos secundarios y la capa roja llama al método Min() en los nodos secundarios.

  1. Evaluación de las hojas:

  1. Decidir el mejor movimiento para el jugador verde usando profundidad 3:

La idea es encontrar el mejor movimiento posible para un nodo dado, profundidad y función de evaluación.

En este ejemplo hemos asumido que el jugador verde busca valores positivos, mientras que el jugador rosa busca valores negativos. El algoritmo evalúa principalmente solo los nodos a la profundidad dada, y el resto del procedimiento es recursivo. Los valores del resto de nodos son los valores máximos de sus respectivos hijos si es el turno del jugador verde, o de forma análoga, el valor mínimo si es el turno del jugador rosa. El valor en cada nodo representa el siguiente mejor movimiento considerando la información dada.

Mientras buscamos en el árbol del juego, estamos examinando solo los nodos en una profundidad fija (dada), no los anteriores ni los posteriores. Este fenómeno suele denominarse el efecto horizonte.

Abrir libros y Tic-Tac-Toe

En los juegos de estrategia, en lugar de dejar que el programa inicie el proceso de búsqueda al principio del juego, es común usar los libros de apertura: una lista de movimientos conocidos y productivos que son frecuentes y que se sabe que son productivos mientras aún estamos No tenemos mucha información sobre el estado del juego si miramos el tablero.

Al principio, es demasiado temprano en el juego y la cantidad de posiciones potenciales es demasiado grande para decidir automáticamente qué movimiento conducirá a un mejor estado del juego (o victoria).

Sin embargo, el algoritmo vuelve a evaluar los próximos movimientos potenciales en cada turno, eligiendo siempre lo que en ese momento parece ser la ruta más rápida hacia la victoria. Por lo tanto, no ejecutará acciones que requieran más de un movimiento para completarse, y es incapaz de realizar ciertos "trucos" bien conocidos debido a eso. Si la IA juega contra un humano, es muy probable que el humano pueda evitarlo de inmediato.

Si, por otro lado, echamos un vistazo al ajedrez, nos daremos cuenta rápidamente de la impracticabilidad de resolver el ajedrez por fuerza bruta a través de un árbol de juego completo. Para demostrar esto, claude shannon calculó el límite inferior de la complejidad del árbol de juegos del ajedrez, lo que resultó en aproximadamente 10^120^ juegos posibles.

¿Qué tan grande es ese número? Como referencia, si comparamos la masa de un electrón (10^-30^kg) con la masa de todo el universo conocido (10^50^-10^60^kg), la relación sería del orden de 10 ^80^-10^90^.

Eso es ~0.0000000000000000000000000000000001% del número de Shannon.

Imagine encargar a un algoritmo que analice todas y cada una de esas combinaciones solo para tomar una sola decisión. Es practicamente imposible de hacer.

Incluso después de 10 movimientos, la cantidad de juegos posibles es tremendamente grande:


Número de jugadas Número de juegos posibles 1 20 2 40 3 8,902 4 197,281 5 4.865.609 6 119,060,324 7 3.195.901.860 8 84.998.978.956 9 2.439.530.234.167 10 69.352.859.712.417


Llevemos este ejemplo a un juego de tres en raya. Como probablemente ya sepa, la estrategia más famosa del jugador X es comenzar en cualquiera de las esquinas, lo que le da al jugador O la mayor cantidad de oportunidades para cometer un error. Si el jugador O juega cualquier cosa además del centro y X continúa con su estrategia inicial, es una victoria garantizada para X. Los libros de apertura son exactamente esto: algunas formas agradables de engañar a un oponente desde el principio para obtener ventaja, o en el mejor de los casos, un victoria.

Para simplificar el código y llegar al núcleo del algoritmo, en el ejemplo del próximo capítulo no nos molestaremos en usar libros de apertura ni trucos mentales. Dejaremos que el minimax busque desde el principio, así que no se sorprenda de que el algoritmo nunca recomiende la estrategia de la esquina.

Implementación Minimax en Python

En el siguiente código, usaremos una función de evaluación que es bastante simple y común para todos los juegos en los que es posible buscar en todo el árbol, hasta las hojas.

Tiene 3 valores posibles:

  • -1 si el jugador que busca el mínimo gana
  • 0 si es empate
  • 1 si el jugador que busca el máximo gana

Dado que implementaremos esto a través de un juego de tres en raya, repasemos los componentes básicos. Primero, hagamos un constructor y dibujemos el tablero:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# We'll use the time module to measure the time of evaluating
# game tree in every move. It's a nice way to show the
# distinction between the basic Minimax and Minimax with
# alpha-beta pruning :)
import time

class Game:
    def __init__(self):
        self.initialize_game()

    def initialize_game(self):
        self.current_state = [['.','.','.'],
                              ['.','.','.'],
                              ['.','.','.']]

        # Player X always plays first
        self.player_turn = 'X'

    def draw_board(self):
        for i in range(0, 3):
            for j in range(0, 3):
                print('{}|'.format(self.current_state[i][j]), end=" ")
            print()
        print()

{.icon aria-hidden=“true”}

Todos los métodos anteriores, excepto el método principal, pertenecen a la clase Juego.

Hemos hablado de movimientos legales en las secciones iniciales del artículo. Para asegurarnos de cumplir con las reglas, necesitamos una forma de verificar si un movimiento es legal:

1
2
3
4
5
6
7
8
# Determines if the made move is a legal move
def is_valid(self, px, py):
    if px < 0 or px > 2 or py < 0 or py > 2:
        return False
    elif self.current_state[px][py] != '.':
        return False
    else:
        return True

Entonces, necesitamos una forma sencilla de comprobar si el juego ha terminado. En tres en raya, un jugador puede ganar conectando tres símbolos consecutivos en una línea horizontal, diagonal o vertical:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Checks if the game has ended and returns the winner in each case
def is_end(self):
    # Vertical win
    for i in range(0, 3):
        if (self.current_state[0][i] != '.' and
            self.current_state[0][i] == self.current_state[1][i] and
            self.current_state[1][i] == self.current_state[2][i]):
            return self.current_state[0][i]

    # Horizontal win
    for i in range(0, 3):
        if (self.current_state[i] == ['X', 'X', 'X']):
            return 'X'
        elif (self.current_state[i] == ['O', 'O', 'O']):
            return 'O'

    # Main diagonal win
    if (self.current_state[0][0] != '.' and
        self.current_state[0][0] == self.current_state[1][1] and
        self.current_state[0][0] == self.current_state[2][2]):
        return self.current_state[0][0]

    # Second diagonal win
    if (self.current_state[0][2] != '.' and
        self.current_state[0][2] == self.current_state[1][1] and
        self.current_state[0][2] == self.current_state[2][0]):
        return self.current_state[0][2]

    # Is whole board full?
    for i in range(0, 3):
        for j in range(0, 3):
            # There's an empty field, we continue the game
            if (self.current_state[i][j] == '.'):
                return None

    # It's a tie!
    return '.'

La IA contra la que jugamos busca dos cosas: maximizar su propia puntuación y minimizar la nuestra. Para hacer eso, tendremos un método max() que la IA usa para tomar decisiones óptimas.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Player 'O' is max, in this case AI
def max(self):

    # Possible values for maxv are:
    # -1 - loss
    # 0  - a tie
    # 1  - win

    # We're initially setting it to -2 as worse than the worst case:
    maxv = -2

    px = None
    py = None

    result = self.is_end()

    # If the game came to an end, the function needs to return
    # the evaluation function of the end. That can be:
    # -1 - loss
    # 0  - a tie
    # 1  - win
    if result == 'X':
        return (-1, 0, 0)
    elif result == 'O':
        return (1, 0, 0)
    elif result == '.':
        return (0, 0, 0)

    for i in range(0, 3):
        for j in range(0, 3):
            if self.current_state[i][j] == '.':
                # On the empty field player 'O' makes a move and calls Min
                # That's one branch of the game tree.
                self.current_state[i][j] = 'O'
                (m, min_i, min_j) = self.min()
                # Fixing the maxv value if needed
                if m > maxv:
                    maxv = m
                    px = i
                    py = j
                # Setting back the field to empty
                self.current_state[i][j] = '.'
    return (maxv, px, py)

Sin embargo, también incluiremos un método min() que nos ayudará a minimizar la puntuación de la IA:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Player 'X' is min, in this case human
def min(self):

    # Possible values for minv are:
    # -1 - win
    # 0  - a tie
    # 1  - loss

    # We're initially setting it to 2 as worse than the worst case:
    minv = 2

    qx = None
    qy = None

    result = self.is_end()

    if result == 'X':
        return (-1, 0, 0)
    elif result == 'O':
        return (1, 0, 0)
    elif result == '.':
        return (0, 0, 0)

    for i in range(0, 3):
        for j in range(0, 3):
            if self.current_state[i][j] == '.':
                self.current_state[i][j] = 'X'
                (m, max_i, max_j) = self.max()
                if m < minv:
                    minv = m
                    qx = i
                    qy = j
                self.current_state[i][j] = '.'

    return (minv, qx, qy)

Y finalmente, hagamos un bucle de juego que nos permita jugar contra la IA:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def play(self):
    while True:
        self.draw_board()
        self.result = self.is_end()

        # Printing the appropriate message if the game has ended
        if self.result != None:
            if self.result == 'X':
                print('The winner is X!')
            elif self.result == 'O':
                print('The winner is O!')
            elif self.result == '.':
                print("It's a tie!")

            self.initialize_game()
            return

        # If it's player's turn
        if self.player_turn == 'X':

            while True:

                start = time.time()
                (m, qx, qy) = self.min()
                end = time.time()
                print('Evaluation time: {}s'.format(round(end - start, 7)))
                print('Recommended move: X = {}, Y = {}'.format(qx, qy))

                px = int(input('Insert the X coordinate: '))
                py = int(input('Insert the Y coordinate: '))

                (qx, qy) = (px, py)

                if self.is_valid(px, py):
                    self.current_state[px][py] = 'X'
                    self.player_turn = 'O'
                    break
                else:
                    print('The move is not valid! Try again.')

        # If it's AI's turn
        else:
            (m, px, py) = self.max()
            self.current_state[px][py] = 'O'
            self.player_turn = 'X'

¡Empecemos el juego!

1
2
3
4
5
6
def main():
    g = Game()
    g.play()

if __name__ == "__main__":
    main()

Ahora vamos a echar un vistazo a lo que sucede cuando seguimos la secuencia de turnos recomendada, es decir, jugamos de manera óptima:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
.| .| .|
.| .| .|
.| .| .|

Evaluation time: 5.0726919s
Recommended move: X = 0, Y = 0
Insert the X coordinate: 0
Insert the Y coordinate: 0
X| .| .|
.| .| .|
.| .| .|

X| .| .|
.| O| .|
.| .| .|

Evaluation time: 0.06496s
Recommended move: X = 0, Y = 1
Insert the X coordinate: 0
Insert the Y coordinate: 1
X| X| .|
.| O| .|
.| .| .|

X| X| O|
.| O| .|
.| .| .|

Evaluation time: 0.0020001s
Recommended move: X = 2, Y = 0
Insert the X coordinate: 2
Insert the Y coordinate: 0
X| X| O|
.| O| .|
X| .| .|

X| X| O|
O| O| .|
X| .| .|

Evaluation time: 0.0s
Recommended move: X = 1, Y = 2
Insert the X coordinate: 1
Insert the Y coordinate: 2
X| X| O|
O| O| X|
X| .| .|

X| X| O|
O| O| X|
X| O| .|

Evaluation time: 0.0s
Recommended move: X = 2, Y = 2
Insert the X coordinate: 2
Insert the Y coordinate: 2
X| X| O|
O| O| X|
X| O| X|

It's a tie!

Como habrás notado, ganar contra este tipo de IA es imposible. Si asumimos que tanto el jugador como la IA están jugando de manera óptima, el juego siempre será un empate. Dado que la IA siempre juega de manera óptima, si nos equivocamos, perderemos.

Mire de cerca el tiempo de evaluación, ya que lo compararemos con la siguiente versión mejorada del algoritmo en el siguiente ejemplo.

Poda alfa-beta

El algoritmo alfa–beta (𝛼−𝛽) fue descubierto de forma independiente por algunas investigaciones a mediados del siglo XX. Alpha–beta es en realidad un minimax mejorado que utiliza una heurística. Deja de evaluar un movimiento cuando se asegura de que es peor que el movimiento examinado previamente. Tales movimientos no necesitan ser evaluados más a fondo.

Cuando se agrega a un algoritmo minimax simple, brinda el mismo resultado, pero corta ciertas ramas que no pueden afectar la decisión final, lo que mejora drásticamente el rendimiento.

El concepto principal es mantener dos valores durante toda la búsqueda:

  • Alpha: La mejor opción ya explorada para el jugador Max
  • Beta: La mejor opción ya explorada para el jugador Min

Inicialmente, alfa es infinito negativo y beta es infinito positivo, es decir, en nuestro código usaremos las peores puntuaciones posibles para ambos jugadores.

Veamos cómo se verá el árbol anterior si aplicamos el método alfa-beta:

Cuando la búsqueda llegue a la primera área gris (8), verificará la mejor opción actual (con valor mínimo) ya explorada a lo largo de la ruta del minimizador, que en ese momento es 7. Dado que 8 es mayor que 7, se nos permite cortar todos los hijos adicionales del nodo en el que estamos (en este caso no hay ninguno), ya que si jugamos ese movimiento, el oponente jugará un movimiento con valor 8, que es peor para nosotros que cualquier posible movimiento que el oponente podría haber hecho si hubiéramos hecho otro movimiento.

Un mejor ejemplo puede ser cuando se trata de un próximo gris. Tenga en cuenta los nodos con valor -9. En ese punto, la mejor opción explorada (con valor máximo) a lo largo del camino para el maximizador es -4. Dado que -9 es menor que -4, podemos eliminar a todos los demás elementos secundarios del nodo en el que estamos.

Este método nos permite ignorar muchas ramas que conducen a valores que no serán de ninguna ayuda para nuestra decisión, ni la afectarán de ninguna manera.

Con eso en mente, modifiquemos los métodos min() y max() de antes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def max_alpha_beta(self, alpha, beta):
        maxv = -2
        px = None
        py = None

        result = self.is_end()

        if result == 'X':
            return (-1, 0, 0)
        elif result == 'O':
            return (1, 0, 0)
        elif result == '.':
            return (0, 0, 0)

        for i in range(0, 3):
            for j in range(0, 3):
                if self.current_state[i][j] == '.':
                    self.current_state[i][j] = 'O'
                    (m, min_i, in_j) = self.min_alpha_beta(alpha, beta)
                    if m > maxv:
                        maxv = m
                        px = i
                        py = j
                    self.current_state[i][j] = '.'

                    # Next two ifs in Max and Min are the only difference between regular algorithm and minimax
                    if maxv >= beta:
                        return (maxv, px, py)

                    if maxv > alpha:
                        alpha = maxv

        return (maxv, px, py)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 def min_alpha_beta(self, alpha, beta):

        minv = 2

        qx = None
        qy = None

        result = self.is_end()

        if result == 'X':
            return (-1, 0, 0)
        elif result == 'O':
            return (1, 0, 0)
        elif result == '.':
            return (0, 0, 0)

        for i in range(0, 3):
            for j in range(0, 3):
                if self.current_state[i][j] == '.':
                    self.current_state[i][j] = 'X'
                    (m, max_i, max_j) = self.max_alpha_beta(alpha, beta)
                    if m < minv:
                        minv = m
                        qx = i
                        qy = j
                    self.current_state[i][j] = '.'

                    if minv <= alpha:
                        return (minv, qx, qy)

                    if minv < beta:
                        beta = minv

        return (minv, qx, qy)

Y ahora, el bucle del juego:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
  def play_alpha_beta(self):
     while True:
        self.draw_board()
        self.result = self.is_end()

        if self.result != None:
            if self.result == 'X':
                print('The winner is X!')
            elif self.result == 'O':
                print('The winner is O!')
            elif self.result == '.':
                print("It's a tie!")


            self.initialize_game()
            return

        if self.player_turn == 'X':

            while True:
                start = time.time()
                (m, qx, qy) = self.min_alpha_beta(-2, 2)
                end = time.time()
                print('Evaluation time: {}s'.format(round(end - start, 7)))
                print('Recommended move: X = {}, Y = {}'.format(qx, qy))

                px = int(input('Insert the X coordinate: '))
                py = int(input('Insert the Y coordinate: '))

                qx = px
                qy = py

                if self.is_valid(px, py):
                    self.current_state[px][py] = 'X'
                    self.player_turn = 'O'
                    break
                else:
                    print('The move is not valid! Try again.')

        else:
            (m, px, py) = self.max_alpha_beta(-2, 2)
            self.current_state[px][py] = 'O'
            self.player_turn = 'X'

El juego es el mismo que antes, aunque si echamos un vistazo al tiempo que tarda la IA en encontrar soluciones óptimas, hay una gran diferencia:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
.| .| .|
.| .| .|
.| .| .|

Evaluation time: 0.1688969s
Recommended move: X = 0, Y = 0


Evaluation time: 0.0069957s
Recommended move: X = 0, Y = 1


Evaluation time: 0.0009975s
Recommended move: X = 2, Y = 0


Evaluation time: 0.0s
Recommended move: X = 1, Y = 2


Evaluation time: 0.0s
Recommended move: X = 2, Y = 2

It's a tie!

Después de probar e iniciar el programa desde cero varias veces, los resultados de la comparación se encuentran en la siguiente tabla:


Algoritmo Tiempo mínimo Tiempo máximo Mínimo 4,57 s 5,34 s Poda alfa-beta 0,16 s 0,2 s


Conclusión

La poda alfa-beta hace una gran diferencia en la evaluación de árboles de caza grandes y complejos. Aunque el tres en raya es un juego simple en sí mismo, todavía podemos notar cómo sin heurísticas alfa-beta el algoritmo toma mucho más tiempo para recomendar el movimiento en el primer turno.