Jogos
Capítulo 6
Jogos vs. Problemas de Procura
•  Adversário “imprevisível"  necessidade de
tomar em consideração todas os movimentos
que podem ser tomados pelo adversário
•  Pontuação com sinais opostos
–  O que é bom para um jogador (vitória=+1) é mau
para o outro (derrota=-1)
•  Limitação temporal  tipicamente não é
encontrado um objectivo mas antes uma
aproximação
Sumário
•  Decisões óptimas em jogos
–  Conceitos básicos
–  Estratégias óptimas e o Minimax
–  Estratégias óptimas com múltiplos jogadores
• 
• 
• 
• 
Cortes α-β
Decisões imperfeitas em tempo real
Jogos que incluem o factor sorte
Estado da arte em jogos
Ingredientes
•  Vamos considerar que:
–  existem dois jogadores, o MAX e o MIN
–  o MAX joga primeiro
–  no fim do jogo o vencedor ganha pontos e o
adversário é penalizado
Caracterização de um Jogo
•  Estado inicial
–  Configuração inicial + ordem de jogada
•  Função sucessores
–  Para cada estado devolve uma lista de pares
<acção,estado>, indicando uma jogada possível
(legal) e o estado resultante
•  Teste terminal
–  Identifica os estados de fim de jogo (ditos terminais)
•  Função de utilidade (ou função objectivo)
–  Atribui um valor numérico aos estados terminais
Árvore do jogo
•  O estado inicial e as jogadas legais para
cada jogador definem a árvore do jogo.
Árvore para o jogo do galo
(2 jogadores, determinístico, alternado)
Sumário
•  Decisões óptimas em jogos
–  Conceitos básicos
–  Estratégias óptimas e o Minimax
–  Estratégias óptimas com múltiplos jogadores
• 
• 
• 
• 
Cortes α-β
Decisões imperfeitas em tempo real
Jogos que incluem o factor sorte
Estado da arte em jogos
Minimax
•  Estratégia mais adequada para jogos
determinísticos
•  Ideia: escolher jogada para o estado com o
maior valor minimax
–  melhor valor para a função de utilidade contra as
melhores jogadas do adversário
Valor-minimax(n) =
{
Função-utilidade(n)
maxs∈sucessores(n) Valor-minimax(s)
mins∈sucessores(n) Valor-minimax(s)
se n é terminal
se n é nó MAX
se n é nó MIN
Minimax: 2 jogadores
•  Observações:
–  Formato dos nós em função do tipo de nó (MIN/MAX)
–  Valores dos estados terminais correspondem à função de
utilidade para MAX (quanto vale cada um dos estados terminais)
–  Valores para os restantes estados obtidos a partir dos valores
para os nós terminais através do cálculo do valor-minimax
–  Resultado do algoritmo: próxima jogada!
Algoritmo Minimax
Função Minimax (estado) devolve acção
v ← ValorMax(estado)
devolve acção em sucessores(estado) com valor v
Função ValorMax(estado) devolve valor de utilidade
se TesteTerminal(estado) então devolve Utilidade(estado)
v ← -∞
para a,e em sucessores(estado)
v ← MAX(v,ValorMin(e))
devolve v
Função ValorMin(estado) devolve valor de utilidade
se TesteTerminal(estado) então devolve Utilidade(estado)
v ← +∞
para a,e em sucessores(estado)
v ← MIN(v,ValorMax(e))
devolve v
Minimax: 2 jogadores
•  Portanto:
–  Começa na raiz e a recursão conduz os cálculos até às folhas. Os
valores minimax são depois usados quando termina a fase de
expansão da recursão;
–  Quando é o Min a jogar, escolhe a jogada que dá menos pontos ao
MAX;
–  Quando é o Max a jogar, escolhe a jogada que lhe dá mais pontos;
–  A seta indica a escolha de MAX no fim da aplicação do algoritmo.
Propriedades do algoritmo minimax
O algoritmo faz uma procura em profundidade, explorando toda a
árvore de jogo.
•  É completo? Sim (se a árvore de procura é finita)
•  É óptimo? Sim (contra um adversário óptimo)
Considerando:
m = profundidade máxima da árvore
r = nº de movimentos legais em cada ponto
•  Complexidade temporal?
–  O(rm)
•  Complexidade espacial?
–  O(rm) para um algoritmo que gera todos os sucessores de uma vez
–  O(m) para um algoritmo que gera os sucessores um a um
•  Para xadrez, r ≈ 35, m ≈100 para um jogo padrão
 impossível determinar a solução exacta
Sumário
•  Decisões óptimas em jogos
–  Conceitos básicos
–  Estratégias óptimas e o Minimax
–  Estratégias óptimas com múltiplos jogadores
• 
• 
• 
• 
Cortes α-β
Decisões imperfeitas em tempo real
Jogos que incluem o factor sorte
Estado da arte em jogos
Minimax: mais de 2 jogadores
•  Função de utilidade devolve vector de valores com
utilidade do estado do ponto de vista de cada jogador
•  Cada jogador procura maximizar a sua utilidade (ex: C
em X, escolhe a jogada que lhe dá mais pontos - 6)
Minimax: mais de 2 jogadores
•  Tipicamente levam a alianças, formais ou informais,
entre os jogadores (também podem existir alianças em
jogos com 2 jogadores).
•  Estas alianças podem ser uma consequência natural de
estratégias óptimas para cada jogador num jogo multijogadores.
Sumário
•  Decisões óptimas em jogos
–  Conceitos básicos
–  Estratégias óptimas e o Minimax
–  Estratégias óptimas com múltiplos jogadores
• 
• 
• 
• 
Cortes α-β
Decisões imperfeitas em tempo real
Jogos que incluem o factor sorte
Estado da arte em jogos
Procura com Cortes
•  Jogos são muito mais difíceis do que os problemas de
procura
•  Factor de ramificação muito elevado - e.g. xadrez
–  factor de ramificação ≈ 35
–  50 jogadas/jogador  35100 nós (destes “apenas” 1040 são nós
distintos)
•  Cortes permitem eliminar partes da árvore de procura
que são irrelevantes para o resultado final. De seguida
vamos falar de um tipo de corte, os cortes α-β .
Cortes α-β
•  Motivação:
–  Minimax: número de estados examinados é
exponencial em função do número de jogadas
–  Não é possível eliminar o factor exponencial, mas
podemos reduzir o número de estados analisados
para metade!
–  É possível calcular exactamente a mesma decisão
resultante do algoritmo Minimax sem ter de analisar
todos os estados
Cortes α-β
•  Considere-se um nó n algures na árvore, tal que
um jogador tem a hipótese de se mover para
esse nó. Se o jogador tem uma hipótese melhor
num nó qualquer acima do nó n, então esse n
nunca vai ser atingido.
•  Assim que soubermos alguma coisa sobre este
n através dos seus descendentes, podemos
cortá-lo (podá-lo).
Cortes α-β: exemplo
Cortes α-β: exemplo
Cortes α-β: exemplo
Cortes α-β: exemplo
Cortes α-β: exemplo
•  Os nós sucessores do primeiro nó a ser expandido em
cada nível de profundidade nunca podem ser cortados
Porquê o nome α-β?
•  α é o valor da melhor
escolha (i.e., valor mais
elevado) encontrada até
ao momento em qualquer
ponto de procura ao
longo do caminho para
max
•  Se v é pior do que α, max
irá evitar escolher v
 ramo com v é cortado
•  β define-se para min de
forma análoga
Algoritmo α-β
Função AlfaBeta (estado) devolve acção
v ← ValorMax(estado, -∞, +∞)
devolve acção em sucessores(estado) com valor v
Função ValorMax(estado,α,β) devolve valor de utilidade
se TesteTerminal(estado)
então devolve Utilidade(estado)
v ← -∞
para a,e em sucessores(estado)
v ← MAX(v,ValorMin(s,α,β))
se v ≥ β então devolve v
α ← MAX(α,v)
devolve v
Algoritmo α-β
Função ValorMin(estado,α,β) devolve valor de utilidade
se TesteTerminal(estado)
então devolve Utilidade(estado)
v ← +∞
para a,e em sucessores(estado)
v ← MIN(v,ValorMax(s,α,β))
se v ≤ α então devolve v
β ← MIN(β,v)
devolve v
Propriedades de α-β
•  Cortes não afectam resultado final (= MINIMAX)
•  Eficiência dos cortes depende da ordenação dos
sucessores
–  Por exemplo, no caso anterior, se em vez do nó com
valor 14 tivesse aparecido o nó com valor 2, não
havia necessidade de gerar os outros nós
•  Com uma “ordenação perfeita" a complexidade
temporal fica reduzida a O(rm/2)
•  Ver applet em
http://wolfey.110mb.com/GameVisual/
launch.php?agent=2
Exercício
•  Qual a melhor ordenação de modo a optimizar
os cortes α-β?
Estados repetidos
•  Em jogos, ocorrem muitas vezes estados
repetidos (devido a permutações)
•  Pode valer a pena guardar estados numa hash
table (chamada transposition table) na primeira
vez que ocorrem
–  Pode duplicar a profundidade alcançada no mesmo
período de tempo!
–  Se são avaliados milhões de nós por segundo não é
viável guardar tantos nós numa tabela
•  Assim, existem muitas estratégias para determinar quais os
estados a guardar
Sumário
•  Decisões óptimas em jogos
–  Conceitos básicos
–  Estratégias óptimas e o Minimax
–  Estratégias óptimas com múltiplos jogadores
• 
• 
• 
• 
Cortes α-β
Decisões imperfeitas em tempo real
Jogos que incluem o factor sorte
Estado da arte em jogos
Decisões imperfeitas
em tempo real
•  Decisões têm que ser tomadas em tempo real
 não é possível analisar toda a árvore de
procura
•  Função de avaliação (Eval) devolve uma
estimativa da utilidade do estado
–  Idealmente a ordenação resultante da função de
avaliação é igual à da função de utilidade
•  Teste terminal é substituído por um teste de
limite (cutoff)
–  Devolve também verdadeiro para estados terminais
Funções de Avaliação
•  O desempenho de um jogo depende da
qualidade da função de avaliação!
•  E como escolher uma boa função de avaliação?
–  Esta deve ser capaz de ordenar os estados terminais
do mesmo modo que a função de utilidade
•  A função de avaliação deve estar fortemente correlacionada
com as hipóteses reais de ganhar
–  O seu cálculo não pode ser demorado
Funções de Avaliação
•  Tipicamente são uma soma linear de
características do jogo (f), associadas a
diferentes pesos (w)
Eval(s) = w1 f1(s) + w2 f2(s) + … + wn fn(s)
•  Ex: Xadrez
–  rainha vale 9, bispo e cavaleiro 3, etc..
–  w1 = 9 e f1(s) = nº de rainhas brancas
–  w2 =3 e f2(s) = nº de bispos
–  ...
Teste Limite
•  Problema da aquiescência
–  Função de avaliação deve aplicar-se apenas a
estados cujo valor não possa ser radicalmente
alterado num futuro próximo (por exemplo, se
estamos só a contar peças no Xadrez, não estamos a
ter em conta jogadas em que se façam capturas de
peças favoráveis)
–  Estados não aquiescentes devem ser expandidos até
que sejam gerados estados sem este problema (por
exemplo, passando a ter em conta movimentos de
captura)
Teste Limite
•  Problema do efeito de horizonte
–  Procura com limite coloca eventuais problemas
futuros para além do horizonte (ex: um movimento
qualquer do adversário que vai ter consequências
desastrosas, mas que não foi previsto dado o limite
de procura imposto).
–  Com as melhorias actuais, conseguem-se limites
cada vez maiores
–  Extensões singulares são outra solução: num caso de
uma jogada ser muito boa, aumenta-se o limite de
pesquisa para os seus sucessores.
Sumário
•  Decisões óptimas em jogos
–  Conceitos básicos
–  Estratégias óptimas e o Minimax
–  Estratégias óptimas com múltiplos jogadores
• 
• 
• 
• 
Cortes α-β
Decisões imperfeitas em tempo real
Jogos que incluem o factor sorte
Estado da arte em jogos
Elemento Sorte
•  Árvore com nós sorte
para além dos nós
MIN e MAX
•  A cada ramo da árvore está associada uma
probabilidade
•  Se for possível estabelecer limites para a função
de avaliação então podem aplicar-se cortes
Expectiminimax(n) =
{
Função-utilidade(n)
se n é terminal
maxs∈sucessores(n) Expectiminimax(s) se n é nó MAX
mins∈sucessores(n) Expectiminimax(s) se n é nó MIN
Σs∈sucessores(n) P(s) · Expectiminimax(s) se n é nó SORTE
Elemento Sorte: exemplo
2.1 = 0.9*2 + 0.1*3
1.3 = 0.9*1 + 0.1*4
Elemento Sorte: exemplo
•  Atenção: alteração de valores das folhas mantendo a mesma ordem
relativa de valores resulta em decisões diferentes.
•  Pelo que há que ter cuidados adicionais na escolha da função de
avaliação.
Sumário
•  Decisões óptimas em jogos
–  Conceitos básicos
–  Estratégias óptimas e o Minimax
–  Estratégias óptimas com múltiplos jogadores
• 
• 
• 
• 
Cortes α-β
Decisões imperfeitas em tempo real
Jogos que incluem o factor sorte
Estado da arte em jogos
Estado da Arte
•  Damas: Chinook derrotou o campeão do mundo
(durante 40 anos) Marion Tinsley in 1994. Uso de uma
base de dados pré-processada que define uma jogada
perfeita para todas as posições envolvendo no máximo
8 peças, num total de 444 biliões de posições.
•  Xadrez: Deep Blue derrotou campeão do mundo Garry
Kasparov em 1997. O Deep Blue procura 200 milhões
de nós por segundo, usa uma função de avaliação muito
sofisticada.
•  Othello: campeões humanos recusam-se a competir
com computadores, que são muito bons.
•  Go: campeões humanos recusam-se a competir com
computadores, que são muito fracos. Neste jogo, r >
300. Logo, a maioria dos programas existentes usa
padrões de conhecimento para sugerir jogadas
hipotéticas.