Saltar al contenido principal

Implementación del Algoritmo Minimax para IA en Python

Aprende a codificar una IA de tres en raya imbatible utilizando el algoritmo Minimax en Python. Este tutorial abarca teoría, implementación y optimización, ideal para los entusiastas de la IA de los juegos.
Actualizado 31 ene 2025  · 14 min de lectura

El algoritmo Mini-Max tiene una rica historia en la IA, que se remonta a la década de 1920. Aunque en aquella época no se utilizaba el término IA para referirse a los algoritmos informáticos, el algoritmo fundacional proporcionó sin duda algunas de las primeras ideas sobre cómo las máquinas podían tomar decisiones óptimas en situaciones adversas. El algoritmo fue formalizado por primera vez por John von Neumann en su artículo de 1928 "Zur Theorie der Gesellschaftsspiele" (Sobre la teoría de los juegos de estrategia), que sentó las bases de la teoría moderna de los juegos y los algoritmos de toma de decisiones.

En 1997, Deep Blue de IBM derrotó al campeón mundial de ajedrez Garry Kasparov utilizando las variantes avanzadas de Mini-max. Desde entonces, el algoritmo ha sido la columna vertebral de enfoques más sofisticados como Búsqueda en Árbol Monte Carlo (MCTS) y el aprendizaje por refuerzo de refuerzo.

En este artículo, no reconstruiremos el famoso Deep Blue para el ajedrez, sino una versión mucho más sencilla para el tres en raya en Python. Por el camino, adquirirás una sólida intuición sobre cómo funciona el algoritmo y cómo aplicarlo a juegos más complejos del mundo real.

¿Qué es el Algoritmo Minimax?

Minimax suele ser un algoritmo de toma de decisiones para juegos de dos jugadores (como el ajedrez, el tres en raya o las damas). Permite a los ordenadores planificar varias jugadas mientras supones que tu oponente siempre hará su mejor jugada posible. En esta sección, veremos una visión general del algoritmo a través del ejemplo del tres en raya.

Visión general del algoritmo Minimax

En un tres en raya del mundo real, cada vez que es tu turno, intentas hacer la mejor jugada posible mientras asumes que tu oponente también hará la mejor. Esto es exactamente lo que hace el algoritmo Minimax: ayuda a un ordenador a hacer la mejor jugada posible pensando con antelación en todas las jugadas posibles.

El algoritmo Minimax recibe su nombre por cómo funciona:

  • "Mini" representa al adversario intentando minimizar tu puntuación
  • "Max" representa que intentas maximizar tu puntuación

Cuando es tu turno, quieres hacer movimientos que te den la mejor oportunidad de ganar (maximizar). Cuando es el turno de tu adversario, supones que hará movimientos que te den el peor resultado (minimizar).

La importancia del Minimax en la IA

El Minimax es muy importante en inteligencia artificial por varias razones:

  1. Ayuda a los ordenadores a tomar decisiones inteligentes en juegos de dos jugadores
  2. Es la base de muchos sistemas modernos de IA para juegos
  3. Enseña a los ordenadores a pensar con antelación y a planificar movimientos

¿Lo mejor? Esta misma idea se utiliza en montones de aplicaciones del mundo real:

  • Oponentes de la IA de los videojuegos
  • Juegos de estrategia como el ajedrez y las damas
  • Incluso algunas herramientas de toma de decisiones empresariales

Aunque Minimax pueda parecer complicado, en realidad no es más que enseñar a un ordenador a pensar como un jugador cuidadoso que considera tanto sus movimientos como los de su oponente antes de tomar una decisión.

Comprender el algoritmo Minimax

Veamos cómo funciona el Minimax con un sencillo ejemplo de tres en raya. Imagina que juegas como X y el ordenador es O.

Cómo piensa el ordenador

Cuando sea el turno del ordenador, sigue estos pasos:

  1. Mira todos los movimientos posibles que puede hacer
  2. Para cada movimiento, imagina lo que podrías hacer a continuación
  3. Sigue pensando en el futuro hasta que llegue a un punto final (como que alguien gane o haya un empate)
  4. Elige el movimiento que le dé más posibilidades de ganar

Marcando el juego

El ordenador puede utilizar un sistema de puntuación sencillo:

  • +10 puntos si gana el ordenador
  • -10 puntos si ganas
  • 0 puntos si hay empate

Piensa en ello como en un árbol de posibilidades:

  • En la parte superior está el tablero de juego actual
  • Cada rama es un movimiento posible
  • En la parte inferior están todos los resultados posibles

Por turnos

El ordenador cambia entre dos modos de pensar:

1. Modo de maximización (turno del ordenador):

  • Busca movimientos que obtengan la puntuación más alta
  • Intenta ganar o forzar un empate

2. Modo minimizar (turno del jugador):

  • Asume que harás movimientos que obtengan la puntuación más baja
  • Prepara tus mejores movimientos

Un ejemplo sencillo

Digamos que es el turno del ordenador (X) en este juego:

Un estado de muestra en un juego de tres en raya que se resuelve con el algoritmo mini-max

El ordenador lo hará:

  1. Mira que tiene 3 plazas vacías para elegir
  2. Para cada lugar vacío, imagina todos los posibles movimientos futuros
  3. Elige el movimiento que conduzca a su mejor resultado
  4. En este caso, debe seleccionar la esquina inferior central para bloquear tu victoria

Esta forma de pensar por adelantado ayuda al ordenador a jugar siempre una partida perfecta de tres en raya.

Pseudocódigo del algoritmo Minimax

Vamos a desglosar cómo escribir el algoritmo Minimax paso a paso. No te preocupes si no conoces el pseudocódigo: ¡piensa en él como si escribieras los pasos en inglés sencillo antes de convertirlo en código real!

Explicación paso a paso

La función Minimax necesita tres cosas principales para funcionar:

  1. El tablero de juego actual
  2. La profundidad (cuántos movimientos por delante estamos mirando)
  3. Tanto si es el turno del jugador maximizador (ordenador) como si es el turno del jugador minimizador (humano)

Este es el pseudocódigo básico:

function minimax(board, depth, isMaximizingPlayer):
   # First, check if the game is over
   if game is won:
       return +10 if computer wins, -10 if human wins
   if game is tied:
       return 0

   # If it's the computer's turn (maximizing)
   if isMaximizingPlayer:
       bestScore = -infinity
       for each empty spot on board:
           make the move
           score = minimax(board, depth + 1, false)
           undo the move
           bestScore = max(score, bestScore)
       return bestScore

   # If it's the human's turn (minimizing)
   else:
       bestScore = +infinity
       for each empty spot on board:
           make the move
           score = minimax(board, depth + 1, true)
           undo the move
           bestScore = min(score, bestScore)
       return bestScore

Aunque la mayoría de los ejemplos de pseudocódigo se leen en inglés y son perfectamente comprensibles, el anterior es diferente, ya que utiliza la recursividad. La recursión es cuando una función se llama a sí misma una y otra vez para resolver un problema mayor. Piensa que es como mirarse en un espejo que refleja otro espejo: ves la misma imagen repetida muchas veces, haciéndose más pequeña cada vez.

En nuestro algoritmo Minimax, necesitamos la recursividad porque intentamos ver todas las posibles jugadas futuras del juego. Cada vez que la función se llama a sí misma, está mirando el siguiente movimiento que podría ocurrir. 

Esto nos ayuda a averiguar la mejor jugada comprobando todas las formas posibles en que podría desarrollarse la partida, como un jugador realmente inteligente que piensa "Si hago esto, entonces ellos podrían hacer aquello, entonces yo podría hacer esto..." y así sucesivamente hasta que termina la partida. Para saber más sobre la recursividad, puedes leer nuestro tutorial independiente sobre recursividad.

Ejemplo ilustrativo

Veamos cómo funciona en una situación de juego sencilla:

1. Posición inicial:

Un estado de muestra en un juego de tres en raya que se resuelve con el algoritmo mini-max

2. El ordenador piensa:

  • "Si coloco X en cualquier lugar vacío...".
  • "¿Qué haría el humano a continuación?"
  • "¿Y qué podría hacer después?"
  • "¿Qué movimiento me da la mejor puntuación final?"

3. Para cada plaza vacía, el ordenador:

  • Hace un movimiento
  • Comprueba si el juego ha terminado
  • Si no ha terminado, imagina el mejor movimiento del humano
  • Continúa hasta encontrar un final
  • Elige el movimiento con la puntuación más alta

Piénsalo como en el ajedrez: tú siempre estás pensando "si muevo aquí, moverán allí, entonces puedo mover aquí...", ¡pero el ordenador puede pensar en TODOS los movimientos posibles a la vez!

Lo bueno de este algoritmo es que siempre encuentra la mejor jugada posible, suponiendo que ambos jugadores jueguen perfectamente. ¡Es como tener una bola de cristal que te muestra todos los futuros posibles del juego!

Implementar Minimax para el tres en raya paso a paso

En esta sección, construiremos una IA imbatible de tres en raya potenciada por el algoritmo Mini-max en Python puro. Desglosaremos la implementación en sencillos pasos y explicaremos la intuición que hay detrás de cada uno y cómo encaja en el panorama general del juego.

Paso 1: Definir una clase TicTacToe

En primer lugar, definimos una clase que contiene toda la lógica y los métodos necesarios para jugar a un juego de tres en raya con nuestros ordenadores:

class TicTacToe:
   def __init__(self):
       # Initialize empty board (using ' ' for empty squares)
       self.board = [" " for _ in range(9)]
       self.human_player = "O"
       self.ai_player = "X"

   def print_board(self):
       """Print the current state of the board"""
       for i in range(0, 9, 3):
           print(f"{self.board[i]} | {self.board[i+1]} | {self.board[i+2]}")
           if i < 6:
               print("---------")

   def available_moves(self):
       """Returns list of available moves (indices of empty squares)"""
       return [i for i, spot in enumerate(self.board) if spot == " "]

Arriba, el método __init__ inicializa un nuevo tablero de juego como una lista de 9 espacios vacíos (representados por espacios " "), con índices 0-8 que representan las posiciones del tablero de izquierda a derecha, de arriba abajo. También establece dos símbolos de jugador: "O" para el jugador humano y "X" para la IA.

El método print_board permite visualizar el estado actual del tablero. Imprime la cuadrícula 3x3 con líneas divisorias entre filas, mostrando las jugadas de cada jugador en sus respectivas posiciones.

El métodoavailable_moves devuelve una lista de todas las jugadas válidas que aún se pueden hacer. Para ello, comprueba qué posiciones del tablero siguen vacías (contienen un espacio " ") y devuelve sus índices. Esto será crucial para que el algoritmo minimax sepa qué movimientos puede considerar.

Estos métodos constituyen la base sobre la que nos apoyaremos para crear nuestra IA de jugador utilizando el algoritmo minimax.

Vamos a probarlos rápidamente:

>>> game = TicTacToe()
>>> game.print_board()
  |   | 
---------
  |   | 
---------
  |   |

>>> game.available_moves()
[0, 1, 2, 3, 4, 5, 6, 7, 8]

Como era de esperar, en este momento tenemos un tablero vacío y todos los movimientos están disponibles.

Paso 2: Implementar métodos para realizar un movimiento y comprobar los estados del tablero

Ahora, vamos a añadir un método para hacer un movimiento:

class TicTacToe:
   ...
  
   def make_move(self, position, player):
       """Make a move on the board"""
       if self.board[position] == " ":
           self.board[position] = player
           return True
       return False

Hemos añadido el método make_move que:

  • Toma una posición (0-8) y un símbolo de jugador ("X" u "O") como entrada
  • Comprueba si la posición seleccionada está vacía (" ")
  • Si está vacío, coloca el símbolo del jugador y devuelve True
  • Si la posición ya está tomada, devuelve False sin hacer ningún cambio

Hagamos algunos movimientos y comprobemos los movimientos restantes:

>>> game = TicTacToe()

>>> game.make_move(0, "X")
>>> game.make_move(1, "O")

>>> game.print_board()
 X | O | 
-----------
   |   | 
-----------
   |   |

>>> game.available_moves()
[2, 3, 4, 5, 6, 7, 8]

Funciona bien. El siguiente paso es añadir un método para comprobar si el tablero está lleno:

class TicTacToe:
   ...

   def is_board_full(self):
       """Check if the board is full"""
       return " " not in self.board

is_board_full es un método booleano que comprueba si quedan espacios vacíos en el tablero.

A continuación, añadimos un método para comprobar si se alcanza un estado ganador:

class TicTacToe:
   ...

   def check_winner(self):
       """Check if there's a winner. Returns winner symbol or None"""
       # Check rows
       for i in range(0, 9, 3):
           if self.board[i] == self.board[i + 1] == self.board[i + 2] != " ":
               return self.board[i]

       # Check columns
       for i in range(3):
           if self.board[i] == self.board[i + 3] == self.board[i + 6] != " ":
               return self.board[i]

       # Check diagonals
       if self.board[0] == self.board[4] == self.board[8] != " ":
           return self.board[0]
       if self.board[2] == self.board[4] == self.board[6] != " ":
           return self.board[2]

       return None

El método check_winner evalúa el estado actual del tablero de tres en raya para determinar si hay un ganador. Comprueba todas las combinaciones ganadoras posibles:

1. Filas (3 posibilidades):

  • Fila superior (índices 0,1,2)
  • Fila central (índices 3,4,5)
  • Fila inferior (índices 6,7,8)

2. Columnas (3 posibilidades):

  • Columna izquierda (índices 0,3,6)
  • Columna central (índices 1,4,7)
  • Columna derecha (índices 2,5,8)

3. Diagonales (2 posibilidades):

  • De arriba-izquierda a abajo-derecha (índices 0,4,8)
  • De arriba-derecha a abajo-izquierda (índices 2,4,6)

Para cada combinación, comprueba si las tres posiciones contienen el mismo símbolo de jugador (X u O) y no son espacios vacíos. Si se encuentra una combinación ganadora, devuelve el símbolo del jugador ganador. Si no se encuentra ningún ganador después de comprobar todas las posibilidades, devuelve Ninguno.

Probemos la función en estados ganadores y no ganadores:

game = TicTacToe()

# Winning state
game.make_move(0, "X")
game.make_move(1, "X")
game.make_move(2, "X")

>>> game.print_board()
 X | X | X
-----------
   |   | 
-----------
   |   |

>>> game.check_winner()
'X'

game = TicTacToe()

# Non-winning state
game.make_move(0, "X")
game.make_move(1, "O")
game.make_move(2, "O")
game.make_move(3, "X")

>>> game.print_board()
 X | O | O
-----------
 X |   | 
-----------
   |   |

>>> game.check_winner() is None
True

Por último, añadimos otro método booleano para especificar si el juego ha terminado o no:

class TicTacToe:
   ...

   def game_over(self):
       """Check if the game is over"""
       return self.check_winner() is not None or self.is_board_full()

El método devuelve Verdadero si se encuentra el ganador o el tablero está lleno.

En este punto, hemos construido todas las mecánicas básicas del juego:

  • El tablero se representa como una lista de 9 casillas inicializadas vacías
  • print_board() muestra visualmente el estado actual del juego
  • available_moves() devuelve índices de cuadrados vacíos
  • make_move() coloca el símbolo de un jugador en el tablero
  • check_winner() examina filas, columnas y diagonales para ganar en cada jugada
  • is_board_full() determina si no quedan movimientos
  • game_over() combina la comprobación del ganador y la comprobación del tablero completo

Estos métodos proporcionan la base necesaria para crear un juego jugable, manejando todas las operaciones básicas como hacer movimientos y determinar el estado del juego.

Ahora viene la parte crítica: darle al ordenador el "cerebro" para que juegue con Minimax.

Paso 3: Implementación de Minimax para el tres en raya

Ahora, vamos a implementar el algoritmo del juego en un nuevo método:

class TicTacToe:
   ...

   def minimax(self, depth, is_maximizing):
       """
       Minimax algorithm implementation
       Returns the best score possible for the current board state
       """
       # Base cases
       winner = self.check_winner()
       if winner == self.ai_player:
           return 1
       if winner == self.human_player:
           return -1
       if self.is_board_full():
           return 0

La función toma dos parámetros:

  • depth - Registra cuántos niveles de profundidad tenemos en la recursión. Esto puede utilizarse para limitar la profundidad de búsqueda en juegos muy complejos, aunque para el tres en raya no necesitamos limitarla.
  • is_maximizing - Una bandera booleana que indica si estamos buscando la puntuación máxima (turno de la IA) o la puntuación mínima (turno del humano). Esto se alterna con cada llamada recursiva a medida que los jugadores se turnan.

En el cuerpo de la función, empezamos definiendo los casos base: Si la IA gana la partida (winner == ai_player), devolvemos 1, ya que es el mejor resultado posible para la IA. Si el humano gana (winner == human_player), devolvemos -1, ya que es el peor resultado para la IA. Si el tablero está lleno sin ningún ganador, devolvemos 0 por empate.

def minimax(self, depth, is_maximizing):
   ...

   # if it is the maximizing player's turn (AI), we want to maximize the score
   if is_maximizing:
       best_score = float("-inf")
       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.ai_player
           # Recursively call minimax with the next depth and the minimizing player
           score = self.minimax(depth + 1, False)
           # Reset the move
           self.board[move] = " "
           # Update the best score
           best_score = max(score, best_score)
       return best_score

Cuando is_maximizing es Verdadero, estamos simulando el turno de la IA y queremos encontrar la jugada que nos lleve a la mayor puntuación posible. Empezamos fijando mejor_puntuación en infinito negativo para que cualquier puntuación real sea mejor. A continuación, para cada movimiento disponible

  1. Coloca el símbolo de la IA en el tablero temporalmente
  2. Evalúa recursivamente lo que ocurriría si hiciéramos este movimiento llamando a minimax con is_maximizing=False (ya que después sería el turno del humano)
  3. Deshaz el movimiento temporal para restaurar el estado del tablero
  4. Sigue la puntuación más alta que hemos visto hasta ahora utilizando max()

Esto nos permite comprobar todos los movimientos posibles que podría hacer la IA. En cada jugada, analizamos lo que podría ocurrir a continuación, hasta que alguien gane o la partida quede empatada. Luego trabajamos hacia atrás para encontrar qué primer movimiento da a la IA la mejor oportunidad de ganar.

Ahora, hagamos la parte de minimizar para el humano:

def minimax(self, depth, is_maximizing):
   ...

   # if it is the maximizing player's turn (AI), we want to maximize the score
   if is_maximizing:
       ...

   else:
       # if it is the minimizing player's turn (human), we want to minimize the score
       best_score = float("inf")
       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.human_player
           # Recursively call minimax with the next depth and the maximizing player
           score = self.minimax(depth + 1, True)
           # Reset the move
           self.board[move] = " "
           # Update the best score
           best_score = min(score, best_score)
       return best_score

Cuando is_maximizing es Falso, estamos simulando el turno del jugador humano y queremos encontrar la jugada que lleve a la menor puntuación posible (ya que una puntuación alta significa que la IA gana). Empezamos con best_score como infinito positivo, por lo que cualquier puntuación real será menor. Para cada movimiento disponible, nosotros:

  1. Coloca el símbolo del humano en el tablero temporalmente
  2. Evalúa recursivamente lo que ocurriría llamando a minimax con is_maximizing=True (ya que después sería el turno de la IA)
  3. Deshaz el movimiento temporal para restaurar el estado del tablero
  4. Lleva la cuenta de la puntuación más baja que hemos visto utilizando min()

Esto simula que el jugador humano intenta hacer los mejores movimientos para evitar que la IA gane. El humano quiere minimizar la puntuación, ya que las puntuaciones positivas representan victorias de la IA. Alternando entre giros maximizadores y minimizadores, el algoritmo puede determinar la secuencia de movimientos óptima para ambos jugadores.

Paso 4: Encontrar el mejor movimiento para la IA utilizando Minimax

Ahora que tenemos listo el algoritmo, necesitamos otro método que utilice el método minimax para determinar la mejor jugada de la IA después de cada jugada humana:

class TicTacToe:
   ...

   def get_best_move(self):
       """Find the best move for AI using minimax"""
       best_score = float("-inf")
       best_move = None

       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.ai_player
           # Recursively call minimax with the next depth and the minimizing player
           score = self.minimax(0, False)
           # Reset the move
           self.board[move] = " "

           # Update the best score
           if score > best_score:
               best_score = score
               best_move = move

       return best_move

El método get_best_move se encarga de determinar el movimiento óptimo para el jugador de la IA utilizando el algoritmo minimax. Funciona mediante:

1. Partiendo de infinito negativo como mejor puntuación y sin seleccionar ninguna jugada

2. Por cada movimiento disponible en el tablero:

  • Colocar temporalmente el símbolo de la IA en esa posición
  • Utilizando minimax para evaluar lo buena que es esa jugada simulando el resto de la partida
  • Deshacer el traslado temporal
  • Si esta jugada conduce a una puntuación mejor que la que hemos visto antes, actualiza tanto la mejor puntuación como la mejor jugada

3. Finalmente devolviendo el movimiento que ha llevado a la puntuación más alta

Este enfoque garantiza que la IA elegirá la jugada que le dé más posibilidades de ganar, suponiendo que el jugador humano también juegue de forma óptima. El método considera todos los posibles estados futuros del juego y elige el camino que maximiza las posibilidades de la IA al tiempo que minimiza las posibilidades de ganar del humano.

Vamos a probarlo con un estado de juego de muestra:

game = TicTacToe()

# Make a couple of moves
game.make_move(0, "X")
game.make_move(1, "O")

# Print the board

>>> game.print_board()
X | O | 
---------
  |   | 
---------
  |   |

>>> game.get_best_move()
3

# AI moves
>>> game.make_move(3, "X")

# I move
>>> game.make_move(4, "O")
>>> game.print_board()
X | O | 
---------
X | O | 
---------
  |   |

# Get the best move for AI
>>> game.get_best_move()
6

Como puedes ver, la IA encontró la combinación ganadora basándose en mis movimientos (era un estado ficticio, pero esto demuestra que nuestro algoritmo funciona).

Paso 5: Implementar un bucle de juego

Ahora que hemos implementado y probado nuestro algoritmo minimax, vamos a crear un bucle de juego que nos permita jugar contra la IA.

class TicTacToe:

   ...

   def play_game(self):
       """Main game loop"""
       print("Welcome to Tic Tac Toe!")
       print("You are 'O' and the AI is 'X'")
       print("Enter positions (0-8) as shown below:")
       print("0 | 1 | 2")
       print("---------")
       print("3 | 4 | 5")
       print("---------")
       print("6 | 7 | 8")
       print("\n")

El método jugar_juego comienza mostrando un mensaje de bienvenida e instrucciones al jugador. Muestra que el jugador humano utiliza "O" y la IA utiliza "X". A continuación, imprime una cuadrícula numerada (0-8) para mostrar al jugador qué número corresponde a cada posición del tablero. Esto facilita que los jugadores sepan exactamente qué número introducir para la jugada deseada.

# ... the rest of the class
def play_game(self):
   ...

   # Randomly decide who goes first
   import random

   ai_turn = random.choice([True, False])

   while not self.game_over():
       self.print_board()

       if ai_turn:
           print("\nAI's turn...")
           move = self.get_best_move()
           self.make_move(move, self.ai_player)
       else:
           while True:
               try:
                   move = int(input("\nYour turn (0-8): "))
                   if 0 <= move <= 8 and self.make_move(move, self.human_player):
                       break
                   else:
                       print("Invalid move! Try again.")
               except ValueError:
                   print("Please enter a number between 0 and 8!")

       ai_turn = not ai_turn

Tras mostrar las instrucciones iniciales, el juego entra en su bucle principal. El juego decide aleatoriamente quién va primero -la IA o el jugador humano- utilizando random.choice([True, False]). Esto crea un elemento de equidad e imprevisibilidad al comienzo de cada partida.

El bucle principal del juego continúa hasta que game_over() devuelve Verdadero (o alguien ha ganado o el tablero está lleno). Durante cada turno, el estado actual del tablero se muestra mediante print_board().

Si es el turno de la IA (ai_turn es Verdadero), el programa:

  1. Imprime un mensaje indicando que la IA está pensando
  2. Llama a get_best_move() para determinar el movimiento óptimo mediante el algoritmo minimax
  3. Realiza el movimiento colocando el símbolo de la IA ("X") en la posición elegida

Si es el turno del humano (ai_turn es Falso), el programa:

1. Entra en un bucle para obtener una entrada válida del jugador2. Pide un número de movimiento entre 0-83. Valida la entrada es:

  • Un número entero válido (utilizando try/except)
  • Dentro del intervalo válido 0-8
  • Señala una posición vacía en el tablero

4. Sigue preguntando hasta que se recibe una entrada válida. Realiza el movimiento colocando el símbolo del jugador ("O") en la posición elegida

Después de cada turno, se da la vuelta a ai_turn utilizando not para alternar entre los jugadores. Esto crea el flujo de ida y vuelta del juego, en el que cada jugador se turna hasta que alguien gana o la partida termina en empate.

La validación de la entrada garantiza que el juego no se bloquee por una entrada no válida del usuario y proporciona mensajes de error útiles para guiar al jugador a introducir los movimientos correctos. Esto crea una experiencia de juego sólida y fácil de usar.

def play_game(self):
   ...
   # Game over
   self.print_board()
   winner = self.check_winner()
   if winner == self.ai_player:
       print("\nAI wins!")
   elif winner == self.human_player:
       print("\nCongratulations! You win!")
   else:
       print("\nIt's a tie!")

Cuando termina la partida, se muestra el estado final del tablero mediante print_board() y se determina el ganador mediante check_winner(). El juego puede terminar de tres formas:

  1. La IA gana - Si check_winner() devuelve el símbolo de la IA ("X"), indica que la IA ha conseguido una línea ganadora
  2. El humano gana - Si check_winner() devuelve el símbolo del humano ('O'), indica que el jugador ha conseguido una línea ganadora
  3. Empate - Si ninguno de los jugadores ha ganado pero el tablero está lleno, lo que significa que no hay más movimientos posibles

Se muestra el mensaje apropiado para anunciar el resultado del juego. Esto proporciona una información clara al jugador sobre cómo ha concluido el juego.

Paso 6: Ponerlo todo junto

Ahora, es el momento de poner todo el código que hemos escrito hasta ahora en un script de Python con lo siguiente cláusula if/main al final:

# Start the game
if __name__ == "__main__":
   game = TicTacToe()
   game.play_game()

Esto permite que el juego se inicie en cuanto ejecutes el script con python script.py. Si te has perdido entre todas las explicaciones y bloques de código, puedes encontrar el código completo del juego en este gist de GitHub.

Aquí tienes un ejemplo de partida que he jugado:

❯ python tic-tac-toe.py
Welcome to Tic Tac Toe!
You are 'O' and the AI is 'X'
Enter positions (0-8) as shown below:
0 | 1 | 2
---------
3 | 4 | 5
---------
6 | 7 | 8


  |   | 
---------
  |   | 
---------
  |   | 

Your turn (0-8): 4
  |   | 
---------
  | O | 
---------
  |   | 

AI's turn...
X |   | 
---------
  | O | 
---------
  |   | 

Your turn (0-8): 5
X |   | 
----------
  | O | O
----------
  |   | 

AI's turn...
X |   | 
---------
X | O | O
---------
  |   | 

Your turn (0-8): 6
X |   | 
---------
X | O | O
---------
O |   | 

AI's turn...
X |   | X
---------
X | O | O
---------
O |   | 

Your turn (0-8): 1
X | O | X
---------
X | O | O
---------
O |   | 

AI's turn...
X | O | X
---------
X | O | O
---------
O | X | 

Your turn (0-8): 8
X | O | X
---------
X | O | O
---------
O | X | O

It's a tie!

Recuerda que, como el tres en raya es un juego sencillo, no hay ninguna posibilidad de vencer a la IA. ¡O acaba en empate o pierdes!

Formalización del algoritmo Mini-max

Ahora, repasemos la definición general de algoritmo más allá del simple ejemplo del tres en raya.

El algoritmo Minimax puede definirse formalmente como una función recursiva que evalúa posiciones en un juego de suma cero. Desglosemos sus componentes formales y sus propiedades.

Definición matemática

Para un estado de juego s, el valor minimax V(s) se define como:

V(s) =
   utility(s)                    if s is terminal
   max(V(s')) for all s' in S    if player = MAX
   min(V(s')) for all s' in S    if player = MIN

Dónde:

  • s' representa los estados sucesores de s
  • S es el conjunto de todas las jugadas legales desde el estado s
  • utilidad(s) es la función de evaluación de los estados terminales

Propiedades clave

1. Información perfecta

  • Todos los jugadores tienen conocimiento completo del estado del juego
  • Sin información oculta ni elementos de azar
  • Resultados deterministas

2. Naturaleza de suma cero

  • La ganancia de un jugador es exactamente igual a la pérdida del otro jugador
  • La suma de las utilidades de todos los jugadores es siempre cero
  • En los juegos de dos jugadores, las utilidades suelen ser {-1, 0, 1}

3. Juego óptimo

  • Supone que ambos jugadores toman decisiones óptimas
  • Garantiza el mejor resultado posible contra el juego perfecto
  • Conduce a un equilibrio de Nash en términos de teoría de juegos

Análisis de la complejidad

Complejidad temporal: O(b^m)

  • b = factor de ramificación (número de movimientos legales en cada estado)
  • m = profundidad máxima del árbol del juego

Complejidad espacial: O(bm)

  • Requiere almacenar el estado del juego en cada nivel
  • Puede optimizarse con la profundización iterativa

Función de evaluación

Para los estados no terminales, la función de evaluación f(s) debe:

  1. Correlacionar con la probabilidad de ganar
  2. Ser eficiente desde el punto de vista computacional
  3. Mantén una escala coherente durante todo el juego

La definición formal:

f(s) = w₁x₁ + w₂x₂ + ... + wₙxₙ

Dónde:

  • wᵢ son los pesos de las distintas características
  • xᵢ son valores de características del estado del juego
  • n es el número de características que se evalúan

Garantía de optimalidad

El algoritmo Minimax garantiza el juego óptimo en estas condiciones:

  1. Información perfecta
  2. Resultados deterministas
  3. Búsqueda completa de estados terminales
  4. Evaluación precisa del estado de los terminales

Esto lo hace especialmente adecuado para juegos como el ajedrez, el tres en raya y las damas, en los que se cumplen estas condiciones.

Variaciones y limitaciones avanzadas

Aunque Minimax es estupendo para juegos sencillos como el tres en raya, tiene algunos problemas con juegos más grandes. Veamos cómo podemos mejorarla y dónde tiene dificultades.

Hacer el Minimax más rápido: Alpha-beta pruning

Imagina que estás jugando al ajedrez y pensando en tus jugadas. Si has encontrado una jugada ganadora, no necesitas comprobar todas las demás jugadas posibles, ¿verdad? La Poda Alfa-Beta funciona del mismo modo: ayuda al ordenador a omitir la comprobación de jugadas que ya sabemos que no serán mejores que las que hemos encontrado.

Piénsalo así:

  • Estás comprando la chocolatina más barata
  • Tienes 1 $ para gastar
  • Si encuentras una chocolatina por 50 céntimos, puedes dejar de mirar las que cuesten más de 1 dólar
  • ¡Así ahorrarás tiempo!

Límites de profundidad: No mirar demasiado lejos

En juegos grandes como el ajedrez, hay demasiadas jugadas posibles como para comprobarlas todas. Así que añadimos un límite de profundidad:

  1. Mira sólo hacia delante 4-5 movimientos en lugar de hasta el final
  2. Haz una buena estimación de lo buena que es la posición en ese momento
  3. Elige la mejor jugada basándote en estas conjeturas

No puedes planificar cada movimiento hasta el final de la partida, ¡pero puedes planificar algunos movimientos por adelantado!

Dónde lucha el Minimax

Minimax no es perfecto. He aquí sus principales problemas:

1. Demasiadas opciones

  • Los juegos como el Go tienen demasiados movimientos posibles
  • Ni siquiera los ordenadores rápidos pueden comprobarlas todas
  • Por eso necesitamos otros métodos para los juegos realmente complejos

2. Problemas de tiempo

  • Cuantos más movimientos mires hacia delante, más tardarás
  • En el ajedrez, los ordenadores no pueden ver todas las jugadas posibles
  • Tienen que ser inteligentes sobre qué movimientos comprobar

3. No es bueno para juegos inciertos

  • Minimax funciona mejor cuando puedes verlo todo
  • No sirve para juegos de cartas en los que no sabes qué cartas tienen los demás
  • No maneja bien los sucesos aleatorios (como las tiradas de dados)

Soluciones modernas

La IA de los juegos actuales suele combinar el Minimax con otras técnicas geniales:

1. Aprendizaje automático

  • Los ordenadores pueden aprender viendo muchos partidos
  • Esto les ayuda a hacer mejores conjeturas sobre los buenos movimientos
  • Juegos como AlphaGo utilizan esto para vencer a campeones humanos

2. Reconocimiento de patrones

  • En lugar de comprobar cada movimiento, busca patrones
  • Igual que los jugadores humanos reconocen las buenas jugadas
  • Esto hace que el ordenador sea mucho más rápido

3. Banco de memoria

  • Recuerda las posiciones que se han visto antes
  • No pierdas tiempo calculando dos veces lo mismo
  • ¡Como tener una chuleta de buenos movimientos!

¿Lo mejor? Estas mejoras ayudan a los ordenadores a jugar casi tan bien como los humanos, ¡y a veces incluso mejor! Pero recuerda: incluso con todos estos añadidos de lujo, el Minimax sigue siendo la base que hace que todo funcione.

Conclusión

En este tutorial, hemos explorado el algoritmo Minimax desde sus conceptos básicos hasta su aplicación práctica. Esto es lo que hemos aprendido:

1. Conceptos básicos

  • Cómo ayuda Minimax a los ordenadores a tomar decisiones en los juegos
  • La diferencia entre minimizar y maximizar jugadores
  • Por qué se llama "minimax" y cómo funciona

2. Capacidad de ejecución

  • Construir un juego de tres en raya desde cero
  • Escribir el algoritmo Minimax en Python
  • Probar y depurar la lógica del juego

3. Temas avanzados

  • Hacer más rápido el algoritmo con la Poda Alfa-Beta
  • Manejo de limitaciones en juegos complejos
  • Mejoras modernas mediante el aprendizaje automático

¿Y ahora qué?

El algoritmo Minimax es sólo una pieza del rompecabezas de la IA. Si tienes ganas de aprender más sobre la IA y los algoritmos, aquí tienes algunos recursos estupendos para continuar tu viaje:

1. Algoritmos relacionados

2. Aplicaciones de aprendizaje automático

3. Pistas de aprendizaje completas

Recuerda, tanto si estás construyendo un juego sencillo como un complejo sistema de IA, comprender algoritmos como el Minimax te proporciona una base sólida para temas más avanzados de inteligencia artificial. Sigue practicando, sigue aprendiendo y, lo más importante, ¡sigue programando!

Preguntas frecuentes sobre el algoritmo Minimax

¿Es difícil entender y aplicar el algoritmo Minimax?

El algoritmo Minimax es relativamente sencillo de entender, sobre todo cuando se aplica a juegos sencillos como el tres en raya. Aunque el concepto de recursividad puede resultar difícil para los principiantes, el principio básico de alternar entre movimientos de maximización y minimización es intuitivo. Este tutorial desglosa la implementación en pasos manejables, haciéndola accesible para programadores con conocimientos básicos de Python.

¿Puedo utilizar este algoritmo para otros juegos además del tres en raya?

Sí, el algoritmo Minimax puede adaptarse a muchos juegos de suma cero para dos jugadores con información perfecta, como el ajedrez, las damas o el conecta cuatro. Sin embargo, para juegos más complejos, necesitarás implementar optimizaciones adicionales como la poda Alfa-Beta y la limitación de profundidad, ya que el número de movimientos posibles aumenta exponencialmente.

¿Cómo es que la IA nunca pierde en el tres en raya?

El algoritmo Minimax funciona simulando todos los posibles estados futuros del juego y eligiendo los movimientos que conducen al mejor resultado posible. En un juego sencillo como el tres en raya, hay relativamente pocos movimientos posibles, lo que permite a la IA calcular el movimiento óptimo en cada situación. Como el tres en raya es un "juego resuelto", el juego perfecto de ambas partes siempre lleva a un empate, por lo que la IA nunca puede perder.

¿Qué conocimientos previos necesito para seguir este tutorial?

Debes tener conocimientos básicos de programación en Python, incluyendo:

Comprensión de funciones y clases

Familiaridad con listas y estructuras de datos básicas

Flujo de control básico (sentencias if, bucles)

Comprender la recursividad es útil pero no necesario, ya que el tutorial explica el concepto.

¿Por qué es importante este algoritmo para el desarrollo de la IA?

El algoritmo Minimax es fundamental para comprender la teoría de juegos y la toma de decisiones en IA. Introduce conceptos importantes como la búsqueda recursiva en árbol, el pensamiento adversario y la toma de decisiones óptimas bajo información perfecta. Estos principios constituyen la base de algoritmos de IA más avanzados utilizados en aplicaciones modernas, desde los juegos hasta la planificación estratégica y los sistemas de apoyo a la toma de decisiones.


Bex Tuychiev's photo
Author
Bex Tuychiev
LinkedIn

Soy un creador de contenidos de ciencia de datos con más de 2 años de experiencia y uno de los mayores seguidores en Medium. Me gusta escribir artículos detallados sobre IA y ML con un estilo un poco sarcastıc, porque hay que hacer algo para que sean un poco menos aburridos. He publicado más de 130 artículos y un curso DataCamp, y estoy preparando otro. Mi contenido ha sido visto por más de 5 millones de ojos, 20.000 de los cuales se convirtieron en seguidores tanto en Medium como en LinkedIn. 

Temas

Los mejores cursos de IA

programa

AI Fundamentals

10hrs hr
Discover the fundamentals of AI, dive into models like ChatGPT, and decode generative AI secrets to navigate the dynamic AI landscape.
Ver detallesRight Arrow
Comienza el curso
Ver másRight Arrow
Relacionado

tutorial

Tutorial del Optimizador Adam: Intuición e implementación en Python

Comprender y aplicar el optimizador Adam en Python. Aprende la intuición, las matemáticas y las aplicaciones prácticas del aprendizaje automático con PyTorch
Bex Tuychiev's photo

Bex Tuychiev

14 min

tutorial

Ajuste fino de GPT-3 mediante la API OpenAI y Python

Libere todo el potencial de GPT-3 mediante el ajuste fino. Aprenda a utilizar la API de OpenAI y Python para mejorar este modelo de red neuronal avanzado para su caso de uso específico.
Zoumana Keita 's photo

Zoumana Keita

12 min

tutorial

Introducción al Q-Learning: Tutorial para principiantes

Conozca el algoritmo de aprendizaje por refuerzo sin modelos más popular con un tutorial de Python.
Abid Ali Awan's photo

Abid Ali Awan

16 min

tutorial

Búsqueda binaria en Python: guía completa para una búsqueda eficiente

Aprende a implementar la búsqueda binaria en Python utilizando enfoques iterativos y recursivos, y explora el módulo bisect integrado para obtener funciones de búsqueda binaria eficientes y preimplementadas.
Amberle McKee's photo

Amberle McKee

12 min

tutorial

Tutorial de Clasificación en Árbol de Decisión en Python

En este tutorial, aprenderás Clasificación en Árbol de Decisión, medidas de selección de atributos y cómo construir y optimizar el Clasificador en Árbol de Decisión utilizando el paquete Python Scikit-learn.
Avinash Navlani's photo

Avinash Navlani

12 min

tutorial

Guía para principiantes de la API de OpenAI: Tutorial práctico y prácticas recomendadas

Este tutorial te presenta la API de OpenAI, sus casos de uso, un enfoque práctico para utilizar la API y todas las prácticas recomendadas que debes seguir.
Arunn Thevapalan's photo

Arunn Thevapalan

13 min

Ver másVer más