Pesquisa com adversários

O tópico destas aulas é a pesquisa com adversários. Pretende-se que use o algoritmo minimax, bem como a sua versão melhorada com os cortes alfa-beta, para encontrar a melhor jogada em vários jogos.

1 - Algoritmo Minimax e Minimax com cortes alfa-beta

Para cada uma das seguintes árvores de jogo

• determine a estratégia óptima para o jogador MAX usando
  • o algoritmo minimax e
  • o algoritmo minimax com cortes alfa-beta
• encontre uma ordenação da árvore de jogo que resulte na melhor performance possível do algoritmo minimax com cortes alfa-beta.

2 - Jogo Maluco

Considere o seguinte jogo: há dois jogadores, MAX e MIN; em cada momento, o estado de um jogo é um inteiro N; na sua vez de jogar, MAX pode escolher uma das seguintes duas jogadas:

• Jogada A: N:=N+(N mod 23)-11.
• Jogada B: N:=N+(N mod 7)-4.

Na sua vez de jogar, MIN pode escolher uma das seguintes duas jogadas:

• Jogada C: N:=N+2*(N mod 17)-16.
• Jogada D: N:=N+((N mod 11)-5)*(N mod 17).

No início, N=100 e MAX joga primeiro. O jogo decorre durante quatro jogadas (duas para cada jogador), após as quais termina.

Suponha que a árvore de jogo é gerada em profundidade primeiro, da esquerda para a direita (i.e. A, B, C e D são aplicadas por esta ordem) e que se usa o algoritmo minimax com cortes alfa-beta:

1. Mostre a parte da árvore do jogo que é gerada
2. Determine o valor do nó inicial
3. Indique a jogada inicial de MAX

3 - Outro Jogo

Considere a seguinte árvore de jogo, cujos estados terminais têm utilidades inteiras, e n e m são variáveis.

1. Atribua valores a n e m tal que para calcular o valor da raiz da árvore não seja possível fazer cortes alfa-beta. Calcule o valor da raiz.
2. Atribua valores a n e m tal que para calcular o valor da raíz da árvore seja possível fazer cortes alfa-beta. Indique o corte alfa-beta e calcule o valor da raiz.

4 - Chomp

Considere o jogo chomp. Dois jogadores (MAX e MIN) têm uma tablete de chocolate com m*n (largura*altura) quadrados. Sabe-se que o quadrado do canto superior esquerdo é venenoso. Os jogadores jogam à vez, de acordo com as seguintes regras: o jogador escolhe um dos quadrados de chocolate restantes, que come juntamente com todos os quadrados que lhe estão abaixo e à direita. Por outras palavras, o jogador retira o rectângulo de chocolate cujo canto superior esquerdo é o quadrado escolhido. Naturalmente, o jogador que comer o quadrado venenoso perde o jogo. A seguinte figura ilustra a árvore do jogo chomp 2*2.

Encontre uma estratégia vencedora para MAX no chomp 3*2 usando cada um dos seguintes algoritmos.

1. o algoritmo minimax
2. o algoritmo minimax com cortes alfa-beta
3. o algoritmo minimax com cortes alfa-beta, sabendo que os valores dos nós estão compreendidos entre -1 e 1.

Para cada um dos algoritmo usados, apresente a parte da árvore de jogo gerada para o caso em que a primeira jogada de MAX corresponde à escolha do quadrado inferior direito, e que nenhuma outra parte da árvore foi previamente gerada.