Jogos e busca adversária

Uma busca em jogo começa com um estado: informação suficiente para determinar o que pode acontecer em seguida. No jogo da velha, isso significa o tabuleiro e o jogador da vez. O tabuleiro sozinho está incompleto porque a próxima marca depende de quem joga.

Defina os seis componentes

Um modelo de jogo fornece:

• Um estado inicial, $S_0$.
• Uma função, $\text{Jogador-da-vez}(s)$, que indica o jogador que age no estado $s$.
• As jogadas permitidas, $\text{A}\stackrel{¸}{\text{c}}\tilde{\text{o}}\text{es}(s)$.
• Um modelo de transição, $\text{Resultado}(s,a)$, que fornece o estado após a ação $a$.
• Um teste de término, $\acute{\text{E}}\text{-terminal}(s)$, que detecta o fim do jogo.
• Uma função de utilidade, $\text{Utilidade}(s,p)$, que fornece ao jogador $p$ um ganho numérico em um estado terminal.

No jogo da velha, comece com um tabuleiro vazio de 3 por 3 e X na vez. Uma ação escolhe uma casa vazia. A transição coloca a marca do jogador atual e muda a vez. O jogo termina assim que alguém forma uma linha, coluna ou diagonal de três marcas, ou quando o tabuleiro cheio resulta em empate. Do ponto de vista de X, atribua +1 à vitória, 0 ao empate e −1 à derrota. O teste de término deve ser executado antes de outra marca ser colocada: o jogo não continua após uma vitória.

Classifique o jogo em eixos separados

Esses eixos são independentes. Os dados tornam o gamão estocástico, embora seu tabuleiro seja visível. Cartas ocultas dizem respeito à informação, não ao fato de uma ação ser aleatória. Em um jogo com informação oculta, o jogador raciocina sobre os estados possíveis compatíveis com suas observações, chamados de estado de crença.

Mantenha fixo o ponto de vista do ganho

Em um jogo de soma zero com dois jogadores, o ganho de um jogador é a perda do outro. Pontuações de soma constante se comportam da mesma forma: vitória 1, derrota 0 e empate ½ para cada um sempre somam 1. Um número basta para expressar a oposição. Chame o jogador que quer aumentá-lo de MAX, e o jogador que quer diminuí-lo de MIN. Esses são papéis; MAX não precisa ser sempre as brancas ou X.

Em uma busca comum, é possível escolher todas as ações ao longo de um caminho. Um agente que joga deve responder a jogadas que não controla. Sua solução é uma estratégia, que especifica o que fazer em cada situação que possa enfrentar. Um plano que só funciona se o oponente der uma resposta favorável não basta.

Uma árvore de jogo começa no estado atual. Cada aresta de saída representa uma jogada permitida, e seu filho é o estado resultante. Identifique cada nó não terminal pelo jogador que age nele. Em um jogo alternado com dois jogadores, os níveis de MAX e MIN se alternam.

Conte turnos individuais

Uma meia-jogada é uma jogada de um jogador. No xadrez, uma jogada completa geralmente inclui um turno das brancas e um das pretas, portanto abrange duas meias-jogadas. Uma busca de profundidade 4 a partir da vez das brancas alcança posições após as brancas, as pretas, as brancas e as pretas terem agido. Conte as arestas a partir da raiz, cuja profundidade é zero.

Seja $b$ o fator de ramificação e $m$ a profundidade máxima. Uma árvore uniforme tem $b^d$ nós na profundidade $d$ e $b^m$ folhas. Seu número total de nós é:

Para $b>1$, os níveis mais profundos predominam, resultando em crescimento exponencial. Com quatro jogadas por posição, a profundidade 3 tem 64 folhas; a profundidade 4 tem 256. Uma meia-jogada adicional multiplica a contagem de folhas por quatro, não por um.

Diferencie partidas de posições

O jogo da velha tem no máximo $9!=362.880$ ordens para preencher o tabuleiro. Muitas ordens continuariam após uma vitória anterior e não são partidas completas permitidas. Parar imediatamente nas vitórias resulta em 255.168 partidas completas: 131.184 vitórias de X, 77.904 vitórias de O e 46.080 empates. Ao longo das partidas permitidas, há apenas 5.478 posições distintas do tabuleiro, incluindo o tabuleiro vazio.

A diferença vem em parte das transposições: ordens de jogadas diferentes que chegam ao mesmo estado. X pode jogar em um canto, O no centro e X no canto oposto, ou X pode jogar nesses dois cantos na ordem inversa. Ambos os caminhos terminam no mesmo tabuleiro e com o mesmo jogador da vez. Uma árvore mantém os dois caminhos; um grafo de jogo pode armazenar o estado compartilhado uma vez. Reutilizar trabalho exige identificar estados completos, não apenas tabuleiros visualmente semelhantes.

Veja por que a busca completa se torna inviável

O xadrez é frequentemente modelado com cerca de 35 jogadas permitidas por posição e uma partida de 100 meias-jogadas, ou 50 jogadas de cada jogador. Isso fornece a escala aproximada:

Ramos reais terminam em profundidades diferentes e têm números diferentes de jogadas, mas essa estimativa já explica por que enumerar uma árvore de jogo completa de xadrez é impraticável. Em um tabuleiro vazio de Go de 19 por 19, só a primeira pedra tem 361 pontos possíveis.

A árvore de busca é o que um algoritmo de fato gera. O minimax simples gera a árvore de jogo completa abaixo do estado em um jogo finito que ele busca até o fim. Poda, limites de profundidade e simulação seletiva geram menos. Uma folha de corte pode, portanto, ser uma posição não terminada, embora uma folha da árvore de jogo completa seja terminal.

Visualize uma estratégia dentro da árvore

Uma subárvore de estratégia para MAX mantém uma aresta selecionada em cada nó MAX e todas as arestas permitidas em cada nó MIN. MAX escolhe sua própria ação, mas deve manter uma resposta para qualquer jogada do oponente. Um único caminho da raiz a uma folha descreve apenas uma partida possível. Ele não consegue mostrar que o plano escolhido resiste às outras respostas.

O minimax escolhe o melhor resultado que MAX pode garantir contra um oponente que joga de modo ótimo. Toda utilidade de folha é medida para MAX. Um número grande favorece MAX mesmo quando o nó avaliado pertence a MIN.

Trabalhe das folhas em direção à raiz

Em um nó terminal, retorne sua utilidade. Em um nó MAX, retorne o maior valor dos filhos. Em um nó MIN, retorne o menor. Continue até que a raiz receba um valor:

O valor de um filho já resume a continuação ótima a partir dele. Por isso, um nó pai compara os valores retornados em vez de reabrir todas as folhas abaixo deles. A recursão funciona com qualquer número de níveis alternados.

Acompanhe uma decisão de duas meias-jogadas

MAX tem três jogadas, cada uma levando a um nó MIN:

Primeiro, tome o mínimo em cada linha. MIN pode fazer A valer 4, B valer 2 e C valer 5. Em seguida, MAX toma o máximo desses três resultados:

O valor minimax é 5. A decisão minimax é a jogada para C. Um é um número que descreve a posição; a outra é uma ação que o programa pode executar.

A maior folha, 15, está sob B, mas MAX não controla a resposta que chega a ela. MIN escolheria 2. A média das folhas de B é 10, o que também parece atraente, mas a média modela uma escolha aleatória com probabilidades adequadas. Um oponente que joga de modo ótimo exige um mínimo.

Interprete a variante principal

A variante principal é a sequência seguida quando os jogadores escolhem jogadas ótimas. Aqui, MAX joga C e MIN escolhe sua folha de valor 5. Em uma árvore mais profunda, siga o máximo ou mínimo escolhido em cada nível. A utilidade terminal nessa sequência corresponde ao valor da raiz. Se várias jogadas empatam, pode existir mais de uma sequência ótima.

Entenda a garantia

Em um jogo finito determinístico de soma zero com dois jogadores e informação perfeita, seguir a estratégia minimax garante pelo menos o valor da raiz. Um oponente que joga de modo ótimo limita MAX a esse valor. Um erro do oponente pode permitir um resultado melhor, portanto 5 é um limite inferior, não uma previsão de que toda partida deve terminar exatamente em 5.

Um programa pode aproveitar uma fraqueza preservando esse limite. Se duas jogadas têm valor minimax 5, ele pode preferir aquela que oferece mais oportunidades para o oponente cometer um erro. Escolher uma jogada de valor minimax 2 porque ela contém um tentador 15 abandona a garantia de 5. A diferença está em a jogada preservar ou não o melhor valor no pior caso.

A definição de minimax já é um programa recursivo. Uma função de valor recebe um estado e retorna um número. Uma função de busca compara as primeiras jogadas possíveis e retorna a ação a ser executada.

Separe a escolha da jogada do cálculo do valor

O pseudocódigo a seguir pressupõe que MAX age na raiz e que os turnos se alternam:

MINIMAX-SEARCH(s):
    if Is-Terminal(s): return no action
    bestMove = no action
    bestValue = -infinity
    for a in Actions(s):
        value = MIN-VALUE(Result(s, a))
        if value > bestValue:
            bestValue = value
            bestMove = a
    return bestMove

MAX-VALUE(s):
    if Is-Terminal(s): return Utility(s, MAX)
    v = -infinity
    for a in Actions(s):
        v = max(v, MIN-VALUE(Result(s, a)))
    return v

MIN-VALUE(s):
    if Is-Terminal(s): return Utility(s, MAX)
    v = +infinity
    for a in Actions(s):
        v = min(v, MAX-VALUE(Result(s, a)))
    return v

Inicialize MAX com infinito negativo para que qualquer filho o melhore; inicialize MIN com infinito positivo. Verifique o término antes de gerar sucessores. Um tabuleiro de jogo da velha cheio sem uma linha vencedora é um empate, não uma posição não terminal cuja melhor jogada deve ser selecionada de uma lista vazia.

Acompanhe o que a recursão descobre

Considere este tabuleiro de jogo da velha, com X na vez e um ponto para cada casa vazia:

X O X
. O .
. . .

O ameaça completar a coluna do meio. Se X jogar em qualquer lugar exceto na casa inferior central, O poderá vencer no próximo turno. Essas jogadas têm valor −1 para X. Jogar na casa inferior central bloqueia a vitória imediata e permite um empate com jogo ótimo, resultando em valor 0. A raiz retorna a casa inferior central. O algoritmo não precisa de uma instrução separada que identifique essa ameaça: os resultados terminais determinam os valores.

Calcule os custos de tempo e memória

O minimax em profundidade examina $O(b^m)$ nós para fator de ramificação $b$ e profundidade máxima $m$. Armazenar todos os irmãos gerados em cada nível ativo exige memória $O(bm)$. Gerar sucessores um por vez reduz o armazenamento da busca ativa para $O(m)$, além da representação do estado. O tempo exponencial, não a pilha de recursão, geralmente é o principal obstáculo.

Preserve a convenção de pontuação

No código MAX/MIN, toda chamada retorna a utilidade de MAX. Não inverta seu sinal apenas porque MIN age em seguida. O negamax usa uma convenção diferente: cada valor é do ponto de vista do jogador atual, portanto o valor de um filho é negado antes de o pai maximizá-lo:

Para um jogo que termina em menos de 100 meias-jogadas, o tempo pode ser incluído atribuindo-se a uma vitória de MAX na profundidade $d$ a pontuação $100-d$, a uma derrota $-100+d$ e a um empate 0. Vitórias mais rápidas recebem então pontuações maiores e derrotas adiadas são menos negativas. O limite estrito de profundidade mantém toda vitória positiva e toda derrota negativa.

Por exemplo, vitórias nas meias-jogadas 3 e 7 recebem 97 e 93 pontos, portanto a vitória mais rápida é preferida. Derrotas nessas profundidades recebem −97 e −93, tornando a derrota mais tardia preferível, embora ambas continuem piores que um empate.

Uma única utilidade de MAX funciona quando os interesses de dois jogadores são estritamente opostos. Com vários jogadores ou interesses que coincidem, mantenha um vetor de utilidades. Para os jogadores A, B e C, o vetor (1, 2, 6) fornece seus ganhos nessa ordem.

Selecione pela entrada do jogador ativo

Em um nó em que C age, compare as terceiras entradas dos vetores dos filhos. Retorne o vetor inteiro do filho preferido por C. Em um nó de B, compare as segundas entradas desses vetores retornados; em um nó de A, compare as primeiras.

Não maximize cada entrada independentemente. Se os resultados disponíveis forem (1, 2, 6) e (4, 2, 3), C escolhe (1, 2, 6). A combinação (4, 2, 6) não é um resultado disponível e não pode ser propagada.

Trabalhe de trás para frente com três jogadores

A joga primeiro, depois B e depois C. Na jogada de A à esquerda, B escolhe entre dois nós de C:

• O primeiro tem folhas (1, 2, 6) e (4, 2, 3). C escolhe (1, 2, 6).
• O segundo tem folhas (6, 1, 2) e (7, 4, 1). C escolhe (6, 1, 2).

B compara as segundas entradas 2 e 1, portanto o ramo esquerdo retorna (1, 2, 6).

Na jogada de A à direita:

• C escolhe (5, 4, 5) em vez de (2, 5, 4), porque 5 é maior que 4 na terceira entrada.
• C escolhe (5, 2, 4) em vez de (7, 7, 1), porque 4 é maior que 1 na terceira entrada.

B compara as segundas entradas 4 e 2, portanto o ramo direito retorna (5, 4, 5). Por fim, A compara as primeiras entradas 1 e 5 e escolhe a direita. A raiz recebe o vetor inteiro (5, 4, 5).

Indique como os empates são resolvidos

Se C puder escolher (2, 3, 4) ou (6, 1, 4), ambos darão 4 a C. O ganho final de A poderá ser 2 ou 6. Uma previsão precisa de uma regra de desempate ou de um modelo da escolha de C. A indiferença de outro jogador não é necessariamente inofensiva para o jogador da raiz.

Se dois perseguidores querem capturar MAX, uma rodada tem uma camada MAX e uma camada MIN para cada perseguidor. Com dois perseguidores, uma rodada tem três meias-jogadas. Esse modelo difere de três jogadores independentes que buscam suas próprias recompensas.

Permita que os interesses coincidam

Em um jogo de soma geral, ambos os jogadores podem preferir (100, 100) a ganhos conjuntos menores. Os jogadores também podem se beneficiar temporariamente ao atacar um líder comum. Esse comportamento semelhante a uma aliança pode resultar de suas próprias preferências e mudar quando a posição muda.

Os cortes comuns da poda alfa-beta dependem de interesses opostos e não se transferem diretamente para vetores de utilidades. O modelo paranoico restaura uma oposição entre dois jogadores, permitindo a busca alfa-beta, mas pode prever uma hostilidade coordenada que os outros jogadores não escolheriam de fato.

A poda alfa-beta fornece o mesmo valor da raiz que o minimax na mesma árvore com os mesmos valores nas folhas. Ela economiza trabalho ao demonstrar que alguns ramos não podem melhorar a escolha. Jogadas ótimas empatadas podem ser retornadas em outra ordem.

Passe uma janela de busca pelo caminho

Dois limites descrevem as escolhas disponíveis acima do nó atual:

• $\alpha$ é o melhor valor disponível para MAX ao longo do caminho: MAX já pode obter pelo menos esse valor.
• $\beta$ é o melhor valor disponível para MIN ao longo do caminho: MIN já pode limitar MAX a no máximo esse valor.

Inicie a raiz com infinito negativo e positivo. Cada filho recursivo recebe os limites atuais. Eles são argumentos locais, não números globais compartilhados entre buscas em irmãos não relacionados.

Em um nó MAX, mantenha o maior valor de filho visto. Pare quando ele atingir ou superar beta: MIN acima já tem uma alternativa que não é maior que beta. Caso contrário, aumente alfa quando MAX encontrar uma melhora. Em um nó MIN, mantenha o menor valor de filho visto. Pare quando ele atingir alfa ou ficar abaixo dele: MAX acima já tem uma alternativa pelo menos tão boa. Caso contrário, reduza beta.

MAX-VALUE(s, alpha, beta):
    if Is-Terminal(s): return Utility(s, MAX)
    v = -infinity
    for a in Actions(s):
        v = max(v, MIN-VALUE(Result(s, a), alpha, beta))
        if v >= beta: return v
        alpha = max(alpha, v)
    return v

MIN-VALUE(s, alpha, beta):
    if Is-Terminal(s): return Utility(s, MAX)
    v = +infinity
    for a in Actions(s):
        v = min(v, MAX-VALUE(Result(s, a), alpha, beta))
        if v <= alpha: return v
        beta = min(beta, v)
    return v

A raiz compara ações e mantém alfa entre elas:

ALPHA-BETA-SEARCH(s):
    if Is-Terminal(s): return no action
    alpha = -infinity
    beta = +infinity
    bestMove = no action
    for a in Actions(s):
        v = MIN-VALUE(Result(s, a), alpha, beta)
        if v > alpha:
            alpha = v
            bestMove = a
    return bestMove

Acompanhe um corte em MIN

Pesquise os ramos MIN A = (4, 9, 6), B = (2, 15, 13) e C = (5, 8, 10), da esquerda para a direita. A precisa examinar as três folhas e retorna 4. A raiz agora tem alfa 4. A primeira folha de B é 2. Seu mínimo final só pode permanecer em 2 ou diminuir, portanto B não pode superar A. Ignore as duas folhas restantes de B. C examina as três folhas e retorna 5. A raiz escolhe C após examinar sete das nove folhas.

Acompanhe um corte em MAX

Suponha que um pai MIN já tenha um filho de valor 3, definindo beta como 3. Seu próximo filho MAX encontra uma folha de valor 6. O valor desse filho é pelo menos 6, portanto MIN preferirá seu 3 já existente. Ignore os filhos restantes desse nó MAX. O raciocínio do corte usa a alternativa de MIN, embora o nó atual seja MAX.

Um nó MIN podado pode retornar um limite superior; um nó MAX podado pode retornar um limite inferior. Seus valores exatos permanecem desconhecidos. O valor final da raiz é exato para a árvore pesquisada. A igualdade também permite um corte porque um ramo que só pode empatar não pode melhorar o melhor valor atual.

A poda alfa-beta economiza mais trabalho quando jogadas fortes são pesquisadas cedo. Os valores não mudam com a ordem das jogadas; o que muda é o momento em que a busca consegue demonstrar um corte.

Compare duas ordens

Para os três ramos MIN A = (4, 9, 6), B = (2, 15, 13) e C = (5, 8, 10), começar por A exige examinar sete folhas. Comece por C. Suas três folhas estabelecem alfa 5. A encontra 4 imediatamente e sofre um corte; B encontra 2 imediatamente e sofre um corte. Apenas cinco folhas são avaliadas, e a resposta continua sendo C com valor 5.

Para uma árvore uniforme com ordenação perfeita, a contagem de folhas é:

Isso é cerca de $O(b^{m\mathrm{/}2})$ em vez de $O(b^m)$ do minimax. O fator de ramificação efetivo cai para cerca de $\sqrt{b}$, permitindo aproximadamente o dobro da profundidade com recursos comparáveis. Com $b=35$, a profundidade 8 com ordenação perfeita avalia 3.001.249 folhas; o minimax comum de profundidade 4 tem 1.500.625 folhas. A comparação diz respeito à escala, não a tempos de execução idênticos.

Na pior ordem, a poda alfa-beta pode examinar todas as folhas do minimax. Suas verificações adicionais de limites acrescentam custo mesmo quando não economizam folhas.

Use pistas de ordenação baratas

A melhor jogada exata é desconhecida antes da busca. Os programas usam estimativas rápidas. No xadrez, podem testar capturas, depois ameaças e depois jogadas tranquilas. Uma jogada matadora causou um corte em outro ponto na mesma profundidade de busca e é testada cedo em outra posição. Essas pistas afetam a eficiência; elas não justificam descartar as outras jogadas permitidas.

O aprofundamento iterativo busca até a profundidade 1, depois 2, depois 3 e assim por diante. Uma jogada forte da iteração anterior se torna uma candidata inicial na próxima. O resultado mais profundo concluído também fica pronto caso o tempo acabe.

O trabalho repetido tem custos diferentes dependendo da poda. Para uma busca uniforme sem poda com fator de ramificação 35, todas as iterações menos profundas acrescentam cerca de $1\mathrm{/}(35-1)\approx \mathrm{2,9}\mathrm{\%}$ à busca final. Para a poda alfa-beta com ordenação perfeita, as profundidades 1 a 7 juntas avaliam 1.677.159 folhas, cerca de 56% da contagem da profundidade 8. Uma ordenação melhor ainda pode fazer o processo completo valer a pena.

Armazene posições com seu significado

Uma tabela de transposições armazena resultados indexados pelo estado completo do jogo. Se outra ordem de jogadas alcançar esse estado, o programa poderá reutilizar uma entrada adequada. Armazene a profundidade pesquisada e se o resultado é exato, um limite inferior ou um limite superior. Uma entrada rasa não substitui a informação exigida por uma busca mais profunda. Um limite pode estreitar uma janela ou justificar um corte, mas não deve ser tratado como um valor exato.

Uma função de avaliação estima quão favorável uma posição não terminada é para MAX. Ela torna possível a busca com profundidade limitada: a fronteira recebe valores estimados que podem ser propagados pelo minimax ou pela poda alfa-beta.

Torne as pontuações úteis para a busca

Um bom avaliador é rápido, concorda com a ordem dos resultados terminais reais e tem correlação com o sucesso a partir de posições não terminais. Os próprios estados terminais devem receber sua utilidade exata. Uma vitória de MAX deve ter pontuação acima de toda estimativa não terminal, para que acumular peças não se torne mais atraente que vencer.

Uma maneira de entender a avaliação é agrupar posições por características compartilhadas. Se esse grupo produz 72% de vitórias, 8% de empates e 20% de derrotas, com utilidades 1, ½ e 0, sua utilidade média é:

Essa interpretação depende de como as posições e continuações foram amostradas. É uma estimativa da qualidade do resultado, não uma prova de vitória forçada.

Some características ponderadas

Um projeto comum é uma soma ponderada:

Cada característica $f_i(s)$ mede uma propriedade da posição; cada peso $w_i$ indica quanto ela contribui. Diferenças entre os lados mantêm claro o ponto de vista. Uma diferença material positiva significa que MAX tem mais material.

Os valores tradicionais do xadrez são peão 1, cavalo 3, bispo 3, torre 5 e dama 9. O rei não recebe um valor material de captura. Suponha que MAX seja as brancas. As brancas têm uma dama, duas torres, um bispo e seis peões:

As pretas têm duas torres, dois cavalos, um bispo e sete peões:

A característica material é, portanto, $28-26=2$. Se as brancas têm 30 jogadas permitidas e as pretas 24, a diferença de mobilidade é 6. Com peso material 1 e peso de mobilidade 0,1:

Esse 2,6 é uma pontuação de características, não uma probabilidade de vitória de 260%. Os pesos definem sua escala.

Considere características que interagem

Uma soma linear simples dá a cada característica uma contribuição fixa independente das demais. O valor real do jogo pode depender de combinações: um par de bispos pode valer mais que a soma de seus efeitos separados, e a importância de um peão pode mudar em um final de jogo. Características combinadas, pesos dependentes da fase ou avaliadores não lineares podem captar esses efeitos. Os pesos podem ser escolhidos por julgamento ou ajustados aos resultados de partidas registradas.

Mais características também custam tempo. Um avaliador elaborado que impede uma meia-jogada adicional útil de busca pode prejudicar a decisão, mesmo que suas estimativas individuais melhorem.

Ajuste a escala à regra de propagação

No minimax determinístico, transformações estritamente crescentes aplicadas de forma consistente preservam a ordem por meio de máximos e mínimos. Elevar apenas pontuações positivas ao quadrado, por exemplo, mantém sua ordem. Elevar ao quadrado pontuações arbitrárias com sinais positivos e negativos não mantém. Em nós de acaso, as distâncias reais entre utilidades importam porque os valores são calculados pela média. Uma pontuação projetada apenas para ordenar posições precisa de calibração antes de poder representar a utilidade esperada.

O minimax heurístico para antes do fim do jogo. Sua resposta é ótima para a árvore pesquisada com as pontuações atribuídas à fronteira. Ainda assim, ele pode escolher uma jogada que leva à derrota no jogo real quando essas estimativas não captam o que acontece em seguida.

Diferencie estados terminais de cortes

Um estado terminal tem um resultado conhecido. Um corte de profundidade deixa a partida inacabada e precisa de uma estimativa. Faça os testes nessa ordem:

H-MINIMAX(s, d):
    if Is-Terminal(s): return Utility(s, MAX)
    if Is-Cutoff(s, d): return Eval(s)
    if To-Move(s) == MAX:
        return max over a of H-MINIMAX(Result(s, a), d + 1)
    return min over a of H-MINIMAX(Result(s, a), d + 1)

O teste de corte geralmente verifica se a profundidade atingiu um limite. A poda alfa-beta pode podar essa mesma árvore heurística. Sua poda continua exata em relação a esses valores da fronteira; ela não transforma estimativas em resultados reais do jogo.

Sob um limite de tempo, o aprofundamento iterativo mantém a ação da iteração mais profunda concluída. Uma raiz parcialmente pesquisada em uma iteração mais profunda pode favorecer o primeiro ramo simplesmente porque seus concorrentes ainda não foram avaliados.

Conclua uma troca tática

Uma posição quiescente é suficientemente estável para que uma curta continuação forçada provavelmente não altere muito sua avaliação. A busca de quiescência continua além da profundidade normal em posições instáveis, geralmente seguindo capturas até que a troca se encerre.

Suponha que a dama branca capture um peão exatamente no limite de profundidade. A pontuação material melhora em 1. Mas as pretas podem recapturar essa dama na meia-jogada seguinte. A mudança material líquida é:

Parar após a primeira captura indica +1; uma breve extensão de capturas revela −8. O problema é avaliar no meio de uma troca, não uma falha da regra de propagação do minimax.

Reconheça perdas adiadas

O efeito horizonte ocorre quando um programa adia uma perda inevitável até que ela fique além da profundidade de busca. Um bispo preso ainda pode ser perdido após vários xeques com peões. Se a busca enxerga os xeques, mas para antes da captura do bispo, ela pode sacrificar peões para esconder essa perda futura.

Uma extensão singular busca mais profundamente ao longo de uma jogada claramente superior às alternativas. Os programas também estendem xeques forçados ou recapturas. As extensões gastam profundidade adicional em sequências selecionadas; elas precisam de um limite de recursos para que a busca ainda possa terminar.

A poda antecipada, como manter apenas algumas das melhores jogadas, pode descartar a jogada vencedora. Sua economia não traz a garantia da poda alfa-beta.

Substitua a busca por conhecimento exato armazenado

Um livro de aberturas fornece jogadas iniciais estudadas. Bases de dados de finais trabalham de trás para frente a partir de resultados conhecidos por meio de análise retrógrada. Bases de xadrez de sete peças incluem os dois reis e fornecem resultados exatos para os finais abrangidos. As regras e as informações de estado usadas na consulta devem corresponder ao jogo em andamento.

Um nó de acaso representa um evento aleatório. Seus ramos apresentam resultados possíveis e suas probabilidades, que somam 1. Nenhum jogador escolhe o ramo mais favorável para si.

Use a regra correspondente a cada nó

Para resultados $r$, um nó de acaso tem valor:

O expectiminimax combina as quatro regras. O expectimax usa MAX e acaso quando não há jogador minimizador. Um modelo de probabilidade de um oponente aleatório pode fornecer ramos de acaso mesmo em um jogo cujas regras de jogada são determinísticas.

Trabalhe de trás para frente com acaso e oposição

MAX escolhe L ou R. Cada jogada leva a um evento aleatório, seguido de uma escolha de MIN.

Após L, uma moeda justa leva a dois nós MIN. Suas folhas são (3, 7) e (8, 4). MIN retorna 3 e 4. O nó de acaso fornece então:

Após R, as probabilidades 0,25 e 0,75 levam a nós MIN com folhas (10, 1) e (6, 5). Seus valores são 1 e 5, portanto:

MAX escolhe R porque 4 é maior que 3,5. Calcular primeiro a média das folhas terminais diretamente faria o acaso substituir a decisão de MIN. Processe cada nó depois que seus filhos tiverem sido resolvidos.

Atribua as probabilidades corretas

Dois dados justos têm 36 resultados ordenados igualmente prováveis. O gamão agrupa ordens invertidas, como 3–5 e 5–3, em um mesmo lançamento. Isso fornece 21 lançamentos distintos: seis duplas com probabilidade 1/36 cada e 15 lançamentos sem dupla com probabilidade 1/18 cada. A verificação é:

Atribuir probabilidade 1/21 a cada um dos 21 lançamentos superestimaria as duplas e subestimaria os lançamentos sem dupla. Ramos que parecem equivalentes não precisam ter probabilidades iguais.

Se cada etapa de decisão tem $b$ jogadas permitidas e um evento de acaso com $n$ resultados, pesquisar $m$ dessas etapas custa cerca de $O(b^m{n}^m)$. A convenção de profundidade deve incluir a frequência do acaso. Com cerca de 20 jogadas permitidas e 21 lançamentos, os ramos adicionais de acaso do gamão limitam rapidamente a busca exaustiva à frente.

Por exemplo, duas etapas contendo cada uma 21 resultados de acaso e 20 ações produzem $(21\times 20{)}^2=176.400$ caminhos. Conte os eventos de acaso separadamente das meias-jogadas dos jogadores ao estimar esse custo.

Pode apenas quando os resultados não vistos tiverem limites

Uma média parcial não é um limite minimax. Se as utilidades estiverem entre 0 e 10 e o primeiro de dois resultados igualmente prováveis valer 2, o nó inteiro estará entre 1 e 6. Em particular:

Se MAX já tiver outra jogada de valor 7, esse nó de acaso não poderá superá-la e o resultado restante poderá ser ignorado. Sem um limite adequado para os valores não vistos, um resultado extremo ainda poderia alterar a média o suficiente para inverter a escolha.

O minimax pergunta qual resultado um oponente pode garantir. O expectimax pergunta qual utilidade média resulta de um modelo de probabilidade. Suas decisões podem diferir mesmo na mesma árvore porque representam comportamentos diferentes.

Compare oposição ótima e aleatória

Para os ramos MIN A = (4, 9, 6), B = (2, 15, 13) e C = (5, 8, 10), o minimax escolhe C com uma garantia de 5. Se o oponente escolher cada resposta uniformemente, os valores esperados serão cerca de 6,33, 10 e 7,67. O expectimax escolhe B.

Isso é sensato sob o modelo uniforme, mas um adversário habilidoso pode responder a B com 2. O expectimax não pressupõe que o oponente minimize uma média. Ele usa as probabilidades especificadas. Com um modelo correto, maximiza a utilidade esperada; a proteção no pior caso é mais fraca que a do minimax. Ele pode empatar com o desempenho médio do minimax quando ambos recomendam a mesma jogada.

Uma árvore pode misturar modelos. O nó de um agente hostil toma um mínimo, enquanto o nó de um agente aleatório toma uma média ponderada. Use a regra do agente que age naquele nó, não uma única regra para todas as camadas que não sejam MAX.

Veja por que a ordem, por si só, é insuficiente

Suponha que a jogada A dê 2 com probabilidade 0,6 e 3 com probabilidade 0,4. A jogada B dá 1 com probabilidade 0,6 e 4 com probabilidade 0,4:

A tem o maior valor esperado. Agora eleve cada valor terminal ao cubo. Sua classificação permanece a mesma, mas os valores esperados passam a ser:

B agora vence a comparação. Calcular a média dos resultados transformados é diferente de transformar sua média. Elevar ao cubo amplifica o benefício do resultado alto de B o suficiente para mudar a decisão.

Preserve decisões com as transformações corretas

Uma transformação afim com coeficiente angular positivo multiplica todo valor esperado pelo mesmo número positivo e soma a mesma constante. Aplicar $10x+5$ dá a A o valor 29 e a B o valor 27, mantendo a preferência por A.

Se A e B fossem nós MIN, seus valores seriam 2 e 1 antes de elevar ao cubo e 8 e 1 depois. Sua ordem permaneceria inalterada. Máximos e mínimos selecionam um valor de filho; médias combinam as magnitudes de vários valores.

Um avaliador usado com acaso deve, portanto, estimar a utilidade esperada pretendida em uma escala consistente, como a probabilidade de vitória ou uma transformação afim com coeficiente angular positivo dessa probabilidade. Uma pontuação de ordenação não linear pode ser adequada ao minimax determinístico e, ao mesmo tempo, produzir escolhas inadequadas diante do risco quando há acaso.

A busca em árvore de Monte Carlo, ou MCTS, estima jogadas a partir de partidas simuladas enquanto constrói uma árvore que orienta simulações futuras. Uma continuação simulada até o fim é uma simulação de partida ou simulação de continuação. Sua política pode selecionar jogadas permitidas aleatórias ou usar conhecimento de baixo custo para produzir um jogo mais sensato.

Armazene evidências em cada nó

Mantenha uma contagem de visitas $N(n)$ e uma recompensa acumulada $U(n)$. Em um jogo de vitória e derrota com dois jogadores, use as vitórias do jogador que fez a jogada que levou ao nó $n$. Um empate geralmente acrescenta meia vitória. Então $U(n)\mathrm{/}N(n)$ estima a taxa de sucesso desse jogador.

A raiz não tem uma jogada de entrada. Suas visitas ainda contam todas as iterações; as vitórias da raiz podem ser acompanhadas do ponto de vista do jogador da raiz, se necessário. As pontuações dos filhos, que orientam a seleção, devem usar de forma consistente o ponto de vista de quem fez a jogada de entrada.

Repita as quatro fases

1. Seleção: A partir da raiz, siga uma política de seleção pelos filhos existentes até chegar a um nó terminal ou a um nó com uma jogada não testada.
2. Expansão: Se o nó não for terminal, acrescente um filho para uma jogada permitida não testada.
3. Simulação: Execute uma simulação de partida a partir desse filho até um resultado terminal.
4. Retropropagação de resultados: Atualize visitas e recompensas dos nós no caminho selecionado.

Se a seleção chegar a um nó terminal, pule a expansão e a simulação. Seu resultado conhecido pode ser propagado imediatamente. A continuação temporária de uma simulação de partida não precisa ser armazenada como novos nós da árvore: a expansão comum acrescenta um filho por iteração.

Acompanhe uma atualização de recompensa

As brancas agem na raiz. A seleção e a expansão seguem:

• n1, alcançado pela jogada das brancas;
• n2, alcançado pela jogada das pretas;
• n3, alcançado pela jogada das brancas.

A simulação termina com vitória das pretas. Aumente as visitas em um na raiz e em n1, n2 e n3. Entre esses três nós filhos, aumente as vitórias apenas em n2, pois quem fez a jogada de entrada em n2 foram as pretas. Os nós filhos das brancas não recebem acréscimo de vitória. Sob uma convenção do jogador da raiz, o total de vitórias da própria raiz também permanece inalterado.

Um empate acrescentaria 0,5 à recompensa de cada filho. Contar a vitória das pretas como sucesso em todos os nós faria as brancas selecionarem jogadas que ajudam as pretas.

Deixe a árvore crescer de modo desigual

Iterações repetidas concentram simulações em ramos promissores ou incertos. Jogadas que parecem fortes tendem a adquirir subárvores maiores, enquanto jogadas ruins recebem menos trabalho. A busca não impõe uma profundidade fixa a todas as sequências. Assim que houver uma jogada permitida disponível, ela poderá parar em um limite de tempo e usar suas estatísticas acumuladas.

A ação final geralmente é o filho da raiz com mais visitas. Uma jogada com duas vitórias em duas simulações tem uma taxa observada perfeita, mas poucas evidências. Uma jogada muito visitada reflete uma análise muito maior pela busca.

A busca pura de Monte Carlo atribui simulações de partida independentes às jogadas da raiz sem expandir uma árvore de decisão. Ela pode deixar passar repetidamente uma resposta forte do oponente porque as jogadas posteriores continuam sendo regidas pela política de simulação. A MCTS aprende onde ramificar mais profundamente à medida que acumula evidências, embora uma refutação tática rara ainda possa levar tempo para ser descoberta.

A MCTS precisa decidir onde outra simulação será mais útil. A explotação revisita jogadas que já parecem fortes. A exploração investiga jogadas com menos evidências que podem se mostrar melhores. Buscar sempre a maior taxa de vitórias observada pode prender a busca a um resultado inicial obtido por sorte.

Calcule uma pontuação UCB1

A pontuação de limite superior de confiança para o filho $n$ é:

O primeiro termo é a taxa de vitórias observada. O segundo é um bônus de exploração. Ele cresce à medida que o pai acumula visitas e diminui à medida que o filho recebe mais visitas. O logaritmo é natural. Durante a seleção, escolha o filho com a maior pontuação combinada.

Trate um filho não visitado como tendo prioridade infinita em vez de dividir por zero. Toda jogada permitida em um nó é testada antes que a seleção passe a favorecer repetidamente alternativas visitadas. A MCTS que usa essa regra de seleção é chamada de UCT, busca em árvore com limites superiores de confiança.

Compare três filhos

Um nó pai tem 50 visitas. Seus filhos têm contagens de vitórias/visitas de 21/30, 7/12 e 3/8. Com $C=\sqrt{2}$ e $\ln 50\approx \mathrm{3,912}$:

O segundo filho é selecionado. Sua taxa de vitórias atual é menor que a do primeiro filho, mas seu bônus de incerteza é maior. O terceiro é ainda menos visitado, mas sua taxa de vitórias menor deixa seu total ligeiramente abaixo do segundo.

Com $C=\mathrm{0,5}$, os mesmos totais passam a ser cerca de 0,881, 0,869 e 0,725. A seleção agora favorece o primeiro filho. Nenhum resultado mudou; o programa mudou o quanto recompensa a incerteza.

Interprete a constante de exploração

Um $C$ positivo maior dá mais peso à exploração. Defini-lo como zero remove o bônus e escolhe apenas pela média observada. A formulação do problema do bandido com recompensas entre 0 e 1 motiva $C=\sqrt{2}$ nessa forma da equação; programas de jogos práticos ajustam a constante. Mudar a escala da recompensa também altera o equilíbrio com o termo de exploração.

Em cada nó pai, seus filhos registram vitórias para o jogador que escolhe ali. Isso torna sensato maximizar UCB1 nos turnos de ambos os jogadores. Armazenar apenas vitórias das brancas em toda a árvore enquanto se maximiza cada pontuação faria as pretas favorecerem o sucesso das brancas.

Separe prioridade de busca de qualidade da jogada

UCB1 escolhe onde gastar a próxima simulação. Um grande bônus de incerteza pode fazer valer a pena investigar uma jogada pouco amostrada. Ao fim da busca, escolha o filho da raiz mais visitado, não aquele com a maior pontuação UCB1 atual. Nas condições de jogo finito da UCT e com exploração contínua, uma busca ilimitada converge para o comportamento minimax; um limite finito de recursos ainda deixa incerteza amostral.

Um método de busca deve ser adequado ao tamanho do espaço de jogadas, à qualidade da avaliação disponível e ao tipo de incerteza no jogo. O mesmo limite de tempo pode produzir decisões muito diferentes dependendo do que o método investiga.

Compare cobertura tática e simulação

A poda alfa-beta pode encontrar uma única refutação tática dentro de sua profundidade de busca. A MCTS pode inicialmente preferir uma jogada que vence a maioria das simulações aleatórias, mas perde diante de uma resposta precisa. À medida que sua árvore cresce, ela pode descobrir essa resposta, mas um limite pequeno de simulações pode deixá-la passar. Uma alta taxa de vitórias nas simulações, portanto, não é uma garantia para o pior caso.

Relacione métodos a programas marcantes

Em 1997, o Deep Blue da IBM usou busca alfa-beta, hardware especializado e avaliação de xadrez para derrotar o campeão mundial Garry Kasparov por 3½ a 2½ em seis partidas. Seu sucesso mostrou o quanto uma busca forte e uma avaliação específica do jogo podiam alcançar juntas.

O Go tornou essa combinação mais difícil. Um tabuleiro vazio de 19 por 19 oferece 361 posições para colocar uma pedra, e avaliar uma posição por características simples é difícil. A MCTS se tornou uma abordagem forte porque podia estimar resultados por meio de partidas e expandir uma árvore seletiva sem exigir um avaliador estático escrito à mão.

O AlphaGo combinou MCTS com redes neurais que sugerem jogadas e avaliam posições. Sua descrição na Nature em 2016 precedeu sua vitória por 4 a 1 sobre Lee Sedol em março de 2016. Mais tarde, o AlphaZero usou avaliação por rede neural no lugar de simulações aleatórias e alcançou um nível superior ao humano no xadrez, no shogi e no Go. Esses programas mostram que uma estrutura de busca pode usar diferentes fontes de valores para as posições.

Diferencie jogar bem de resolver um jogo

Um programa pode vencer um campeão sem provar o valor da posição inicial. Em 2007, a equipe de Jonathan Schaeffer usou busca e grandes bases de dados de finais para estabelecer que o jogo de damas é um empate com jogo perfeito. Resolver o jogo estabelece um resultado contra toda estratégia adversária possível, não apenas contra os oponentes testados em confrontos.

Ajuste o método ao modelo

Em um jogo estocástico, amostre resultados aleatórios segundo suas probabilidades reais durante o percurso da árvore e as simulações de partida. Um evento com probabilidade 0,8 deve ocorrer cerca de quatro vezes mais frequentemente que um com probabilidade 0,2 ao longo de muitas amostras. Isso estima o mesmo valor esperado ponderado que a propagação explícita de acaso calcula.

Toda abordagem ainda depende de regras e transições de estado corretas. A poda alfa-beta com profundidade limitada depende de seu avaliador; a MCTS depende de sua política de simulação ou avaliação e de seu limite finito de amostras. Modelar um oponente hostil como aleatório pode custar caro, qualquer que seja o mecanismo de busca usado para calcular a resposta desse modelo.