FACENS – Engenharia da Computação
Inteligência Artificial
Buscas Competitivas
Busca Competitiva - Jogos
• Jogos de soma zero: ambientes
determinísticos completamente
observáveis, em que as utilidades finais
dos agentes somam zero.
• Em jogos de tabuleiros de dois jogadores,
a vitória pode ser computada com
utilidade +1, derrota -1 e empate 0.
• Portanto, a soma final da utilidade dos
dois jogadores é zero.
Busca Competitiva - Jogos
• Considerendo-se dois jogadores para o
caso do jogo da velha, um chamado de
MAX e o outro de MIN.
• Para MAX, que joga com X, uma utilidade
boa é +1 (X ganhou).
• Para MIN, que joga com O, uma utilidade
boa é -1 (O ganhou).
Busca Competitiva - Árvore
Busca Competitiva - Solução
• MAX deve encontrar uma sequencia de
movimentos que leve a um estado
terminal com utilidade +1.
• O problema é que isto depende dos
movimentos de MIN.
• O solução ótima: considerar que MIN é um
oponente infalível, e sempre fará os
melhores movimentos possíveis.
• Logicamente, inviável para jogos mais
complexos como xadrez e damas.
Busca Competitiva - MINIMAX
• Dado um nó não-folha, seu valor
MINIMAX é a utilidade deste estado para
um jogador, considerando que ambos
tenham um desempenho ótimo até o final
do jogo.
• Dentre as possibilidades, MAX sempre
escolherá a que resulta na maior utilidade,
e MIN na menor.
Busca Competitiva - MINIMAX
Busca Competitiva – Algoritmo MINIMAX
• Criar uma função MINIMAX que recebe um
estado do tabuleiro e de quem é a vez (X
ou O).
• 1: Verificar se alguém ou houve empate.
— X ganhou: retornar +1
— O ganhou: retornar -1
— empate: retornar 0
• 2: Se não terminou, buscar todas as
possíveis jogadas para o jogador da vez.
— 2.1: Para cada jogada, chamar MINIMAX com
o novo tabuleiro e com o outro jogador.
— 2.2: Entre os valores resultados por MINIMAX,
escolher o maior (se o jogador for MAX) ou o
menor (se o jogador for MIN).
Leitura recomendada
• Capítulo 6 (p. 156-187), Russel & Norvig.
• Algoritmos e implementações:
— http://aima.cs.berkeley.edu/