Quando você joga contra o computador, ele não “pensa” como uma pessoa. Ele faz uma coisa muito mais simples e muito mais rápida: imagina jogadas, imagina as respostas a elas, e assim por diante, até onde o tempo permitir — e depois dá uma nota a cada posição imaginada para escolher a melhor. Quase todo adversário de jogo de tabuleiro é uma variação dessa ideia. Este texto explica como ela funciona e por que os jogos com informação escondida, como a Batalha Naval e o Dominó, precisam de um método diferente.
Jogos de informação perfeita: a árvore de jogadas
No Xadrez, nas Damas, no Reversi e no Shogi, os dois lados veem tudo: não há carta virada nem navio escondido. Nesse tipo de jogo, dá pra representar o que pode acontecer como uma árvore: a posição atual é a raiz, cada jogada possível é um galho, e cada resposta do adversário é um galho do galho.
O problema é o tamanho. Em média, existem em torno de 10 jogadas possíveis por posição no Reversi, 35 no Xadrez e 80 no Shogi — e é por isso que o Shogi, com a regra de soltar peças capturadas de volta no tabuleiro, é muito mais difícil de calcular do que parece. Olhar 6 jogadas à frente no Xadrez já significa avaliar da ordem de 1,8 bilhão de posições (35 elevado a 6). Ninguém — nem o computador — chega ao fim da árvore. Por isso ele olha só até uma certa profundidade e avalia o que encontra.
Minimax: assumir que o adversário joga bem
O algoritmo clássico se chama minimax. A ideia é simples: quando é a vez do computador, ele escolhe o galho de maior nota (é o “max”); quando é a vez do adversário — você —, assume-se que escolherá o galho que dá a menor nota ao computador (é o “min”). A nota que sobe até a raiz é o valor da melhor jogada supondo que os dois joguem o melhor possível dentro da profundidade analisada.
E de onde vem a nota? De uma função de avaliação, escrita à mão para cada jogo. No Xadrez ela conta material (uma dama vale mais que um peão) e posição (peças centralizadas, rei protegido). No Reversi, o que mais pesa costuma ser ocupar os cantos — que nunca podem ser virados — e ter mais opções de jogada que o adversário. A qualidade dessa função é, em boa parte, o que separa um computador esperto de um ingênuo.
Poda alfa-beta: não olhar o que não muda nada
Minimax puro olha galhos que jamais afetariam a decisão. A poda alfa-beta evita isso: se, ao examinar uma jogada, o computador já vê que o adversário teria uma resposta tão boa que ele nunca escolheria esse caminho, ele abandona o galho inteiro sem olhar o resto. O resultado final é exatamente o mesmo do minimax, só que muito mais barato — no melhor caso, dá pra olhar o dobro da profundidade com o mesmo esforço. É o método usado, por exemplo, no Reversi do TabulePlay.
Aprofundamento iterativo: pensar por tempo, não por profundidade
Fixar a profundidade (por exemplo, “olhe sempre 5 jogadas à frente”) tem um defeito: em posições calmas ele desperdiça tempo, e em posições cheias de opções ele pode demorar demais. Os programas de Xadrez e Shogi resolvem isso com o aprofundamento iterativo: primeiro pesquisam 1 jogada à frente, depois 2, depois 3… até esgotar um orçamento de tempo. A cada rodada eles guardam a melhor jogada encontrada, então quando o relógio acaba sempre há uma resposta boa na mão — e ela é a mais profunda que deu tempo de calcular. É essa a abordagem dos adversários do Xadrez e do Shogi no TabulePlay, enquanto o das Damas usa uma profundidade fixa.
Quando o computador “é o melhor”: jogos resolvidos
Existem jogos em que a árvore inteira já foi percorrida. O jogo da velha é o exemplo mais simples: com jogo perfeito dos dois lados, dá sempre empate. As damas americanas (8×8, sem captura para trás) foram “resolvidas” em 2007, depois de quase duas décadas de cálculo do programa Chinook: também empatam com jogo perfeito. O Xadrez, por outro lado, é grande demais para isso — e o computador vence os melhores humanos desde 1997 (quando o Deep Blue derrotou Garry Kasparov) não por ter esgotado o jogo, mas por olhar muito fundo e avaliar bem.
Quando há informação escondida
Batalha Naval e Dominó quebram a premissa de tudo isso: o computador não sabe onde estão os seus navios, nem quais pedras estão na sua mão. Não existe “a posição” para montar uma árvore — existem muitas posições possíveis, e o que ele sabe é só uma parte delas. Aqui, o adversário precisa raciocinar sobre o que é provável, não sobre o que é certo.
Batalha Naval: mapa de probabilidade
O nível difícil do computador na Batalha Naval faz o seguinte a cada tiro: para cada casa do tabuleiro, conta de quantos jeitos os navios que ainda faltam afundar poderiam cobri-la, dadas as águas e os acertos já conhecidos (casas com acertos pesam muito mais, porque indicam onde há um navio). Depois atira na casa com maior contagem. Esse mapa de densidade faz o computador “perseguir” um navio atingido sem que ninguém precise programar a perseguição em separado — ela sai naturalmente da conta. O nível médio usa um atalho clássico: atira em casas alternadas, como um tabuleiro de xadrez (já que o menor navio ocupa 2 casas, nenhum escapa), e, ao acertar, explora as casas vizinhas. O fácil atira ao acaso.
Dominó: heurística sobre a própria mão
No Dominó, o computador só enxerga a própria mão, a mesa e quantas pedras restam no monte. Não dá para buscar em árvore; o que ele faz é dar uma nota a cada jogada legal. No nível médio, prefere descartar o número que mais se repete na própria mão (assim fica menos “preso” depois) e dá uma leve preferência às duplas, que são mais difíceis de encaixar quando guardadas. No difícil, evita ainda abrir uma ponta num número que a própria mão não tem como defender depois. No fácil, joga qualquer pedra válida.
Por que o computador não joga sempre o melhor lance
Um adversário perfeito seria chato: você perderia todas as vezes, sem entender por quê. Por isso os níveis de dificuldade existem. Diminuir a força do computador pode significar olhar menos jogadas à frente, usar uma função de avaliação mais simples, ou escolher, de vez em quando, uma jogada que não é a melhor. O objetivo não é que o computador ganhe — é que a partida seja um bom desafio para o seu nível.
O computador trapaceia?
Nos jogos daqui, não. Nos de informação perfeita, ele vê o mesmo tabuleiro que você. Nos de informação escondida, ele decide só com o que também poderia saber: a Batalha Naval usa apenas os tiros que ele mesmo deu, e o Dominó usa a própria mão, a mesa e a contagem do monte. A vantagem dele é memória e cálculo — nunca espiar.
Como testamos
Antes de qualquer tela existir, a lógica de cada jogo pode ser testada sozinha: no Dominó, por exemplo, simulamos milhares de rodadas completas, com o computador jogando contra si mesmo em todos os níveis, conferindo a cada jogada que nenhuma pedra some ou se duplica, que todo encaixe é válido e que toda rodada termina. É um teste chato de escrever e essencial: um erro de regra que só aparece uma vez em mil partidas é o tipo de erro que estraga a experiência de quem cai justo nela.
Se quiser ver algumas dessas ideias em ação, jogue uma partida contra o computador em cada nível: a diferença de comportamento é fácil de sentir.