Si vous étiez sur internet dans les années 2010, vous connaissez probablement le jeu addictif, 2048. Voyons jusqu’où nous pouvons scorer grâce à la puissance du machine learning.

Mécaniques de jeu

Le jeu fonctionne de la manière suivante. Le plateau commence avec 2 tuiles aléatoires. Chaque tuile aléatoire a 90% de chance d’être un 2 et 10% de chance d’être un 4.

Il y a 4 mouvements possibles : Haut, Bas, Gauche et Droite. Chaque mouvement correspond à un “glissement” sur le plateau, où toutes les tuiles sont déplacées dans cette direction jusqu’à ce qu’elles entrent en collision avec une autre tuile. Si deux tuiles ont la même valeur $N$, les tuiles fusionnent en une tuile supérieure de valeur $2N$. Chaque fois que nous fusionnons, notre score augmente de $2N$.

Est-ce vraiment si difficile ?

Oui, ça l’est. Du moins pour obtenir une tuile arbitrairement haute. Pour comprendre pourquoi, disons que vous avez atteint 1024. Vous avez alors utilisé 16 cases comme “bloc-notes” pour produire ce score. Pour obtenir 2048, cependant, vous devez produire une autre tuile de 1024 avec $16-1=15$ cases comme bloc-notes. Pour obtenir 4096, vous devez le faire avec 14 cases, et ainsi de suite. Il existe donc en fait un score maximum théorique de 3 932 156, qui peut être calculé uniquement à partir des contraintes d’espace. Nous n’irons pas jusque-là aujourd’hui, mais nous allons essayer de battre les meilleurs humains.

Méthodes

Il existe deux classes de méthodes que nous allons utiliser : les méthodes par recherche et les méthodes par apprentissage. Les méthodes par recherche tentent d’explorer une multitude d’états de jeu possibles et font un choix basé sur le coup qui a le plus de chances de mener à un résultat souhaité. Les méthodes par apprentissage définissent un modèle de joueur et simulent un grand nombre de parties pour apprendre ses paramètres.

Joueur Aléatoire

C’est notre référence de base. Il est assez mauvais.

Monte Carlo

Cette méthode fonctionne comme suit :

• Nous avons un plateau principal, sur lequel nous jouons uniquement des coups optimaux
• Pour chaque coup possible $m$, créer une copie du plateau, et y jouer le coup $m$
• Ensuite, laisser un joueur aléatoire jouer des coups sur ce plateau jusqu’à ce qu’il perde. Enregistrer ensuite la somme des tuiles du plateau final. Ce sera notre score.
• Répéter cela $N$ fois, où un $N$ plus élevé signifie que plus de parties ont été explorées.
• Choisir le coup avec le score moyen le plus élevé comme coup optimal.

Voici le pseudocode :

def choose_best_move(board):
    scores = [] # Liste des sommes moyennes des tuiles
    moves = [UP, DOWN, LEFT, RIGHT]
    for move in moves:
        # Créer une copie du plateau
        board_copy = copy(board)
        # Jouer le coup (inclut l'apparition d'une tuile)
        board_copy.make_move(move)
        tile_sums = []
        # Étant donné ce coup, nous laissons un joueur aléatoire
        # jouer jusqu'à la fin de la partie. Puis, nous enregistrons
        # la somme moyenne des tuiles finales sur le plateau.
        for n in range(num_games):
            board_copy2 = copy(board_copy)
            # Faire jouer un agent aléatoire jusqu'à sa défaite
            board_copy2.random_game()
            sums.append(board_copy2.tile_sum())
        # Sauvegarder la somme moyenne des tuiles dans la configuration de défaite
        scores.append(sum(tile_sums) / len(tile_sums))
    return moves[argmax(scores)]

Réseau N-Tuple

Les réseaux N-Tuple, initialement conçus sous le nom de RAMnets, se sont avérés extrêmement performants pour jouer à 2048 lorsqu’ils sont entraînés par apprentissage par différence temporelle. Ils définissent une fonction $F$ qui associe un certain type de caractéristique, codée en binaire, à un score représentant à quel point cette caractéristique spécifique est bonne.

Cette fonction, contrairement à la plupart des réseaux de neurones modernes, n’est pas calculée mais stockée dans un tableau, dont chaque élément représente le score de la caractéristique correspondant à son indice.

Pour comprendre comment nous allons indexer ce tableau, examinons l’implémentation du plateau de jeu.

Implémentation du Plateau

struct Board {
    raw: u64,
}

En effet, nous faisons tenir l’intégralité du plateau dans un entier non signé de 64 bits. Nous y parvenons en observant que :

1. La valeur de chaque case est soit vide, soit $2^n$ où $n\ge 1$.
2. L’expérience montre que nous n’atteindrons probablement pas la case $2^{16}=65536$.

Cela nous donne la borne $1\le n\le 15$. Ainsi, nous avons $15+1$ valeurs possibles pour chaque case, ce qui signifie que nous pouvons la coder sur $4$ bits. Pour retrouver la valeur réelle d’une case, nous utilisons :

Architecture

Le réseau que nous utilisons est un réseau de tuples $4\times 6$, qui possède 4 caractéristiques, chaque caractéristique représentant une configuration de $6$ tuiles sur le plateau. Puisque chaque tuile occupe $4$ bits, chaque caractéristique utilisera $6\times 4=24$ bits.

Comme notre réseau est une correspondance (map) d’une caractéristique $\to$ à un score, nous utilisons un tableau de $2^{4\times 6}=\text{16 777 216}$ flottants 32 bits pour stocker chaque caractéristique. Puisque chaque flottant fait 4 octets, cela porte la taille de notre réseau à $4\times 4\times \text{16 777 216}=\text{268 435 456}$ octets.

Une observation pratique que nous pouvons faire est que la valeur d’une caractéristique ne devrait pas changer en fonction de sa position sur le plateau. Par exemple, une ligne avec les tuiles $(512,1024,2048,4096)$ est aussi bonne qu’elle soit en haut, en bas, à gauche ou à droite du plateau. En fait, même si nous inversons son ordre, elle est tout aussi bonne. Cela signifie que nous pouvons réutiliser les mêmes poids pour calculer le score de la caractéristique sur toutes les orientations, ou symétries, du plateau. Un carré possède 8 symétries de ce type, que nous montrons ci-dessous.