Resumo Técnico: Solução Forte do 2048 em um Tabuleiro 4×3

Definição do Problema

Este artigo aborda a "solução forte" de uma variante estocástica de jogo de um único jogador: 2048 em um tabuleiro 4×3 (denotado como 2048$^{4\times3}$). Diferentemente da versão padrão 4×4, esta variante utiliza uma grade de 12 células. O jogo é modelado como um Processo de Decisão de Markov (MDP) onde um agente seleciona ações (cima, baixo, esquerda, direita) para fundir peças adjacentes de valor igual. Após uma ação válida, o estado do tabuleiro transita deterministicamente para um "estado posterior" (deslizamento e fusão de peças). Subsequentemente, o ambiente gera estocasticamente uma nova peça (2 com 90% de probabilidade, 4 com 10%) em uma célula vazia aleatória, transitando para o próximo estado.

O objetivo é calcular a política ótima $\pi^*$ e a função de valor ótima $v^*(s)$, representando a recompensa cumulativa esperada de qualquer estado alcançável $s$. O principal desafio reside no tamanho do espaço de estados: a variante 4×3 contém aproximadamente $1,15 \times 10^9$ estados alcançáveis e $7,4 \times 10^8$ estados posteriores. Esta escala é cerca de $10^4$ vezes maior que a variante 3×3 previamente resolvida (Mini2048), tornando a enumeração e o armazenamento diretos inviáveis em hardware padrão.

Metodologia

Os autores propõem uma solução baseada em particionamento do espaço de estados por "idade" e representação compacta de dados.

1. Particionamento Baseado em Idade

A inovação central é definir a idade de um estado como a soma de todos os números das peças no tabuleiro ($idade(s) = \sum c_i$).

• Invariância: A idade permanece constante entre um estado e seu estado posterior imediato após uma ação válida (já que fundir peças preserva a soma dos valores, e deslizar não altera os valores).
• Progressão: A idade aumenta em 2 ou 4 durante a transição estocástica (geração de uma nova peça).
• Implicação Algorítmica: Esta propriedade permite particionar o espaço de estados em subconjuntos disjuntos baseados na idade.
  • Passagem Adiante (Enumeração): Estados válidos de idade $n$ podem ser gerados exclusivamente a partir de estados posteriores de idades $n-2$ e $n-4$. O algoritmo itera através de idades crescentes, mantendo apenas três conjuntos na memória (idade atual, idade+2, idade+4) para enumerar todos os estados e estados posteriores alcançáveis.
  • Passagem Retrocedida (Cálculo de Valor): Os valores ótimos são calculados iterando retrocedidamente da idade máxima até a idade inicial. O valor de um estado é o valor máximo de seus estados posteriores alcançáveis; o valor de um estado posterior é o valor esperado de seus próximos estados alcançáveis (ponderado pelas probabilidades de geração).

2. Representação Compacta

Para lidar com os requisitos de armazenamento (estimados em ~4,4 TiB para IDs brutos de 48 bits), os autores empregam códigos Elias-Fano para armazenar conjuntos de IDs de estados únicos.

• Estrutura: IDs únicos ordenados são divididos em bits de ordem superior ($h_i$) e bits de ordem inferior ($l_i$). Os bits inferiores são armazenados em um vetor de bits contíguo, enquanto os bits superiores são codificados em um vetor de bits esparsos $H$ usando operações de classificação.
• Otimizações:
  • Redução de Simetria: Os IDs são normalizados para o valor mínimo entre simetrias horizontal, vertical e de rotação de 180 graus.
  • Adaptação da Base: A base de codificação é ajustada com base no valor máximo da peça para uma idade específica.
  • Eliminação de Célula: A informação de uma célula é descartada durante a codificação porque a soma (idade) restringe o total, permitindo a reconstrução completa posteriormente.
• Eficiência: Isso reduz o armazenamento para todos os IDs de estados posteriores de ~4,4 TiB para aproximadamente 1,4 TiB, mantendo capacidades de busca eficientes. Para o jogo ótimo especificamente, uma representação especializada (usando o algoritmo BuRR) reduz o requisito para menos de 300 GiB.

Resultados Chave

• Estatísticas do Espaço de Estados: O número total de estados alcançáveis é 1.152.817.492.752, e o número de estados posteriores é 739.648.886.170.
• Pontuação Esperada Ótima: Para os estados iniciais mais comuns (duas peças de valor 2), a pontuação esperada sob uma estratégia ótima é aproximadamente 50.724,26.
  • Estados iniciais com uma peça 4 (idade 6) produzem uma pontuação esperada ligeiramente menor (~50.720,62).
  • Estados iniciais com duas peças 4 (idade 8) produzem a menor (~50.708,99), indicando uma pequena desvantagem em começar com peças de maior valor.
• Distribuição de Estados: O número de estados por idade é geralmente gerenciável (menos de $3 \times 10^6$ por idade), permitindo que o algoritmo mantenha várias camadas de idade na memória.
• Estados Terminais: "Vales" na distribuição da contagem de estados ocorrem em idades que são múltiplos de 2048, refletindo a dificuldade de formar peças grandes com espaço limitado no tabuleiro. Certas idades (por exemplo, 8190, 12286) têm zero estados posteriores válidos porque formar essas somas exigiria mais peças do que as 12 células disponíveis permitem.
• Sensibilidade à Ação: A diferença de valor entre ações ótimas e subótimas atinge o pico perto das idades 2048 e 4096, sugerindo que decisões iniciais imediatamente após a formação de peças grandes são críticas.

Significado e Alegações

O artigo afirma ter resolvido fortemente a variante 2048$^{4\times3}$, uma tarefa anteriormente considerada intratável devido ao tamanho do espaço de estados. O significado deste trabalho reside em:

1. Escalabilidade: Demonstrar que um jogo com mais de $10^9$ estados pode ser resolvido em um computador pessoal dentro de alguns dias, aproveitando propriedades estruturais específicas do jogo (idade) em vez de métodos de força bruta.
2. Contribuição Metodológica: A introdução da técnica de particionamento por "idade" permite a enumeração e o cálculo de valor de MDPs estocásticos onde os valores dos estados dependem de expectativas, contornando efetivamente a necessidade de poda $\alpha\beta$ (que é ineficaz em ambientes estocásticos).
3. Disponibilidade de Dados: Os autores fornecem a função de valor ótima e uma representação compacta do espaço de estados, servindo como base para futuras pesquisas em aprendizado por reforço e análise de jogos.
4. Eficiência de Armazenamento: A aplicação bem-sucedida de códigos Elias-Fano para comprimir um conjunto massivo de estados de jogo para ~1,4 TiB torna o conjunto de dados acessível para pesquisadores com recursos computacionais moderados (por exemplo, SSDs de 4 TiB).

Os autores observam que, embora o objetivo principal fosse resolver o jogo, o conjunto de dados resultante e o conceito de "idade" podem servir como base para estudos adicionais em jogos estocásticos e avaliação de aprendizado por reforço.