Algoritmo minmax

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 pode formular 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 joga primeiro

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 Min