MiniMax

MiniMax em um Jogo Dois jogadores : MAX and MIN MAX começa e os jogadores alternam até que o jogo termine. O vencedor leva uma recompensa, o perdedor uma penalidade Jogos como busca:

– Estado Inicial– Função Sucessora: lista de movimentos legais.– Teste Terminal: O jogo terminou?– Função de Utilidade: Dá um valor aos estados terminais. Por

exemplo, no jogo da velha: vitória=+1 derrota=-1 empate=0.

MAX usa uma árvore de busca para determinar seu próximo movimento.

Árvore Parcial para Jogo da Velha

Estratégia Ótima

Encontra a estratégia para MAX assumindo que MIN é infalível.

Premissa: Os dois jogadores jogam de forma ótima. Dada uma árvore de jogo, a estratégia ótima pode ser

determinado usando o valor minimax de cada nó:

VALOR-MINIMAX(n)=UTILIDADE(n) Se n é terminal

maxs ∈ sucessores(n) VALOR-MINIMAX(s) Se n ∈ MAX

mins ∈ sucessores(n) VALOR-MINIMAX(s) Se n ∈ MIN

Exemplo de árvore de jogo para dois jogadores

Exemplo de árvore de jogo para dois jogadores

A decisão minimax

Minimax maximiza o resultado de pior caso para max

Exemplo de árvore de jogo para dois jogadores

E se o MIN não for um bom jogador?

A definição de melhor jogada para MAX assume que MIN joga de forma ótima.

Logo, estamos maximizando o resultado em um cenário de pior caso para MAX.

Se MIN não jogar otimamente, MAX pode se dar ainda melhor.

Exemplo

8 4

8

Como fazer...

Implementado como uma busca em profundidade

Tem que avaliar todos os filhos antes de poder avaliar um nó.

Logo, para avaliar a raiz, tem que avaliar a árvore inteira!

Isto pode ser extremamente custoso, se o fator de ramificação for muito alto.

Melhorias

• Métodos pada não examinar todos os nós:– Antecipação Limitada– Poda Alfa-Beta

Poda Alfa Beta

A árvore de jogo é percorrida em ordem de profundidade A cada nó que não seja folha, é armazenado um valor, sendo:

– Alpha: para os MAX

• É o máximo (melhor) valor encontrado até então nos descendentes dos nós MAX

– Beta: para os MIN

• É o mínimo (melhor) valor encontrado até então nos descendentes dos nós min

Se:É no MAX: Se valor_alfa_de(nó) >= valor_beta_ancestral; ouÉ no MIN: Se valor_beta_de(nó) <= valor_alfa_de_ancestral; ENTÃOcorta_busca_abaixo(nó)

Poda Alfa-Beta

Para implementar isto, nós manipulamos os valores alfa-beta, armazenando-os em cada nó interno da árvore de busca....

Exemplo do Alfa-Beta

[-∞, +∞]

[-∞,+∞]

Faixa de Valores Possíveis

Faça a busca pelo primeiro mais fundo até a primeira folha

[-∞,3]

[-∞,+∞]

Exemplo do Alfa-Beta(continuação)

[-∞,3]

[-∞,+∞]

Exemplo do Alfa-Beta(continuação)

[3,+∞]

[3,3]

Exemplo do Alfa-Beta(continuação)

[-∞,2]

[3,+∞]

[3,3]

Este nó é pior para o jogador MAX

Exemplo do Alfa-Beta(continuação)

[-∞,2]

[3,14]

[3,3] [-∞,14]

,

Exemplo do Alfa-Beta(continuação)

[−∞,2]

[3,5]

[3,3] [-∞,5]

,

Exemplo do Alfa-Beta(continuação)

[2,2][−∞,2]

[3,3]

[3,3]

Exemplo do Alfa-Beta(continuação)

[2,2][-∞,2]

[3,3]

[3,3]

Exemplo do Alfa-Beta(continuação)

Outro Exemplo de Poda Alfa-Beta

Conceito da poda alfa-beta

Seja um nó n na árvore Se um jogador tem uma

jogada melhor em– Um nó pai de n– Ou em um nó mais alto

do que n n nunca será atingido em

um jogo real. Logo, quando sabemos o

suficiente sobre n, ele pode ser ignorado.

Comentários Finais sobre a poda alfa-beta

A poda não afeta os resultados finais. Sub-árvores inteiras podem ser podadas. A ordenação dos movimentos afeta e efetividade

da poda. Na melhor situação, a complexidade de tempo do

minimax com poda alfa-beta cai para O(bm/2)

– Fator de ramificação igual a !!– Poda alfa-beta permite que se olhe o dobro da

distância do minimax normal no mesmo tempo. Estados repetidos continuam sendo possíveis.

b