CCT-UFCA/Ciência da Computação/Inteligência Artificial/Busca Competitiva

Busca Competitiva

Até agora, estudamos problemas de busca em que havia apenas um agente tentando alcançar um objetivo.

Na busca competitiva, temos dois agentes que jogam um contra o outro.

• Exemplo: xadrez, damas, jogo da velha, Go.
• Cada ação de um jogador afeta a utilidade do outro.
• Esses ambientes são chamados de competitivos e fazem parte da Teoria dos Jogos.

Em termos de IA, estamos lidando com ambientes:

• Determinísticos (não há sorte, o próximo estado é previsível),
• Completamente observáveis (ambos veem todo o tabuleiro),
• Multiagente competitivo (MAX × MIN).

Jogadores: MAX e MIN

• MAX → tenta maximizar a utilidade (ganhar ou ficar mais perto da vitória).
• MIN → tenta minimizar a utilidade de MAX (impedir sua vitória).

Exemplo:

• No jogo da velha, se MAX busca ganhar, MIN joga para bloquear.
• A árvore de jogo alterna camadas de jogadas de MAX e jogadas de MIN.

Elementos do Problema

Assim como nas buscas vistas antes, precisamos definir:

1. Estado inicial → posição inicial do jogo.
2. Ações possíveis → jogadas permitidas em cada estado.
3. Modelo de transição → o que acontece após cada jogada.
4. Teste de terminal → identifica se o jogo acabou (vitória, derrota, empate).
5. Função de utilidade → atribui um valor numérico (ex.: vitória = +1, derrota = -1, empate = 0).

Algoritmo MinMax

• Ideia: assume que os dois jogadores são racionais (sempre tomam a melhor decisão).
• O algoritmo percorre a árvore de jogo de forma parecida com a busca em profundidade.
• Nos nós de MAX, escolhe o maior valor.

• Nos nós de MIN, escolhe o menor valor.

Exemplo:

Imagine que estamos em um jogo onde MAX (quer ganhar) joga primeiro e MIN responde. A árvore de possibilidades fica assim:

Etapas:

1. MAX começa. Ele pode escolher esquerda ou direita.
2. Se escolher esquerda, MIN decide entre {3, 5, 2}.
   • MIN é oponente, então escolhe o menor valor → 2.
3. Se escolher direita, MIN decide entre {9, 0}.
   • MIN escolhe o menor → 0.
4. Agora MAX compara:
   • Esquerda leva a 2
   • Direita leva a 0
   • MAX escolhe o maior → 2.

Resultado do MinMax: a jogada ótima de MAX é ir para a esquerda, garantindo pelo menos valor 2.

Complexidade:

• Tempo: O(b^m), onde b = fator de ramificação (número de jogadas possíveis), m = profundidade.
• Espaço: também O(b^m).
• Para jogos como xadrez, isso é gigantesco, tornando o MinMax puro impraticável.

Poda Alfa-Beta

• Uma melhoria do MinMax que corta (poda) ramos da árvore que não precisam ser analisados.
• O resultado é o mesmo do MinMax, mas com menos trabalho.

Funcionamento:

• Mantém dois valores:
  • α (alfa): melhor valor encontrado até agora para MAX.
  • β (beta): melhor valor encontrado até agora para MIN.
• Se em algum momento α ≥ β, cortamos aquele ramo (não precisa ser expandido).

Exemplo:

Imagine essa árvore de jogo:

Etapas com poda alfa-beta

1. MAX começa pela esquerda:
   • MIN avalia 3 → guarda como melhor até agora (β = 3).
   • MIN avalia 12 → maior que 3, mas como ele é MIN, fica com 3.
   • MIN avalia 8 → maior que 3, mas MIN ainda fica com 3.
   • Resultado do nó esquerdo = 3.
2. MAX guarda α = 3 (melhor valor até agora).
3. MAX agora olha a direita:
   • MIN vê o primeiro filho → 2.
   • Nesse momento já dá para parar! Por quê?
     • MAX tem α = 3 (garantido à esquerda).
     • MIN à direita encontrou 2, que é menor que 3.
     • Ou seja, MAX nunca escolherá a direita, então não precisamos nem avaliar o 14.

✂️ Poda: o nó com valor 14 não precisa ser avaliado.

Curiosidades

• O algoritmo Deep Blue (da IBM) usou MinMax com poda alfa-beta para vencer Garry Kasparov (campeão mundial de xadrez) em 1997.

• No entanto, jogos como o Go são muito mais complexos → foi preciso criar novas técnicas (ex.: AlphaGo em 2016, que combina busca e aprendizado de máquina).

Conclusão

• A busca competitiva ensina como a IA toma decisões em jogos de adversários.
• MinMax é a base, mas é pesado em jogos grandes.
• Poda alfa-beta melhora a eficiência sem mudar o resultado.

• Esse tema é a ponte entre IA clássica em jogos e IA moderna (aprendizado de máquina).

Referências

1. RUSSELL, S. J.; NORVIG, P. Inteligência artificial. 3 ed. LTC, 2013. 1016 p.
2. COPPIN, B. Inteligência Artificial. 1a ed. LTC, 2010. 664 p.