Jouer seul à Quixo grâce à un bot en Golang

Cet article relate ma troisième semaine d'intégration chez Marmelab.

Durant mes deux premières semaines chez Marmelab, j'ai pu développer une app Python & une app Symfony permettant de jouer à Quixo à 2 ! L'objectif de cette semaine sera de pouvoir jouer à Quixo seul contre l'ordinateur. L'ordinateur devra être le plus compétant possible à Quixo !

Comme les semaines précédentes, les technologies me sont imposées. Je devrai donc développer cette IA en Go.

Suivi de projet

Pour ce projet, le suivi du projet sera légèrement différent des semaines précédentes. Il y aura toujours un Product Owner et un tuteur pour m'accompagner, mais cette fois, mon tuteur ne sera pas dans nos locaux, mais à Caen ! Chez Marmelab, nous avons deux collègues en télétravail. Travailler avec un collègue à distance fait donc partie du processus d'intégration.

Je devrai donc veiller à bien documenter le projet, mes Pull Requests ainsi que les cartes sur Trello. Ça permettra à mon tuteur de tester rapidement mes développements sans avoir besoin de me demander de précisions et de risquer une réponse tardive.

L'environnement

Je suis désormais assez à l'aise avec les outils de Marmelab et je les utiliserai pour les projets des semaines à venir. Ils permettent une arrivée rapide sur un projet et un confort de développement sympathique. Je les ai déjà explicité dans mes deux derniers articles.

Grâce aux Makefiles et à docker chacun des projets que je développerai s'installera et s'exécutera de la même façon : make install & make start.

Architecture

Le but de mon IA est de proposer le meilleur coup possible à un moment T et il sera appelé par d'autres applications. Après réflexion et discussion avec mon tuteur, nous décidons des composants nécessaires :

• Un serveur d'API.
• Un simulateur permettant de jouer un cube.
• Un scoreur renvoyant le score du jeu pour un joueur.

Voici l'arbographie attendue :

quixo-ia/
├─ main
├─ server
├─ simulation
└─ scorer

Dans un premier temps, le simulateur se contentera de me renvoyer le meilleur coup à jouer en fonction du plateau de jeu à un moment T. C'est-à-dire sans prendre en compte les prochains coups à jouer. Si le temps me le permet, je devrai faire en sorte que le simulateur calcule le meilleur coup à jouer en prenant en compte tous les potentiels coups qui en découlent, mais avec une limite de "réflexion" de 30 secondes.

Développement

La structure de données

J'ai déjà entendu parler du langage Go, mais je n'ai pas encore pris le temps de m'y essayer. Cette semaine va donc me permettre de découvrir un nouveau langage !

Après avoir étudié la documentation et la syntaxe du langage, j'implémente la structure de donnée suivante :

type Coords struct {
	X int
	Y int
}

type Cube struct {
	Coords Coords
	Value  int
}

type Board struct {
	Grid          [][]int
	CurrentPlayer int
	SelectedCube  Cube
}

Elle est similaire à la structure que j'ai choisie en PHP ; un plateau de jeu représenté par un tableau à 2 dimensions, un joueur et un potentiel cube sélectionné.

En implémentant la fonction me renvoyant un Board, je rencontre ma première surprise concernant le Go : un attribut d'une structure ne peut être nul (nil, en Go). En effet, lorsque j'instancie une partie d'un moment T, il peut y avoir, ou non, un cube séléctionné. Si il n'y a pas de cube séléctionné, Go va tout de même instancier un SelectedCube avec des valeurs par défaut. Malheureusement, les coordonnées par défaut seront (0, 0) qui sont des coordonnées possibles. Je dois donc gérer ce cas. Pour ça, je décide d'utiliser des coordonnées impossibles dans mon cas qui représenteront un cube sélectionné : (-1, -1). Voici le résultat :

func GetBoardWithNoCubeSelected(grid [][]int, player int) Board {
	return Board{
		Grid:   grid,
		Player: player,
		SelectedCube: Cube{
			Coords: Coords{X: -1, Y: -1},
		},
	}
}

func GetBoard(grid [][]int, player int, selectedCube Cube) Board {
	return Board{grid, player, selectedCube}
}

func hasCubeSelected(board game.Board) bool {
	return board.SelectedCube.Coords.X > -1 && board.SelectedCube.Coords.Y > -1
}

Le Serveur

Je dois réaliser un serveur avec une seule route. Pour ça j'utilise la bibliothèque net/http intégrée à Go :

import (
	"net/http"
)

const port int = 8001

func Start() {
	http.HandleFunc("/best-move", bestMove)
	http.ListenAndServe(":"+strconv.Itoa(port), nil)
}

func bestMove(w http.ResponseWriter, r *http.Request) {
	board := getBoardFromRequest(r) // Parse body and return Board struct
	bestMove := simulation.GetBestMoveForPlayer(board)
	sendResponse(w, bestMove)
}

Le serveur est donc très simple grâce à cette bibliothèque.

Le scorer

Pour le scorer, je fais quelque chose de simple et rapide : le score d'un plateau de jeu est égal au maximum de la somme des symboles alignés. C'est-à-dire que je calcule le nombre de symboles alignés sur chaque ligne, colonnes et diagonales et je renvoie le maximum. De cette façon, je m'assure que l'IA se rapprochera toujours de la victoire.

Cependant, cette fonction est grandement améliorable et je me laisse la possibilité de revenir dessus s'il me reste du temps. Voici quelques améliorations que je pourrais apporter :

• Prise en compte du nombre de symboles.
• Prise en compte de la position des symboles.

Simulation

Maintenant que mon scorer est implémenté, je peux passer à la partie simulation. Le but est de jouer tous les coups et de récupérer leur score. Le meilleur coup à jouer sera celui avec le meilleur score.

Dans un premier temps, je décide de me limiter aux coups possibles sur un seul tour. Le résultat est très simple :

func GetBestMove(
	board game.Board,
) Move {
	movables := game.GetMovablesCubes(board)
	bestMove := Move{}
	bestScore := 0
	for i := 0; i < len(movables); i++ {
		destination, score := getBestDestinationWithScore(board, movables[i])

		if score > bestScore {
			bestScore = score
			bestMove = Move{
				CoordsStart: movables[i].Coords,
				CoordsEnd:   destination,
			}
		}
	}
	return bestMove
}

L'IA est désormais fonctionnelle, je peux faire une partie de Quixo seul. Cependant, le challenge n'est pas au rendez-vous. Elle pourrait gagner contre un joueur débutant, mais son manque d'anticipation se fait ressentir et le meilleur coup que l'IA jouera est facilement prévisible.

Pour éviter ça, je dois faire en sorte que l'IA puisse "réfléchir" sur plusieurs coups. Il faut tout de même garder la contrainte d'un temps de calcul de 30 secondes pour récupérer le meilleur coup.

Pour anticiper ça, je calcul le nombre de mouvements possible sur N tours. Voici le calcul :

Il y a 16 cubes (maximum) déplaçable, chacun ayant 3 destinations possibles. Sur un tour il y a donc 16*3 soit 48 mouvements possible. Donc sur N tours il y a 48^(N) coups possible. Le nombre de possibilités augmente donc exponentiellement. À partir de 6 coups le nombre de possibilités est supérieur à 1 milliard !

Mais certains mouvements donneront un plateau identique à un autre mouvement, je pourrai donc les recouper et ainsi diminuer le nombre de coup à explorer.

Pour implémenter cela, j'utiliserai une structure en arbre. Le noeud racine représente la situation à partir de laquelle on recherche le meilleur coup. Ses descendants seront les plateaux résultant des déplacements qui eux-mêmes auront des descendants etc.

Pour créer et parcourir l'arbre, je crée une structure Noeud avec 3 paramètres :

• L'ancètre du noeud
• Le plateau de jeu
• Le score de ce plateau
• Le mouvement réalisé pour arriver à ce plateau

En go :

type Node struct {
	Ancestor *Node
	Board    game.Board
	Score    int
	Move     Move
}

Je stockerai ensuite les noeuds ayant le score maximal (représentant la victoire) dans un tableau. Je parcoure ensuite les ancêtres de chacun de ces noeuds pour déterminer le coup ayant le plus de potentiel de victoire.

Les goroutines

Pour explorer le plus de possibilités dans le temps imparti, je vais utiliser des goroutines. Les goroutines permettent de paralléliser des tâches en créant une nouvelle routine. Les routines communiquent avec la fonction qui les a créées grâce à des channels. Cela me permettra de multiplier le nombre de possibilités explorées par le nombre de coeurs disponibles sur ma machine.

Voici le résultat :

func GetAllWinnablesBoardNode(board game.Board) []BoardNode {
	timeStart := time.Now()
	nodes := []BoardNode{{
		Board: board,
		Score: scorer.GetBoardScore(board),
	}}
	leaves := []BoardNode{}
	for time.Now().Sub(timeStart).Seconds() < 30 { // J'explore toutes les possibilités pendant 30 secondes

		var wg sync.WaitGroup
		nodesChannel := make(chan BoardNode, len(nodes)*16*3) // Création du channel d'une taille égal au maximum de coups possibles

		for _, node := range nodes { // Pour chaque noeud je crée une routine
			wg.Add(1)
			go MakeAllMovesForBoard(nodesChannel, node, &wg) // Création de la routine qui renverra les noeuds des coups possibles pour ce noeud
		}
		wg.Wait() // Synchronisation des routines (J'attend la fin d'éxécution de chacune des routines)

		close(nodesChannel) // Fermeture du channel

		nodes = []BoardNode{}

		for node := range nodesChannel { // Parcourt des noeuds présent dans le channel
			if node.Score == 5 { // Si c'est un noeud représentant un coup gagnant, je le stock
				leaves = append(leaves, node)
			} else { // Sinon je continue d'explorer cette possibilité
				nodes = append(nodes, node)
			}
		}
	}
	return leaves
}

J'ai trouvé le fonctionnement des routines assez simple et bien documenté. Cependant, cette fonction crashait au bout d'une dizaine de secondes, car le nombre de routines créées était bien trop important pour ma machine. Pour régler ça, je peux limiter le nombre de routine exécutées en parallèle. Malheureusement, je ne dispose plus d'assez de temps pour ça. Je limite donc le temps de recherche à 5 secondes.

Première expérience sur GO : mon ressenti

Dans l'ensemble, je trouve que GO est un langage assez confortable avec un typage fort qui m'a permis d'éviter certains bugs. De plus il était parfaitement adapté à mon cas d'utilisation. La création de routine est un outil puissant et plutôt simple d'utilisation comparé aux threads de Java, C ou Python.

En ce qui concerne mon intégration, c'est la première fois que je me suis retrouvé confronté à un langage inconnu. J'ai donc dû commencer par lire un peu de documentation. J'ai également dû me tourner vers l'équipe plusieurs fois pour leur demander des conseils ou pour m'aider à comprendre un peu mieux Go.

Bien que je n'ai pas eu le temps d'optimiser la recherche du meilleur coup, la démo de cette semaine s'est bien déroulé. J'ai pû lancer une partie contre l'IA et toute l'équipe s'est associée contre l'IA. Nous avons réussi à la vaincre, non sans difficulté ! Voici le résultat :

Comme d'habitude le code est disponible sur GitHub. La semaine prochaine, je devrai développer une API en NodeJS qui sera consommée par une application mobile en React Native !