Negamax

Na programação de jogos de xadrez, o algoritmo de busca negamax é uma variante na implementação do algoritmo de busca minimax e seus derivados^[1]. Ambos os algoritmos baseiam-se na propriedade de soma zero de um jogo entre dois jogadores.

O algoritmo negamax baseia-se na equação $\max(a,b)=-\min(-a,-b)$ para simplificar a implementação da lógica do algoritmo minimax, que por sua vez leva em consideração a avaliação das posições dos jogadores separadamente.

Mais precisamente, o valor de uma posição para o jogador A é a negação do valor para o jogador B soma zero^[1]. Dessa forma, o jogador em movimento procura uma jogada que maximize a negação do valor resultante da jogada: esta posição sucessora deve, por definição, ter sido avaliada pelo oponente. Funcionando independentemente de A ou B estarem a jogar. Isso significa que um único procedimento pode ser usado para avaliar ambas as posições, seja a vez dos jogadores A ou B. Esta é uma simplificação de codificação sobre minimax, que requer que A selecione o movimento com o sucessor de valor máximo enquanto B seleciona o movimento com o sucessor de valor mínimo.

O objetivo do algoritmo de pesquisa negamax é encontrar o valor da pontuação do nó para o jogador que está jogando no nó raiz (geralmente atribuímos +1 para as peças brancas e -1 para as peças negras). O pseudocódigo abaixo mostra o algoritmo base negamax, ^[2] com um limite de profundidade de busca máxima configurável:

função negamax(nó, profundidade, cor)
  se profundidade = 0 ou nó é um nó terminal então
    retorna valor heurístico do nó × cor
  valor = −∞
  para cada filho do nó faça
    valor = máximo(valor, −negamax(filho, profundidade − 1, −cor))
  retorna valor

(* Chamada inicial da função negamax para o nó raiz do Jogador A *)
negamax(nó raíz, profundidade, 1)

(* Chamada inicial da função negamax para o nó raiz do Jogador B *)
negamax(nó raíz, profundidade, −1)

Referências

↑ ^a ^b «Negamax - Chessprogramming wiki». www.chessprogramming.org. Consultado em 12 de abril de 2022
↑ Breuker, Dennis M. Memory versus Search in Games, Maastricht University, October 16, 1998

[:0-1] «Negamax - Chessprogramming wiki». www.chessprogramming.org. Consultado em 12 de abril de 2022

[Breuker-2] Breuker, Dennis M. Memory versus Search in Games, Maastricht University, October 16, 1998

[1]

[2]