Le jeu du Taquin en python

Cette série d'articles retrace mon parcours d'intégration au sein de Marmelab qui s'articule autour du jeu du Taquin.

Chez Marmelab, tout commence par la présentation d'un jeu au nouvel arrivant : pour moi, ce sera le Taquin. Sur mon bureau, un ordinateur portable et des grilles de jeu (mélangées ou dans l'ordre). Après un rapide tour des locaux, j'apprends que toute mon intégration sera tournée autour de ce jeu. Tout y passera, des premiers programmes en ligne de commande à la création d'IA afin de résoudre des grilles.

Présentation du jeu du Taquin

Historique

Tout d'abord, laissez-moi vous présenter le Taquin. Connu en anglais sous le nom de 15 Puzzle, le taquin est un jeu simple inventé dans les années 1870 aux États-Unis. Noyes Palmer Chapman, un receveur des postes de Canastota (état de New York), est probalement à l'origine du jeu, bien que le célèbre créateur de jeu Sam Loyd en ait lui aussi réclamé la paternité.

Les règles du jeu

Dans sa version traditionnelle, le jeu se présente sous la forme d'une grille carrée de 16 cases (4 x 4). Quinze d'entre elles contiennent une séquence de chiffres, ou plus souvent une image découpée. La dernière case est, quant à elle, vide.

Le principe est simple : une fois les pièces mélangées, il suffit de faire glisser les cases une à une afin de reformer le puzzle original.

Des puzzles parfois insolubles

Tous les puzzles ne sont malheureusement pas résolvables. Parmi les puzzles de 16 cases, il n'en existe en effet que 10 461 394 944 000 dont il est possible de trouver une solution, soit la moitié de factorielle 16.

Sam Lyod avait lui proposé 1000$ à quiconque trouvait la solution à un puzzle dont les cases 14 et 15 étaient inversées. Bien entendu, personne n'a jamais réclamé la récompense puisqu'un tel puzzle n'est pas soluble.

Un jeu qui fait des émules

Célèbre depuis les années 1970, le Rubik's cube est l'un des fiers descendants du Taquin. La principale différence consiste en son aspect 3d.

La création du jeu

Première semaine et donc premier projet autour du Taquin. Il s'agira pour cette fois de réaliser le jeu en Python et en ligne de commande. Par ailleurs, j'apprends vite que le temps est limité puisque je n'ai que 4 jours et demi avant la démonstration à toute l'équipe.

Gestion du projet en mode agile

Chez Marmelab, tous les projets sont gérés à l'aide des méthodes agiles, si bien que toute la vie de l'entreprise s'articule autour d'elles. Ma première tâche fut donc de rencontrer le product owner (PO) afin qu'il me présente ses attentes. Ce dernier représente le client du projet et c'est lui qui aura la tâche de valider ou non le travail réalisé.

Cette réunion d'introduction nous a permis de fixer ensemble le périmètre du projet. Le PO m'a d'abord listé les tâches qu'il avait imaginées sous forme de récits (user story en anglais). Ce mode de présentation a pour intérêt de mettre en avant les besoins de l'utilisateur et ce que va vraiment lui apporter la fonctionnalité. Après en avoir discuté ensemble, j'ai pu estimer leur durée approximative une par une, ce qui a permis au PO de les prioriser.

Exemple de récit

As Tom, I want to make a move

Pour gérer le projet, j'utiliserai Trello. Ce logiciel est comparable à un tableau à plusieurs colonnes dans lesquelles on peut déplacer des post-it représentant les tâches à effectuer. Il s'agit d'un outil de communication important qui permet de visualiser l'avancée du projet au jour le jour.

Il est intéressant de faire un parallèle ici avec le logiciel de gestion des sources : GitHub. Lors du développement, une carte doit correspondre à une pull request (PR). Lorsque la pull request est terminée, je déplace la carte dans la colonne Effectué (Done). Une fois le code validé par des collègues en charge de la revue de code (code review), le PO la valide à son tour côté utilisateur et la déplace dans la colonne Validé (Validated).

Le langage Python

En arrivant chez Marmelab, je ne connaissais de Python que le nom. J'ai donc eu la chance de le découvrir par la meilleure façon qu'il soit : la pratique.

Pour faire simple, Python est un langage dont la syntaxe est assez légère. A la différence des langages auxquels j'étais habitué, il s'articule autour du principe d'indentation.

Exemple de code python

if tile_to_move not in movable_tiles(puzzle):
  raise TileNotMovableException

Ce langage est souvent utilisé pour apprendre l'informatique. En effet, il peut se lire de manière très litérale, un peu comme si on lisait de l'anglais.

Ainsi, l'exemple précédent peut se comprendre aisément par la phrase suivante :

Si la case à déplacer n'est pas dans les cases déplaçables, alors tu dois générer une erreur.

L'environnement technique

L'environnement technique de ce projet a été imposé par le client. Il est assez classique pour un projet Marmelab et a pour avantage d'être sensiblement le même sur l'ensemble des projets de l'entreprise. Cela facilite bien entendu la cohérence entre tous les projets.

Makefile

Le Makefile permet de lancer des commandes indépendamment des spécificités du projet. Ainsi un projet développé en Javascript comportera les mêmes commandes qu'un projet Python.

Le fichier comporte les instructions suivantes :

make          # Affiche les commandes disponibles
make install  # Installe le projet (compilation, dépendances)
make run      # Lance le projet
make test     # Lance les tests
make lint     # Lance le linter

Docker

Docker a pour objectif d'encapsuler le projet dans un conteneur virtuel de manière à s'affranchir des spécificités des machines physiques. De manière plus concrète, j'utilise pour ce projet python3. Grâce à Docker, les personnes qui souhaient jouer au jeu n'auront pas besoin d'installer python3 sur leur machine. Tout ce qu'elles auront à faire ce sera de télécharger le Docker correspondant au projet. Je me suis basé naturellement basé sur l'image officielle de Python 3.

Travis

Travis permet d'automatiser le lancement des tests et du linter à chaque fois qu'une PR est publiée sur GitHub. Cela permet de s'assurer que tout est toujours rétro compatible (dans la mesure où les tests sont bien écrits).

Linter PEP8

Le linter permet de s'assurer que la syntaxe du code source est respectée. Chaque langage a ses propres règles. Nous nous sommes ici basés sur les règles définies par PEP8.

Architecture du projet

Le projet s'articule autour de deux modules Game et Renderer. Selon le principe agile, cette architecture n'a pas été décidée à l'origine. Elle est issue de besoins liés aux tests unitaires et à la modularité du code, qui sont apparus au cours de la semaine.

project/
  src/
    game/
    renderer/

Le premier module contient l'ensemble des algorithmes qui permettent, une fois combinés les uns aux autres, de jouer au jeu. On y retrouve ainsi des fonctions pour générer des grilles, pour déplacer des cases ou encore pour mélanger le jeu.

# La méthode de mélange
def shuffle(grid, timeout=1):
    shuffle_thread = ShuffleThread(grid.copy())
    time_thread = Timer(timeout, shuffle_thread.stop)

    shuffle_thread.start()
    time_thread.start()

    shuffle_thread.join()

    return shuffle_thread.result()

Le second concerne l'affichage et l'ensemble des fonctions de rendu graphique. Sa fonction la plus compliquée et qui a fait l'objet des plus grands débats est celle d'affichage d'une grille. Le rendu console ressemble à ça :

Démo : interface et gameplay

Après ces quelques jours de développement rythmés par des présentations régulières de l'avancement, j'ai effectué une démonstration à l'ensemble de l'équipe. Celle-ci, avec l'écriture de cet article, marque la fin de ce premier projet d'intégration.

Vous trouverez ci-dessous deux gif présentant l'interface. Mais comme rien ne vaut un vrai test, n'hésitez pas à lancer le jeu chez vous en le téléchargeant sur GitHub : marmelab/15-puzzle-cli.

PS : l'interface est un peu différente, il s'agit d'une capture prise au cours de la semaine.

PS2 : je triche un peu pour gagner plus rapidement, ne me jugez pas :D.

Bilan

Personnel

Cette semaine fut riche en apprentissages, tant au niveau technique que méthodologique. J'ai ainsi eu la possibilité de découvrir un langage que je ne connaissais pas : python, avec des outils que je n'avais que peu utilisé : Docker, Makefile, GitHub, et suivant une méthodologie agile (user stories, revue de code, test first, daily standup meeting).

Note à moi même : travailler la communication en pensant à présenter plus souvent mon travail au PO afin d'avoir directement des retours.

15-puzzle-cli

Le bilan des développements à l'issue de cette première semaine est assez positif. En effet, j'ai pu aboutir à une version jouable du Taquin. Cependant, celle-ci est loin d'être parfaite et on peut s'en rendre compte simplement en y jouant.

Pour l'heure, l'intérêt d'en avoir fait un jeu vidéo est un peu limité puisque la majorité du travail a été consacré à la reproduction de l'existant. La valeur ajoutée consiste surtout dans les fonctions de mélange automatique et de changement de taille à la volée.

Cependant, il s'agit d'une base sur laquelle ajouter de nombreuses fonctionnalités. Et c'est en parcourant le backlog du projet que l'on peut s'en rendre compte. On peut en effet imaginer développer une IA de suggestion des prochains coups afin d'aider des personnes à résoudre plus facilement le puzzle. On peut même inventer de nouvelles règles telle qu'une version sans bordure qui permettrait peut être de rendre un plus grand nombre de puzzles solubles.

La prochaine étape sera de réaliser le jeu en Go, en ajoutant cette fois-ci des suggestions de déplacement et bien d'autres choses.

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