Minimax

Visão geral

Minimax é um algoritmo clássico de busca adversária (adversarial search) usado para tomada de decisão em jogos de dois jogadores (two-player), soma zero (zero-sum) e informação perfeita (perfect-information) (por exemplo, Jogo da Velha (Tic-Tac-Toe), Damas (Checkers), finais de Xadrez (Chess)). Ele seleciona a jogada que maximiza o pior resultado possível, assumindo que o oponente joga de forma ótima.

Intuitivamente:

  • Você (o maximizador, “MAX”) escolhe uma jogada tentando tornar o resultado final o melhor possível.
  • Seu oponente (o minimizador, “MIN”) responde tentando tornar o resultado o pior possível para você.
  • O minimax busca em uma árvore de jogo (game tree) de sequências possíveis de jogadas e propaga valores a partir de estados folha até escolher a melhor jogada na raiz.

O minimax é fundamental em IA porque formaliza o jogo ótimo em cenários competitivos e motiva otimizações importantes como Poda Alfa-Beta e busca com limite de profundidade e funções de avaliação.

Quando o minimax se aplica (pressupostos)

O minimax é mais diretamente aplicável quando:

  1. Dois jogadores alternam turnos.
  2. O jogo é de soma zero: o ganho de um jogador é a perda do outro.
  3. O jogo tem informação perfeita: não há cartas escondidas, nem “neblina de guerra”.
  4. O ambiente é determinístico: não há rolagens de dados nem aleatoriedade.

Se esses pressupostos não se sustentam, o minimax pode exigir modificações (por exemplo, nós de chance levam ao expectiminimax (expectiminimax); informação oculta sugere raciocínio por estados de crença).

Formulação como árvore de jogo

O minimax representa a jogabilidade como uma árvore:

  • Nós são estados do jogo (s).
  • Arestas são ações/jogadas legais (a \in \text{Actions}(s)).
  • A raiz é o estado atual.
  • Os níveis alternam entre:
    • Nós MAX: o jogador atual tenta maximizar o resultado.
    • Nós MIN: o oponente tenta minimizar o resultado.
  • Nós folha são estados terminais (vitória/derrota/empate) ou estados de corte (com limite de profundidade).

Para definir minimax com precisão, normalmente especificamos:

  • TerminalTest(s): se (s) é um estado terminal.
  • Utility(s): recompensa numérica em estados terminais (por exemplo, vitória = +1, empate = 0, derrota = −1 na perspectiva de MAX).
  • Actions(s): jogadas legais a partir de (s).
  • Result(s, a): estado sucessor após aplicar a ação (a).

Utilidades e estrutura de “soma zero”

Em um jogo de soma zero, é comum definir uma única função de utilidade na perspectiva de MAX:

  • MAX quer maximizar Utility(s)
  • MIN quer minimizar o mesmo número

Esse objetivo escalar compartilhado é o que torna o minimax elegante e simétrico.

Recursão do minimax (regras de retropropagação (“backup”))

O minimax calcula o valor minimax (minimax value) (V(s)) de cada estado:

  • Se (s) é terminal:
    [ V(s) = \text{Utility}(s) ]
  • Se (s) é um estado MAX:
    [ V(s) = \max_{a \in \text{Actions}(s)} V(\text{Result}(s,a)) ]
  • Se (s) é um estado MIN:
    [ V(s) = \min_{a \in \text{Actions}(s)} V(\text{Result}(s,a)) ]

A jogada escolhida na raiz é a ação que atinge o max apropriado (para MAX) ou o min apropriado (para MIN).

Interpretação: “maximizar o pior caso”

Na perspectiva de MAX, cada jogada candidata leva a uma subárvore na qual MIN responderá adversarialmente. Assim, MAX avalia uma jogada pelo resultado que MIN consegue forçar após ela. Em seguida, MAX escolhe a jogada com o melhor resultado garantido.

Essa é uma regra de decisão robusta: ela não depende de o oponente cometer erros.

Um exemplo concreto: Jogo da Velha

O Jogo da Velha é pequeno o suficiente para que o minimax possa buscar na árvore de jogo completa.

Uma definição comum de utilidade:

  • MAX = X, MIN = O
  • Utility(s):
    • X vence: +1
    • empate: 0
    • O vence: −1

A partir do tabuleiro vazio inicial, o minimax explora todas as sequências possíveis de jogadas. Se ambos jogarem de forma ótima, o minimax calculará que o valor do estado inicial é 0 (um empate forçado). Então ele selecionará qualquer jogada que preserve esse valor.

Isso ilustra um ponto importante:

  • O minimax não necessariamente tenta “vencer rápido”.
  • Ele tenta maximizar a utilidade final sob oposição ótima.
  • Se o melhor resultado possível for um empate, o minimax conduzirá para o empate.

Algoritmo minimax básico (pseudocódigo)

Aqui está uma implementação clara e direta de minimax. Esta versão busca apenas até estados terminais (sem limite de profundidade):

def minimax_value(state, maximizing_player):
    if terminal_test(state):
        return utility(state)

    if maximizing_player:  # MAX node
        v = float("-inf")
        for action in actions(state):
            v = max(v, minimax_value(result(state, action), False))
        return v
    else:  # MIN node
        v = float("inf")
        for action in actions(state):
            v = min(v, minimax_value(result(state, action), True))
        return v


def minimax_decision(state):
    best_action = None
    best_value = float("-inf")
    for action in actions(state):
        v = minimax_value(result(state, action), False)
        if v > best_value:
            best_value = v
            best_action = action
    return best_action

Complexidade

Seja:

  • (b) = fator de ramificação (branching factor) (média de jogadas legais por estado)
  • (m) = profundidade máxima (meios-lances (plies)) até terminal

Então a complexidade de tempo é:

  • Tempo: (O(b^m)) (explode rapidamente)
  • Espaço: (O(m)) para recursão em profundidade (ignorando o armazenamento do estado do jogo)

Esse custo exponencial é o motivo pelo qual, na prática, o minimax depende fortemente de otimizações.

Minimax com limite de profundidade e funções de avaliação

Muitos jogos (notavelmente o xadrez) têm árvores de jogo grandes demais para buscar até estados terminais. A abordagem prática padrão é:

  • Buscar apenas até a profundidade (d)
  • Nos estados de corte, retornar uma função de avaliação (evaluation function) heurística em vez da utilidade real

Isso produz o minimax com limite de profundidade (depth-limited minimax):

  • Se TerminalTest(s): retornar Utility(s)
  • Senão, se Depth == 0: retornar Eval(s)
  • Senão, recursar normalmente

Funções de avaliação na prática

Uma função de avaliação Eval(s) estima quão favorável é uma posição não terminal para MAX. Exemplos:

  • Xadrez: material ponderado + mobilidade + segurança do rei + estrutura de peões
  • Damas: contagem de peças + peças avançadas + controle do centro
  • Othello: diferença de discos + ocupação de cantos + estabilidade

Funções de avaliação são uma grande alavanca de projeto: uma avaliação melhor muitas vezes supera uma busca mais profunda com avaliação ruim.

Você pode pensar em Eval(s) como uma heurística feita à mão (ou, em sistemas modernos, aprendida por um modelo).

O efeito horizonte (e busca de quiescência)

Uma armadilha bem conhecida é o efeito horizonte (horizon effect): uma busca com limite de profundidade pode não captar um evento tático logo além de sua profundidade de corte (por exemplo, uma sequência forçada de capturas no xadrez), levando a avaliações instáveis.

Uma mitigação comum é a busca de quiescência (quiescence search):

  • No limite de profundidade, não avaliar imediatamente.
  • Estender a busca para posições “ruidosas”, explorando jogadas forçantes (capturas, xeques) até alcançar uma posição “quieta”.
  • Então aplicar Eval.

A busca de quiescência melhora a estabilidade tática ao custo de computação adicional.

Poda alfa–beta (otimização-chave)

A poda alfa–beta (alpha–beta pruning) é a otimização padrão para minimax. Ela evita buscar ramos que não podem afetar a decisão final.

  • (\alpha): melhor (maior) valor encontrado até agora ao longo do caminho para MAX
  • (\beta): melhor (menor) valor encontrado até agora ao longo do caminho para MIN

Se, em qualquer momento:

  • MAX encontra um valor (\ge \beta), MIN evitará esse ramo → poda
  • MIN encontra um valor (\le \alpha), MAX evitará esse ramo → poda

A poda alfa–beta é coberta em detalhes em Poda Alfa-Beta, mas o principal aprendizado prático é:

  • Com boa ordenação de jogadas, a poda alfa–beta pode reduzir drasticamente a complexidade efetiva.
  • No melhor caso, ela pode se aproximar de (O(b^{m/2})), efetivamente dobrando a profundidade pesquisável.

Pseudocódigo de alfa–beta (com limite de profundidade)

def alphabeta(state, depth, alpha, beta, maximizing_player):
    if terminal_test(state):
        return utility(state)
    if depth == 0:
        return eval_fn(state)

    if maximizing_player:
        v = float("-inf")
        for action in actions(state):
            v = max(v, alphabeta(result(state, action), depth - 1, alpha, beta, False))
            alpha = max(alpha, v)
            if alpha >= beta:  # beta cutoff
                break
        return v
    else:
        v = float("inf")
        for action in actions(state):
            v = min(v, alphabeta(result(state, action), depth - 1, alpha, beta, True))
            beta = min(beta, v)
            if beta <= alpha:  # alpha cutoff
                break
        return v

Técnicas práticas de engenharia usadas com minimax

Além de alfa–beta, programas reais que jogam usam várias técnicas padrão.

Ordenação de jogadas (crítica para alfa–beta)

O poder de poda do alfa–beta depende fortemente de buscar primeiro as melhores jogadas. Heurísticas comuns de ordenação incluem:

  • Capturas/xeques primeiro (jogadas táticas)
  • Jogada da variação principal primeiro (melhor linha da iteração anterior)
  • Heurística da jogada “killer”: jogadas que causaram cortes na mesma profundidade anteriormente
  • Heurística de histórico: preferir globalmente jogadas que frequentemente causam cortes

Uma boa ordenação pode ser a diferença entre explorar milhões versus bilhões de nós.

Aprofundamento iterativo

Em vez de buscar diretamente até a profundidade (d), programas frequentemente fazem:

  • Buscar profundidade 1, depois 2, depois 3, … até o tempo acabar.

Benefícios:

  • Produz um algoritmo a qualquer momento (anytime algorithm): sempre tem uma “melhor jogada atual”.
  • Fornece forte ordenação de jogadas (usa a melhor linha da profundidade (k) para ordenar a profundidade (k+1)).
  • Funciona bem com controles de tempo (por exemplo, relógios de xadrez).

Tabelas de transposições (cache de estados repetidos)

Sequências diferentes de jogadas podem chegar à mesma posição; isso é uma transposição (transposition). Uma tabela de transposições (transposition table) armazena em cache posições avaliadas para evitar recomputação.

Detalhes de implementação:

  • Use um hash do estado (por exemplo, hashing de Zobrist (Zobrist hashing) no xadrez).
  • Armazene:
    • valor avaliado
    • profundidade de busca
    • tipo de limite (exato / limite inferior / limite superior)
    • melhor jogada (para ordenação)

Tabelas de transposições são essenciais em jogos com muitas transposições (xadrez, damas).

Janelas de aspiração

Ao usar aprofundamento iterativo, muitas vezes você tem um bom palpite para a pontuação na próxima profundidade. Você pode buscar com uma janela ([\alpha, \beta]) estreita em torno desse palpite para aumentar a poda. Se a pontuação cair fora da janela, você busca novamente com uma janela mais ampla.

Essa é uma otimização prática de velocidade usada em muitos motores.

Negamax: uma formulação equivalente mais simples

Em jogos de dois jogadores e soma zero, o minimax pode ser escrito em uma forma simétrica compacta chamada negamax (negamax), usando a identidade:

[ \max(x) = -\min(-x) ]

O negamax trata ambos os jogadores de maneira uniforme, invertendo sinais ao alternar turnos. Isso frequentemente simplifica o código, especialmente quando combinado com alfa–beta.

Variantes e extensões

Expectiminimax (jogos com chance)

Se o jogo tem aleatoriedade (dados, cartas embaralhadas), a árvore inclui nós de chance (chance nodes) que calculam a esperança sobre os resultados:

[ V(s) = \sum_{o} P(o \mid s) , V(\text{Result}(s, o)) ]

Isso é comum em cenários no estilo gamão, mas está fora do pressuposto determinístico do minimax puro.

Jogos não soma zero e multi-jogador

O minimax depende de uma única utilidade escalar alinhada por oposição. Em:

  • cenários de não soma zero (non-zero-sum) (por exemplo, negociação)
  • jogos multi-jogador

você pode precisar de generalizações (por exemplo, utilidades vetoriais, conceitos de equilíbrio). O minimax deixa de ser toda a história.

Onde o minimax é usado (e por que ainda importa)

IA clássica para jogos de tabuleiro

Minimax + alfa–beta + funções de avaliação formaram a base de:

  • motores de xadrez por décadas
  • programas de damas e Othello
  • muitos solucionadores de jogos de “informação perfeita”

Mesmo em sistemas modernos, componentes do minimax continuam relevantes para busca tática, finais, ou tomada de decisão restrita.

Sistemas híbridos com aprendizado

IAs modernas para jogos frequentemente combinam busca com avaliação aprendida ou políticas (policies):

  • Uma rede neural (neural network) pode fornecer Eval(s) e/ou prioris de jogada (move priors) para ordenação.
  • A busca fornece antecipação (lookahead) e correção tática.

Esse padrão de “avaliação aprendida + busca” aparece em muitos sistemas adjacentes ao Aprendizado por Reforço, e contrasta com abordagens como Busca em Árvore de Monte Carlo (que estima valores via amostragem em vez de retropropagações completas do minimax).

Intuições de segurança e tomada de decisão robusta

A ideia do minimax de “maximizar o pior caso” também aparece amplamente em otimização robusta (robust optimization) e pensamento adversarial (adversarial thinking) (embora os detalhes algorítmicos difiram significativamente fora de jogos por turnos).

Limitações e armadilhas comuns

  • Explosão exponencial: Sem poda e heurísticas, o minimax se torna intratável rapidamente.
  • Erro de avaliação domina em profundidades rasas: Uma função de avaliação fraca pode tornar uma busca mais profunda menos valiosa do que o esperado.
  • Efeito horizonte: Limites de profundidade podem esconder eventos decisivos logo além do corte.
  • Pressuposto de oponente ótimo: Contra humanos ou bots mais fracos, o minimax pode escolher jogadas excessivamente conservadoras; variantes às vezes modelam oponentes subótimos.
  • Requisito de informação perfeita: Jogos com informação oculta exigem outros formalismos (estados de crença, amostragem, modelagem do oponente).

Resumo

Minimax é um algoritmo fundamental de busca adversária que:

  • modela jogos de dois jogadores e soma zero como uma árvore de jogo
  • usa regras recursivas de retropropagação max/min para calcular valores sob jogo ótimo
  • torna-se prático por meio de:
    • limites de profundidade + funções de avaliação
    • Poda Alfa-Beta
    • técnicas de engenharia como ordenação de jogadas, aprofundamento iterativo e tabelas de transposições

Mesmo com a IA moderna usando cada vez mais abordagens baseadas em aprendizado, o minimax permanece um conceito central: ele formaliza o planejamento adversarial ótimo e fornece a ponte conceitual entre a busca clássica e os sistemas modernos de jogo.