Algoritmo Minimax

Algoritmo Minimax e Alfa-Beta

Jean Carlos
RA: 31057

O algoritmo Minimax
O algoritmo minimax se baseia na construção de uma árvore de decisões (árvore contendo todos os possíveis estados do jogo e de qual estado se pode chegar a qual), pontua cada um dos nós segundo as chances de vitória ou derrota dos jogadores e retorna como melhor solução sempre aquela que busca minimizar as chances de perda e maximizar as chances de vitória.
Desta forma, nós pontuados positivamente (melhores chances para a vitória) serão buscados como solução, enquanto que nós pontuados negativamente (nós onde há a possibilidade de derrota) serão evitados.
Tomemos como exemplo um jogo da velha onde queremos maximizar as chances do computador vencer (tentando, assim, trazer algum desafio ao jogador humano).
Facilmente o computador consegue criar e manter em memória uma árvore contendo todas as possíveis jogadas para o jogo da velha (o mesmo não pode ser dito para o caso de jogos de xadrez, devido às dimensões da árvore de decisões deste). Construamos então uma árvore de decisões na qual é o jogador humano quem começa o jogo.
A construção da árvore é feita de forma bem simples: há raiz conterá o estado inicial do jogo, com o tabuleiro completamente em branco. Os filhos deste nó devem ser as possíveis jogadas adotadas pelo jogador humano (inicialmente nove, então teremos aqui nove nós-filhos).
Para cada nó, crie seus nós filhos segundo as possibilidades de jogo, lembrando de armazenar em cada nó qual seria o estado atual do jogo se aquele fosse o estado corrente.
Após a construção de toda a árvore, começamos pontuando cada nó da seguinte forma:


Se este nó não é um nó-folha:
Se, para este nó, o próximo a jogar é o humano e um dos nós-filhos representa um estado em que ele vence, então este é um nó ruim, pois aumentará as chances do computador perder – pontuaremos ele com valor -1;
Caso contrário, pontuamos este nó com o somatório dos valores de seus filhos;