Un jeu d'Othello dans le terminal avec Python

Premier jour chez Marmelab et me voilà (déjà) exposé à des défis tous aussi stimulants, ambitieux et enrichissants les uns que les autres.

Au sommaire de mes 5 premières semaines d'intégration au sein des équipes, le jeu d'Othello (Reversi pour nos amis anglophones). Le but étant de développer chaque semaine un projet dans une technologie qui m'est inconnue, dans un temps réduit et en fournissant un résultat fonctionnel autour de ce célèbre jeu de société.

Mon premier projet n'échappe pas à la règle ! Le challenge étant de développer un jeu d'Othello entièrement jouable dans un terminal et tout cela en Python et en moins de 4 jours !

Le jeu d'Othello

Pour ceux qui ne connaissent pas encore le jeu d'Othello, il s'agit d'un jeu inventé 1971 au Japon sur les bases d'un jeu Anglais appelé "Reversi". Il est d'ailleurs régulièrement nommé "Reversi" par respect du Copyright.

Les règles sont assez simples. Il s'agit de remplir une "matrice" (8*8) appelée "Othellier" à l'aide de pions à deux faces (blanc / noir). Une couleur est attribuée à chaque joueur, le gagnant étant celui qui possède le plus de cases à la fin de la partie.

A chaque placement de pion, l'ensemble des pions de la couleur adverse situés entre le pion placé et un autre pion de cette même couleur sont retournés, dans toutes les directions (horizontales, verticales et diagonales) possibles sur la matrice.

Malgré son aspect simple en surface, le jeu d'Othello constitue un vrai défi d'un point de vue algorithmique, et notamment d'intelligence artificielle. Dès 1976, de nombreux programmes sont développés afin de concurrencer les humains à ce jeu; le premier programme de bon niveau étant "MAX" de Rob Phillips. Programme à partir duquel je vais peut-être pouvoir m'inspirer pour mon prochain défi, développer une IA fonctionnelle entièrement en Golang !

Python, un langage insoupçonné

Premières lignes de code, premières impressions.. L'image que je me faisais du langage Python était entièrement biaisée. Non seulement, c'est loin d'être un langage de niche, mais en plus, il introduit des notions et des types de données (sets, lists, tuples, dicts, ...) que je n'avais pas du tout l'habitude de convoiter en PHP où presque tout est "array".

J'ai même eu l'occasion de me retrouver dans de nombreux principes de la philosophie du langage. Plusieurs aphorismes ont d'ailleurs été énoncés par "Tim Peters", un grand contributeur de l'écosystème Python, afin de définir ces principes. Parmi ceux-ci, je retiendrais:

• Explicit is better than implicit.
• Simple is better than complex.
• Complex is better than complicated.
• Flat is better than nested.
• Readability counts.
• If the implementation is hard to explain, it's a bad idea.

Source: The Zen of Python

Contrairement à mes appréhensions, l'utilisation stricte de l'indentation n'est pas un frein au développement. Après quelques minutes, cela devient tout à fait naturel, et beaucoup plus facile à lire. De plus, ça incite à factoriser d'avantage pour ne pas "sur-imbriquer" notre code.

Coté performance, il serait difficile de donner des chiffres compte tenu de l'envergure du projet. Néanmoins, le langage est utilisé par de nombreux gros projets et entreprises avec une forte nécessité en terme de performances. On peu ainsi citer Google, la NASA, Blender pour la partie scripting, ... (source)

Si je devais faire le rapprochement avec un autre langage plus familier, ce serait le Ruby. En effet, c'est un langage interprété, rapide, portable, sa syntaxe est concise et lisible, il a tout pour plaire !

Passons à la pratique

Chez Marmelab, un projet n'est viable que s'il répond à certaines règles aussi simples que précises, c'est ce que j'ai appris dès les 15 premières minutes après mon arrivée.

Tout d'abord, un projet doit obligatoirement posséder un Makefile. Non seulement cela permet à n'importe qui d'installer et de tester rapidement un projet peu importe sa connaissance du fonctionnement; mais en plus, il est toujours possible de travailler sur ce même projet même après plusieurs mois.. Je me suis donc attelé à la tâche en créant un Makefile permettant d'installer, de lancer, de tester et de valider la syntaxe du code à travers pep8, un linter qui implémente les règles du Python Enhancement Proposals.

Comme vous pouvez le voir, j'ai également entièrement "containerisé" le programme à l'aide d'une image Docker officielle pour Python 3. Comme précisé dès le départ, je devais pouvoir être en mesure de fournir à n'importe quel "testeur" un environnement semblable à celui de mon poste de développement. Une expérience très enrichissante à laquelle je m'adonnerais volontié lors de mes futurs développements !

Ensuite, me voilà lancé dans le développement. Je commence à créer l'ensemble des fichiers de jeu ("board.py", "game.py", "cell.py", ...) et écrire mes première lignes de code et là.., stupeur, je ne parviens pas à lier mes modules entre eux, mais pourquoi donc ?

Après une petite entrevue avec mon collègue référent, j'apprends que les dossiers où sont situés les fichiers doivent posséder un fichier nommé "__init__.py" pour être découverts par le système de modules. Malgré cette petite anicroche, je reste tout de même séduit par le système de module de Python, à la fois très loin du système de namespaces de PHP mais très proche de celui d'ES6 (sans la notion d'export).

from .cell import new_cell, get_symbol, TYPE_WHITE, TYPE_BLACK, TYPE_EMPTY
from .matrix import new_matrix, draw_cells, get_size as get_matrix_size
from .vector import get_directionnal_vectors, get_vector_add_generator

Premiers commits, premières pull requests, je reçois instantanément mes premières remarques. La plupart des remarques portent sur de petits détails. Surpris, je continue aveuglément à développer sans prendre toute l'importance d'une seule parmi celles-ci.

Plus tard, et le programme quasi abouti, voici venu le temps des tests, me voici donc au pied du mur, j'ai inclus le plus gros de la logique dans une classe, rendant les tests unitaires (un peu) plus difficiles. Je fais donc le choix de sortir l'ensemble de ma logique de la classe et de donc de profiter pleinement du système de module fourni par Python.

Résultat, une grosse perte de temps, la réécriture de plusieurs méthodes, mais surtout un code beaucoup plus clair et qui suit les principes du paradigme fonctionnel. Ce refactoring m'a égalemment permis de déceler de nombreuses petites erreurs qui étaient quasi invisibles lorsque noyées dans la masse de la classe. C'est là que la citation "diviser pour mieux régner" prend tout son sens..

Pour remettre les pieds dans le plat, voici l'algorithme le plus important du jeu, mais aussi celui qui m'a pris le plus de temps à développer. Cette méthode permet de récupérer les pions (nommés "cells") retournés en fonction du plaçage d'un pion sur l'Othellier.

def get_flipped_cells_from_cell_change(matrix, cell):
    """ Return a set of flipped cells from cell change """

    flipped_cells = []
    empty_cell = new_cell(0, 0, TYPE_EMPTY)
    xPos, yPos, cType = cell['x'], cell['y'], cell['type']

    if not get_matrix_cell(matrix, xPos, yPos, empty_cell)['type'] is TYPE_EMPTY:
        return []

    # Loop over all possibles directions (except null vector)
    for vector in get_directionnal_vectors():
        vector_add_generator = get_vector_add_generator((xPos, yPos), vector)
        vector_flipped_cells = []

        # While there's no empty cell, same color disk or border, go forward
        for (x, y) in vector_add_generator:
            if get_matrix_cell(matrix, x, y, empty_cell)['type'] in [TYPE_EMPTY, cType]:
                break
            vector_flipped_cells.append(new_cell(x, y, cType))

        # If the're flipped disks and last cell has same type, it's ok
        last_cell = get_matrix_cell(matrix, x, y, empty_cell)
        if len(vector_flipped_cells) > 0 and last_cell['type'] is cType:
            flipped_cells += vector_flipped_cells

    return flipped_cells

Pour chaque direction (Nord, Nord Est, ... respectivement représentées par des vecteurs (0, 1), (1, 1), ...) autour du pion qui est placé, nous allons parcourir toutes les cellules dans cette même direction qui ne sont pas de la même couleur que le pion placé. Si la dernière cellule rencontrée est de la même couleur, nous pouvons donc ajouter les cellules retournées à un tableau global et parcourir les autres directions...

A la fin de la méthode, tous les pions qui changeront de couleur sont retournés par la méthode. Si le nombre de pions retournés est supérieur à 0, nous pouvons considérer le coup comme valide et donc proposer le choix à l'utilisateur.

Et voici le rendu final du jeu, dans le terminal seulement dans un premier temps.

Et après ?

Un programme n'est jamais terminé. Et pour preuve, me voici déjà déterminé à faire évoluer le jeu à partir de mes propres réflexions mais également de celles de mes collègues.

Parmi les pistes d'amélioration discutées et retenues, nous avons:

• Introduire une immutabilité générale du "board" (Othellier) pour plus de testabilité
• Ne pas introduire de calculs inutiles en appliquant une Mémoïsation sur la méthode principale de calcul du jeu
• Améliorer les performances générales en passant au préalable une matrice de convolution sur le "board" pour construire une "matrice" virtuelle plus petite et moins coûteuse en calculs
• Refactoriser d'avantage certaines fonctions
• ...

Conclusion

Si je devais résumer cette première expérience en quelques mots, ce serait "Découverte", "Bonnes pratiques" et "Qualité". En effet, en plus d'avoir découvert un nouveau langage, j'ai eu la chance de bénéficier d'un regard externe sur mes développements à travers un PR Reviewing rapide et ainsi d'apprendre sur les exigences qualité de l'entreprise (tests unitaires, code linting, codage KISS / DRY, workflow de gestion des sources...) auxquelles je n'étais pas du tout habitué.

Le rythme de développement sur ces 4 jours fut assez intense. Néanmoins, avec plus de réflexion en amont, j'aurais facilement gagné du temps. Au total, 6 pull requests ont été créées pour une moyenne de 1.5PR par jour. Avec une meilleure "découpe" de mon travail, il y aurait eu d'avantage de PRs et cela aurait été beaucoup plus facile pour mes reviewers de suivre l'avancement du projet; point sur lequel je vais devoir appliquer d'avantage d'efforts pour la suite.

Par ailleurs, l'ambiance propice au partage de connaissances et de sources m'a permis d'être plus impliqué et source d'ingéniosité dans ma façon de développer.

Si je devais recommencer, je penserais fonctionnel avant de penser objet, je développerais des tests unitaires avant de développer (TDD) et surtout je penserais à mes collègues de PR Review avant de commiter la moindre modification et de surcharger le dépôt.

Histoire à suivre dans le prochain épisode, le développement d'une IA en GO, langage plus bas niveau qui m'est totalement inconnu (et tant mieux) !

Note: Pour les plus curieux d'entre vous, le code source du jeu est disponible sur Github: marmelab/reversi.py