Résumé Technique : Résolution Forte de 2048 sur un Plateau 4×3

Définition du Problème

Ce papier traite de la « résolution forte » d'une variante stochastique d'un jeu à un joueur : 2048 sur un plateau 4×3 (noté 2048$^{4\times3}$). Contrairement à la version standard 4×4, cette variante utilise une grille de 12 cellules. Le jeu est modélisé comme un Processus de Décision Markovien (MDP) où un agent sélectionne des actions (haut, bas, gauche, droite) pour fusionner des tuiles adjacentes de valeur égale. Après une action valide, l'état du plateau transite de manière déterministe vers un « après-état » (glissement et fusion des tuiles). Par la suite, l'environnement fait apparaître stochastiquement une nouvelle tuile (2 avec une probabilité de 90 %, 4 avec 10 %) dans une cellule vide aléatoire, passant ainsi à l'état suivant.

L'objectif est de calculer la politique optimale $\pi^*$ et la fonction de valeur optimale $v^*(s)$, représentant la récompense cumulative attendue depuis n'importe quel état atteignable $s$. Le défi principal réside dans la taille de l'espace d'états : la variante 4×3 contient environ $1,15 \times 10^9$ états atteignables et $7,4 \times 10^8$ après-états. Cette échelle est environ $10^4$ fois plus grande que celle de la variante 3×3 précédemment résolue (Mini2048), rendant l'énumération et le stockage directs infeasibles sur du matériel standard.

Méthodologie

Les auteurs proposent une solution basée sur le partitionnement de l'espace d'états par « âge » et une représentation compacte des données.

1. Partitionnement par Âge

L'innovation centrale consiste à définir l'âge d'un état comme la somme de tous les nombres de tuiles sur le plateau ($age(s) = \sum c_i$).

• Invariance : L'âge reste constant entre un état et son après-état immédiat suite à une action valide (puisque la fusion de tuiles préserve la somme des valeurs, et le glissement ne modifie pas les valeurs).
• Progression : L'âge augmente de 2 ou 4 lors de la transition stochastique (apparition d'une nouvelle tuile).
• Implication Algorithmique : Cette propriété permet de partitionner l'espace d'états en sous-ensembles disjoints basés sur l'âge.
  • Passage Avant (Énumération) : Les états valides d'âge $n$ peuvent être générés uniquement à partir des après-états des âges $n-2$ et $n-4$. L'algorithme itère sur les âges croissants, ne maintenant en mémoire que trois ensembles (âge actuel, âge+2, âge+4) pour énumérer tous les états et après-états atteignables.
  • Passage Arrière (Calcul de Valeur) : Les valeurs optimales sont calculées en itérant à rebours depuis l'âge maximal jusqu'à l'âge initial. La valeur d'un état est la valeur maximale de ses après-états atteignables ; la valeur d'un après-état est la valeur attendue de ses états suivants atteignables (pondérée par les probabilités d'apparition).

2. Représentation Compacte

Pour gérer les besoins de stockage (estimés à ~4,4 TiB pour des IDs bruts de 48 bits), les auteurs utilisent des codes Elias-Fano pour stocker des ensembles d'IDs d'états uniques.

• Structure : Les IDs uniques triés sont divisés en bits de poids fort ($h_i$) et bits de poids faible ($l_i$). Les bits faibles sont stockés dans un vecteur de bits contigu, tandis que les bits forts sont encodés dans un vecteur de bits creux $H$ utilisant des opérations de rang.
• Optimisations :
  • Réduction de Symétrie : Les IDs sont normalisés vers la valeur minimale parmi les symétries horizontale, verticale et de rotation à 180 degrés.
  • Adaptation de Base : La base d'encodage est ajustée en fonction de la valeur maximale de tuile pour un âge spécifique.
  • Suppression de Cellule : L'information d'une cellule est supprimée lors de l'encodage car la somme (âge) contraint le total, permettant une reconstruction complète ultérieure.
• Efficacité : Cela réduit le stockage de tous les IDs d'après-états de ~4,4 TiB à environ 1,4 TiB tout en maintenant des capacités de recherche efficaces. Pour le jeu optimal spécifiquement, une représentation spécialisée (utilisant l'algorithme BuRR) réduit l'exigence à moins de 300 GiB.

Résultats Clés

• Statistiques de l'Espace d'États : Le nombre total d'états atteignables est de 1 152 817 492 752, et le nombre d'après-états est de 739 648 886 170.
• Score Espéré Optimal : Pour les états initiaux les plus courants (deux tuiles de valeur 2), le score espéré sous une stratégie optimale est d'environ 50 724,26.
  • Les états initiaux avec une tuile 4 (âge 6) donnent un score espéré légèrement inférieur (~50 720,62).
  • Les états initiaux avec deux tuiles 4 (âge 8) donnent le plus bas (~50 708,99), indiquant un léger désavantage à commencer avec des tuiles de plus haute valeur.
• Distribution des États : Le nombre d'états par âge est généralement gérable (moins de $3 \times 10^6$ par âge), permettant à l'algorithme de maintenir plusieurs couches d'âge en mémoire.
• États Terminaux : Des « vallées » dans la distribution du nombre d'états se produisent aux âges qui sont des multiples de 2048, reflétant la difficulté de former de grandes tuiles avec un espace de plateau limité. Certains âges (par exemple, 8190, 12286) n'ont aucun après-état valide car former ces sommes nécessiterait plus de tuiles que les 12 cellules disponibles ne le permettent.
• Sensibilité aux Actions : La différence de valeur entre les actions optimales et sous-optimales atteint un pic près des âges 2048 et 4096, suggérant que les décisions prises immédiatement après la formation de grandes tuiles sont critiques.

Signification et Revendications

Le papier revendique avoir résolu fortement la variante 2048$^{4\times3}$, une tâche précédemment considérée comme intraitable en raison de la taille de l'espace d'états. La signification de ce travail réside dans :

1. Évolutivité : Démontrer qu'un jeu avec plus de $10^9$ états peut être résolu sur un ordinateur personnel en quelques jours en exploitant des propriétés structurelles spécifiques au jeu (l'âge) plutôt que des méthodes de force brute.
2. Contribution Méthodologique : L'introduction de la technique de partitionnement par « âge » permet l'énumération et le calcul de valeur de MDP stochastiques où les valeurs d'état dépendent d'attentes, contournant efficacement le besoin de l'élagage $\alpha\beta$ (qui est inefficace dans les environnements stochastiques).
3. Disponibilité des Données : Les auteurs fournissent la fonction de valeur optimale et une représentation compacte de l'espace d'états, servant de référence pour les futures recherches en apprentissage par renforcement et en analyse de jeux.
4. Efficacité de Stockage : L'application réussie des codes Elias-Fano pour compresser un ensemble massif d'états de jeu à ~1,4 TiB rend le jeu accessible aux chercheurs disposant de ressources informatiques modérées (par exemple, des SSD de 4 TiB).

Les auteurs notent que, bien que l'objectif principal ait été de résoudre le jeu, le jeu de données résultant et le concept d'« âge » peuvent servir de fondation pour des études ultérieures sur les jeux stochastiques et l'évaluation de l'apprentissage par renforcement.