Poda alfa-beta

A poda alfa-beta acelera a busca realizada por um motor de xadrez, um programa que compara lances e respostas. A busca pode ser visualizada como uma árvore: cada nó é uma posição, e cada ramo é um lance legal. Sem a poda, o programa examinaria muitas continuações que acabariam se mostrando irrelevantes.

O método mantém dois limites durante a busca. Alfa é o melhor resultado que um lado já pode garantir no caminho atual. Beta é um limite criado por uma alternativa que o adversário já tem disponível. Quando uma continuação se torna tão ruim que um jogador racional nunca a escolheria, continuar a analisá-la não pode mudar a decisão no nó superior.

O ramo é interrompido por causa de um limite lógico na árvore, não apenas porque um lance parece pouco atraente. Com a mesma profundidade e as mesmas avaliações no limite da busca, alfa-beta retorna a mesma escolha que uma busca completa que pressupõe as melhores respostas de ambos os lados.

A economia depende muito da ordem dos lances. Testar primeiro os lances fortes estabelece limites úteis mais cedo e permite interromper mais ramos sem análise adicional. Uma função de avaliação, que atribui uma estimativa numérica a uma posição, fornece os valores nos pontos em que a busca finita termina.