BuscaCompetitiva

Busca competitiva
(jogos “adversariais”)
Aula 4 - Cap. 6 Russell & Norvig
Fundamentos da IA
Mestrado - FEI - 2005

Jogos
São domínios clássicos em IA
– abstratos: fáceis de formalizar e representar; – podem ter sua complexidade reduzida ou aumentada; – exigem a tomada de decisões (muitas vezes em um curto intervalo de tempo);
– Há interação e pode haver não determinismo. Jogos vs. busca
O oponente é “imprevisível”
– levar em consideração todos os movimentos possíveis de oponente;

Limite de tempo
– tomar uma decisão, mesmo que não seja ótima. Decisões ótimas em jogos
Inicialmente jogos com dois jogadores:
– ‘MAX’ e ‘MIN’;

Um jogo pode ser definido como uma árvore de busca:
– estado inicial
– função sucessor (-> movimento, estado)
– teste de término
– função utilidade: dá um valor numérico para os estados terminais

Árvore de jogo (2 jogadores)

Do ponto de vista de max, valores altos de utilidade são bons.

Estratégias ótimas
A solução ótima para MAX depende dos movimentos de MIN, logo:
– MAX deve encontrar uma estratégia de contingência que especifique o movimento de MAX no estado inicial, e depois o movimento de MAX nos estados resultantes de cada movimento de MIN e assim por diante...

Estratégias ótimas
Dada uma árvore de jogo, a estratégia ótima pode ser determinada a partir do valor minimax de cada nó.
O valor minimax (para MAX) é a utilidade de MAX para cada estado, assumindo que MIN escolhe os estados mais vantajosos para ele mesmo (i.e. os estado com menor valor utilidade para MAX)

Valor minimax
UTILIDADE(n)
se n é terminal maxx∈Succ(n)Valor Minimax(s) se n é um nó de MAX minx∈Succ(n)Valor Minimax(s) se n é um nó de MIN

Minimax

A ação a1 é a escolha ótima para MAX, porque leva ao sucessor com mais alto valor minimax.
A melhor jogada para um jogo determinístico assumindo o melhor oponente. Algoritmo minimax

Algoritmo minimax
Ótimo (para um oponente ótimo);
Tempo: busca completa em profundidade na árvore do jogo: O(bm)
– m: profundidade
–