Busca e IA de jogos: A* e minimax em Python

O conceito em palavras simples

A IA clássica resolve problemas buscando entre os estados possíveis. O A* encontra o caminho mais barato somando o custo já percorrido a uma estimativa do custo restante, e o minimax escolhe jogadas em jogos de dois jogadores supondo que o adversário joga bem.

Encontre o caminho mais curto numa grade com a busca A* e escolha a melhor jogada de um jogo com minimax.

Ideias principais

O A* encontra o melhor caminho quando a estimativa (heurística) nunca superestima o custo real.
O minimax explora a árvore do jogo até uma profundidade fixa ou até o fim da partida.
A poda alfa-beta pula ramos que não podem mudar a decisão.
Algoritmos genéticos buscam de outro jeito: eles evoluem uma população de soluções candidatas.

Quando usar?

Entender o que acontece dentro das redes neurais e das bibliotecas de IA.
Aprender a ideia antes de implementá-la nos desafios correspondentes.
Se preparar para cursos de aprendizado de máquina, entrevistas e projetos.

Veja na prática

Clique em Executar para ver o A* explorar a grade; clique nas células para pôr ou tirar paredes. Na árvore do jogo, clique numa folha para mudar sua pontuação.

Código de exemplo

Executar 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))

Saída esperada

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

Como funciona

A fila de prioridade sempre expande a célula com menor custo + estimativa, sendo a estimativa a distância de Manhattan até o objetivo, então o A* chega a G em 5 passos contornando as paredes. minimax() pega o máximo na nossa vez e o mínimo na vez do adversário; a primeira jogada garante 3, o melhor dos três piores casos.

Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.

Exercícios práticos

Altere as entradas e teste casos de borda antes de usar conjuntos de dados maiores.

Mude as entradas ou os pesos e preveja a saída antes de executar.
Imprima os valores intermediários para acompanhar cada passo do cálculo.
Resolva os desafios indicados abaixo para implementar a ideia você mesmo.

Executar no IDE Python →

Pratique com um desafio

Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.

Todos os desafios