Em maio de 2016, o matemático australiano Mark Watkins publicou um resultado pelo qual a comunidade de variantes do xadrez trabalhava havia quinze anos: o antixadrez a partir da posição inicial padrão é uma vitória forçada das brancas com a jogada 1.e3. A prova foi computacional. Exigiu uma árvore de posições de jogo grande o bastante para ocupar vários terabytes de armazenamento comprimido e um esforço de verificação distribuído pela comunidade do Lichess ao longo de vários anos. É o maior jogo completamente resolvido até hoje por qualquer grupo.

O antixadrez — também chamado xadrez da perda ou giveaway chess — é uma variante em que o objetivo é invertido: você ganha perdendo todas as suas peças ou ficando afogado, e as capturas são obrigatórias sempre que disponíveis. A regra de captura obrigatória reduz drasticamente o fator de ramificação do jogo; muitas posições admitem apenas uma ou duas jogadas legais; o jogo é muito menor em termos de espaço de estados que o xadrez padrão. Ainda assim, a prova de que 1.e3 ganha levou quinze anos de trabalho acumulado e foi saudada por teóricos de jogos por computador como uma conquista de referência. A versão completa do artigo sobre antixadrez no Caissly cobre as regras e a prova com mais profundidade.

A pergunta natural seguinte — pode o xadrez padrão ser resolvido? — é o tema deste texto. A resposta curta é não, não em qualquer prazo relevante para humanos. A resposta longa é mais interessante, porque revela o que resolver um jogo realmente significa e onde estão hoje os limites do que é viável.

O que significa “resolvido”

Na teoria combinatória dos jogos, um jogo está fortemente resolvido quando, para cada posição alcançável, conhecem-se seu valor de teoria dos jogos (vitória, empate, derrota) e uma jogada ótima. Fracamente resolvido significa que o valor a partir da posição inicial padrão é conhecido, com um algoritmo para jogar otimamente dali. Ultrafracamente resolvido significa que o valor é conhecido mas as jogadas ótimas não.

O antixadrez está fracamente resolvido. Sabemos que 1.e3 ganha para as brancas; sabemos jogar otimamente desde o início; ainda não temos uma tablebase cobrindo cada posição alcançável do jogo. A solução forte é em princípio possível para o antixadrez, mas não foi completada.

O xadrez padrão não está em nenhuma dessas categorias. Não conhecemos o valor da posição inicial. A crença consensual — baseada em análise de motores em profundidades muito além das humanas — é que a posição inicial é empate com o melhor jogo. Não temos prova. Não resolvemos uma única das dez primeiras jogadas até um valor terminal. Resolvemos toda posição com sete peças ou menos (a tablebase Lomonosov de sete peças), mas sete peças ainda estão muito distantes de trinta e duas.

Por que o xadrez é mais difícil

A diferença combinatória entre antixadrez e xadrez padrão não é uma questão de grau. O antixadrez tem cerca de 1040 posições distintas. O xadrez padrão tem cerca de 1044 a 1047 posições legais e 10120 partidas distintas (o número de Shannon, a estimativa padrão de ordem de grandeza). A regra de captura obrigatória no antixadrez colapsa árvores de jogadas que, no xadrez padrão, se ramificariam amplamente e permaneceriam ramificadas por uma centena de meios. Uma partida típica de antixadrez dura vinte a trinta jogadas; uma típica de xadrez padrão dura quarenta a sessenta.

Essa é a assimetria central. Resolver um jogo por computação força-bruta exige tocar em cada posição que o algoritmo não consegue descartar por simetria ou transposição. Para o xadrez, o limite inferior do número de posições relevantes está em torno de 1040 após poda agressiva, e o superior é muito maior. Nenhum substrato computacional disponível ou projetado tem o armazenamento ou o orçamento de operações por segundo para enumerar esse espaço em qualquer prazo humanamente relevante.

A questão nem se aproxima do limiar do possível. Até a computação quântica, que dá ganho de velocidade em certos problemas de busca, não muda o problema fundamental de ordem de grandeza para o xadrez. O número de posições legais é maior que o número de átomos no universo observável por várias ordens de grandeza.

Tablebases de finais como solução parcial

O que conseguimos resolver é o final. As tablebases Syzygy e Lomonosov de sete peças cobrem cada posição no tabuleiro com sete ou menos peças totais (incluindo os reis). A de seis peças Syzygy cabe em cerca de 150 GB; a de sete peças, em cerca de 17 TB. Cada posição nessas regiões tem seu valor de teoria dos jogos calculado e sua jogada ótima identificada.

Isso é genuinamente útil. O estudo de finais no mais alto nível consulta as tablebases rotineiramente. Estudos famosos — as posições de Lucena e Philidor, a técnica de empate de Vancura, a oposição R+P vs R — são todos confirmados por análise de tablebase há mais de uma década. As tablebases também produziram novos resultados: certos finais de sete peças que grandes mestres haviam julgado empatados por um século são na verdade ganhos com jogo profundo envolvendo sequências de cinquenta ou mais jogadas que humanos não conseguem razoavelmente encontrar.

A próxima fronteira é a de oito peças. O armazenamento comprimido para uma tablebase de oito peças é estimado em cerca de dois petabytes, viável mas caro. Uma tablebase de nove peças, pelas projeções atuais, está fora do alcance de qualquer projeto único plausível mas não do mercado global de armazenamento em nuvem. A fronteira das dez peças é genuinamente especulativa.

Essas tablebases resolvem finais. Não escalam, nem em princípio, para resolver o jogo inteiro. O fator de ramificação e a contagem de posições do meio-jogo são altos demais para qualquer enumeração no estilo tablebase.

O que um jogo não resolvido nos deixa

A consequência interessante é que o xadrez permanecerá não resolvido em futuro previsível e, ainda assim, continuará sendo jogado em um nível que motores chamam de quase-ótimo. Isso é incomum. A maioria dos jogos finitos bem estudados tem uma lacuna clara entre o jogo ótimo e o jogo humano — as damas (resolvidas, empate com o melhor jogo) são o maior jogo limpamente resolvido, e a diferença entre a análise da prova e o jogo humano nas damas é enorme. O antixadrez está resolvido, e o jogo humano segue sem se aproximar das linhas ótimas da prova em muitas posições práticas.

O xadrez ruma a um peculiar estado intermediário: o jogo dos motores é tão forte que é tomado como proxy do ótimo, mas não é formalmente provado ótimo. Os principais motores discordam em certas posições. Novas execuções de treinamento do Leela Chess Zero produzem mudanças de avaliação em linhas antes consideradas estáveis. A fronteira do jogo está sendo explorada por redes neurais em vez de enumerada por busca exaustiva.

O que isso significa para o jogador é, sobretudo, libertador. O xadrez é, pela evidência atual, empate no mais alto nível — mas o caminho até esse empate envolve tantos pontos de decisão que jogadores humanos perderão e ganharão partidas enquanto humanos jogarem. O jogo não está apenas não resolvido; é estruturalmente tão maior que os jogadores que o jogam que a questão da resolução não afeta a experiência vivida do jogo.

A questão mais ampla

Às vezes se afirma que qualquer jogo que humanos joguem com seriedade suficiente acabará sendo resolvido. O antixadrez foi resolvido por enumeração computacional. As damas também. O Lig 4 foi resolvido em 1988. O Reversi foi fracamente resolvido em tabuleiro 8×8. O padrão é que jogos de espaço de estados pequeno cedem à computação, jogos de espaço grande não, e o xadrez fica no lado errado dessa linha em qualquer prazo previsível.

O Go, com cerca de 10170 posições distintas, fica ainda mais distante desse lado. AlphaGo e seus sucessores não resolveram o Go; jogaram-no a um nível que humanos não podem igualar, deixando intocada a pergunta formal sobre o jogo ótimo. O mesmo padrão vale para o xadrez e, cada vez mais, para todo jogo que humanos tratam como sério.

A morte da teoria de aberturas e a impossibilidade de resolver o jogo são a mesma observação por dois ângulos. A fronteira do analisável ultrapassou a do jogável. Podemos verificar jogo quase-ótimo nas aberturas que conhecemos. Não podemos, nem em princípio, esgotar o jogo em si. O que resta, para humanos, é jogar.

Referências

Ligações internas no Caissly: Antixadrez cobre a variante resolvida; Atômico e Xadrez 960 cobrem outras variantes modernas. Entradas de técnica de finais: Posição de Lucena, Posição de Philidor, Posição de Vancura.

Edição Nº 004 · A Revista · Editorial Caissly