• O algoritmo Mini-max é um algoritmo recursivo ou de retrocesso usado na tomada de decisões e na teoria dos jogos. Ele fornece um movimento ideal para o jogador, assumindo que o oponente também está jogando de maneira ideal.
• O algoritmo Mini-Max usa recursão para pesquisar na árvore do jogo.
• O algoritmo Min-Max é usado principalmente para jogos em IA. Como xadrez, damas, jogo da velha, go e vários jogos de reboque. Este algoritmo calcula a decisão minimax para o estado atual.
• Neste algoritmo dois jogadores jogam, um é chamado MAX e o outro é chamado MIN.
• Ambos os jogadores lutam contra isso, pois o jogador oponente obtém o benefício mínimo enquanto eles obtêm o benefício máximo.
• Ambos os jogadores do jogo são oponentes um do outro, onde MAX selecionará o valor maximizado e MIN selecionará o valor minimizado.
• O algoritmo minimax executa um algoritmo de busca em profundidade para a exploração da árvore de jogo completa.
• O algoritmo minimax desce até o nó terminal da árvore e, em seguida, retrocede a árvore como recursão.

Pseudocódigo para algoritmo MinMax:

 function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva 

Chamada inicial:

Minimax(nó, 3, verdadeiro)

Funcionamento do algoritmo Min-Max:

• O funcionamento do algoritmo minimax pode ser facilmente descrito usando um exemplo. Abaixo, pegamos um exemplo de árvore de jogo que representa o jogo para dois jogadores.
• Neste exemplo, há dois jogadores, um é chamado Maximizer e o outro é chamado Minimizer.
• O Maximizer tentará obter a pontuação máxima possível e o Minimizer tentará obter a pontuação mínima possível.
• Este algoritmo aplica DFS, portanto, nesta árvore do jogo, temos que percorrer todo o caminho pelas folhas para chegar aos nós terminais.
• No nó terminal, os valores terminais são fornecidos, então iremos comparar esses valores e retroceder na árvore até que o estado inicial ocorra. A seguir estão as principais etapas envolvidas na resolução da árvore do jogo para dois jogadores:

Passo 1: Na primeira etapa, o algoritmo gera toda a árvore do jogo e aplica a função de utilidade para obter os valores de utilidade para os estados terminais. No diagrama de árvore abaixo, consideremos que A é o estado inicial da árvore. Suponha que o maximizador faça o primeiro turno, que tem o valor inicial do pior caso = - infinito, e o minimizador fará o próximo turno, que tem o valor inicial do pior caso = + infinito.

Passo 2: Agora, primeiro encontramos o valor das utilidades para o Maximizer, seu valor inicial é -∞, então compararemos cada valor no estado terminal com o valor inicial do Maximizer e determinaremos os valores mais altos dos nós. Encontrará o máximo entre todos.

• Para nó D max(-1,- -∞) => max(-1,4)= 4
• Para o nó E max(2, -∞) => max(2, 6)= 6
• Para o nó F max(-3, -∞) => max(-3,-5) = -3
• Para nó G max(0, -∞) = max(0, 7) = 7

Etapa 3: Na próxima etapa, é a vez do minimizador, então ele comparará o valor de todos os nós com +∞ e encontrará o 3^terceirovalores do nó da camada.

• Para nó B= min(4,6) = 4
• Para nó C= min (-3, 7) = -3

Passo 4: Agora é a vez do Maximizer, que escolherá novamente o valor máximo de todos os nós e encontrará o valor máximo para o nó raiz. Nesta árvore de jogo, existem apenas 4 camadas, portanto chegamos imediatamente ao nó raiz, mas em jogos reais, haverá mais de 4 camadas.

• Para o nó A max(4, -3)= 4

Esse foi o fluxo de trabalho completo do jogo minimax para dois jogadores.

Propriedades do algoritmo Mini-Max:

Completo-O algoritmo Min-Max está completo. Definitivamente encontrará uma solução (se existir), na árvore de pesquisa finita.Ótimo-O algoritmo Min-Max é ideal se ambos os oponentes estiverem jogando de maneira otimizada.Complexidade de tempo-À medida que executa DFS para a árvore do jogo, a complexidade de tempo do algoritmo Min-Max é O(b^eu) , onde b é o fator de ramificação da árvore do jogo e m é a profundidade máxima da árvore.Complexidade Espacial-A complexidade espacial do algoritmo Mini-max também é semelhante ao DFS, que é Sobre .

Limitação do algoritmo minimax:

A principal desvantagem do algoritmo minimax é que ele fica muito lento para jogos complexos como xadrez, go, etc. Esse tipo de jogo tem um enorme fator de ramificação e o jogador tem muitas opções para decidir. Esta limitação do algoritmo minimax pode ser melhorada a partir de poda alfa-beta que discutimos no próximo tópico.