Le jeu du Taquin en go

Cette série d'articles retrace mon parcours d'intégration au sein de Marmelab qui s'articule autour du jeu du Taquin. (Part 1. Le jeu du Taquin en Python)

Mercredi 11h. Après une semaine de travail, le premier sprint dédié à la création d'un Taquin en Python vient de se terminer par une présentation du jeu à tous mes collègues. S'en suit un compte rendu de Kévin (référent technique en Python), puis de François (Product Owner) où j'en apprends plus sur la suite de l'intégration.

Fini le Python pour le moment, je serai chargé de réécrire tout le jeu en GO. Cette fois-ci la tâche s'annonce plus ardue. En effet, en plus de devoir tout reprendre dans un nouveau langage, il me faudra développer un serveur web et suggérer au joueur le meilleur coup à jouer à un instant T.

Réécriture du jeu en GO

Développé par Google depuis 2009, le langage (GO) est un langage de programmation compilé qui s'inspire du C. Il s'agit donc d'un langage assez proche de la machine ce qui le rend très performant. Je le trouve en revanche un peu strict pour un développeur comme moi habitué aux langages de haut niveau.

Il a cependant de nombreux avantages et je trouve qu'une de ses principales forces est de mettre en avant le multithreading. Si bien que le mot clef éponyme go existe dans le langage et est associé à la création de processus appelés des goroutines. Le langage fournit également un système de pile de données asynchrone : les channels. Elles sont utilisées pour échanger des informations entre les différents processus. C'est également une manière de les synchroniser. En effet un processus peut se mettre en pause tant que le channel est vide. C'est le cas de mon processus d'affichage de messages qui ne fait rien tant qu'il n'y a pas de message à afficher.

func RenderListener(msgChan chan Message) {
  for {
    msg := <-msgChan
    if msg.Clear {
      renderer.ClearTerminal()
    }
    fmt.Println(msg.Content)
  }
}

Les bases du jeu

Deux choix sont rapidement apparus lors du travail de réécriture des bases du jeu. Le premier fut de reprendre le code Python et de simplement le traduire en GO, le second, quant à lui, fut d'essayer de comprendre les forces du langage pour en tirer parti.

J'ai donc commencé par reprendre les principaux algorithmes qui formaient le coeur du jeu. Il aurait été intéressant à ce stade de tout reprendre depuis le début, mais cela nécéssitait beaucoup de temps pour peu de valeur ajoutée pour l'utilisateur final. Or le principe de l'agile est de toujours proposer des changements visibles ; ce qui n'est pas le cas lorsque l'on réécrit un code dans un autre langage. J'ai donc opté à ce stade pour une amélioration de l'existant à l'aide des spécificités du langage GO, en utilisant par exemple des structures de données plutôt que de simples tableaux de valeur.

La structure de données Coords est assez explicite

type Coords struct {
   X byte
   Y byte
}

Vous pouvez retrouver un comparatif ci-dessous du code en python et du code transcrit en GO. On remarquera facilement leurs similitudes.

def find_tile(grid, value):
    y = 0
    while y < len(grid):
        x = 0
        while x < len(grid[y]):
            if int(grid[y][x]) == int(value):
                return [y, x]
            x += 1
        y += 1
    raise NoTileFoundException('The grid does not contain this tile')

func findTileByValue(grid Grid, value byte) (Coords, error) {
  var tile Coords
  size := byte(len(grid))
  y := byte(0)
  for y < size {
    x := byte(0)
    for x < byte(len(grid[y])) {
      if grid[y][x] == value {
        tile.Y = y
        tile.X = x
        return tile, nil
      }
      x++
    }
    y++
  }
  return tile, errors.New("The grid does not contain this tile")
}

L'apport de la programmation événementielle

La principale amélioration de ce Taquin fut sans nul doute la refonte du système de jeu. Alors que la version Python fonctionnait de manière séquentielle (une action après l'autre), cette nouvelle version a introduit une forme de programmation événementielle (des parties de programme s'exécutent en parallèle et se synchronisent à l'aide d'événements).

Le principe mis en place est assez simple. Chaque partie du jeu sera désormais contrôlée par une routine spécifique. Elles seront de trois types :

• lecture seule : écoute des événements du programme
• écriture seule : créé des événements dans le programme
• lecture et écriture : effectue les deux opérations précédentes

L'association de ces différentes routines créé ainsi un programme complet. On voit bien que chaque routine a sa propre durée de vie et que certains traitements se font en parallèle. Un événément clavier contrôle le jeu, alors que la partie affichage est totalement décorrélée du reste du programme.

Je trouve cette architecture très intéressante dans le sens où elle permet de bien séparer les modules, tout comme elle permet d'ajouter facilement de nouvelles actions en les "branchant" simplement sur certains événements. On aurait, par exemple, très bien pu imaginer lancer en tâche de fond un système de sauvegarde automatique à chaque fin de tour. Il aurait pour cela suffit d'écouter le channel grid qui est lui-même alimenté par la routine game dès qu'un nouvel état du plateau est calculé (après un déplacement par exemple).

project/
  src/
    events/
    game/
    renderer/
    main.go

L'arborescence du projet est donc très proche avec l'ajout d'un dossier dédié aux événéments.

Trouver le meilleur coup : une forme d'intelligence artificielle

Les événements ont justement été exploités en seconde partie du sprint pour mettre en place le système de suggestion de coups en "parallèle" du jeu. Pour rappel, un coup est un mouvement que peut effectuer le joueur pour modifier le puzzle, par exemple le déplacement d'une case vers le haut. Le principe est simple : à chaque fois que l'utilisateur le souhaite, il peut appuyer sur une touche d'aide et le meilleur coup à jouer sera affiché à l'écran.

Étude des solutions existantes

La réalisation est quant à elle un peu plus complexe. Bien qu'il existe des milliers de solutions, elles ne sont pas toutes acceptables d'un point de vue utilisateur. Les contraintes sont multiples : d'un côté l'algorithme doit être rapide, de l'autre il doit suggérer une solution dite optimale (c'est-à-dire comportant le moins de coups possibles). Qui voudrait faire plus de 1000 déplacements pour résoudre un Taquin ?

Le calcul d'une heuristique pertinente

J'ai dans un premier temps pris papier et crayon pour dessiner le problème. J'en suis rapidement arrivé à me représenter un graphe où chaque noeud serait une grille, et chaque arète un mouvement. Cependant la question qui se posait alors était de savoir si un mouvement nous rapprochait ou nous éloignait de la solution.

C'est alors que j'ai choisi de simplement compter le nombre de cases mal positionnées. Puis, j'ai découvert que la distance de Manhattan donnait des résultats plus intéressants. Enfin j'ai décidé d'appliquer un coefficient afin de favoriser les cases de moins grande valeur. La résolution manuelle d'un Taquin doit en effet se faire en plaçant bien la case 1, puis la 2, puis la 3...

func TaxicabWithValues(grid Grid, grid2 Grid) int {
  sum := 0
  size := len(grid)
  y := 0

  for y < size {
    x := 0
    for x < size {
      if grid[y][x] != grid2[y][x] {
        expectedPos, _ := findTileByValue(grid2, grid[y][x])
        sum += int(math.Abs(float64(y-int(expectedPos.Y))) + math.Abs(float64(x-int(expectedPos.X)))) // Compute the taxicab sum
        sum += size*size - int(grid[y][x]) // Add a coefficient
      }
      x++
    }
    y++
  }
  return sum
}

Chaque plateau de jeu sera alors associé à un coût. Plus le puzzle est éloigné de la solution, et plus sa valeur sera élevée. Zéro représente alors la grille résolue. Le nombre de combinaisons du Taquin étant fini, il est possible dans l'absolu de calculer l'ensemble des grilles existantes et leur coût associé. Dans la pratique, cela demanderait de stocker beaucoup d'informations, si bien qu'elles seront ici recalculées à chaque fois.

Élaboration d'un algorithme

En me basant sur cette heuristique, je suis parti du principe que si la grille résultant du mouvement posséde un coût inférieur à la grille précédente, c'est que ce mouvement est le plus pertinent. Bien entendu, cela ne fonctionnait pas puisque souvent la résolution du Taquin implique d'augmenter temporairement le coût de la grille pour mieux la résoudre.

Après divers essais infructueux, mêlant l'aléatoire aux coefficients arbitraires (certains trouvant des résultats après plus de cent mille mouvements), je me suis penché sur des algorithmes de plus court chemin tels que le A*. Au final j'en suis arrivé à un algorithme à base d'une liste de priorité et de parcours en profondeur. L'ordre des noeuds dans la liste est déterminé par la distance de Manhattan (taxicab) à laquelle on ajoute le nombre de mouvements qui nous ont permis d'en arriver là (plus on utilise de mouvements, et plus la grille est couteuse à obtenir).

func SolvePuzzle(shuffledGrid Grid, solvedGrid Grid) ([]Coords, error) {
  var coords []Coords

  node := Node{0, TaxicabWithValues(shuffledGrid, solvedGrid), shuffledGrid, coords}
  var openList []Node
  openList = AddToPriorityList(openList, node)

  for len(openList) > 0 {
    openList, node = RemoveFromPriorityList(openList)

    if reflect.DeepEqual(node.Grid, solvedGrid) {
      return node.Moves, nil
    }

    possibleMoves, _ := ListMovableTiles(node.Grid)
    for _, coords := range possibleMoves {
      neighboorGrid, _ := Move(node.Grid, coords)
      neighboorNode := Node{node.Cost + 1, node.Cost + 1 + Taxicab(neighboorGrid, solvedGrid), neighboorGrid, append(node.Moves, coords)}

      openList = AddToPriorityList(openList, neighboorNode)
    }
  }

  return coords, errors.New("No solution found")
}

Limites

L'algorithme mis en place n'est pas assez bon. Il résoud certes des problématique simples avec des cases déplacées jusqu'à 25 fois (ce qui correspond à peu près à ce que l'on pourrait faire à la main lorsque l'on joue). Malheureusement, dès lors que cette étape est dépassée, il est beaucoup trop coûteux pour trouver une solution.

Après une démonstration à l'équipe il a été décidé d'augmenter la durée des développements d'une journée afin de mettre en place une nouvelle solution. Il s'agit désormais d'appliquer un algorithme de plus court chemin sur des petites parties de graphe, et d'avancer ainsi pas à pas jusqu'à trouver la solution.

Chaque itération se déroulera de la manière suivante :

• Extraire un sous graphe d'une profondeur donnée calculable (soit une combinaison de X mouvements à l'avance)
• Déterminer dans ce sous graphe la séquence de coups donnant le meilleur résultat à l'aide de cet algorithme
• Sauvegarder cette sous séquence
• Recommencer jusqu'à obtenir une solution

Contraintes de temps

Cependant, l'utilisateur n'a pas forcément besoin d'une solution complète. En effet, tout ce qu'il souhaite est un conseil permettant de l'approcher de la solution à un instant donné. C'est la raison pour laquelle, et sur les conseils de mes collègues, j'ai ajouté une contrainte de temps. Il s'agira désormais de construire un graphe aussi complexe que possible durant X secondes, puis de retourner à l'utilisateur la meilleure solution dans ce petit graphe. De plus, il faudra désormais parcourir l'arbre en largeur plutôt qu'en profondeur. L'intérêt est de permettre de ne pas négliger des possibilités en s'engouffrant trop vite dans une mauvaise direction.

Si le sujet vous intéresse, n'hésitez pas à lire l'article de Julien sur le développement d'un bot pour jouer au reversi.

Le nouvel algorithme est donc un peu différent :

• Extraire un sous graphe pendant X secondes
• Déterminer dans ce sous graphe la séquence de coups donnant le meilleur résultat
• Retourner à l'utilisateur la meilleure solution relative

Jouer à travers le web

Pour finir la dernière tâche importante de la semaine fut de mettre en place une API exposant trois routes simples. Cela permettra par la suite de créer des clients web exploitant ce projet.

On retrouvera donc les routes new, move et suggest qui permettent, comme leur nom l'indique, de créer un puzzle, de déplacer une case et de suggérer le meilleur coup.

func Server(port int) {
  r := mux.NewRouter()
  r.Headers("Content-Type", "application/json")
  r.HandleFunc("/new", New).Methods("GET")
  r.HandleFunc("/move", Move).Methods("POST")
  r.HandleFunc("/suggest", Suggest).Methods("GET")

  server := &http.Server{
    Handler:      r,
    Addr:         fmt.Sprintf(":%d", port),
    WriteTimeout: 15 * time.Second,
    ReadTimeout:  15 * time.Second,
  }
  server.ListenAndServe()
}

À ce stade, la plus grosse difficulté fut d'adapter les données issues du jeu en GO afin qu'elles soient compatibles avec le web. La majeure partie du coeur du jeu utilise en effet des bytes, alors que les fonctions pour extraire les données des requêtes demandent des entiers.

Bilan

Personnel

Tout comme la précédente, cette semaine fut vraiment très intéressante. J'ai eu la chance de découvrir le langage GO qui m'a beaucoup rappelé mes débuts en informatique. J'y ai retrouvé des notions bas niveau tels que les pointeurs et le typage fort. J'ai également pu refaire de l'algorithmie et de la gestion de graphes lors de mes recherches sur la sugestion de coups. Je pense que pour cette dernière partie le GO est très adapté lors de l'écriture d'une solution finale de par son optimisation pointue. Malheureusement, je l'ai trouvé compliqué à manier en phase de recherche notamment à cause de ses règles très strictes de compilation (difficile d'ajouter de l'affichage à la volée, ou de commenter des parties de code).

En ce qui concerne les méthodologies, j'ai malheureusement encore un peu de mal à travailler en TDD, c'est-à-dire de d'abord penser aux tests et seulement ensuite au code. Cela doit devenir un réflexe et je dois éviter de faire les tests rétroactivement. De plus, je dois penser à faire des tâches plus courtes pour publier plus souvent des commits. Je trouve néanmoins assez compliqué de le faire lorsque l'on fait de la recherche.

Enfin, j'apprécie beaucoup l'entraide au sein de l'équipe. Mes collègues m'ont souvent demandé où j'en étais, n'ont pas hésité à me donner des pistes de réflexion lorsque j'étais bloqué.

15-puzzle-go

Au total, mes développements m'ont donc amené à réécrire totalement le jeu et je suis assez content d'avoir pu introduire des notions de programmation événementielle. Leur intégration a rendu le jeu vraiment plus fluide pour l'utilisateur qui peut désormais bouger les pièces du puzzle à l'aide des flèches du clavier.

La suggestion du meilleur coup est le plus gros point faible de cette semaine. Elle fonctionne très bien pour des grilles pas trop mélangées, et ne fonctionne plus du tout à partir d'environ 20-25 permutations. Soit l'algorithme a prouvé ses limites et il faut en changer, soit il est nécessaire de faire des optimisations.

La semaine prochaine sera consacrée à la création d'une version du jeu jouable dans un navigateur web à l'aide de Symfony. Il ne s'agira cependant pas de tout réécrire, mais d'utiliser le moteur de jeu en GO grâce à l'API développée.

Le code source du jeu est bien entendu disponible sur GitHub marmelab/15-puzzle-go. N'hésitez pas à le reprendre et à l'améliorer =).