A poda alfa-beta é um algoritmo de busca em árvore que busca diminuir o número de nós avaliados pelo algoritmo minimax em sua árvore de busca. É um algoritmo de busca adversarial utilizado comumente para jogos de tabuleiro de dois jogadores, como Jogo da Velha, Xadrez e Ligação 4. O algoritmo interrompe a avaliação de um movimento quando pelo menos uma possibilidade foi encontrada que demonstra que o movimento é pior do que um movimento previamente examinado. Tais movimentos não precisam ser avaliados mais a fundo. Quando aplicado a uma árvore minimax padrão, ele retorna o mesmo movimento que o minimax retornaria, mas poda ramos que não podem, de forma alguma, influenciar a decisão final.
O algoritmo é um exemplo clássico de abordagem de branch and bound na inteligência artificial, e é a base de muitos programas de jogos, incluindo os primeiros computadores de xadrez e os motores modernos. Seus ganhos de eficiência permitem buscas mais profundas dentro do mesmo orçamento computacional, tornando-o uma técnica fundamental na busca adversarial.
História
John McCarthy, durante o Workshop de Dartmouth em 1956, conheceu Alex Bernstein, da IBM, que estava escrevendo um programa de xadrez. McCarthy inventou a busca alfa-beta e a recomendou a Bernstein, mas Bernstein não se convenceu. Allen Newell e Herbert A. Simon, que utilizaram o que McCarthy chamou de "aproximação" em 1958, escreveram que a alfa-beta "parece ter sido reinventada diversas vezes". Arthur Samuel já possuía uma versão inicial para uma simulação de damas. Richards, Timothy Hart, Michael Levin e/ou Daniel Edwards também inventaram a alfa-beta de forma independente nos Estados Unidos. McCarthy propôs ideias semelhantes durante o workshop e as sugeriu a um grupo de seus alunos, incluindo Alan Kotok, no MIT, em 1961. Alexander Brudno concebeu o algoritmo alfa-beta de forma independente, publicando seus resultados em 1963. Donald Knuth e Ronald W. Moore refinaram o algoritmo em 1975. Judea Pearl provou sua otimalidade em termos de tempo de execução esperado para árvores com valores de folha atribuídos aleatoriamente, em dois artigos. A otimalidade da versão randomizada da alfa-beta foi demonstrada por Michael Saks e Avi Wigderson em 1986.
Ideia Central
Uma árvore de jogo pode representar muitos jogos de soma zero para dois jogadores, como xadrez, damas e reversi. Cada nó na árvore representa uma situação possível no jogo. A cada nó terminal (resultado) de um ramo é atribuída uma pontuação numérica que determina o valor do resultado para o jogador que tem a vez de jogar.
O algoritmo mantém dois valores, alfa e beta, que representam, respectivamente, a pontuação mínima que o jogador maximizador tem garantida e a pontuação máxima que o jogador minimizador tem garantida. Inicialmente, alfa é infinito negativo e beta é infinito positivo, ou seja, ambos os jogadores começam com sua pior pontuação possível. Sempre que a pontuação máxima que o jogador minimizador (o jogador "beta") tem garantida se torna menor que a pontuação mínima que o jogador maximizador (o jogador "alfa") tem garantida (ou seja, beta < alfa), o jogador maximizador não precisa considerar mais descendentes deste nó, pois eles nunca serão alcançados na partida real.
Para ilustrar com um exemplo real, suponha que alguém está jogando xadrez e é a sua vez. O movimento "A" melhorará a posição do jogador. O jogador continua a procurar movimentos para garantir que não perdeu um melhor. O movimento "B" também é um bom movimento, mas o jogador então percebe que ele permitirá que o oponente force o xeque-mate em dois lances. Assim, outros desdobramentos do movimento B não precisam mais ser considerados, pois o oponente pode forçar a vitória. A pontuação máxima que o oponente poderia forçar após o movimento B é infinito negativo: uma derrota para o jogador. Isso é menor do que a posição mínima previamente encontrada; o movimento A não resulta em uma derrota forçada em dois lances.
Melhorias em Relação ao Minimax Ingênuo
O benefício da poda alfa-beta reside no fato de que ramos da árvore de busca podem ser eliminados. Dessa forma, o tempo de busca pode ser limitado ao subconjunto mais 'promissor', e uma busca mais profunda pode ser realizada no mesmo tempo. Como seu predecessor, ele pertence à classe de algoritmos de branch and bound. A otimização reduz a profundidade efetiva para pouco mais da metade da do minimax simples, se os nós forem avaliados em uma ordem ótima ou quase ótima (melhor escolha para o lado a jogar ordenada primeiro em cada nó).
Com um fator de ramificação (médio ou constante) de b e uma profundidade de busca de d lances, o número máximo de posições de nós folha avaliadas (quando a ordenação dos movimentos é pessimal) é O(b^d) - o mesmo que uma busca minimax simples. Se a ordenação dos movimentos para a busca for ótima (ou seja, os melhores movimentos são sempre buscados primeiro), o número de posições de nós folha avaliadas é cerca de O(b 1 b 1 ... b) para profundidade ímpar e O(b 1 b 1 ... 1) para profundidade par, ou O(b^(d/2)) = O(√(b^d)). Neste último caso, onde a profundidade da busca é par, o fator de ramificação efetivo é reduzido à sua raiz quadrada, ou equivalentemente, a busca pode ir duas vezes mais fundo com a mesma quantidade de computação. A explicação para b1b1... é que todos os movimentos do primeiro jogador devem ser estudados para encontrar o melhor, mas para cada um deles, apenas o melhor movimento do segundo jogador é necessário para refutar todos os outros movimentos do primeiro jogador (exceto o primeiro e melhor) - a poda alfa-beta garante que nenhum outro movimento do segundo jogador precise ser considerado.
Quando os nós são considerados em uma ordem aleatória (ou seja, o algoritmo randomiza), assintoticamente, o número esperado de nós avaliados em árvores uniformes com valores de folha binários é Theta(((b-1+√(b^2+14b+1))/4)^d). Para as mesmas árvores, quando os valores são atribuídos aos valores das folhas de forma independente e igualmente provável (zero ou um), o número esperado de nós avaliados é Theta((b/2)^d).
Considerações de Implementação
Na prática, a poda alfa-beta é frequentemente implementada com aprofundamento iterativo, onde a profundidade da busca é aumentada incrementalmente. A ordenação dos movimentos é crítica para alcançar um desempenho quase ótimo; heurísticas comuns incluem examinar capturas primeiro, usar movimentos killers e empregar tabelas de transposição. O algoritmo pode ser estendido com técnicas como busca de quiescência para evitar efeitos de horizonte, e forma a base para algoritmos mais avançados, como busca de variação principal e negascout. A poda alfa-beta é amplamente utilizada em programas de xadrez, incluindo aqueles que rodam em sistemas de computador-de-xadrez, e foi integrada a várias estruturas de IA para jogos.
Legado e Impacto
A poda alfa-beta teve um impacto duradouro na inteligência artificial e na teoria dos jogos. Foi um componente-chave nos primeiros programas de xadrez e permanece relevante nos motores de jogos modernos, especialmente para jogos com grandes fatores de ramificação. As melhorias de eficiência do algoritmo foram extensivamente estudadas, e seus princípios influenciaram outras áreas de busca e otimização. Embora técnicas mais recentes, como aprendizado-de-máquina e aprendizado-profundo, tenham transformado a IA para jogos, a poda alfa-beta continua sendo uma ferramenta fundamental na busca adversarial, e seu desenvolvimento histórico destaca a natureza colaborativa e iterativa da pesquisa em IA.