Découverte du langage Go pour ma deuxième semaine d'intégration : Go Go Quarto Ranger !

Après avoir fourni une interface console en Python pour jouer au Quarto à deux, le nouvel objectif de ma phase d'intégration est maintenant de produire une IA capable de jouer au Quarto contre le joueur, et assez douée pour le battre. Il devra s'agir d'une API écrite en langage Go. Cela permettra d'y connecter, dans un premier temps, la console Python. Puis de bâtir des interfaces plus attractives en continuant à s'appuyer sur la même IA.

Golang, un langage particulier

Après une assez longue expérience de développement web, j'ai déjà été confronté à la fois à la rigueur des langages typés et compilés (avec C#), et à la souplesse des langages prototypés et interprétés (avec JavaScript). Mais là, Go pousse la rigueur à son maximum.

Un typage (très) fort

Juste après avoir expérimenté Python, le gap est énorme. Ici chaque variable et chaque retour de fonction doivent être impérativement typés.

func GetPiecesRaw(x int, y int, grid [][]int) []int {
	return grid[y]
}

Le typage implicite à la déclaration existe tout de même et sera même largement utilisé :

newGrid := [][]int{} // [ := ] nous dispense de préciser le type à la déclaration de la variable

De plus il n'existe pas de mécanisme de Cast ou de conversion implicite comme on en trouve dans la plupart des langages. Chaque conversion de type doit être codée explicitement.

strconv.Itoa(node.State.Piece) // La fonction de conversion int vers string, un allié fidèle

Pas d'opérateur ternaire

Certains concepts évidents sont absents de la grammaire de go. L'exemple qui m'a le plus frappé est l'absence d'opérateur ternaire

childNode.Value = childNode.MyNode ? WinningLeafValue : LoosingLeafValue // Ceci n'existe pas en go

L'opération doit s'écrire toujours en syntaxe conditionnelle complète

if (childNode.MyNode) {
    childNode.Value = WinningLeafValue
} else {
    childNode.Value = LoosingLeafValue
}

Aucune variable orpheline

Si une variable ou un module est déclaré mais jamais utilisé, alors le programme ne compilera pas. Ça n'a l'air de rien, mais en cours de développement, la contrainte est monumentale.

A chaque fois que l'on veut ajouter un point de debug, il faut importer la librairie fmt pour la sortie standard, écrire les logs. Et une fois fait, il faut tout supprimer. Et recommencer à chaque fois, pour chaque fichier ou on veut avoir du log.

C'est usant. On se réconforte en sachant que lorsque le programme est lancé, le code n'est pas seulement juste, il est également propre.

Les goroutines

Le langage go a été conçu à l'origine pour la programmation système. Il est donc particulièrement indiqué pour gérer les programmes concurrents. Pour cela, il faut utiliser la notion de goroutine avec le mot clé go.

go func() {
    // Le code concurrent ici.
}()

La goroutine permet d'exécuter du code en parallèle un peu comme des threads. Mais un thread n'est pas forcément généré pour chaque goroutine. Le système réparti le code exécuté automatiquement en fonction de la topologie de la machine.

La grosse spécificité d'une goroutine, c'est qu'elle ne peut pas être killed ou aborted par du code extérieur. Elle seule peut décider de s'arrêter. Il faut pour cela implémenter un chan qui permettra de communiquer des données à travers plusieurs goroutines, et ainsi déclencher des évènements à l'intérieur d'une goroutine.

//On déclare les chan pour transférer les informations en amont
//Déclaration d'un chan pour transférer l'information en cas de timeout
stoppedchan := make(chan bool)
//Déclaration d'un chan pour transférer la grille de jeu générée si succès
statechan := make(chan state.State)
//Déclaration du chan d'arret de la routine
quit := make(chan struct{})

//Goroutine à exécuter en parallèle (ici un timer)
go func() {
    time.Sleep(time.Second * time.Duration(secondNumber))
    //Le timer a aboutit avant la fin du calcul, c'est un timeout
    stoppedchan <- true
    //Récupération de la grille (égal a currentState en cas de timeout)
    statechan <- currentState
}()

//Récupération des données lorsqu'elles seront affectées
minMaxStopped := <-stoppedchan
newState := <-statechan
close(quit)

Des particularités appréciées

C'est cette rigueur et cette gestion orientée "code concurrent" qui font de go un langage à part. Dans notre contexte, le gain que le projet Quarto peut en tirer est faible, mais il existe tout de même.

Les goroutines vont pouvoir servir à mettre en œuvre un algorithme de minimax pour notre IA, de façon distribuée, et à implémenter un mécanisme d'arrêt si la profondeur de l'arbre des possibles prend trop de temps à calculer.

Une IA pour jouer au quarto: l'algorithme du minimax

Principes

Le concept de base est simple : chaque état du jeu possède un coût. Plus sa valeur est faible, plus le joueur a de chances de gagner.

La méthode consiste à construire un arbre représentant les états successifs de la partie avec toutes les combinaisons possibles. Puis à attribuer une valeur aux feuilles de l'arbre. Plus la situation représentée par la feuille est favorable au joueur, plus sa valeur est faible.

• Une victoire vaudra 0.
• Une défaite vaudra 100 (maximum à définir arbitrairement)

Ensuite, on attribue les valeurs aux branches en parcourant l'arbre à l'envers.

• Si c'est c'est notre tour, la branche vaut le minimum de ses enfants.
• Si c'est le tour de l'adversaire, la branche vaut le maximum de ses enfants.

À son tour, l'IA va alors construire son arbre, et jouer le coup correspondant à la branche de plus faible valeur (situation la plus favorable).

Application au jeu du Quarto

Appliqué à notre jeu, cet algorithme va générer plusieurs difficultés.

• Notre arbre va atteindre une taille monumentale.

Un tour de jeu se divise en deux étapes :

1. Placement d'une pièce parmi 16 cases (en début de partie)
2. Sélection d'une pièce parmi 15 pièces restantes (en début de partie)

La cime de l'arbre en début de partie va donc avoir 16 * 15 = 240 enfants

Ce nombre décroit progressivement à chaque niveau avec la diminution des pièces restantes. Et de plus, le nombre maximum de tours est limité au nombre de pièces, soit 16. Mais notre arbre complet atteint tout de même la valeur monumentale de centaines de quadrillons de nœuds. (Pour comparer, le nombre de combinaisons du loto n'est que de 14 millions)

Note : Il y a une petite particularité à prendre en compte au premier tour, ou le joueur ne fait que sélectionner une pièce ; et au dernier tour, ou le joueur ne fait que placer une pièce.

Ce tableau simplifié ne prend pas en compte les nœuds gagnants ou perdants. Qui sont finaux et n'ont normalement plus d'enfants. Mais même en les intégrant, l'échelle de valeur reste du même ordre de grandeur.

La machine dont je dispose n'est pas en mesure de calculer une telle quantité de combinaisons dans un temps acceptable pour le joueur. (ni même dans un temps acceptable pour un être humain).

C'est une situation courante avec minimax. On essaie généralement de calculer un maximum de combinaisons, sans réussir à prendre en compte la totalité. Il faut juste être en mesure d'attribuer une valeur à un instant t de la partie, selon si la disposition des pièces est plus ou moins favorable au joueur.

• L'évaluation d'un état intermédiaire de la partie est très subjective.

Dans ce jeu, l'ensemble des ressources est partagé entre les joueurs. Il n'y a pas d'opposition blanc contre noir comme dans la plupart des jeux de ce type (Dames, Echecs), mais à la place chaque joueur peut gagner avec les pièces qui l'arrangent au moment de son tour.

La conséquence, c'est qu'une situation très défavorable pour le joueur peut aussi bien être considérée comme très favorable selon le point de vue qu'on choisit d'adopter. Et pour un état donné du plateau (exemple : Alignement de 3 carrés blancs), les deux joueurs ont exactement les mêmes chances d'en tirer profit lorsque leur tour débute.

Une petite analogie partielle avec les Echecs permet de mieux comprendre la difficulté.

Considérons une fin de partie : Le joueur A manipule les pions noirs. Il met le roi Blanc en échec. La situation est alors très favorable au joueur A. Puis c'est au joueur B de jouer. La situation est donc très défavorable au joueur B.

Considérons maintenant la même situation avec notre problématique de ressources partagées du Quarto. Le joueur A met le roi "Blanc" en échec. La situation est alors très favorable au joueur A. Puis c'est au joueur B de jouer. La situation est alors très favorable également pour le joueur B. C'est possible car le roi "Blanc" n'appartient ni au joueur A, ni au joueur B, mais simplement au joueur dont c'est le tour.

Au cours du développement, il n'a d'ailleurs pas été possible de trouver une méthode pertinente d'évaluation des feuilles avant d'atteindre un statut de victoire ou de défaite. Il a donc fallu trouver d'autres astuces pour construire notre IA.

Structuration de l'IA

Une API standard

L'IA se présente sous la forme d'une API très simple, ne possédant qu'une seule route.

Route "SuggestMove" :

[POST] http://myQuartoServer/suggestMove

• Elle prend en entrée un état du jeu (Grille remplie et prochaine pièce choisie).
• Elle retourne le nouvel état du jeu après avoir joué un tour.

Etat du jeu :

{
    "Grid":
    [
        [4,5,1,3],
        [0,0,0,0],
        [9,7,10,0],
        [0,0,0,0]
    ],
    "Piece":2,
    "Move":[0,2]
}

Le fait de retourner la grille complète a permis de faire des appels successifs très rapides en mode IA contre IA et d'évaluer facilement la qualité du jeu réalisé.

Le mouvement effectué est tout de même retournée à part pour éviter aux clients de l'API d'avoir à effectuer, à chaque tour, un différentiel entre la grille fournie, et la grille reçue pour connaître le pion qui à bougé.

Application de règles de jeu par des fonctions dédiées

Pour combler la difficulté à mettre en œuvre un algorithme de minimax efficace, j'ai décidé de coder des fonctions logiques permettant au programme d'appliquer des règles de jeu en fonction de différentes situations.

En simplifiant, les règles sont réparties en plusieurs groupes :

• Le mode de jeu gagnant (M0)
• Le mode de jeu "intelligent" (M1)
• Le mode de jeu défensif (M2)
• Le mode de jeu aléatoire (M3)

A chaque étape le programme applique successivement les fonctions des quatre groupes, jusqu'à obtenir un résultat. De cette façon, dans le meilleur des cas, le programme a fait un mouvement efficace, dans le pire des cas, il a fait un mouvement aléatoire. Mais dans tous les cas, il est capable de jouer un tour.

Exemple de fonctionnement pour placer une pièce :

Tentative de mise en œuvre de minimax

Au-dessus des fonctions "basiques", il restait à mettre en place le minimax. Le principe choisi est le suivant :

• Lancer dans une première goroutine la méthode de construction et d'évaluation de l'arbre des possibles qui renvoie un nouvel état de jeu.
• Lancer dans une seconde goroutine un timer de quelques secondes qui renvoie un état vide une fois arrivé à terme.

    stoppedchan := make(chan bool)
	statechan := make(chan state.State)
	quit := make(chan struct{})

	go func() {
		time.Sleep(time.Second * time.Duration(secondNumber))
		stoppedchan <- true
		statechan <- currentState
	}()

	go func() {

		tree := InitAllTree(currentState, piecesList, boxList, quit)
		bestState := ChooseBestChildState(tree)

		stoppedchan <- false
		statechan <- bestState
    }()

La première des goroutines qui aboutit demande à l'autre de s'éteindre. Si le programme a reçu une action de jeu, il la retourne comme résultat. Sinon, il exécute le système de fonctions dédiées pour obtenir un résultat "dégradé" à la place.

Un programme perfectible mais pas si bête

Au terme du sprint, la première partie concernant les fonctions dédiées permettait de retourner un résultat correct. Mais la partie minimax n'a pas pu être finalisée dans les temps. Je suis passé par plusieurs problèmes sans obtenir leur résolution complète.

• Le lancement du minimax provoquait une saturation du processeur entrainant un "freeze" total de la machine serveur
• Les interactions entre goroutines ont été un peu laborieuses à mettre en œuvre correctement.
• Finalement, le timeout se déclenchait systématiquement avant le résultat du minimax.

Mais la partie "dégradée" de l'IA fournit déjà une expérience de jeu correcte. Le bilan est mitigé, Le potentiel du minimax laissé inachevé laisse un arrière-goût de frustration, mais la capacité actuelle de l'IA est déjà très satisfaisante.

Nous n'en resterons de toute façon pas là, puisque cette partie a ensuite pu être complétée lors des sprints suivants de mon intégration.

Au terme de ce sprint, la seule interface pour jouer était l'interface console en Python de mon précédent projet

Les articles dédiés aux prochains sprints en diront plus sur le sujet. (Notamment avec la création d'interfaces web agréables)

N'hésitez pas à consulter l'état actuel du projet