Xadrez em quatro dimensões: por dentro do Tesseract

As variantes de xadrez costumam acrescentar um truque a um tabuleiro que toda a gente percebe. Nós queríamos o contrário: manter as regras reconhecivelmente xadrez e mudar o espaço — de duas dimensões para quatro. O resultado é o Tesseract, o décimo terceiro jogo do nosso Lab e, com alguma distância, a coisa matematicamente mais exigente que já pusemos num navegador.

Quatro dimensões soa a marketing até se tentar escrever o gerador de lances. Aí passa a ser muito literal: aqui uma torre ataca ao longo de oito raios, não de quatro. Um bispo ataca ao longo de vinte e quatro. Há duas novas peças de deslize porque o espaço 4D tem dois novos tipos de diagonal, e há dois tipos de peão porque um peão precisa de um eixo para a frente e o tabuleiro passou a ter dois de sobra. Cada uma destas afirmações teve de sobreviver a um verificador escrito de forma independente antes de nós próprios acreditarmos nelas.

Um tabuleiro com 625 casas

O tabuleiro é uma rede 5×5×5×5 — 625 casas, coordenadas (x, y, z, w) a variarem de 1 a 5. Internamente, uma casa é um único inteiro: idx = (x−1) + 5(y−1) + 25(z−1) + 125(w−1). O renderizador usa o mesmo empacotamento, por isso um índice de casa atravessa a fronteira entre motor e renderizador sem tradução — não há erros de coordenadas na costura, porque não há costura.

O clássico problema de motor de cair para fora do tabuleiro piora em 4D: cada raio de deslize tem de saber onde está a borda em oitenta direções. Os motores 2D clássicos resolvem isto com uma mailbox — um tabuleiro com margem cujas casas de bordo estão marcadas como inválidas — e acontece que a ideia generaliza lindamente. O Tesseract usa uma mailbox 9⁴: 6561 entradas de 32 bits, cerca de 26 KB, onde o tabuleiro jogável 5⁴ fica a duas casas de distância de todas as bordas — exatamente o alcance de um cavalo. Detetar que se saiu do tabuleiro passa a ser uma única consulta a um vetor. A alternativa, tabelas de raios por casa, teria custado cerca de 350 KB e muito mais falhas de cache.

Oitenta direções de ataque

Em n dimensões, a generalização natural do movimento no xadrez é o conjunto de vetores de direção não nulos com componentes em {−1, 0, 1}. Em 4D isso dá 3⁴ − 1 = 80 direções, que se dividem consoante o número de eixos que mudam ao mesmo tempo: 8 direções mudam um eixo, 24 mudam dois, 32 mudam três e 16 mudam os quatro.

Essas quatro classes são o conjunto de peças. A torre fica com a classe um. O bispo fica com a classe dois — as diagonais familiares, das quais há agora vinte e quatro. A classe três pertence ao unicórnio, peça emprestada do Raumschach, a variante tridimensional de 1907 — desliza pelas diagonais espaciais que não existem num tabuleiro plano. A classe quatro pertence ao dragão, o nome que demos à peça que se move pelas verdadeiras 4-agonais, as direções em que as quatro coordenadas mudam ao mesmo tempo. A dama e o rei tomam as oitenta. O cavalo também generaliza: um salto (2, 1, 0, 0) em qualquer par de eixos e combinação de sinais — 48 saltos distintos.

A intuição falha aqui de formas interessantes, por isso contámos. Somando os lances legais de uma peça em todas as casas de um tabuleiro vazio: a torre chega a 10 000; o bispo a 18 000. Num tabuleiro plano a torre é a peça de deslize mais forte; em quatro dimensões o bispo tem simplesmente mais espaço. O dragão, senhor da classe de direções mais exótica, junta apenas 5664 — as 4-agonais são curtas e poucas a partir da maioria das casas —, e é por isso que o par fica na terceira fila da placa em vez de guardar um canto. Isto não são impressões; são constantes fixas na autoverificação do motor, e a compilação falha se o gerador de lances alguma vez discordar delas.

Uma posição inicial que é um teorema

Desenhar uma posição inicial para um tabuleiro que ninguém nunca jogou é uma armadilha: como se sabe que as brancas não estão mate em quatro, ou que uma muralha de peões não faz do jogo um empate por construção? Optámos por tornar a posição demonstrável em vez de plausível. O exército das pretas é a reflexão pontual exata do das brancas — cada peça passa por σ: p → 6−p nas quatro coordenadas. A simetria pontual garante equilíbrio material e posicional perfeito e tem uma consequência mais discreta de que gostamos ainda mais: nada começa atacado. Se uma peça branca atacasse uma peça preta no lance zero, a simetria faria existir também o ataque inverso, e a posição seria uma confusão tática. Não é, e isso é verificável.

A posição inicial é um teorema, não uma convenção — o seu equilíbrio decorre da simetria pontual, e o motor verifica-o em cada compilação.

As doze peças maiores ficam numa placa 5×5 em y=1, w=1 (o rei ao centro da primeira fila, o par de dragões na terceira), e os peões respondem à pergunta de desenho mais estranha do tabuleiro: qual é o lado da frente? O Tesseract tem peões Y, que avançam pelo eixo y, e peões W, que avançam por w, e ambas as espécies assentam nos dois hiperplanos centrais — a única faixa do tabuleiro onde um peão branco fica exatamente em frente da sua imagem preta espelhada. Saem três tamanhos de exército (ligeiro, normal, denso), alargando a faixa de peões; o normal são 32 peças de cada lado, o mesmo censo do xadrez clássico, o que nos pareceu certo.

Contar todos os lances, duas vezes

Um motor de xadrez só é tão fiável quanto o seu gerador de lances, e um gerador de lances 4D tem modos de falha que nenhum humano deteta à vista — a intuição de ninguém assinala uma cravada de unicórnio em falta ao longo de uma triagonal. Por isso o Tesseract é verificado como se verificam os motores a sério: perft, a contagem exaustiva de nós-folha alcançáveis a uma dada profundidade, calculada duas vezes por dois geradores que não partilham nada.

O gerador rápido é legal, não pseudolegal: calcula uma vez por nó quem dá xeque e quem está cravado, varrendo para fora a partir do rei, e depois só emite os lances que sobrevivem — xeque duplo dá apenas lances de rei, xeque simples dá capturar-ou-interpor, e uma peça cravada só pode viajar ao longo do raio da sua cravada. O gerador ingénuo é deliberadamente burro e lento. Concordaram em 50 618 nós validados cruzadamente, com zero divergências; o perft(3) completo a partir da abertura são 11 661 294 nós. Um laboratório de peões à parte — uma posição construída para exercitar avanços duplos, os dois eixos de captura, o en passant e a promoção — acrescenta mais 559 319 nós concordantes. E como o motor é todo em inteiros, com zero vírgula flutuante na lógica de jogo, um guião fixo de 40 meias-jogadas tem de aterrar no mesmo hash de Zobrist em todos os navegadores e em todas as compilações. O determinismo não é um extra simpático; é o que torna o modo online sequer possível.

Tornar legíveis quatro dimensões

O problema mais difícil nunca foi o motor. Foi o ecrã. Uma posição 4D tem de aterrar num monitor 2D sem mentir sobre a geometria, e o truque habitual — desenhar uma sombra rotativa e bonita de um tesserato — não serve para nada na hora de jogar. A nossa resposta é quase embaraçosamente plana: desenhar a rede 5⁴ como uma grelha 5×5 de tabuleiros 5×5. Os eixos x e y vivem dentro de cada tabuleiro pequeno; z e w escolhem o tabuleiro. A correspondência é worldX = (w−3)·PITCH + (x−3)·CELL, e a propriedade crucial é ser afim nas quatro coordenadas: cada reta 4D — um raio de torre, uma triagonal de unicórnio, uma 4-agonal de dragão — projeta-se numa linha reta de casas realçadas no ecrã. É pela retidão que o olho aprende a geometria.

A câmara é ortográfica de propósito — a perspetiva quebraria essa afinidade e estragaria também a seleção por clique, que aqui é uma inversa em forma fechada da projeção e não um raycast na GPU. O campo inteiro é desenhado como um só quadrilátero texturado (os 25 tabuleiros cozidos numa única textura de tela), dezasseis malhas instanciadas para os exércitos e cinco para os realces: cerca de 24 chamadas de desenho no pior caso, numa tela em frameloop="demand" que desenha exatamente zero fotogramas enquanto pensa. Para os momentos em que quer a forma honesta da coisa, uma segunda vista desenha o verdadeiro tesserato — cubo interior em w=1, exterior em w=5, a girar numa rotação isoclínica — e devolve a lição de geometria aos seus olhos.

Um adversário que cabe num Web Worker

A posição inicial tem 226 lances legais, contra vinte no xadrez clássico, e é esse o fator de ramificação medido com que a pesquisa tem de viver. Uma pesquisa com essa largura tem de ser humilde e tem de estar fora da thread principal; o nível mestre pensa até 3,5 segundos, o que congelaria o separador se corresse onde vive o React. Por isso o motor corre negamax fail-soft com aprofundamento iterativo num Web Worker, apoiando-se com força na poda por lance nulo, nas reduções de lances tardios e na poda por futilidade para sobreviver à largura. Saem quatro níveis de dificuldade, do adversário instantâneo de 60 ms com avaliação deliberadamente ruidosa até a um mestre com tabela de 16 MB que chega à profundidade seis. Até a aleatoriedade da IA é determinista — o ruído nos lances da raiz vem de um gerador com semente ligada ao registo da partida, por isso uma partida repetida repete-se de forma idêntica.

Problemas com soluções verificadas por máquina

Todas as aplicações de xadrez têm problemas; a maioria tem alguns partidos. Em quatro dimensões, um problema partido seria impossível de corrigir a partir de um relatório de utilizador — ninguém consegue detetar à vista a refutação de um mate em 3 em 4D. Por isso nenhum problema sai só porque nós dizemos. Cada um dos doze estudos do pacote tem de passar três verificações automáticas: exatidão (uma pesquisa até ao dobro da profundidade anunciada encontra mate em exatamente N, começando pelo lance-chave indicado), unicidade (nenhum outro primeiro lance dá mate tão depressa) e carácter forçado (toda a resposta da defesa continua a perder). O tutorial guiado leva o mesmo tratamento — as suas oito lições são provadas vencíveis jogando todos os lances legais da peça da lição no motor a sério. Se uma lição puder ser perdida, é a compilação que se perde primeiro.

Xadrez em quatro dimensões por um canal em que não se confia

O jogo online corre sobre um canal de difusão em tempo real, e tratamos esse canal exatamente pelo que é: um retransmissor não fidedigno. Os pares acordam uma chave por ECDH e cada lance atravessa a rede autenticado — um HMAC sobre uma serialização canónica que inclui a versão do protocolo, o identificador da partida, a identidade de 128 bits associada ao remetente e um número de sequência de meia-jogada. Depois vem a verificação que torna o resto quase decorativo: o cliente que recebe volta a validar cada lance recebido no seu próprio gerador de lances legais. Com um lance forjado ou corrompido não se discute; ele é simplesmente ilegal, e o motor determinista faz com que os dois tabuleiros ou concordem na perfeição ou detetem a dessincronização pelo hash de Zobrist logo no lance seguinte.

// A move on the wire: eight digits (from-xyzw, to-xyzw) + optional promotion.
const WIRE_MOVE = /^[1-5]{8}[QRBNUD]?$/;

"22132313";  // Y-pawn at (2,2,1,3) steps forward along y to (2,3,1,3)
"24132513Q"; // the same pawn reaching y=5 promotes: Q R B N U or D

O Tesseract pegou na plataforma que construímos ao longo de treze jogos — os níveis de qualidade partilhados, o sintetizador de áudio, o contrato de ecrã inteiro, a regra da tela única — e apontou tudo isso a uma única pergunta: pode um navegador ensinar um humano a ver em quatro dimensões? Depois de uma semana a perder contra o nosso próprio nível principiante, achamos que a resposta honesta é: devagar, e é aí que está a graça.