Búsqueda e IA para juegos: A* y minimax en Python

El concepto en palabras sencillas

La IA clásica resuelve problemas buscando entre los estados posibles. A* encuentra el camino más barato sumando el coste recorrido y una estimación del coste restante, y minimax elige jugadas en juegos de dos jugadores suponiendo que el rival juega bien.

Encuentra el camino más corto en una cuadrícula con la búsqueda A* y elige la mejor jugada de un juego con minimax.

Ideas clave

A* encuentra el mejor camino cuando la estimación (heurística) nunca sobrestima el coste real.
Minimax explora el árbol del juego hasta una profundidad fija o hasta el final de la partida.
La poda alfa-beta se salta las ramas que no pueden cambiar la decisión.
Los algoritmos genéticos buscan de otra forma: hacen evolucionar una población de soluciones candidatas.

¿Cuándo se utiliza?

Entender qué pasa dentro de las redes neuronales y las bibliotecas de IA.
Aprender la idea antes de implementarla en los retos correspondientes.
Prepararte para cursos de aprendizaje automático, entrevistas y proyectos.

Pruébalo en acción

Pulsa Reproducir para ver cómo A* explora la cuadrícula; haz clic en las casillas para poner o quitar muros. En el árbol del juego, haz clic en una hoja para cambiar su puntuación.

Código de ejemplo

Ejecutar código →

main.py

import heapq

# A* finds the cheapest path using cost so far + a guess of the cost left.
grid = ["S..#",
        ".#..",
        "...G"]
start, goal = (0, 0), (2, 3)
guess = lambda r, c: abs(r - goal[0]) + abs(c - goal[1])   # Manhattan distance

frontier = [(guess(*start), 0, start, [start])]
seen = set()
while frontier:
    _, cost, (r, c), path = heapq.heappop(frontier)
    if (r, c) == goal:
        print("path:", path, "cost:", cost)
        break
    if (r, c) in seen:
        continue
    seen.add((r, c))
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 4 and grid[nr][nc] != "#":
            heapq.heappush(frontier, (cost + 1 + guess(nr, nc), cost + 1, (nr, nc), path + [(nr, nc)]))

# Minimax: the maximizer assumes the opponent always picks the worst for it.
def minimax(node, maximizing):
    if isinstance(node, int):
        return node
    values = [minimax(child, not maximizing) for child in node]
    return max(values) if maximizing else min(values)

tree = [[3, 5], [2, 9], [0, 7]]   # our move, then the opponent's reply
print("best guaranteed score:", minimax(tree, True))

Resultado esperado

path: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3)] cost: 5
best guaranteed score: 3

Cómo funciona

La cola de prioridad siempre expande la casilla con menor coste + estimación, donde la estimación es la distancia Manhattan a la meta, así que A* llega a G en 5 pasos rodeando los muros. minimax() toma el máximo en nuestro turno y el mínimo en el del rival; la primera jugada garantiza 3, el mejor de los tres peores casos.

Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.

Ejercicios prácticos

Modifica las entradas y prueba casos límite antes de usar conjuntos de datos mayores.

Cambia las entradas o los pesos y predice la salida antes de ejecutar.
Imprime los valores intermedios para seguir cada paso del cálculo.
Resuelve los retos enlazados abajo para implementar la idea por tu cuenta.

Ejecutar en el IDE de Python →

Practica con un reto

Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.

Todos los retos