Problema
A poda alfa-beta dá a mesma resposta do minimax enquanto pula ramos que não podem mudar o resultado. Ela acompanha dois limites: alpha, a melhor pontuação que MAX já tem garantida, e beta, a melhor pontuação que MIN já tem garantida.
A árvore de jogo é completa: cada nó interno tem branching filhos e todas as folhas estão na mesma profundidade. leaves lista as pontuações das folhas da esquerda para a direita. A raiz é um nó MAX e os níveis se alternam MAX, MIN, MAX, …
Percorra os filhos da esquerda para a direita, começando com alpha = -∞ e beta = +∞:
- 'Em um nó MAX, depois de cada filho: best = max(best, value), depois alpha = max(alpha, best).'
- 'Em um nó MIN, depois de cada filho: best = min(best, value), depois beta = min(beta, best).'
- Assim que alpha ≥ beta, pule os filhos restantes do nó.
Implemente alpha_beta(leaves, branching).
Entrada
leaves: As pontuações das folhas, da esquerda para a direita; o comprimento é uma potência de branching.
branching: Filhos por nó interno.
Saída
Retorne [value, evaluated]: o valor minimax da raiz e quantas folhas foram avaliadas.
Restrições
2 ≤ branching ≤ 5, comprimento de leaves = branching^depth com 1 ≤ depth ≤ 8, no máximo 10.000 folhas
-1.000 ≤ cada folha ≤ 1.000
Exemplos
Entrada:
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2]
branching = 3
Saída esperada:
expected = [3, 7]Entrada:
std::vector<long long> leaves = {3, 12, 8, 2, 4, 6, 14, 5, 2};
long long branching = 3;
Saída esperada:
std::vector<long long> expected = {3, 7};Entrada:
long[] leaves = new long[] {3, 12, 8, 2, 4, 6, 14, 5, 2};
long branching = 3;
Saída esperada:
long[] expected = new long[] {3, 7};Explicação
O primeiro nó MIN vê 3, 12, 8 e retorna 3, então alpha = 3. O segundo nó MIN vê 2, beta = 2 ≤ alpha, então 4 e 6 são pulados. O terceiro vê 14, 5, 2 e retorna 2. O valor da raiz é max(3, 2, 2) = 3 depois de 7 das 9 folhas.
Entrada:
leaves = [5, 6, 7, 4]
branching = 2
Saída esperada:
expected = [5, 4]Entrada:
std::vector<long long> leaves = {5, 6, 7, 4};
long long branching = 2;
Saída esperada:
std::vector<long long> expected = {5, 4};Entrada:
long[] leaves = new long[] {5, 6, 7, 4};
long branching = 2;
Saída esperada:
long[] expected = new long[] {5, 4};Explicação
O nó MIN da esquerda avalia 5 e 6 e retorna 5, então alpha = 5. O nó MIN da direita avalia 7 (beta = 7) e depois 4 (beta = 4 ≤ 5). As 4 folhas são avaliadas e o valor é 5.
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.