Ambiente e Pesquisa Competitiva

Agentes, Ambiente e Pesquisa em Contextos Competitivos

1. Agentes e o Ambiente

Um agente é uma entidade que percebe o ambiente através de sensores e atua nele utilizando atuadores para atingir objetivos. A relação entre o agente e o ambiente define os desafios enfrentados na tomada de decisões.

1.1 Características do Ambiente

Os ambientes podem ser classificados de acordo com as seguintes dimensões:

• Acessível vs. Inacessível:
  • Um ambiente acessível permite ao agente obter toda a informação necessária para a tomada de decisões (e.g., tabuleiro de xadrez).
  • Num ambiente inacessível, o agente trabalha com informação incompleta ou parcial (e.g., tráfego urbano).
• Determinístico vs. Não-determinístico:
  • Num ambiente determinístico, as ações produzem sempre os mesmos resultados (e.g., resolução de puzzles).
  • Num ambiente não-determinístico, as ações podem ter resultados imprevisíveis (e.g., condução autónoma em condições adversas).
• Estático vs. Dinâmico:
  • Ambientes estáticos não mudam enquanto o agente decide (e.g., sudoku).
  • Ambientes dinâmicos podem mudar independentemente das ações do agente (e.g., trânsito em tempo real).
• Discreto vs. Contínuo:
  • Num ambiente discreto, o conjunto de estados e ações possíveis é finito (e.g., jogos de tabuleiro).
  • Num ambiente contínuo, estados e ações podem variar continuamente (e.g., controlo de drones).
• Episódico vs. Não-episódico:
  • Em ambientes episódicos, a experiência do agente é dividida em episódios independentes (e.g., classificação de imagens).
  • Em ambientes não-episódicos, as ações têm impacto cumulativo (e.g., planeamento estratégico).

---

2. Pesquisa em Contextos Competitivos

Nos contextos competitivos, a pesquisa é frequentemente aplicada a jogos, onde o objetivo é maximizar os ganhos de um jogador e minimizar os do adversário.

2.1 Jogos como Problemas de Pesquisa

Os jogos são modelados como problemas de pesquisa em árvores ou grafos, com estados representando configurações do jogo e ações conectando estados sucessivos.

2.2 Algoritmo Minimax

• Descrição:
  O algoritmo minimax é usado para jogos determinísticos de soma zero com dois jogadores. Assume que ambos os jogadores agem racionalmente:
  • O jogador que toma a vez tenta maximizar o seu ganho.
  • O adversário tenta minimizar o ganho do outro jogador.
• Exemplo: Jogos como xadrez ou damas.

2.3 Poda Alpha-Beta (Pruning)

• Descrição:
  Uma otimização do minimax que elimina partes da árvore de decisão que não podem influenciar o resultado final, reduzindo o número de estados avaliados.
• Vantagem: Mantém a mesma solução ótima, mas com menos cálculos.
• Exemplo: É amplamente usada em jogos de tabuleiro como o xadrez, onde o espaço de busca é vasto.

2.4 Decisões Imperfeitas em Tempo Real

• Em jogos com limites de tempo, é impossível explorar a árvore de busca completa.
• Estratégias:
  • Cut-off em profundidade: Limitar a profundidade máxima explorada.
  • Funções de avaliação heurística: Estimam a qualidade de um estado sem explorar até o final do jogo.

---

3. Jogos Determinísticos vs. Estocásticos

• Determinísticos:
  • Não envolvem elementos de aleatoriedade.
  • Exemplos: Xadrez, damas.
• Estocásticos:
  • Incluem incertezas, como lançamentos de dados ou cartas.
  • Exemplos: Monopólio, póquer.

3.1 Jogos Estocásticos com Informação Perfeita

• Descrição:
  Todos os jogadores têm acesso completo à informação do jogo, mas os resultados são afetados por fatores aleatórios.
• Algoritmo Expectiminimax:
  • Uma extensão do minimax para jogos estocásticos.
  • Inclui nós de "expectativa", que representam médias ponderadas dos resultados de ações aleatórias.
  • Exemplo: Gamão.

3.2 Jogos Estocásticos com Informação Imperfeita (Parcial)

• Descrição:
  Cada jogador tem apenas uma visão parcial do estado do jogo, criando desafios adicionais.
• Algoritmos:
  • Miniminimax: Uma variação do minimax adaptada para incertezas.
  • Teoria dos Jogos: Modela interações estratégicas entre agentes racionais, frequentemente usando equilíbrios de Nash.
  • Exemplo: Póquer (onde as cartas dos outros jogadores são desconhecidas).

---

Desafios e Considerações

• Complexidade Computacional:
  Jogos como xadrez têm espaços de busca gigantescos, exigindo otimizações como poda alpha-beta.
• Incerteza e Aleatoriedade:
  Nos jogos estocásticos, é essencial integrar modelos probabilísticos para lidar com o acaso e a informação parcial.
• Jogos em Tempo Real:
  Requerem decisões rápidas, muitas vezes baseadas em aproximações heurísticas.