Poda Alfa-Beta

Visão geral

Poda alfa–beta (alpha–beta pruning) é uma otimização clássica para a busca minimax (minimax search) em jogos de dois jogadores (two-player), de soma zero (zero-sum), de informação perfeita (perfect-information) (por exemplo, xadrez, damas, Othello). Ela produz a mesma escolha de movimento que o minimax puro, mas pode pular a avaliação (“podar”) de grandes partes da árvore do jogo que não podem afetar a decisão final.

A poda alfa–beta é uma das ideias fundamentais em busca adversarial (adversarial search):

Ela se baseia diretamente em Minimax: mesmo objetivo, mesmo valor retornado.
Ela complementa abordagens baseadas em amostragem (sampling-based approaches) como Busca em Árvore de Monte Carlo, frequentemente usada quando a busca por força bruta (brute-force search) é inviável.

A ideia-chave é manter limites (bounds) sobre o que o jogador atual pode garantir:

α (alpha): a melhor (maior) pontuação que o jogador maximizador pode garantir até agora.
β (beta): a melhor (menor) pontuação que o jogador minimizador pode garantir até agora.

Quando o algoritmo descobre que continuar descendo por um ramo não pode melhorar esses limites, ele para de explorar esse ramo.

Quando alfa–beta se aplica (suposições)

A poda alfa–beta é tipicamente descrita para:

Jogos de dois jogadores
Recompensas de soma zero (o ganho de um jogador é a perda do outro)
Informação perfeita (sem cartas/dados escondidos)
Transições determinísticas

Ainda é possível adaptá-la a cenários relacionados (por exemplo, na forma negamax; variantes multijogador existem, mas são menos elegantes), porém as garantias e a intuição padrão ficam mais claras sob essas suposições.

Recapitulando minimax (por que a poda é possível)

No minimax, uma árvore de jogo alterna:

nós MAX (MAX nodes): o jogador atual escolhe o movimento que maximiza a avaliação.
nós MIN (MIN nodes): o oponente escolhe o movimento que minimiza a avaliação.

Os valores das folhas vêm de:

Utilidades terminais (vitória/derrota/empate), ou
Uma função de avaliação heurística (heuristic evaluation function) ao usar limites de profundidade (depth limits) (comum em motores de xadrez).

A complexidade de tempo ingênua é:

Tempo: (O(b^d))
onde (b) = fator de ramificação (branching factor) (movimentos por posição) e (d) = profundidade (meias-jogadas (plies))
Espaço: (O(d)) para recursão em profundidade (depth-first recursion) (ignorando tabelas de transposição (transposition tables))

A poda alfa–beta reduz o número de nós visitados ao notar que algumas subárvores não podem, de forma alguma, influenciar o resultado do minimax.

O significado de α e β (intuição de limites)

Pense em termos de garantias:

α (alpha): um limite inferior para MAX

Em um nó MAX, MAX quer um valor alto. À medida que MAX avalia os filhos, ele acompanha o melhor valor encontrado até então. Esse valor é α.

α começa em (-\infty) (nenhuma garantia ainda).
À medida que MAX encontra opções melhores, α aumenta.
α é um limite inferior do que MAX pode forçar a partir deste nó, dadas as informações exploradas.

β (beta): um limite superior para MIN

Em um nó MIN, MIN quer um valor baixo. À medida que MIN avalia os filhos, ele acompanha o melhor (menor) valor encontrado até então. Esse valor é β.

β começa em (+\infty).
À medida que MIN encontra opções melhores (menores), β diminui.
β é um limite superior do que MAX pode obter se MIN jogar de forma ótima a partir deste nó.

A condição de poda: α ≥ β

Ao explorar um nó, se em algum momento você encontrar:

α ≥ β

então o nó atual já é bom demais para um lado (ou ruim demais para o outro) a ponto de o oponente nunca permitir esse resultado, dadas alternativas já descobertas mais acima na árvore. Portanto, os irmãos restantes sob este nó não podem afetar a decisão final, e você pode parar de explorá-los.

Isso é frequentemente chamado de um corte (cutoff):

Em um nó MIN, é comumente descrito como um corte beta (beta cutoff).
Em um nó MAX, é comumente descrito como um corte alfa (alpha cutoff).

Como a poda funciona (um passo a passo prático)

Considere um nó MAX na raiz (MAX para jogar). Suponha que MAX já examinou um movimento e encontrou que ele leva a um valor de α = 6. Isso significa: “MAX pode garantir pelo menos 6 ao escolher esse movimento”.

Agora MAX considera outro movimento, que leva a um nó MIN (oponente para responder). MIN começa a explorar as respostas.

MIN encontra uma resposta que produz valor 5 (da perspectiva de MAX).
MIN preferirá ≤ 5 (pois MIN minimiza).
Então, nesse nó MIN, β se torna 5.

Mas na raiz, MAX já tem α = 6 disponível a partir de um movimento diferente. Se MIN puder forçar a linha a ser 5, MAX nunca escolheria esse segundo movimento na raiz (porque 5 é pior do que 6). Portanto:

assim que MIN estabelece β = 5, temos β ≤ α (isto é, α ≥ β),
então podemos podar o restante das respostas de MIN para esse movimento: MAX não vai escolhê-lo de qualquer forma.

Esse é o coração do alfa–beta: uma vez que uma linha é provada pior do que uma alternativa conhecida, mais detalhes tornam-se irrelevantes.

Algoritmo alfa–beta (pseudocódigo)

Abaixo está um minimax alfa–beta padrão com limite de profundidade (expresso em um estilo direto MAX/MIN). Esta versão retorna o valor minimax; na prática, você também acompanha o melhor movimento na raiz.

def alphabeta(node, depth, alpha, beta, maximizing_player):
    if depth == 0 or node.is_terminal():
        return evaluate(node)

    if maximizing_player:
        value = float("-inf")
        for child in node.children():
            value = max(value, alphabeta(child, depth - 1, alpha, beta, False))
            alpha = max(alpha, value)
            if alpha >= beta:
                break  # beta cutoff
        return value
    else:
        value = float("inf")
        for child in node.children():
            value = min(value, alphabeta(child, depth - 1, alpha, beta, True))
            beta = min(beta, value)
            if alpha >= beta:
                break  # alpha cutoff
        return value

Notas sobre correção

A poda alfa–beta nunca poda um ramo que poderia mudar o valor final do minimax.
Ela retorna o mesmo valor que o minimax completo, apenas mais rápido.
A correção depende da suposição de que ambos os jogadores jogam de forma ótima (cenário minimax).

Complexidade e por que a ordenação de movimentos importa

O impacto da poda alfa–beta depende dramaticamente da ordenação de movimentos (move ordering) na busca.

Pior caso

Se os movimentos são ordenados da forma menos útil (por exemplo, melhores movimentos por último), a poda alfa–beta pode quase não podar nada:

Tempo: ainda (O(b^d))

Melhor caso (ordenação perfeita de movimentos)

Se os melhores movimentos são buscados primeiro em cada nó, a poda alfa–beta atinge sua melhoria famosa:

Tempo: (O(b^{d/2})) (frequentemente citada como aproximadamente dobrar a profundidade de busca pelo mesmo custo)

Intuição: com excelente ordenação, o primeiro filho frequentemente estabelece limites α/β fortes, permitindo que muitos irmãos sejam cortados rapidamente.

Caso típico/médio

Motores reais ficam entre esses extremos. Com boas heurísticas, a poda alfa–beta frequentemente gera grandes economias por fator constante e pode permitir buscas significativamente mais profundas.

Ordenação de movimentos: o “ingrediente secreto” de uma poda eficaz

Como a poda depende de encontrar rapidamente limites fortes, implementações práticas de alfa–beta investem bastante em ordenação de movimentos.

Heurísticas comuns em motores de jogos incluem:

Capturas/promoções primeiro (movimentos que provavelmente mudam a avaliação de forma brusca)
Xeques primeiro (no xadrez)
Heurística do movimento assassino (killer move heuristic): movimentos que causaram cortes na mesma profundidade em outros ramos são tentados cedo
Heurística de histórico (history heuristic): manter estatísticas sobre movimentos que frequentemente causam cortes e priorizá-los
Movimento da Variação Principal (PV) (Principal Variation (PV) move) primeiro: buscar primeiro a melhor linha encontrada em iterações anteriores
Ordenação por tabela de transposição (transposition table ordering): se uma posição foi avaliada antes, reutilizar seu melhor movimento como o primeiro candidato

Um padrão prático importante é o aprofundamento iterativo (iterative deepening):

Buscar profundidade 1, escolher o melhor movimento.
Buscar profundidade 2, mas tentar primeiro o melhor movimento anterior.
Repetir até a profundidade (d).

O aprofundamento iterativo pode parecer desperdício (re-buscar profundidades rasas), mas ele melhora dramaticamente a ordenação de movimentos e funciona extremamente bem com alfa–beta na prática.

Um pequeno exemplo concreto (poda em ação)

Suponha que MAX esteja escolhendo entre dois movimentos, A e B:

Avaliar A completamente produz valor 8.
Então, na raiz, α = 8.

Agora explore B, que leva a um nó MIN. MIN examina uma resposta e encontra que ela leva ao valor 7 (da perspectiva de MAX). Para MIN:

β = 7 nesse nó MIN.

Agora compare:

α (raiz) = 8
β (nó MIN atual sob B) = 7

Como α ≥ β, MIN já pode forçar B a ser ≤ 7, e MAX já tem um 8 garantido via A. Logo, MAX nunca escolherá B, e podemos podar todas as respostas restantes sob B.

Mesmo esse exemplo pequeno mostra o mecanismo essencial: resultados fortes cedo (boa ordenação) criam limites apertados que disparam a poda.

Detalhes de implementação que importam na prática

Formulação negamax (comum em código)

Muitas implementações usam negamax, que explora a simetria de soma zero para unificar MAX e MIN em uma única função. A ideia:

Valor para o jogador atual = negativo do valor para o oponente.

Isso reduz duplicação de código e, muitas vezes, combina bem com alfa–beta.

def negamax(node, depth, alpha, beta, color):
    # color = +1 for current player, -1 for opponent
    if depth == 0 or node.is_terminal():
        return color * evaluate(node)

    value = float("-inf")
    for child in node.children():
        value = max(value, -negamax(child, depth - 1, -beta, -alpha, -color))
        alpha = max(alpha, value)
        if alpha >= beta:
            break
    return value

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

Em jogos grandes (como xadrez), você não consegue buscar até estados terminais. Em vez disso:

Busque até uma profundidade fixa (ou limite de tempo).
Avalie as folhas heuristicamente.

A poda alfa–beta permanece correta em relação ao limite de profundidade e à função de avaliação: ela retorna a decisão minimax para a árvore de jogo truncada.

O efeito horizonte e a busca de quietude

Uma armadilha clássica do minimax com limite de profundidade é o efeito horizonte (horizon effect): a busca para logo antes de uma grande mudança tática (por exemplo, uma sequência de capturas), levando a avaliações instáveis.

Uma correção comum é a busca de quietude (quiescence search), que estende a busca além da profundidade nominal para posições “barulhentas” (como capturas forçadas) até alcançar posições “quietas”. A poda alfa–beta normalmente também é usada dentro da busca de quietude.

Tabelas de transposição (cache)

Árvores de jogo geralmente não são árvores na prática — elas são grafos acíclicos direcionados (directed acyclic graphs, DAGs) porque a mesma posição pode ser alcançada por diferentes sequências de movimentos (uma transposição (transposition)).

Uma tabela de transposição armazena:

posições avaliadas,
melhores movimentos,
e às vezes limites α/β (entradas de limite exato/inferior/superior (exact/lower/upper bound entries)).

Isso pode reduzir enormemente trabalho repetido e melhorar a ordenação de movimentos. Alfa–beta + tabelas de transposição é uma combinação padrão em motores fortes.

O que a poda alfa–beta não faz

Ela não muda a decisão ótima em comparação ao minimax.
Ela não garante acelerações sem boa ordenação de movimentos.
Ela não é usada principalmente em jogos com:
- nós de chance (chance nodes) (dados) sem modificação (expectiminimax),
- informação oculta (hidden information) (pôquer), em que outros modelos se aplicam.

Para fatores de ramificação extremamente grandes e horizontes longos, sistemas modernos frequentemente usam abordagens como Busca em Árvore de Monte Carlo ou combinam busca com políticas de avaliação aprendidas (learned evaluation policies).

Aplicações práticas

Motores clássicos de jogos de tabuleiro

A poda alfa–beta tem sido central em motores por décadas:

Xadrez: fator de ramificação ~30–40 em meio-jogos típicos; alfa–beta mais ordenação agressiva, aprofundamento iterativo, busca de quietude e tabelas de transposição é uma receita padrão.
Damas/Othello: resultados igualmente fortes com busca no estilo minimax.

Mesmo na era do aprendizado profundo (deep learning), alfa–beta continua relevante:

Alguns sistemas ainda dependem de alfa–beta para cálculo tático e busca precisa.
Abordagens híbridas podem usar redes neurais (neural nets) para avaliação/ordenação de movimentos, mantendo o alfa–beta para antecipação (lookahead).

Qualquer planejamento adversarial com racionalidade limitada

Fora dos jogos tradicionais, ideias de alfa–beta aparecem em planejamento adversarial sempre que:

há um objetivo do tipo minimax,
o ambiente é determinístico,
e limites podem ser mantidos para cortar ramos irrelevantes.

Resumo

A poda alfa–beta é uma otimização de Minimax que:

Mantém dois limites:
- α: melhor pontuação garantida para MAX até agora (limite inferior)
- β: melhor pontuação garantida para MIN até agora (limite superior)
Poda quando α ≥ β, porque exploração adicional não pode mudar a escolha final.
Melhora o tempo de execução de (O(b^d)) no pior caso para cerca de (O(b^{d/2})) no melhor caso com excelente ordenação de movimentos.
É mais eficaz quando combinada com:
- forte ordenação de movimentos (movimento da PV, heurísticas do movimento assassino/de histórico, capturas primeiro),
- aprofundamento iterativo,
- tabelas de transposição,
- e frequentemente busca de quietude para estabilidade tática.

A poda alfa–beta permanece uma técnica fundamental em busca adversarial — simples em princípio, mas extremamente poderosa quando bem engenheirada.