Utilizando o algoritmo Minimax, corte Alpha-Beta e outros refinamentos…

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:
1.    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;

2.    Se este é um nó-folha e representa:

• A vitória do computador, pontuamos com valor 1;
• A derrota do computador, pontuamos com valor -1;
• O empate, pontuamos com valor 0.

Uma vez pontuada a árvore, inicia-se o jogo e, a cada jogada dos participantes, deve-se ir percorrendo a árvore, sendo que o computador para efetuar sua jogada irá checar qual dos nós-filhos do nó atual possui maior pontuação: esta deverá ser a sua jogada.

O corte alpha-beta

Como se pode perceber, o algoritmo minimax consegue encontrar a melhor solução. Entretanto ele precisa percorrer toda a árvore. Ela pode ser facilmente mantida para um jogo-da-velha, onde temos “somente” 400 mil nós, mas para um jogo de xadrez, onde podemos ter 10 elevado a 70 nós, construir, avaliar e percorrer toda a árvore torna-se algo inviável.

Sendo assim, é perceptível que precisamos ter algum meio para “podar”, cortar os galhos que jamais serão solução para nós. Tomemos como exemplo um jogo-da-velha onde o computador será o jogador MAX e o jogador humano, o jogador MIN.
Em um dado nó onde o jogador MAX deverá tomar uma decisão, teremos vários nós filhos, cada qual com seus próprios valores. O jogador MAX sempre quer maximizar, então é óbvio que ele escolherá sempre o nó que possuir maior valor, descartando sempre os demais, então, para que manter os outros nós?
Podemos então podar esse “galho” de nossa árvore! O algoritmo de corte alpha-beta, aplicado juntamente com o minimax, possui justamente essa função. A poda pode ser feita após a completa criação da árvore, bem como pode ser feita durante a construção da mesma, após a pontuação completa dos filhos ou por meio de alguma função heurística a fim de avaliar o valor de cada filho.

Um jogo com MiniMax e poda Alpha-Beta : TileTroop

Objetivo do jogo : invadir o castelo do oponente.

Regras de Movimentação:

1) Cada terreno hexagonal do jogo só pode conter, no máximo, 8 tropas de um jogador;

2) Cada terreno hexagonal contém dois números que informam, respectivamente, o número de tropas que podem se mover na jogada em questão e o número de tropas total (MoveTroops/TotalTroops) ;

3) As movimentações são possíveis apenas para os vizinhos do terreno hexagonal escolhido;

4) A cada rodada, o número de tropas em cada terreno é incrementado em 1 para o jogador da vez;

5) Para conquistar um terreno verde, o jogador deve movimentar, pelo menos, 1 tropa para ele;

6) Para conquistar um terreno inimigo, o jogador deve movimentar um número de tropas maior que o total de tropas do inimigo. Por exemplo, caso o jogador 1 tenha um terreno (6/6) e um terreno vizinho do inimigo com (3/3), o jogador 1 poderá conquistar o terreno inimigo, caso movimente, pelo menos, 3 tropas suas para o terreno do adversário;

7) O jogador vencedor será o que primeiro conquistar o castelo do adversário.

Refinamentos

1) Realizamos uma numeração padrão para cada terreno e seus vizinhos.

Dessa maneira, poderemos utilizar a seguinte estratégia para gerar as possíveis movimentações do jogador (também chamadas de sequências de configuração):

1.1) Cada terreno é representado por uma variável e o valor das tropas que podem ser movidas é o resultado da equação. Por exemplo, para a figura acima e 8 como o valor do número de tropas que podem ser movidas, teríamos:

X1 + X2 + X3 + X4 + X5 + X6 + X7 = 8

1.2) Essa equação foi representada da seguinte maneira: 00000011111111 (ou 0000008). Os números de 1’s entre os 0’s representa quantas tropas devem ser enviadas para o terreno vizinho. Por exemplo, para a seguinte permutação do número acima mencionado, 01011011001101 (ou 0122021), teríamos a movimentação de 0 tropas para o terreno 1, 1 tropa para o terreno 2, 2 tropas para o terreno 3, 2 tropas para o terreno 4, 0 tropas para o terreno 5, 2 tropa para o terreno 6 e 1 tropa para o terreno 7. Todas as permutações de 0’s e 1’s são possíveis movimentações para cada terreno hexagonal, se desconsiderarmos o número de tropas que já existem nos vizinhos do terreno em questão. O número de permutações pode ser facilmente encontrado aplicando a fórmula do número de permutações com repetição.

1.3) De todas as permutações geradas, excluímos aquelas que não são possíveis quando analisamos o total de tropas dos vizinhos (a soma das tropas não pode ser maior que oito).

1.4) Para sabermos qual são as melhores movimentações para um terreno específico, aplicamos a seguinte heurística, chamada de Heurística Básica.

Basic Heuristic = ( n1 * type1 + n2 * type2 + n3 * type3 + … + nk * typek ) / ( número de 0’s a partir do segundo caractere + 1 ).

Dessa forma, atribuímos heurísticas melhores às configurações nas quais existam maiores movimentações para os vizinhos (conquista de novos territórios), principalmente se estes territórios pertencerem ao oponente ( áreas do oponente ou o castelo do oponente) ou forem áreas sem dono (chamadas de green tiles). Os pesos para cada tipo encontram-se abaixo:

public static final int W_TILE_OPPONENT_CASTLE = 25;
public static final int W_TILE_OPPONENT = 10;
public static final int W_TILE_GREEN = 6;
public static final int W_TILE_ME = 2;
public static final int W_TILE_MY_CASTLE = 2;

2) Neste jogo, é permitido realizar mais de uma ação por jogador. Portanto, cada “nó” utilizado pelo algoritmo Minimax será um conjunto dessas sequências de configurações.

3) Os nós são construídos através da escolha de sequências de configurações para cada terreno pertencente ao jogador da vez. Ou seja, essas sequências de configurações são “encapsuladas” em um nó e são consideradas uma “jogada” completa.

4) O número de nós formados pela combinação de todas as possíveis sequências de configuração seria muito grande. Portanto selecionamos os 10 melhores nós e enviamos ao algoritmo MiniMax.

5) A heurística para o nó é a soma das heurísticas básicas das suas sequências de configuração.

Download do código: http://www.4shared.com/file/WwiB9RZW/hexBattle.html