A busca adversária é uma busca onde examinamos o problema que surge quando tentamos planejar antecipadamente o mundo e outros agentes estão planejando contra nós.

estrutura de dados

• Nos tópicos anteriores, estudamos as estratégias de busca que estão associadas apenas a um único agente que visa encontrar a solução que muitas vezes se expressa na forma de uma sequência de ações.
• Porém, pode haver algumas situações em que mais de um agente esteja procurando a solução no mesmo espaço de busca, e esta situação geralmente ocorre durante o jogo.
• O ambiente com mais de um agente é denominado como ambiente multiagente , em que cada agente é oponente de outro agente e joga um contra o outro. Cada agente precisa considerar a ação de outro agente e o efeito dessa ação em seu desempenho.
• Então, Pesquisas nas quais dois ou mais jogadores com objetivos conflitantes tentam explorar o mesmo espaço de busca pela solução são chamadas de buscas adversárias, geralmente conhecidas como Jogos. .
• Os jogos são modelados como um problema de pesquisa e uma função de avaliação heurística, e estes são os dois principais fatores que ajudam a modelar e resolver jogos em IA.

Tipos de jogos em IA:

Informações perfeitas:Um jogo com informações perfeitas é aquele em que os agentes podem olhar o tabuleiro completo. Os agentes têm todas as informações sobre o jogo e também podem ver os movimentos uns dos outros. Exemplos são Xadrez, Damas, Go, etc.Informações imperfeitas:Se em um jogo os agentes não possuem todas as informações sobre o jogo e não estão cientes do que está acontecendo, esse tipo de jogo é chamado de jogo com informações imperfeitas, como jogo da velha, Battleship, blind, Bridge, etc.Jogos determinísticos:Jogos determinísticos são aqueles jogos que seguem um padrão estrito e um conjunto de regras para os jogos, e não há aleatoriedade associada a eles. Exemplos são xadrez, Damas, Go, jogo da velha, etc.Jogos não determinísticos:Não determinísticos são aqueles jogos que possuem vários eventos imprevisíveis e têm um fator de acaso ou sorte. Este fator de acaso ou sorte é introduzido por dados ou cartas. Eles são aleatórios e cada resposta de ação não é fixa. Esses jogos também são chamados de jogos estocásticos.
Exemplo: Gamão, Monopólio, Pôquer, etc.

Nota: Neste tópico discutiremos jogos determinísticos, ambiente totalmente observável, soma zero e onde cada agente atua alternativamente.

Jogo de soma zero

• Os jogos de soma zero são uma busca adversária que envolve pura competição.
• No jogo de soma zero, o ganho ou perda de utilidade de cada agente é exatamente equilibrado pelas perdas ou ganhos de utilidade de outro agente.
• Um jogador do jogo tenta maximizar um único valor, enquanto outro jogador tenta minimizá-lo.
• Cada movimento de um jogador no jogo é chamado de camada.
• Xadrez e jogo da velha são exemplos de jogos de soma zero.

Jogo de soma zero: pensamento incorporado

O jogo de soma zero envolveu o pensamento incorporado no qual um agente ou jogador está tentando descobrir:

• O que fazer.
• Como decidir a mudança
• Precisa pensar em seu oponente também
• O oponente também pensa no que fazer

Cada um dos jogadores tenta descobrir a resposta do seu oponente às suas ações. Isso requer pensamento incorporado ou raciocínio retroativo para resolver os problemas do jogo na IA.

Formalização do problema:

Um jogo pode ser definido como um tipo de pesquisa em IA que pode ser formalizada nos seguintes elementos:

Estado inicial:Especifica como o jogo é configurado no início.Jogadoras):Especifica qual jogador se moveu no espaço de estados.Ações):Ele retorna o conjunto de movimentos legais no espaço de estados.Resultado(s, a):É o modelo de transição, que especifica o resultado dos movimentos no espaço de estados.Teste(s) Terminal(is):O teste de terminal é verdadeiro se o jogo terminar, caso contrário, é falso em qualquer caso. O estado onde o jogo termina é chamado de estados terminais.Utilidade(s, p):Uma função de utilidade fornece o valor numérico final para um jogo que termina nos estados terminais s para o jogador p. Também é chamada de função de recompensa. Para o xadrez, os resultados são vitória, derrota ou empate e seus valores de pagamento são +1, 0, ½. E para o jogo da velha, os valores de utilidade são +1, -1 e 0.

Árvore do jogo:

Uma árvore de jogo é uma árvore onde os nós da árvore são os estados do jogo e as bordas da árvore são os movimentos dos jogadores. A árvore do jogo envolve estado inicial, função de ações e função de resultado.

Exemplo: árvore do jogo Tic-Tac-Toe:

A figura a seguir mostra parte da árvore do jogo da velha. A seguir estão alguns pontos-chave do jogo:

• Existem dois jogadores MAX e MIN.
• Os jogadores têm um turno alternativo e começam com MAX.
• MAX maximiza o resultado da árvore do jogo
• MIN minimiza o resultado.

Exemplo de explicação:

• Do estado inicial, MAX tem 9 movimentos possíveis ao começar primeiro. MAX lugar x e MIN lugar o, e ambos os jogadores jogam alternadamente até chegarmos a um nó folha onde um jogador tem três seguidos ou todos os quadrados estão preenchidos.
• Ambos os jogadores calcularão cada nó, minimax, o valor minimax que é a melhor utilidade alcançável contra um adversário ideal.
• Suponha que ambos os jogadores estejam bem cientes do jogo da velha e joguem a melhor jogada. Cada jogador está fazendo o seu melhor para evitar que outro ganhe. MIN está atuando contra Max no jogo.
• Então, na árvore do jogo, temos uma camada de Max, uma camada de MIN, e cada camada é chamada de Dobra . Max coloca x, então MIN coloca o para evitar que Max ganhe, e este jogo continua até o nó terminal.
• Neste caso, MIN vence, MAX vence ou há empate. Esta árvore de jogo é todo o espaço de busca de possibilidades em que MIN e MAX estão jogando jogo da velha e revezando-se alternadamente.

Conseqüentemente, a pesquisa contraditória para o procedimento minimax funciona da seguinte forma:

• O objetivo é encontrar a estratégia ideal para MAX vencer o jogo.
• Ele segue a abordagem da pesquisa em profundidade.
• Na árvore do jogo, o nó folha ideal pode aparecer em qualquer profundidade da árvore.
• Propague os valores minimax até a árvore até que o nó terminal seja descoberto.

Em uma determinada árvore de jogo, a estratégia ótima pode ser determinada a partir do valor minimax de cada nó, que pode ser escrito como MINIMAX(n). MAX prefere passar para um estado de valor máximo e MIN prefere passar para um estado de valor mínimo então: