CSI_457_IA_BuscaCompetitiva

Prévia do material em texto

DECSI - UFOP, CSI 457
Notas de Aula
Busca Competitiva
Inteligência Arti�cial
Prof. Dr. Talles Henrique de Medeiros
Talles Medeiros
2021/1
Conteúdo
Conteúdo
1 Busca Competitiva 3
1.1 Estratégia Ótimas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 O Algoritmo Minimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Propriedades do Algoritmo Minimax . . . . . . . . . . . . . . . . . . . 6
1.3 A Poda Alfa-Beta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Decisões Imperfeitas em Tempo Real . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Notas Bibliográ�cas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2
1 Busca Competitiva
1 Busca Competitiva
O cenário em que o agente precisa considerar as ações de outros agentes e a forma como essas
ações afetam o seu próprio bem-estar introduz muitas contingências no processo de resolução
de problemas do agente. Em ambientes competitivos, em que os objetivos dos agentes estão em
con�ito, temos a origem dos problemas de busca competitiva — frequentemente conhecidos
como jogos.
A teoria de jogos, um ramo da economia, visualiza qualquer ambiente multiagente como um
jogo. Em IA, os “jogos” mais comuns são de um tipo bastante especializado — que os teóricos de
jogos denominam jogos determinísticos de revezamento de dois jogadores de soma zero com
informações perfeitas (como o xadrez).
Os jogos costumam ser desa�adores, por exemplo, o xadrez possui um fator de rami�cação de
cerca de 35, e as partidas chegam até 50 movimentos por jogador. Assim, a árvore de busca tem
aproximadamente 35100 ou 10154 nós (embora o grafo de busca tenha “apenas” cerca de 1040 nós
distintos).
Falaremos da de�nição de movimento ótimo e um algoritmo para descobri-lo. Depois aborda-
remos situações em que o tempo é limitado. A poda nos permite ignorar partes da árvore de
busca que não fazem diferença para a escolha �nal, e as funções de avaliação de heurísticas nos
oferecem a oportunidade de fazer uma aproximação da verdadeira utilidade de um estado sem
realizar uma busca completa.
Consideraremos jogo com dois jogadores, que denominaremos MIN e MAX. O jogador MAX faz
o movimento primeiro, e depois eles se revezam até o jogo terminar. No �nal do jogo, os pontos
�cam com o vencedor e as penalidades são aplicadas ao perdedor. O jogo pode ser de�nido
como:
• B0: o estado inicial que especi�ca o início do jogo.
• JOGADORES(s): de�ne qual o jogador deve se movimentar em um estado.
• AÇÕES(s): retornam o conjunto de movimentos válidos em um estado.
• RESULTADO(s,a): o modelo de transição que de�ne o resultado de um movimento.
• TESTE DE TÉRMINO(s): verdadeiro quando o jogo termina e, do contrário, falso. Os
estados em que o jogo é encerrado são chamados estados terminais.
• UTILIDADE(s,p): de�ne o valor numérico para um jogo que termina no estado terminal
B por um jogador ? . Por exemplo, em xadrez usamos +1, −1 ou 1/2 para vitória, derrota e
empate, respectivamente. Alguns jogos possuem maior gama de resultados possíveis.
3
1 Busca Competitiva
Figura 1.1: Uma parte da árvore de busca do jogo da velha.
Vamos ver uma árvore parcial de busca para um jogo da velha, �gura 1.1, que exibe no nó raiz o
estado inicial, e mostra o jogador MAX colocando um X em um quadrado vazio. Nessa árvore
parcial, é mostrada a alternância de movimentos entre MIN(O) e MAX(X) até os nós terminas
serem atingidos. Estes nós terminais possuem o valor de utilidade conforme a regra do jogo.
Não é difícil perceber que á árvore do jogo da velha não é grande, contendo menos de 9! = 362.880
nós terminais. Já o xadrez apresenta cerca de 1040 nós terminais.
1.1 Estratégia Ótimas
Em um problema de busca normal, a solução ótima seria uma sequência de ações que levasse
a um objetivo. No entanto, em jogos temos um agente de comportamento imprevisível que
precisamos considerar.
A estratégia de contingência de MAX deve especi�car o movimento de MAX no estado inicial e
nos demais movimentos nos estados resultantes de cada possível resposta de MIN. Em seguida
especi�car os movimentos de MAX nos estados resultantes de cada possível resposta de MIN, e
assim por diante. Grosseiramente falando, uma ótima estratégia leva a resultados pelo menos
tão bons como qualquer outra estratégia quando se está jogando com um adversário infalível.
Faremos uma análise de um jogo simples, de árvore bem reduzida (�gura 1.2), para compreen-
dermos os conceitos de uma estratégia ótima. Os movimentos possíveis para MAX no nó raiz
são identi�cados por �1, �2 e �3. As respostas possíveis para �1 correspondentes a MIN são
�11, �12 e �13, e assim sucessivamente. Este jogo termina após um movimento de MAX e MIN.
4
1 Busca Competitiva
As utilidades são indicadas nos nós terminais e variam de 2 a 14.
Figura 1.2: O melhor movimento de MAX na raiz é �1 porque leva a um estado com o mais alto
valor minimax, e a melhor resposta de MIN é �11 porque leva a um estado com o
mais baixo valor minimax.
A estratégia ótima pode ser determinada pelo valor minimax de cada nó, que de�nimos como
VALOR-MINIMAX(=). Este valor é a utilidade, segundo a visão do jogador MAX, de se encontrar
no estado correspondente. O valor minimax de um estado terminal é a própria utilidade deste
estado. Assim temos uma condição que implementa a determinação do VALOR-MINIMAX(=):
Algorithm 1: Valor Minimax(s)
Result: Calcula o valor minimax de todos nós
if TESTE DE TERMINO(s) then
VALOR-MINIMAX(s) = UTILIDADE(s) ;
else
if JOGADOR(s) = MAX then
VALOR-MINIMAX(s) = "0G0∈��$�( (B) MINIMAX(RESULTADO(s,a)) ;
else
if JOGADOR(s) = MIN then
VALOR-MINIMAX(s) = "8=0∈��$�( (B) MINIMAX(RESULTADO(s,a)) ;
else
end
end
Essa de�nição de jogo ótimo para MAX supõe que MIN também jogue de forma ótima - ela
maximiza o resultado para MAX no pior caso. Caso MIN não jogar de forma ótima, MAX terá
um desempenho ainda melhor. Pode haver outras estratégias contra oponentes não ótimos que
poderão funcionar melhor que a estratégia de minimax; porém, essas estratégias necessariamente
têm um desempenho pior contra oponentes ótimos.
5
1 Busca Competitiva
1.2 O Algoritmo Minimax
Este algoritmo calcula a decisão minimax a partir do estado corrente. Ele faz uso de uma
computação recursiva simples dos valores minimax de cada estado sucessor, implementando
diretamente as equações da de�nição. A recursão percorre todo o caminho descendente até as
folhas da árvore e, depois, os valores minimax são propagados de volta pela árvore, à medida
que a recursão retorna.
Figura 1.3: Este algoritmo retorna a ação correspondente ao melhor movimento possível, isto é,
o movimento que leva ao resultado com a melhor utilidade, sob a suposição de que o
oponente joga para minimizar a utilidade.
O algoritmo retorna a ação correspondente ao melhor movimento possível, isto é, o movimento
que leva ao resultado com a melhor utilidade, sob a suposição de que o oponente joga para
minimizar a utilidade. A notação arg<0G0∈��$�( (B) 5 (0) calcula o elemento 0 do conjunto B
que possui o valor máximo de 5 (0). O algoritmo faz uma exploração em profundidade completa
da árvore de busca.
1.2.1 Propriedades do Algoritmo Minimax
• Completo: Sim, se a árvore for �nita.
• Ótimo: Sim, contra um oponente ótimo.
• Complexidade de Tempo: $ (1<)
• Complexidade de Espaço: $ (1<)
Isto torna custosa a busca pela solução em jogos de tamanho razoáveis. Veja, como exemplo, o
xadrez: 1 ≈ 35 e< ≈ 100. Impossível se analisar uma solução exata para este caso, mas esse
algoritmo serve como base para a análise matemática de jogos e para algoritmos mais práticos.
6
1 Busca Competitiva
1.3 A Poda Alfa-Beta
O problema do algoritmo minimax é o aumento da quantidade de estados que precisam ser
examinados em relação à quantidade de movimentos, que cresceexponencialmente. Apesar de
não se conseguir transformar em busca de complexidade exponencial em uma complexidade
linear, é possível usar de artifícios para reduzir o espaço de busca.
Mas como fazer isso? Há meios para se eliminar alguns nós da árvore do jogo por meio do
princípio de poda, que desconsidera algumas partes da árvore sem afetar sua solução �nal obtida
pela busca minimax. Essa técnica é conhecida como poda alfa-beta. Para compreender, vamos
considerar o mesmo exemplo da �gura 1.2, mas agora desconsiderando alternativas. Veja a
�gura 1.4
Figura 1.4: A poda alfa-beta deixou de examinar 2 nós da árvore de busca, sem comprometer o
resultado �nal do algoritmo minimax. Ambos retornam a mesma solução.
A �gura 1.4 mostra que foram examinados todos os nós da subárvore mais à esquerda, obtendo
o valor MIN = 3 para o nó raiz. Na subárvore do meio, encontrou-se o valor MIN = 2 e isso nos
permite descartar os demais nós dessa subárvore, pois o nó pai (MAX) não escolherá nenhum
outro nó desta subárvore, pois seu MAX já é maior que o MIN atual. Na subárvore mais à direita
foi necessário examinar todos os nós. Como pode ser facilmente percebido, a efetividade da poda
alfa-beta depende da ordem em que os nós sucessores são examinados. Com a melhor ordem
possível, a complexidade de tempo do algoritmo torna-se $ (1</2). Isso dobra a profundidade
de busca que conseguimos fazer.
O nome do algoritmo é dado a partir de dois parâmetros que descrevem os limites sobre os
valores propagados de volta que aparecem em qualquer lugar ao longo do caminho:
• Alfa (U): o valor da melhor escolha (isto é, a de valor mais alto) que encontramos até o
momento em qualquer ponto de escolha ao longo do caminho para MAX.
• Beta (V): o valor da melhor escolha (isto é, a de valor mais baixo) que encontramos até
agora em qualquer ponto de escolha ao longo do caminho para MIN.
A poda alfa-beta pode ser aplicada a árvores de qualquer profundidade e frequentemente é
possível podar subárvores inteiras em lugar de podar apenas folhas. O princípio geral é este:
considere um nó + em algum lugar na árvore, tal que o Jogador tenha a escolha de movimento
7
1 Busca Competitiva
até esse nó. Se o Jogador tiver uma escolha melhor U no nó pai de + ou em qualquer ponto de
escolha adicional acima dele, então + nunca será alcançado em um jogo real. Assim, uma vez que
descobrimos o su�ciente sobre + (examinando alguns de seus descendentes) para chegar a essa
conclusão, poderemos podá-lo.
Figura 1.5: Princípio geral da poda alfa-beta. O U é o valor da melhor escolha (valor mais alto)
encontrado até então para qualquer ponto de escolha de MAX. Se + é pior do que U ,
MAX não percorrerá este caminho (irá podar este ramo de busca). O V é de�nido de
maneira análoga. Em resumo, se U é melhor que+ para o jogador, nunca chegaremos
a + em um jogo.
1.4 Decisões Imperfeitas em Tempo Real
Em jogos, mesmo a poda alfa-beta faz com que a árvore seja examinada até sua profundidade em
algum momento. Na prática isso não é razoável pois movimentos precisam ser feitos em poucos
minutos. Uma proposta para cortar a busca mais cedo é a aplicação de funções de avaliação
heurística aos estados da busca, transformando os nós não terminais em nós terminais. Assim,
uma função de avaliação heurística (AVAL) substituirá a função de utilidade, e o teste de término
por um teste de corte que decide quando aplicar AVAL.
Algorithm 2: Minimax Heuristica
if TESTE DE CORTE(s,d) then
AVAL(s)
else if JOGADOR(s) = MAX then
<0G0∈��$�( (B) H-MINIMAX(RESULTADO(s,a), d+1)
else if JOGADOR(s) = MIN then
<8=0∈��$�( (B) H-MINIMAX(RESULTADO(s,a), d+1)
8
1 Busca Competitiva
Figura 1.6: Algoritmo de busca alfa-beta.
Para ajudar na compreensão faremos uma avaliação usando o jogo de xadrez, onde durante
anos os a�cionados desenvolveram meios para julgar o valor de uma posição. Um programa de
jogos é fortemente dependente da qualidade de sua função de avaliação.
A função de avaliação deve ordenar os estados terminais do mesmo modo que a verdadeira
função de utilidade: estados que são vitórias devem ser avaliados melhores que empates, que
por sua vez devem ser melhores que perdas. Caso contrário, um agente que utilizasse a função
de avaliação poderia errar, mesmo que pudesse antecipar todos os movimentos até o �m do
jogo. Em segundo lugar, a computação não deve demorar tempo demais! Em terceiro lugar, no
caso de estados não terminais, a função de avaliação deve estar fortemente relacionada com as
chances reais de vitória.
Quando falamos de chances, não quer dizer que o jogo não possui informações completas, mas
que ele possui limitações computacionais e precisa �nalizar a busca em nós não terminais. Isso
insere, sem dúvidas, uma incerteza sobre o resultado.
A maioria das funções de avaliação atua calculando diversas características do estado. Conside-
radas em conjunto, as características de�nem diversas categorias ou classes de equivalência de
estados: os estados de cada categoria têm os mesmos valores para todas as características. Por
exemplo, ao �nal do jogo, uma categoria contém ao todo dois peões versus um peão. Qualquer
9
1 Busca Competitiva
Figura 1.7: Dois estados onde a função de avaliação nos mostra um cenário favorável às peças
pretas (a) e um cenário que favorece as peças brancas (b). No cenário (a), as peças
pretas capturaram 1 cavalo e 2 bispos a mais que as brancas, tornando o estado
favorável para o time preto. No cenário (b), com a torre branca colocada em uma
posição diferente, irá capturar a rainha preta e tornará as chances do time branco
maiores de vitória.
categoria especí�ca, em termos gerais, conterá alguns estados que levam a vitórias, alguns que
levam a empates e alguns que levam a derrotas. A função de avaliação não tem como saber quais
são os estados de cada grupo, mas pode retornar um único valor capaz de re�etir a proporção
de estados que conduzem a cada resultado. Matematicamente, podemos fazer uma função linear
ponderada que expresse uma probabilidade de sucesso.
�+�!(B) = F1 51(B) +F2 52(B) + · +F= 5= (B) =
=∑
8=1
F8 58 (B) (1.1)
onde cadaF8 é um peso e cada 58 é uma característica da posição. No caso do xadrez, 58 poderia
representar os números de cada tipo de peça no tabuleiro,F8 poderia corresponder aos valores
das peças (1 para peão, 3 para bispo etc.).
Esta suposição é muito forte e jogos mais modernos de xadrez fazem avaliações mais completas
do que essa. Isso é fruto da experiência de anos dos humanos jogando xadrez. Porém, é possível
utilizar técnicas de aprendizagem de máquina para estimar esses pesosF para uma função de
avaliação heurística.
1.5 Notas Bibliográficas
Consulte o livro "Inteligência Arti�cial"de Stuart Russel e Peter Norvig, capítulo 05 para
complementar sua leitura desta nota de aula. Pois ela foi baseada nesse capítulo.
10
1 Busca Competitiva
Figura 1.8: Jogo do Exercício 02.
1.6 Resumo
O estudo de jogos em IA é fascinante e amplo, de modo a demandar um tempo maior para fazer
um aprofundamento devido. Nesta nota de aula, nosso foco �cou na descrição do problema de
jogos de 2 jogadores com informações completas. O algoritmo minimax, a poda alfa-beta e a
abordagem de funções de avaliação heurística são su�cientes para um ponto de partida neste
interessante campo de estudo da IA.
1.7 Exercícios
1. Faça uma breve revisão histórica sobre o jogo de xadrez e os programas inteligentes
desenvolvidos para ele. Iniciando com o trabalho de Claude Shannon, Programming a
Computer for Playing Chess, em 1950.
2. Considere o jogo, representado na �gura 1.8, de 2 jogadores descrito a seguir: Posição
inicial de um jogo simples. O jogador A joga primeiro. Os dois jogadores se revezam na
movimentação e cada jogador deve mover sua �cha para um espaço adjacente aberto em
qualquer sentido. Se o oponente ocupar um espaço adjacente, um jogador pode saltar sobre
um oponente até o próximo espaço aberto, se houver (por exemplo, se A estiver em 3 e B
estiver em 2, A poderá voltar a 1). O jogo termina quando um jogador chegarà extremidade
oposta do tabuleiro. Se o jogador A alcançar o espaço 4 primeiro, o valor do jogo para A será
+1; se o jogador B alcançar o espaço 1 primeiro, o valor do jogo para A será -1.
• a Desenhe a árvore do jogo completa, usando as convenções a seguir:
– Escreva cada estado como ((�, (�), onde (� e (� denotam as posições das �chas.
– Coloque cada estado terminal em um quadrado e escreva o valor de seu jogo
em um círculo.
– Insira os estados de ciclo (estados que já aparecem no caminho para a raiz) em
quadrados duplos. Tendo em vista que o valor não está claro, identi�que cada
um com um símbolo “?”
• b Agora marque cada nó com seu valor minimax propagado de volta (também em
um círculo). Explique como você tratou os valores “?” e por quê.
3. Usando o jogo da velha como exemplo. Nós de�nimos -= como o número de linhas,
colunas ou diagonais com exatamente = - e não $ . Da mesma forma, $= é o número de
linhas, colunas ou diagonais com apenas = $ . A função utilidade atribui +1 a qualquer
11
1 Busca Competitiva
posição com -3 = 1 e −1 em qualquer posição com $3 = 1. Todas as outras posições
terminais têm utilidade 0. Para posições não terminais, utilizamos uma função linear de
avaliação de�nida como �E0; (B) = 3-2(B) + -1(B) − (3$2(B) +$1(B)).
a) Existem cerca de quantos jogos da velha possíveis?
b) Mostre toda a árvore de jogo começando de um tabuleiro vazio até a profundidade 2
(isto é, um X e um O na tabuleiro), levando a simetria em conta.
c) Marque em sua árvore as avaliações de todas as posições com profundidade 2.
d) Utilizando o algoritmo minimax, marque em sua árvore os valores propagados para
as posições à profundidade 1 e 0, e utilize esses valores para escolher a melhor jogada
da partida.
e) Circule os nós à profundidade 2 que não seriam avaliados se a poda alfa-beta fosse
aplicada, assumindo que os nós são gerados na ordem ótima para a poda alfa-beta.
12
	Busca Competitiva
	Estratégia Ótimas
	O Algoritmo Minimax
	Propriedades do Algoritmo Minimax
	A Poda Alfa-Beta
	Decisões Imperfeitas em Tempo Real
	Notas Bibliográficas
	Resumo
	Exercícios