Pesquisa Alfa-Beta
A pesquisa alfa-beta (também chamado corte alfa-beta ou poda alfa-beta ) é uma variante optimizada do processo de busca minimax , isto é, um algoritmo para determinar um óptimo movimento em jogos com duas partes opostas. Durante a pesquisa, dois valores - alfa e beta - são atualizados para indicar quais resultados os jogadores podem alcançar com o jogo ideal. Com a ajuda desses valores, pode-se decidir quais partes da árvore de busca não precisam ser examinadas porque não podem influenciar o resultado da solução do problema .
A pesquisa alfa-beta simples (não otimizada) oferece exatamente o mesmo resultado da pesquisa minimax.
Descrição informal
O algoritmo Minimax analisa a árvore de pesquisa completa. Ao fazer isso, os nós também são considerados que não estão incluídos no resultado (a escolha da ramificação na raiz). A pesquisa alfa-beta ignora todos os nós dos quais, no momento em que a pesquisa os atinge, já é certo que não podem influenciar o resultado.
Um exemplo claro de como funciona é um jogo para duas pessoas em que o primeiro jogador escolhe uma das várias sacolas e recebe de seu oponente o item de menor valor dessa sacola.
O algoritmo Minimax pesquisa todos os bolsos completamente para a seleção e, portanto, leva muito tempo. A pesquisa alfa-beta, por outro lado, inicialmente pesquisa apenas na primeira bolsa completamente o item de valor mínimo. Todos os outros bolsos são pesquisados apenas até que o valor de um objeto alcance ou caia abaixo deste mínimo. É então certo que esta bolsa não é melhor do que a primeira para o primeiro jogador, e a busca nela pode ser interrompida. Caso contrário, esta sacola será uma escolha melhor e seu valor mínimo servirá como uma nova fronteira para futuras pesquisas.
Situações semelhantes são familiares a todo jogador de xadrez que atualmente verifica um lance específico para ver se ele lhe parece vantajoso. Se, ao analisar o lance, ele encontrar uma resposta do oponente que é desfavorável para ele, ele considerará esse lance como "refutado" e o rejeitará. Seria inútil investigar mais respostas do oponente para determinar se ele tem réplicas mais eficazes e o quão ruim é o movimento em consideração.
O algoritmo
A pesquisa alfa-beta funciona da mesma maneira que a descrição informal acima. A ideia é que dois valores (alfa e beta) sejam passados que descrevem o pior cenário para os jogadores. O valor alfa é o resultado mínimo que o jogador A alcançará, o valor beta é o resultado máximo que o jogador B alcançará. (Deve-se notar aqui que para o jogador B é uma questão de obter o menor resultado possível, já que ele está jogando "minimizando"!)
Se um nó de maximização (do jogador A) tem um lance cujo retorno excede o valor beta, a busca neste nó é abortada ( corte beta , porque o jogador B nem mesmo ofereceria esta opção para A porque seria seu máximo anterior Concessão excederia). Se, em vez disso, o trem entregar um resultado que exceda o valor alfa atual, ele será aumentado de acordo.
O mesmo se aplica aos nós de minimização, com valores menores que alfa sendo cancelados (corte alfa) e o valor beta sendo ajustado para baixo.
A figura acima mostra um exemplo de árvore com 18 folhas, das quais apenas 12 são avaliadas. Os três valores delimitados de um nó interno descrevem o valor alfa, o valor de retorno e o valor beta.
O algoritmo de pesquisa usa uma chamada janela alfa-beta, cujo limite inferior é o valor alfa e o limite superior é o valor beta. Esta janela é passada para os nós filhos, começando na raiz com a janela máxima [-inf, inf]. As folhas 1, 2 e 3 são avaliadas por um nó maximizador e o melhor valor 10 é passado para o nó pai minimizador . Isso ajusta o valor beta e transfere a nova janela [-inf, 10] para o próximo nó filho de maximização , que tem as folhas 4, 5 e 6. O valor de retorno 12 da planilha 5 é tão bom que excede o valor beta 10. Assim, a folha 6 não precisa mais ser considerada porque o resultado 12 desta subárvore é melhor do que o da subárvore esquerda e, portanto, nunca seria selecionado pelo jogador minimizador.
O mesmo se aplica ao nó minimizador com corte 3-alfa. Embora essa subárvore tenha sido avaliada apenas parcialmente, é claro que o nó raiz maximizador nunca escolheria essa variante, porque o nó minimizador poderia forçar um resultado de no máximo 3, enquanto o resultado 12 é garantido da subárvore do meio.
implementação
Nota: As diferenças para o algoritmo Minimax simples são destacadas em amarelo.
Programa principal (extrato):
gespeicherterZug = NULL;
int gewuenschteTiefe = 4;
int bewertung = max(gewuenschteTiefe,
-unendlich, +unendlich);
if (gespeicherterZug == NULL)
es gab keine weiteren Zuege mehr (Matt oder Patt);
else
gespeicherterZug ausführen;
A variante normal é:
int max(int tiefe,
int alpha, int beta) {
if (tiefe == 0 or keineZuegeMehr(spieler_max))
return bewerten();
int maxWert = alpha;
Zugliste = generiereMoeglicheZuege(spieler_max);
for each (Zug in Zugliste) {
fuehreZugAus(Zug);
int wert = min(tiefe-1,
maxWert, beta);
macheZugRueckgaengig(Zug);
if (wert > maxWert) {
maxWert = wert;
if (tiefe == gewuenschteTiefe)
gespeicherterZug = Zug;
if (maxWert >= beta)
break;
}
}
return maxWert;
}
int min(int tiefe,
int alpha, int beta) {
if (tiefe == 0 or keineZuegeMehr(spieler_min))
return bewerten();
int minWert = beta;
Zugliste = generiereMoeglicheZuege(spieler_min);
for each (Zug in Zugliste) {
fuehreZugAus(Zug);
int wert = max(tiefe-1,
alpha, minWert);
macheZugRueckgaengig(Zug);
if (wert < minWert) {
minWert = wert;
if (minWert <= alpha)
break;
}
}
return minWert;
}
A variante NegaMax é:
int miniMax(int spieler, int tiefe,
int alpha, int beta) {
if (tiefe == 0 or keineZuegeMehr(spieler))
return bewerten(spieler);
int maxWert = alpha;
Zugliste = generiereMoeglicheZuege(spieler);
for each (Zug in Zugliste) {
fuehreZugAus(Zug);
int wert = -miniMax(-spieler, tiefe-1,
-beta, -maxWert);
macheZugRueckgaengig(Zug);
if (wert > maxWert) {
maxWert = wert;
if (tiefe == gewuenschteTiefe)
gespeicherterZug = Zug;
if (maxWert >= beta)
break;
}
}
return maxWert;
}
Nota: Enquanto a implementação padrão maximiza para um jogador e minimiza para o outro jogador, a variante Negamax maximiza para ambos os jogadores e troca e nega alfa e beta durante a recursão. Conclui-se que a função de avaliação deve se comportar de maneira diferente em ambas as implementações.
- Implementação padrão: quanto melhor for a posição no tabuleiro para o jogador que maximiza, maior será o valor de retorno da função de avaliação (função de avaliação ()). Quanto melhor for para o jogador que está minimizando, menor será o valor de retorno.
- Implementação do Negamax: Uma vez que ambos os jogadores maximizam, a função de avaliação deve entregar valores maiores quanto melhor for a posição do tabuleiro da pessoa que está desenhando (função de avaliação (jogador)). O valor é sempre dado do seu ponto de vista.
Otimizações
Se a árvore do jogo só pode ser calculada até uma certa profundidade devido à complexidade do jogo em consideração, basicamente duas abordagens de otimização são possíveis. Por um lado, a função de avaliação pode ser melhorada e, por outro lado, o próprio algoritmo alfa-beta oferece potencial de otimização. Quanto melhor for a função de avaliação, menos profundamente a árvore do jogo terá que ser visualizada para atingir um determinado nível de habilidade.
A seguir, apenas as otimizações da pesquisa alfa-beta são discutidas.
Pré-classificação de trens
Em contraste com o algoritmo Minimax, a ordem em que os nós filhos (trens) são processados desempenha um papel importante na pesquisa alfa-beta. Quanto mais rápido a janela alfa-beta é reduzida, mais pontos de corte são alcançados. É por isso que é importante primeiro olhar para os movimentos que dão o melhor resultado. Várias heurísticas são usadas na prática. No xadrez z. B. você pode classificar os movimentos de acordo com se ou qual peça é capturada, ou qual peça captura. “Torre vence senhora” é classificado antes de “torre vence torre” e “fazendeiro bate torre” é classificado entre os dois.
Pesquisa de variação principal
Um nó na pesquisa alfa-beta pertence a uma das três categorias (com base na variante NegaMax):
- Nó alfa: cada movimento subsequente retorna um valor menor ou igual a alfa, o que significa que nenhum movimento bom é possível aqui.
- Nó beta: pelo menos um movimento subsequente entrega um valor maior ou igual ao beta, o que significa um corte
- Nó de variação principal: pelo menos um trem subsequente entrega um valor maior que alfa, mas todos entregam um valor menor que beta.
Às vezes você pode ver logo em que nó é. Se o primeiro trem subsequente testado entregar um valor maior ou igual a beta, então é um nó beta. Se ele entregar um valor menor ou igual a alfa, então possivelmente é um nó alfa (desde que os trens sejam bem pré-classificados). No entanto, se entregar um valor entre alfa e beta, pode ser um nó de variação principal .
A pesquisa de variação principal agora assume que um movimento subsequente que fornece um valor entre alfa e beta acabará sendo o melhor movimento possível. Portanto, a janela alfa-beta abaixo do mínimo é (alfa, alfa + 1) reduzida (janela zero) para atingir um número máximo de cortes, mas para provar que os trens restantes são piores.
Se, ao pesquisar com esta janela zero, descobrir que o trem tem um valor maior que alfa (mas o resultado ainda é menor que beta , caso contrário você pode fazer um corte beta imediatamente ), a pesquisa deve ser repetida com uma janela maior: Lá se você já conhece um limite inferior para o valor de tensão da pesquisa de janela zero, a janela deve se estender a partir desse valor para beta durante a pesquisa de repetição . Por causa da busca por repetição às vezes necessária, este método só pode ser usado para obter sucesso se os trens forem bem pré-classificados, pois isso minimiza atribuições incorretas em uma das três categorias mencionadas. Ou seja, torna-se improvável que um movimento subsequente tenha um valor melhor do que alfa e a pesquisa terá que ser repetida. Por outro lado, os nós de variação principais também podem ser usados em conjunto com o aprofundamento iterativo para pré-classificar os trens.
int AlphaBeta(int tiefe, int alpha, int beta)
{
if (tiefe == 0)
return Bewerten();
BOOL PVgefunden = FALSE;
best = -unendlich;
Zugliste = GeneriereMoeglicheZuege();
for each (Zug in Zugliste)
{
FuehreZugAus(Zug);
if (PVgefunden)
{
wert = -AlphaBeta(tiefe-1, -alpha-1, -alpha);
if (wert > alpha && wert < beta)
wert = -AlphaBeta(tiefe-1, -beta, -wert);
} else
wert = -AlphaBeta(tiefe-1, -beta, -alpha);
MacheZugRueckgaengig(Zug);
if (wert > best)
{
if (wert >= beta)
return wert;
best = wert;
if (wert > alpha)
{
alpha = wert;
PVgefunden = TRUE;
}
}
}
return best;
}
Pesquisa de aprofundamento iterativo (aprofundamento iterativo)
A pesquisa iterativa em primeiro lugar é o aumento passo a passo da profundidade da árvore de pesquisa. Como a pesquisa alfa-beta é uma pesquisa em profundidade , geralmente não é possível determinar com antecedência quanto tempo o cálculo levará. Portanto, você começa com uma profundidade de busca rasa e aumenta gradualmente. O resultado de um cálculo pode ser usado para melhor pré-classificar os trens se a profundidade da pesquisa for aumentada.
Janelas de aspiração
As janelas de aspiração são usadas em conjunto com a primeira pesquisa de profundidade iterativa . Basicamente, a pesquisa alfa-beta começa na raiz com uma janela máxima. Com a primeira pesquisa de profundidade iterativa, pode-se presumir que um novo cálculo com uma profundidade maior fornecerá um valor de resultado semelhante. Portanto, a janela de pesquisa pode ser inicialmente definida para uma área (relativamente) pequena em torno do valor de resultado do cálculo anterior. Se esta janela for muito pequena, a pesquisa deve ser repetida com uma janela maior ou máxima (semelhante à pesquisa de variação principal ).
Heurística assassina
A heurística assassina é um tipo especial de pré-classificação do trem. Assume-se aqui que movimentos que causaram um corte também causarão um corte em outras partes da árvore de pesquisa (na mesma profundidade). Portanto, no futuro, eles sempre serão considerados em primeiro lugar, desde que representem movimentos válidos na posição de jogo que acabamos de considerar. Essa heurística não pode ser usada de maneira sensata em todos os jogos, uma vez que a perspectiva de que esses movimentos chamados matadores ainda sejam movimentos válidos em outras partes da árvore de pesquisa depende do tipo de jogo.
Busca silenciosa
Com a pesquisa alfa-beta ou o algoritmo Minimax, não é muito benéfico se a pesquisa for encerrada quando uma profundidade de pesquisa fixa for atingida. Desta forma, no xadrez, por exemplo, capturar um peão coberto pela rainha pode parecer vantajoso se o recuo estiver abaixo do horizonte de busca e, portanto, “esquecido” pelo algoritmo. Por este motivo, a transição da busca alfa-beta para a função de avaliação ocorre de forma dinâmica, especificamente de tal forma que se espera uma constância aproximada abaixo da profundidade mínima de busca em relação à função de avaliação. Esta "paz" é em termos dos valores do mesmo nome função de avaliação para o procedimento é chamado de busca de descanso ( Inglês pesquisa Quiescence ). No xadrez, a busca pela paz leva ao fato de uma troca de golpes ser analisada até o fim.
Pesquisa de movimento zero
A busca de movimento zero é uma otimização que aproveita o fato de que em alguns jogos (por exemplo, xadrez) o movimento certo é uma vantagem.
Comparação de Minimax e AlphaBeta
A tabela a seguir mostra um exemplo de cálculo de uma posição de xadrez com uma profundidade de busca constante de quatro meios movimentos (cada jogador se move duas vezes). O algoritmo Minimax normal foi usado e alfa-beta sem classificação de trem e com (simples) classificação de trem. As informações de porcentagem nos pontos de corte referem-se a toda a árvore de pesquisa e descreve o quanto de toda a árvore de pesquisa não foi avaliada. Essas são estimativas baseadas no fato de que as subárvores são aproximadamente do mesmo tamanho (com cortes, não se sabe o quão grande a subárvore realmente teria).
| algoritmo | avaliações | Cutoffs | Proporção de cortes | Tempo de computação em segundos |
|---|---|---|---|---|
| Minimax | 28.018.531 | 0 | 0,00% | 134,87 s |
| Alpha Beta | 2.005.246 | 136.478 | 91,50% | 9,88 s |
| Triagem de trens AlphaBeta + | 128.307 | 27.025 | 99,28% | 0,99 s |
Pode ser visto claramente que a busca alfa-beta significa um aumento considerável na velocidade em comparação com o Minimax. A classificação de trens também melhora o tempo de computação neste exemplo por um fator de 10. O fato de que o número de cortes diminui absolutamente com a classificação de trens pode ser explicado pelo fato de que ocorrem em níveis mais altos na árvore de pesquisa e, portanto, partes maiores são cortadas.
história
Embora a importância central do algoritmo Minimax para a programação de xadrez já fosse enfatizada por seus pioneiros Alan Turing e Claude Shannon na década de 1940, a pesquisa alfa-beta começou no final dos anos 1950, com apenas cortes alfa no início foram usados. Foi só na década de 1960 que o algoritmo alfa-beta se tornou parte integrante dos programas de xadrez. Uma primeira descrição, embora não publicada, é de 1963. O primeiro estudo detalhado apareceu em 1975.
literatura
- Jörg Bewersdorff : sorte, lógica e blefe. Matemática no jogo - métodos, resultados e limites. 5ª edição. Vieweg + Teubner, Wiesbaden 2010, ISBN 978-3-8348-0775-5 , doi: 10.1007 / 978-3-8348-9696-4 , pp. 177-197 (Capítulo 2.10).
- Alexander Reinefeld: Desenvolvimento do método de busca da árvore do jogo: do cérebro de xadrez de Zuse ao computador de xadrez moderno. In: Wolfgang Reisig & Johann-Christoph Freytag (Hrsg.): Informatik. Questões atuais em um contexto histórico. Springer, Berlin / Heidelberg / New York 2006, ISBN 978-3-540-32742-4 , doi: 10.1007 / 3-540-32743-6_11 , pp. 241-276.
- Wolfgang Ertel: Curso Básico de Inteligência Artificial : Uma Introdução Orientada à Prática, Inteligência Computacional . 4ª edição. Springer Vieweg, Wiesbaden 2016, ISBN 978-3658135485 , doi: 10.1007 / 978-3-658-13549-2 , pp. 125-127.
Links da web
- Burkhard Monien, Ulf Lorenz & Daniel Warner: o algoritmo do alfabeto para pesquisas em árvores de jogos . 2006.
- Visualização da pesquisa alfa-beta como um miniaplicativo Java para qualquer árvore de jogo
Notas de rodapé
- ↑ Jörg Bewersdorff: Luck, Logic and Bluff. Matemática no jogo - métodos, resultados e limites. 5ª edição. 2010, p. 184.
- ^ Allen Newell , JC Shaw & HA Simon : Programas de xadrez e o problema da complexidade. In: IBM Journal of Research and Development. Volume 2, Edição 4, 1958, doi: 10.1147 / rd.24.0320 , pp. 330-335 ( PDF; 2.172 MB ).
- ↑ DJ Edwards e TP Hart: A heurística alfa-beta (= AI Memos. 030). Massachusetts Institute of Technology, 1963 ( PDF; 288 kB ).
- ^ Donald E. Knuth & Ronald W. Moore: Uma análise da poda alfa-beta. In: Artificial Intelligence. Volume 6, Edição 4, 1975, doi: 10.1016 / 0004-3702 (75) 90019-3 , pp. 293-326
