Dois jogos de fusão, uma pergunta: algum deles pode ser jogado sem falhas? A resposta passa pelo canto de um tabuleiro, por um adversário que nunca aparece e por um número com dezessete expoentes de altura.
Escrito e editado em inglês. Esta versão em português foi produzida por tradução automática; quando a precisão importa, o original em inglês é a referência. Ler o original em inglês →
Comece pelo jogo que todos conhecem. 2048, quatro direções, uma grade 4×4, peças que dobram ao se tocar, está, em sentido estrito, sem solução. Ninguém escreveu um algoritmo que o jogue com perfeição. O que temos são aproximações muito fortes. Uma busca expectimax, que enxerga cerca de oito movimentos à frente e avalia cada tabuleiro por um punhado de heurísticas ajustadas à mão (células livres, peças grandes presas a uma borda, suavidade), alcança a peça 32768 em mais de um terço das partidas, 1 e o motor público mais forte chega à peça 65536 em alguns por cento das vezes. 2 Generalizado para um tabuleiro m×n, apenas decidir se uma peça-alvo é alcançável já é NP-difícil. 3 Forte não é o mesmo que resolvido.
Até onde uma única peça pode subir? Em dezesseis células, a resposta é um pequeno e elegante exercício de contagem. Disponha o tabuleiro como uma escada descendente, 65536, 32768, 16384, e assim por diante até um 2 solitário. Cada peça está exatamente uma potência de dois abaixo da sua vizinha, de modo que as dezesseis potências distintas de 21 a 216 preenchem o tabuleiro perfeitamente, e 65536 = 216 fica no topo: um expoente por célula. Esse é o teto se o jogo só lhe der 2. Mas 2048 gera um 4 uma vez em cada dez, e um único 4 bem cronometrado introduz um décimo sétimo expoente, elevando o verdadeiro máximo para 131072 = 217: potências equivalentes a dezessete peças acomodadas em dezesseis casas. 4 Nenhum ser humano a construiu; algumas IAs chegaram perto.
Por que esses tabuleiros recompensam guardar a maior peça em um canto? Uma peça no meio pode ser empurrada de quatro maneiras e vive sendo separada das peças com as quais quer se unir. Uma peça de canto toca duas paredes; empurrões em direção às paredes em que ela já encosta não conseguem movê-la, e, enquanto você evitar empurrar para longe delas, ela fica parada enquanto todo o resto se organiza ao seu redor. Encadeie o restante em uma serpente monótona, com a maior no canto, dobrando-se de um lado para o outro em ordem decrescente, e um só deslize pode desencadear uma cascata de fusões. 1 Essa é a heurística que domina o jogo humano casual, e é quase exatamente o que as IAs redescobrem quando se deixa que ajustem os próprios pesos.
Um jogo de fusão com surgimento aleatório de peças não tem adversário, só clima. “Resolvê-lo” é vencer os dados em média, não vencer uma mente.
Agora incline o tabuleiro para três dimensões. 3927 é o primo cúbico de 2048: uma rede 3×3×3 de 27 células, seis direções de deslocamento em vez de quatro, e peças que se fundem de três em três, 3 para 9 para 27 para 81, base três onde 2048 é base dois. 5 O empilhamento no canto sobrevive à dimensão extra? Um cubo tem oito cantos, e uma célula de canto agora toca três faces em vez de duas; ela deveria ser ainda mais estável, presa por três paredes ao mesmo tempo, embora as seis direções deem ao tabuleiro mais maneiras de desmontar a sua estrutura. A serpente se torna um caminho dobrado que atravessa as três camadas. Até onde consegui apurar, ninguém verificou se a analogia de fato se sustenta: isto é raciocínio, não medição.
E o teto? A regra de um expoente por célula sugeriria 327 ≈ 7,6 trilhões como um limite superior folgado. Mas a analogia se desfaz bastante. O expoente extra de 2048 vinha de um 4 sortudo; 3927 só gera a menor peça, um simples 3, então não há bônus. Pior: uma fusão tripla exige três peças alinhadas, e toda linha, coluna e pilar de um cubo 3×3×3 tem exatamente três células, de modo que toda fusão consome uma linha inteira. Essa restrição pesa muito mais do que qualquer coisa no jogo plano e quase certamente puxa o máximo real para bem abaixo de 327. Qual é esse número verdadeiro, não encontrei calculado em lugar nenhum. (Raciocínio claramente identificado como tal; a mecânica acima foi extraída dos documentos de design do jogo.)
Eis a sutileza que torna escorregadia a ideia de “jogo perfeito”. Um jogo de fusão com surgimento aleatório de peças é um jogo estocástico de um só jogador, uma paciência contra um dado, não um duelo. Nada escolhe o pior surgimento para arruinar você; há apenas o gerador de números aleatórios, indiferente. Assim, a noção correta de jogo ótimo é o expectimax: maximizar o resultado esperado sobre a distribuição dos surgimentos. Não é, de modo algum, o minimax: o minimax pressupõe um adversário, e se você de fato deixar um adversário posicionar cada peça (“evil 2048”, o 2048 malvado), o jogo se torna algo mais cruel, que você pode ser forçado a perder. Como os dados podem, em princípio, entregar qualquer sequência, uma estratégia que garanta uma determinada peça pode simplesmente não existir. Por isso, a resposta honesta a “existe uma estratégia perfeita?” é que, para um jogo estocástico, o melhor que se pode sequer definir é uma estratégia ótima em média, e calculá-la exatamente está fora de alcance para 2048 6 e em aberto para 3927.