Poda (computação)

Na ciência da computação, poda (em inglês: pruning) é a remoção de partes de uma árvore de decisão ou de neurônios de uma rede neural. Isso pode ocorrer porque não há significativa contribuição para a precisão ou interpretabilidade da árvore, reduzindo-se a complexidade da árvore e aumentando-se a sua generalização. Uma estratégia comum é aumentar a árvore até que cada nó contenha um pequeno número de instâncias e, em seguida, usar a poda para remover os nós que não fornecem informações adicionais.

Poda alfa-beta

Uma ilustração da Poda Alfa Beta

A poda alfa-beta (ou poda α-β) é uma variação do algoritmo minimax que visa reduzir o número de nós que são avaliados na árvore de busca. É uma busca adversarista comumente utilizada na implementação de jogadores automáticos em jogos com dois jogadores (Jogo da Velha, Xadrez, Go, etc.). Ele para completamente de avaliar um movimento quando ele encontra, de maneira comprovada, um movimento cujo valor associado seja pior que um movimento previamente examinado. Sendo assim, os movimentos posteriores não necessitam ser avaliados.

A poda alfa beta não altera o resultado da avaliação de uma sub-árvore e a sua vantagem está no fato de que, em árvores de busca com um fator de ramificação muito grande, a utilização de memória será significativamente reduzida.

Ideia principal

O algoritmo mantém dois valores, alpha e beta, os quais representam a pontuação máxima que é garantida ao jogador maximizador (max) e a pontuação mínima que é garantida ao jogador minimizador (min), respectivamente. Inicialmente, alpha recebe o valor "infinito negativo" e beta, "infinito positivo". Portanto, ambos os jogadores iniciam com a suas piores pontuações possíveis.

Pode acontecer que, ao selecionar um ramo de um certo nó, a pontuação mínima que é garantida ao jogador minimizador se torne menor do que a pontuação máxima que é garantida ao jogador maximizador (beta <= alpha). Se isso ocorrer, o "nó pai" não deve selecionar esse nó, pois isso fará com que a pontuação para o node pai seja pior. Por fim, os outros ramos do nó não precisarão ser explorados.

Exemplo em linguagem matemática

O exemplo abaixo demonstra, de uma forma simples, o princípio matemático presente no funcionamento da poda α-β.

${\begin{aligned}\mathbf {minimax} &=\max \left\{\min \left\{5,10,20\right\},\min \left\{2,x,y\right\},\min \left\{15,7,2\right\}\right\}\\&=\max \left\{5,z,2\right\}{\mbox{ com }}z\leq 2\\&=5\\\end{aligned}}$

Note que, independente do valor de $x$ e $y$ o resultado da equação é o mesmo.