A REGRA DO GO QUE MUDA A RESPOSTA

Resolver um jogo significa conhecer seu resultado quando os dois lados jogam perfeitamente. Num tabuleiro de go, esse resultado é um valor: o número de pontos pelo qual as pretas vencem com jogo perfeito — 28 num tabuleiro 4×7 significa que as pretas possuem todas as 28 interseções. As damas foram resolvidas em 2007, assim como o Hex em tabuleiros pequenos. Para o go, existem provas por computador para muitos tabuleiros de até 30 interseções, a maioria de um programa chamado MIGOS (2003 e 2009).

Há um porém. Esses resultados clássicos usam uma regra simplificada para posições repetidas — uma regra de “ko” básica — um jogador não pode recapturar imediatamente uma pedra isolada que acabou de capturar uma das suas, o que faria os mesmos dois lances se repetirem para sempre — mais convenções especiais: um passe suspende uma proibição de ko, uma partida para numa posição repetida, e assim por diante. Essas convenções foram pensadas para que o valor de uma posição não dependesse de como ela foi alcançada.

A regra que as pessoas realmente jogam

As regras chinesas, como estão escritas, e o go por computador usam o superko posicional: nenhum lance pode recriar qualquer posição do tabuleiro inteiro que já tenha ocorrido na partida. Resolver sob essa regra é muito mais difícil, porque a legalidade de um lance passa a depender de toda a história da partida. Isso quebra três ferramentas que tornam a resolução viável:

• reaproveitar resultados da mesma posição alcançada por outro caminho — os dois caminhos podem proibir lances diferentes;
• reconhecer grupos e territórios seguros sem busca, o que supõe que o dono sempre pode capturar invasores — sob superko, essa captura pode ser proibida;
• podar lances que nunca ajudam, como preencher o próprio olho — uma das interseções vazias de que um grupo precisa para continuar vivo — sob o superko, um lance desses pode se tornar decisivo.

O custo era enorme: com uma variante do superko, o MIGOS precisou de 1,1 hora para o tabuleiro 4×4, contra 3,3 segundos sob o ko básico. A primeira solução do 5×5 sob superko, em 2024, levou 5,25 horas em seis processos. Além do 5×5, nenhum tabuleiro com pelo menos duas fileiras tinha sido resolvido sob superko.

Um atalho que continua correto

Sami Kharma e Florian Schintke, do Zuse Institute Berlin, criaram o Sanko. Seu núcleo é um simples teorema de transferência de prova (proof-transfer theorem): uma prova armazenada de que um jogador vence continua válida num novo caminho, a menos que uma posição que o vencedor precisa criar já tenha aparecido. Só as posições do vencedor importam — se o perdedor não puder mais recriar uma posição, ele só perde uma opção. Verificar isso leva um tempo proporcional ao comprimento do caminho, não ao tamanho da prova. No tabuleiro 3×7, esse atalho sozinho reduz o trabalho de 664 bilhões de passos para 112 milhões.

Eles também adaptaram o reconhecimento clássico de grupos seguros para que continue correto sob superko, e só podaram os lances do lado cuja vitória tentavam provar, de modo que uma busca que falha é relatada como desconhecida, nunca como vitória do outro lado.

Novos valores

• 5×5 em 15,7 minutos com seis threads — cerca de 20 vezes mais rápido que antes, em parte graças a um hardware melhor; com uma única thread, o 4×4 é resolvido 58 vezes mais rápido. Numa máquina de 192 threads, o 5×5 leva cerca de um minuto e meio.
• Os primeiros valores sob superko de mais 23 tabuleiros; 11 deles nunca tinham sido resolvidos sob nenhuma regra. O 3×10 vale 8 pontos para as pretas — o MIGOS só tinha provado pelo menos 6, e dois meses de busca não tinham encontrado um limite superior.
• Em tabuleiros de uma fileira, os valores de 1×9 a 1×15 se repetem em 0, 1, 2, 2 — mas o 1×16 quebra o padrão, valendo 1 em vez de 2.

A surpresa do 4×7

Pelas regras antigas, o 4×7 é uma vitória de tabuleiro inteiro: as pretas capturam tudo, 28–0. Sob superko, ele vale 12. Os autores reproduziram a linha ótima de 31 lances publicada para o MIGOS: todos os lances são legais, e as pretas ainda tomam o tabuleiro inteiro. Resolvendo a linha de trás para frente, encontraram a quebra logo depois do lance 25: na posição após o lance 25, jogado pelas pretas, as brancas deveriam jogar G2 (ou C1) em vez de A2.

O que vem depois é um ko estranho. As brancas capturam; a recaptura das pretas recriaria uma posição anterior — proibido. Qualquer outro lance das pretas põe o próprio grupo em perigo. As pretas têm de passar, as brancas passam, e a partida termina com o grupo branco vivo: o que os autores do MIGOS já tinham chamado de “vida ao luar” (moonshine life). Pelas regras antigas, o passe suspenderia a proibição, e as pretas recapturariam e ganhariam tudo. Sob superko, o melhor que as pretas conseguem nessa linha é uma vida compartilhada (seki) que vale só 3 pontos; por isso, o jogo perfeito abandona a linha publicada mais cedo — e o melhor que as pretas conseguem garantir a partir do tabuleiro vazio é 12.

Nenhuma das buscas estava errada. A diferença vem de regras que só importam bem no final de uma partida. O conselho dos autores: valores calculados sob convenções que tornam a repetição inofensiva não devem ser citados como valores do go com superko sem verificação.

Verificável por qualquer pessoa

Cada valor se apoia em duas provas independentes, e o solucionador passou por dezenas de milhares de verificações cruzadas sem nenhuma divergência. Diferentemente de soluções anteriores de tabuleiros de go vazios, o código-fonte do solucionador e o comando exato por trás de cada resultado são públicos; a cadeia de provas do 4×7 se reproduz em menos de vinte segundos. As provas ainda não são certificados que alguém de fora possa verificar de forma independente, e o 6×6 continua fora de alcance — pela extrapolação dos autores, cerca de 50 dias numa de suas máquinas, ou mais.