Reversi bot: Go et Symfony en action

Second challenge dans les équipes de Marmelab. Cette fois ci, il est question de conçevoir un jeu d'Othello faisant intervenir une intelligence artificielle développée en GO. Le jeu doit être jouable dans Facebook Messenger à travers un bot.

Ce post portera donc sur deux projets intimement liés que sont le développement d'une IA en Golang et la mise en place d'un serveur de bot Facebook Messenger sous Symfony 3.

Principes et pré-requis

Comme dans tout projet, il a été nécessaire d'établir un état des lieux avant de réellement commencer à développer. Je me suis donc atteler à définir l'architecture la plus adaptée au projet et à chercher les différents outils de développement qui me seraient utiles.

Infrastructure du projet

Contrairement à mon projet de jeu dans le terminal, il est question d'échanger avec l'API Facebook messenger à travers un système de Webhook. "Webhook" est le nom commun donné à des actions de callback généralement en HTTP, protocole stateless par nature. Il a donc été nécessaire d'introduire de la persistance au jeu à travers la mise en place d'une base de données.

Docker fournit un système pour lier des containers (docker-compose), permettant ainsi de construire de véritables architectures. Voici une schéma de l'architecture de services du projet.

Comme vous pouvez le voir, il s'agit d'une architecture web classique faisant intervenir un container de serveur HTTP (nginx), un container de serveur php-fpm (ici en version 5.6) et un container de serveur de base de données.

Le container du serveur d'IA en GO est externe à l'architecture de docker-compose afin de conserver toute son indépendance, il est appelé de manière classique (HTTP GET) à travers l'ouverture d'un port entre les deux plateformes.

Outils de développement

Cela faisait très longtemps que je n'avais pas eu l'occasion de travailler avec des services externes nécessitant l'accès à mon poste de développement depuis internet (cf webhook). Je me suis donc mis à la recherche de solutions afin de pouvoir exposer à Facebook une url à laquelle ils puissent m'appeler.

Parmi les pistes envisagées avant de trouver le Saint Graal, nous avions:

• Déploiement de mon code sur un serveur externe à chaque test (approche plutôt moyenâgeuse, longue à mettre en place et pas vraiment efficace..)
• Déploiement de mon code sur un service Paas type Heroku (git push heroku master... et c'est déployé. Plus rapide mais tout aussi archaïque)
• Plusieurs idées saugrenues de redirection de port sur un serveur externe... Enfin, rien de bien simple à mettre en place

Sur les conseils de mes collègues, j'apprends qu'un service existe pour répondre à cette problématique, Ngrok !

Ngrok permet d'exposer un serveur local directement sur internet à travers un tunnel sécurisé. L'utilisation est super simple, il suffit d'une commande dans le terminal pour générer instantanément une url d'accès sur le web (en http et en https).

De plus, Ngrok fournit également une interface web en local permettant de suivre les échanges avec le serveur ciblé mais également de rejouer des actions HTTP ! Autant dire que c'est l'outil parfait pour travailler avec des webhooks.

Organisation

Comme précisé en introduction, le projet est scindé en deux parties distinctes. L'une étant le serveur de bot sous Symfony 3, l'autre étant l'intelligence artificielle développée en Golang.

Dans les deux cas, des choix organisationnels ont étés fait afin de trouver un équilibre entre complexité et évolutivité.

Serveur de bot sous Symfony

Connaissant déjà le framework Symfony (dans sa version 2) depuis plusieurs années, le véritable défi dans le développement du serveur de bot fut d'imaginer une architecture suffisamment souple pour répondre à ma décision d'appliquer un architecture DDD et de prévoir l'avenir en donnant la possibilité de pouvoir ajouter d'autres plateformes de messagerie (Slack, Skype, ...).

Pour cela, j'ai commencé par séparer toute ma logique métier dans un dossier "reversi" de la logique propre à l'implémentation dans un dossier "AppBundle". A mon sens, la principale caractéristique d'une séparation des responsabilités réussie est la possibilité de pouvoir changer de Framework facilement (ex: passer de Laravel à Symfony...).

Quand à l'architecture logique du jeu, suffisamment souple pour permettre l'ajout de nouvelles plateformes, elle se décompose ainsi:

• Un contrôleur propre à la plateforme (ici Facebook).
• Un contrôleur de jeu (appelé GameContextHandler)
• Un écouteur sur les événements du jeu propre à la plateforme (toujours Facebook ici)

Le contrôleur de la plateforme est chargé de transformer la requête entrante du webhook (message utilisateur...) en un ValueObject appelé "GameContext" et qui contient l'identité de la personne (id et plateforme) et son message.

Le contrôleur de jeu, lui, est chargé d'analyser le "GameContext" (voir s'il existe déjà une partie, si le message est valide, ...) et de dispatcher des événements (actions du type ACTION_FINISH, ACTION_SHOW_BOARD, ...).

Voici par exemple la portion de code du "GameContextHandler" chargée d'initialiser une partie si elle n'existe pas et que la personne a tapée "othello" ou bien d'afficher un message d'accueil et la board si la personne a voulu commencer un partie.

<?php
    ...
    $playerToken = $context->getPlayerToken();
    if (!($game = $this->manager->get($context))) {
        if (strtolower($context->getMessage()) !== 'othello') {
            $this->dispatcher->dispatch(GameEvents::ACTION_EXPLAIN_START, new GameEvent($playerToken));
            return;
        }
        $game = $this->manager->create($context);
        $this->dispatcher->dispatch(GameEvents::ACTION_WELCOME, new GameEvent($playerToken, $game));
        $this->dispatcher->dispatch(GameEvents::ACTION_ASK_FOR_POSITION, new GameEvent($playerToken, $game));

        return;
    }

Le dernier maillon de la chaîne est l'écouteur d'événements du jeu. Il est chargé pour une plateforme particulière de répondre à des actions de jeu. Par exemple pour Facebook, il s'agira d'appeler en POST l'API messenger à l'aide de la librairie Guzzle afin d'envoyer un message de bienvenue à une personne ayant voulu initialiser une partie (en tapant "othello").

Vous trouverez l'ensemble du code disponible sous licence MIT à l'url suivante: https://github.com/marmelab/reversi-sf

Intelligence artificielle en GO

A l'occasion de ce projet, j'ai eu l'occasion de découvrir pour la toute première fois le langage Golang (GO pour les intimes).

Go fournit nativement une pléthore de fonctionnalités bas niveau avec la facilité de développement d'un langage de haut niveau. C'est un langage compilé, il est typé, il possède un garbage collector et il est très très performant ! Autant dire, que pour un développeur PHP tel que moi, le dépaysement est quasi total.

Mais pourquoi avoir choisi ce langage ? D'accord, il est performant mais ça ne fait pas tout ? Comment mettre le langage au profit des performances de mon IA ? Ces différentes questions m'ont permis de remettre en cause mon développement et de re-structurer mon code.

En effet, dans le cas d'un jeu à sommes nulles comme ici, appliquer une intelligence artificielle consiste à parcourir toutes les possibilités de jeu à partir d'un état (board à un instant T) tout en appliquant un algorithme MinMax. Le but étant de minimiser le score de l'adversaire et de maximiser le score de l'AI et par conséquent, choisir le coup le plus adécquat.

Dans un premier temps, j'avais développé mon exploration de l'arbre en DFS (Depth First Search), ce qui revient à explorer récursivement toute une branche avant d'explorer les branches voisines. J'avais appliqué une limite de profondeur à cette exploration de branche afin de ne pas prendre trop de temps pour explorer l'ensemble des branches.

Or, ce que l'on demande à une intelligence artificielle, ce n'est pas de déterminer le meilleur coup selon une profondeur limite, mais bien en un temps déterminé. Cependant, en faisant intervenir une limite de temps plutôt qu'une limite de profondeur, je prenais le risque de ne pas avoir le temps de parcourir toutes les branches en largeur.

Sur les remarques de mes collègues, je refactorise mon code afin de transformer l'exploration en BFS (Breadth First Search). Ce type d'exploration permet d'explorer un arbre en largeur, étage par étage, sans prendre le risque de perdre des possibilités si l'exploration doit s'arrêter (temps maximum écoulé). Dans un même temps, je décide de profiter un maximum des fonctionnalités offertes par le langage et d'explorer l'arbre de façon distribuée.

Nativement, go fournit un système de "threads allégés" appelés des Goroutines. Associées aux Channels (sortes de queues asynchrones permettant d'échanger des informations avec des Goroutines), les goroutines fournissent un outils parfait pour l'exploration asynchrone d'arbres.

Ci-dessus l'architecture mise en place, elle fait intervenir les éléments suivants.

• Des "Visitors" (goroutines chargées de parcourir l'arbre et d'empiler des noeuds à scorer)
• Des "Scoring Workers" (goroutines chargées de calculer les scores à partir des noeuds provenant de la file de noeuds)
• Un "Aggregator" (fonction chargée d'aggréger les scores afin de retourner le meilleur coup trouvé à la fin du temps imparti)

Voici une portion de code qui permet de réellement cerner le fonctionnement du système de "temps limite imparti".

func GetBestCellChangeInTime(currentBoard board.Board, cellType uint8, duration time.Duration) (cell.Cell, error) {

	nodes := make(chan Node, 100)
	scores := make(chan Scoring)
	timeout := make(chan bool, 1)

	go func() {
		time.Sleep(duration)
		timeout <- true
	}()

	// Visit nodes and calculate associated scores
	...

	return CaptureBestCellChange(scores, timeout), nil

}

func CaptureBestCellChange(scores chan Scoring, stopProcess chan bool) cell.Cell {

	finished := false

	for !finished {
		select {
		case finished = <-stopProcess:
		case scoring := <-scores:
			// Aggregate scores
			...
		}
	}

	// Return aggregate result
}

Comme vous pouvez le voir, nous utilisons ici une "chan" de type booléen à laquelle nous ajoutons la valeur "true" (via une goroutine asynchrone) après le temps défini par "duration".

Durant ce temps, la méthode "CaptureBestCellChange" agrége les scores jusqu'à ce que le timeout survienne. À cet instant, elle retourne le résultat de son aggrégation. Afin de mettre en place ce mécanisme, le système de select de Go est utilisé. Il permet de mettre en place une sorte d'écouteur sur plusieurs channels sous la forme d'un "switch".

Malgré le soin appliqué à l'architecture, il subsiste quelques problèmes quand à la méthode d'aggrégation utilisée mais également sur le nombre de Goroutines concurrentes qui explose et qu'il faudrait limiter. Un refactoring de ces deux points est prévu prochainement.

Les sources du projet son disponibles ici. En dehors de l'AI, le projet permet également de jouer à Othello dans le terminal.

Go et Symfony, duo gagnant ?

Au final, on obtient comme prévu un jeu d'Othello entièrement jouable sur Facebook Messenger. Bien que l'API Facebook Messenger ne soit pas tout à fait destinée au développement de jeux (faute au temps de latence des webhooks), elle tient correctement ses promesses.

Quand à Symfony, il joue son rôle, bien qu'un framework plus léger aurait fait le même travail. Ici, seuls Doctrine ORM, le système de routing, l'injection de dépendances et le dispatcher ont étés utilisés. D'autres librairies externes à Symfony telles que Guzzle et Image Intervention (de Laravel) ont respectivement été utilisées comme client HTTP et générateur d'image de la board d'Othello.

Conclusion

Pour conclure, je dirais que ces deux projets ont étés source d'étonnement mais aussi de découverte. Bien qu'il soit développé par Google, go est entièrement Open-Source et très performant, ce qui fait de lui le langage tout indiqué pour le développement d'une IA. Je suis certain qu'il fera ses preuves sur de très gros projets dans les années qui viennent.

Quand à Facebook, comme toujours, ils mettent à disposition des développeurs des outils simples et faciles à appréhender. Leur API est très facile d'utilisation et très fournie (Templates, Quick replies, ... presque tout est possible). Je suis impatient de découvrir une autre de leurs technologies la semaine prochaine; le célèbre framework de développement mobile natif, React Native.

Concernant l'organisation de ces projets et notamment du projet sous Symfony, j'ai été agréablement surpris par la facilité avec laquelle il est possible de travailler avec un binôme, même à distance. Les pulls reviews et les conseils de mes mentors ont toujours étés très rapides et efficaces. Cela en partie grâce à la Stack utilisée (Slack, Hangouts et Github) qui permet de répondre à tous les besoins.

Enfin, je tiens à dire que ça a été un véritable plaisir de travailler avec des technologies telles que le langage Golang ou l'API Facebook messenger. En plus d'apprendre un nouveau langage, cela m'a permis d'imaginer de nombreuses applications que je ne tarderais pas de développer dès que le temps m'en donnera l'occasion.