Si vous avez été sur internet dans les années 2010, vous connaissez probablement le jeu addictif, 2048. Voyons jusqu’où nous pouvons aller en termes de score grâce à la puissance de l’apprentissage automatique.

Mécaniques du jeu

Le jeu fonctionne comme suit. 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 avec la 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 élevée. 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 un autre 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’atteindrons pas ce score aujourd’hui, mais nous essaierons de battre les meilleurs humains.

Méthodes

Il existe deux classes de méthodes que nous allons utiliser : les méthodes basées sur la recherche et les méthodes basées sur l’apprentissage. Les méthodes basées sur la recherche tentent d’explorer une multitude d’états de jeu possibles et de faire une estimation en fonction du mouvement qui a le plus de chances de conduire à un résultat souhaité. Les méthodes basées sur l’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, où nous jouons uniquement des coups optimaux
• Pour chaque coup possible $m$, créez une copie du plateau, et sur celle-ci effectuez le coup $m$
• Ensuite, laissez un joueur aléatoire effectuer des coups sur ce plateau jusqu’à ce qu’il perde. Ensuite, nous enregistrons la somme des tuiles du plateau final. Ce sera notre score.
• Répétez cela $N$ fois, où un $N$ plus élevé signifie que plus de parties ont été explorées.
• Choisissez 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éez une copie du plateau
        board_copy = copy(board)
        # Effectuez 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'à ce que la partie soit terminée. Ensuite, nous enregistrons
        # la somme moyenne des tuiles finales sur le plateau.
        for n in range(num_games):
            board_copy2 = copy(board_copy)
            # Laissez un agent aléatoire jouer jusqu'à ce qu'il perde
            board_copy2.random_game()
            sums.append(board_copy2.tile_sum())
        # Enregistrez la somme moyenne des tuiles dans la configuration perdante
        scores.append(sum(tile_sums) / len(tile_sums))
    return moves[argmax(scores)]

Réseau N-Tuple

Les réseaux N-Tuple, initialement conçus comme des RAMnets , se sont révélés extrêmement efficaces pour jouer à 2048 lorsqu’ils sont entraînés en utilisant l’apprentissage par différence temporelle. Ils définissent une fonction $F$ qui associe un certain type de caractéristique, encodé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 index.

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

Implémentation du Plateau

struct Board {
    raw: u64,
}

C’est exact, nous stockons l’intégralité dans un entier non signé de 64 bits. Nous faisons cela en observant que

1. Chaque valeur de tuile est soit vide, soit $2^n$ où $n\ge 1$
2. D’après l’expérience, nous n’obtiendrons probablement pas la tuile $2^{16}=65536$.

Cela donne la borne $1\le n\le 15$. Ainsi, nous avons $15+1$ valeurs possibles pour chaque tuile, ce qui signifie que nous pouvons la compresser en $4$ bits. Pour retrouver la valeur de la tuile, 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. Comme chaque tuile occupe $4$ bits, chaque caractéristique utilisera $6\times 4=24$ bits.

Puisque notre réseau est une carte de caractéristique $\to$ score, nous utilisons un tableau de $2^{4\times 6}=\text{16,777,216}$ flottants 32 bits pour stocker chaque caractéristique. Comme chaque flottant occupe 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 de la 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 tout aussi bonne qu’elle soit en haut, en bas, à gauche ou à droite du plateau. En fait, même si nous inversons son ordre, elle reste 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.