Busca Adversarial e Jogo

A busca adversarial é o estudo da tomada de decisões em ambientes competitivos, onde um agente deve escolher movimentos em uma árvore de jogo contra um oponente que está tentando alcançar o resultado oposto.

Definition

A busca adversarial calcula um movimento para um jogador explorando uma árvore de jogo na qual os jogadores alternam turnos, usando o princípio minimax (cada jogador otimiza assumindo que o oponente joga de forma ótima) juntamente com poda e avaliação heurística para lidar com árvores grandes.

Scope

Este tópico abrange a busca em jogos de dois jogadores, soma zero e informação perfeita: a regra de decisão minimax, o corte alfa-beta que permite ao minimax pular ramos comprovadamente irrelevantes, funções de avaliação e busca com profundidade limitada para jogos grandes demais para serem resolvidos exatamente, e a busca em árvore Monte Carlo para jogos com fatores de ramificação muito grandes. Aborda como as árvores de jogo são modeladas e como os limites computacionais forçam cortes heurísticos. Não abrange a análise geral de equilíbrio da teoria dos jogos de incentivos multiagentes, que é tratada em sistemas multiagentes.

Core questions

• Como a regra minimax determina um movimento ótimo contra um oponente ótimo?
• Como o corte alfa-beta elimina ramos sem afetar o valor minimax?
• Como as funções de avaliação são usadas para cortar a busca em uma profundidade fixa em jogos grandes?
• Quando a busca em árvore Monte Carlo é preferível ao minimax com profundidade limitada?

Key concepts

• árvore de jogo
• valor minimax
• corte alfa-beta
• função de avaliação (heurística)
• busca com profundidade limitada e o efeito horizonte
• jogos de soma zero com informação perfeita
• busca em árvore Monte Carlo
• ordenação de movimentos

Key theories

Regra de decisão Minimax

Em um jogo de soma zero para dois jogadores, cada jogador escolhe o movimento que maximiza seu próprio resultado mínimo garantido; propagar esses valores máximos/mínimos pela árvore de jogo produz o movimento ótimo na raiz.

Corte alfa-beta

Ao rastrear os melhores valores já garantidos aos jogadores maximizador e minimizador, a busca alfa-beta prova que certas subárvores não podem afetar a decisão final e as ignora, retornando o valor minimax exato enquanto, no melhor caso, quadruplica aproximadamente a profundidade alcançável em um dado tempo.

Busca em árvore Monte Carlo

Quando os fatores de ramificação são muito grandes para uma análise exaustiva, a busca em árvore Monte Carlo constrói uma árvore assimétrica guiada por rollouts aleatórios e uma regra de seleção que equilibra exploração e explotação, um método que transformou o jogo de computador em jogos como Go.

Clinical relevance

A busca adversarial produziu sistemas de IA marcantes, desde motores de xadrez usando busca alfa-beta até programas de Go baseados em busca em árvore Monte Carlo, e as mesmas técnicas informam a negociação automatizada, jogos de segurança e qualquer cenário modelado como uma disputa entre partes otimizadoras.

History

O artigo de Shannon de 1950 enquadrou o xadrez de computador como busca minimax com uma função de avaliação, e o teorema minimax de von Neumann forneceu a base da teoria dos jogos. O corte alfa-beta foi desenvolvido durante as décadas de 1950-60 e analisado rigorosamente por Knuth e Moore (1975). A busca em árvore Monte Carlo, formalizada nos anos 2000, impulsionou o próximo salto na força de jogo, especialmente no Go.

Key figures

• Claude E. Shannon
• John von Neumann
• Arthur Samuel
• Donald E. Knuth
• Ronald W. Moore

Seminal works

• shannon1950
• knuth1975
• browne2012

Frequently asked questions

O corte alfa-beta altera o movimento que o minimax escolheria?

Não. O corte alfa-beta retorna exatamente o mesmo valor e movimento que o minimax completo; ele apenas evita explorar ramos que comprovadamente não podem influenciar o resultado. Seu benefício é a velocidade, e com uma boa ordenação de movimentos, ele pode buscar aproximadamente o dobro da profundidade no mesmo tempo.

Por que usar a busca em árvore Monte Carlo em vez de minimax em jogos como Go?

Go tem um fator de ramificação enorme e carece de uma função de avaliação simples e precisa, então o minimax de profundidade fixa é ineficaz. A busca em árvore Monte Carlo, em vez disso, estima a qualidade do movimento através de muitas jogadas aleatórias e faz a árvore crescer seletivamente em direção a linhas promissoras, o que se adapta muito melhor a esses jogos.