Algoritmo minmax

Disponível somente no TrabalhosFeitos
  • Páginas : 13 (3046 palavras )
  • Download(s) : 0
  • Publicado : 7 de novembro de 2012
Ler documento completo
Amostra do texto
Introdução a Inteligência Artificial

JOGOS


JOGOS

Jogos

QUE JOGOS?
• 2 jogadores que jogam alternadamente.
• informação perfeita: cada jogador (agente) tem acesso a toda a informação proveniente
do ambiente.

Os jogos podem ser considerados idealizações de
mundos onde existem adversários que tentam diminuir o
bem estar do nosso agente

EXEMPLOS
Damas, Xadrez, Go, Othello,Tic-tac-toe
OBJECTIVO

A presença de um opositor torna mais difícil a tomada de
decisões ao introduzir incerteza nessas decisões, pois
não é possível saber a cem por cento o que ele irá fazer

Estratégia de vitória
PROBLEMA com métodos clássicos
• Explosão combinatória (35100 xadrez !!)
• Incerteza devido à existência de um agente hostil
• Heurísticas: análise dos descendentes de um nónão chega ...

Jogos

Outro tipo de incerteza associada aos jogos deriva do
facto de, normalmente, o espaço de procura ser muito
grande e de não haver tempo para o procurar todo

Isso leva a que não se possa saber com total certeza
quais as consequências das decisões tomadas

Características frequentes dos jogos

Acessibilidade/inacessibilidade do ambiente
Contingência
• O agente podeformular um plano vitorioso, mas não sabe se o
pode por em prática até ao fim porque o adversário pode impedir
que isso aconteça
• Isso pode implicar que em cada jogada o agente tenha que
formular um novo plano

Espaço de pesquisa extenso
Utilidade influenciada pelo factor tempo
Aleatoriedade

1

Definição formal de um jogo
Estado inicial
• Configuração inicial
• Quem jogaprimeiro

Max e Min
No nosso estudo iremos considerar apenas jogos em
que existem dois jogadores, que denominaremos por
MAX e MIN

Conjunto de operadores
• (regras de jogo)

MAX será o jogador a jogar primeiro
Teste de término
• Condições de fim de jogo
– (ex.: “check mate” no xadrez)

Função utilidade
• Valor numérico associado ao fim do jogo
– (ex.: 1, 0, -1 no xadrez)

Max e MinMax e Min
A estratégia MINMAX
1. Gerar a árvore do jogo completa

• Num problema de pesquisa clássica, MAX tem que descobrir
uma sequência de passos que o leve a um estado vencedor (de
acordo com a função utilidade) e realizar o primeiro passo da
sequência

2. Aplicar a função de utilidade aos nós terminais
3. Retropropagar esses valores até à raiz para determinar a jogada “óptima”,usando o princípio de que o adversário joga de forma perfeita
Exemplo 1

• Mas, num jogo, o adversário, MIN, também tem uma palavra a
dizer...
• MAX tem, por isso, que descobrir uma estratégia que o leve a
um estado vencedor independentemente do que MIN fizer

Max e Min

MINMAX

Exemplo 2

2

MinMax
Decisões perfeitas - MinMax
Iremos começar por ver um algoritmo que permitedescobrir
a estratégia ideal (ou óptima) mesmo sabendo que,
normalmente, não se tem tempo para descobrir essa
estratégia

Princípio: gerar toda a árvore de jogo e decidir qual a
melhor jogada de MAX
Efectua uma procura em profundidade primeiro, logo:
Características:

O MinMax é um algoritmo que determina a estratégia óptima
para o jogador Max decidindo qual o próximo melhor
movimento a fazerMinimax
1.

Minimax

Aplicar a função utilidade a todos os nós terminais

3.

b – número de movimentos legais
m – profundidade máxima da árvore

Gerar toda a árvore de jogo até aos nós terminais

2.

• Complexidade espacial: O(b * m)
• Complexidade temporal: O(bm)

Usar esses valores para determinar a utilidade dos nós do nível acima;
Neste passo o procedimento é oseguinte:



4.

Caso se esteja a determinar a utilidade de um nó Max, atribui-se-lhe o
maior dos valores utilidade dos seus filhos
Caso se esteja a determinar a utilidade de um nó Min, atribui-se-lhe o
menor dos valores utilidade dos seus filhos

Propagar os valores (repetindo o passo 3) até chegar à raiz; Neste
ponto selecciona-se a jogada que dá mais pontos

Decisões possíveis
O...
tracking img