Mise en place pour l'IA

Ajul – étape 7

1. Introduction

Cette étape a pour but de rédiger quelques classes qui seront utiles pour écrire l'« intelligence artificielle », qui sera le sujet de l'étape suivante et qui permettra de jouer à Ajul contre l'ordinateur.

2. Concepts

Pour mettre en œuvre notre « intelligence artificielle », nous utiliserons un algorithme connu sous le nom de Monte Carlo Tree Search, abrégé MCTS et parfois traduit en recherche arborescente Monte Carlo.

Comme nous le verrons à l'étape suivante, pour déterminer quel coup jouer, cet algorithme construit une partie de ce que l'on appelle l'« arbre de jeu », qui représente la manière dont une partie d'Ajul peut évoluer à partir d'un état donné. MCTS essaie de ne construire que la partie de l'arbre de jeu correspondant aux coups qui semblent prometteurs. Pour déterminer quels sont ces coups, il simule un grand nombre de parties durant lesquelles les joueurs jouent (presque) aléatoirement, et utilise les points qu'ils obtiennent ainsi pour évaluer leurs coups.

Les sections suivantes expliquent donc ce qu'est l'arbre de jeu, comment MCTS fait jouer les joueurs quasi-aléatoirement, et comment il évalue leurs coups.

2.1. Arbre de jeu

L'arbre de jeu (game tree) est une représentation des différentes manières dont une partie d'Ajul peut évoluer à partir d'un état donné. Les nœuds de cet arbre représentent les différents états possibles de la partie, tandis que ses arêtes — les flèches reliant les nœuds entre eux — représentent les coups qui peuvent être joués pour passer d'un état à un autre.

Par exemple, admettons qu'il ne reste plus qu'un coup à jouer dans une partie d'Ajul, car la seule source non vide est la zone centrale, et elle ne contient qu'une tuile, de couleur A ; de plus, à la fin de la manche courante, un joueur aura rempli une ligne de son mur, mettant ainsi fin à la partie. Admettons également que le joueur qui doit jouer le dernier coup ne puisse placer la tuile de la zone centrale que sur trois destinations différentes de son plateau : la ligne de motif 1, la ligne de motif 5, ou la ligne plancher. En d'autres termes, ce joueur doit choisir quel coup jouer parmi les trois valides à sa disposition, qui sont :

  1. prendre la tuile de couleur A de la zone centrale et la déposer sur la ligne de motif 1, qui se note 0A1 en utilisant la notation compacte des coups décrite à la §3.3 de l'étape 6,
  2. prendre la tuile de couleur A de la zone centrale et la déposer sur la ligne de motif 5, qui se note 0A5,
  3. prendre la tuile de couleur A de la zone centrale et la déposer sur la ligne plancher, qui se note 0A0.

L'arbre de jeu qui correspond à cette situation est illustré à la figure 1 ci-dessous.

game-tree;16.png
Figure 1 : Exemple d'arbre de jeu en fin de partie

Le nœud à la racine de l'arbre, nommé « état 1 », correspond à l'état décrit plus haut, celui dans lequel il ne reste plus qu'un coup à jouer. Ses enfants, c.-à-d. les nœuds nommés « état 2 » à « état 4 », correspondent aux trois états suivants possibles, dans lesquels la partie est terminée.

Cet arbre de jeu pourrait être utilisé par le joueur courant à l'état 1 pour décider quel coup jouer. Par exemple, s'il constate que :

  • dans l'état 2, son score final est de 43 points et il remporte la partie,
  • dans l'état 3, son score final est de 45 points et il remporte la partie,
  • dans l'état 4, son score final est de 37 points et il arrive en seconde position,

alors il serait logique qu'il décide de jouer le coup 0A5 afin d'arriver à l'état 3 et de remporter la partie en maximisant ses points.

Bien entendu, dans le cas général, choisir quel coup jouer ne peut pas se faire simplement en construisant l'arbre de jeu et en regardant quel coup donne le meilleur résultat, pour deux raisons :

  1. l'arbre de jeu est souvent beaucoup trop grand pour être construit en totalité,
  2. les coups joués par les adversaires sont inconnus, et il est par conséquent impossible de savoir avec certitude comment se terminera une partie.

Néanmoins, beaucoup d'algorithmes d'« intelligence artificielle » construisent en tout cas partiellement un arbre de jeu, et c'est le cas de MCTS, comme expliqué ci-après.

2.2. Arbre de jeu MCTS

L'algorithme MCTS sera décrit en détail à l'étape suivante, mais il convient déjà de savoir que son idée centrale est de ne construire que partiellement l'arbre de jeu, en se focalisant sur les coups qui semblent les plus prometteurs. Pour déterminer si un coup est prometteur, MCTS simule un grand nombre de parties durant lesquelles ce coup est joué, afin de se faire une idée du nombre de points qu'il pourrait rapporter à son auteur.

Dès lors, notre mise en œuvre de MCTS devra mémoriser, pour chaque coup de l'arbre de jeu (partiel) qu'elle construira, les informations suivantes :

  • le nombre de parties incluant ce coup qui ont été simulées jusqu'à présent,
  • la somme des points qui ont été obtenus à la fin de ces parties par l'auteur du coup.

En combinant ces deux informations, il lui sera possible de déterminer la moyenne des points qu'un coup peut rapporter à son auteur.

Comme ces informations sont associées aux coups, et que les coups correspondent aux arêtes de l'arbre de jeu, il serait logique de les stocker dans les arêtes. Toutefois, étant donné que chaque nœud a exactement une arête « entrante » — à l'exception de la racine, qui n'en n'a aucune — il est aussi possible de stocker les informations associées à une arête dans son nœud « d'arrivée ». C'est la solution que nous adopterons dans ce projet, et à un nœud de notre arbre de jeu seront donc associés les attributs suivants :

  • ses éventuels enfants,
  • le coup de l'arête entrante,
  • le nombre de parties incluant ce coup simulées jusqu'à présent,
  • la somme des points obtenus à la fin de ces parties par l'auteur du coup.

Pour mémoire, les enfants d'un nœud sont les nœuds qui correspondent aux états qu'il est possible d'atteindre depuis lui en jouant un coup valide. En pratique, afin de réduire la taille de l'arbre de jeu, nous ne considérerons que les enfants correspondants aux coups valides et uniques.

Notez que les nœuds de notre arbre de jeu MCTS ne contiennent pas l'état de la partie auquel ils correspondent. Cela n'est pas strictement nécessaire, car cet état peut toujours être recalculé en partant de l'état initial — celui de la racine — et en rejouant les coups se trouvant sur le chemin menant à un nœud pour connaître l'état qui lui correspond. C'est ce que nous ferons afin d'économiser la mémoire qui devrait sinon être utilisée pour stocker, dans chaque nœud, l'état du jeu qui lui correspond.

2.2.1. Priorité des nœuds

Comme nous l'avons dit plus haut, MCTS ne construit que partiellement l'arbre de jeu, en se focalisant sur les nœuds qui semblent les plus prometteurs. Pour ce faire, MCTS part de la racine de l'arbre de jeu partiel qu'il construit et commence par trouver quel enfant de la racine est le plus prometteur. Si cet enfant a lui aussi des enfants, la recherche se poursuit avec son enfant le plus prometteur à lui. Et ainsi de suite.

MCTS doit donc pouvoir déterminer lequel des enfants d'un nœud est le plus prometteur. Pour ce faire, il choisit celui ayant la priorité maximale, la priorité \(P(n)\) d'un nœud \(n\) étant donnée par : \[ P(n) = \begin{cases} \frac{S(n)}{N(n)} + C\sqrt{\frac{2\ln N(p)}{N(n)}}&\textrm{si }N(n) > 0\\ +\infty&\textrm{sinon} \end{cases} \] où \(S(m)\) est la somme des points obtenus par l'auteur du coup associé au nœud \(m\) à la fin des parties simulées depuis lui, \(N(m)\) est le nombre de parties simulées, et \(p\) est le nœud parent de \(n\). Quant à \(C\), il s'agit d'une constante que nous avons fixée à 80, cette valeur semblant empiriquement donner de bons résultats pour Ajul.

Les deux termes de la formule permettant de calculer \(P\), qui peut paraître compliquée au premier abord, ont chacun un but différent :

  • le premier, \(S(n)/N(n)\) — qui n'est autre que la moyenne des points obtenus lors des parties durant lesquelles le coup correspondant au nœud \(n\) a été joué — a pour but d'augmenter la priorité des nœuds prometteurs, c.-à-d. rapportant en moyenne beaucoup de points,
  • le second, \(\sqrt{\cdots}\), a pour but d'augmenter la priorité des nœuds à partir desquels peu de parties ont été simulées par rapport à leurs frères.

Autrement dit, le premier terme a pour but d'encourager ce que l'on appelle souvent l'« exploitation » (ici des coups prometteurs), tandis que le second a pour but d'encourager l'« exploration » (ici des coups encore peu évalués). La constante \(C\) nous permet de choisir à quel point encourager l'exploration au détriment de l'exploitation.

2.2.2. Représentation empaquetée

Afin d'économiser de la mémoire, nous représenterons les attributs des nœuds de notre arbre de manière partiellement empaquetée, en stockant :

  • le coup (empaqueté, donc occupant 10 bits) et le nombre de parties simulées \(N\) dans un premier attribut de type int,
  • la somme des points obtenus \(S\) dans un second attribut de type int.

Cette représentation nous permet de simuler au maximum 222 parties — soit plus de 4 millions — pour décider quel coup jouer, ce qui est largement suffisant. En pratique, notre mise en œuvre n'en simulera jamais plus de 100 000.

2.3. Sélection des coups

Dans la description plus haut, nous avons affirmé que l'algorithme MCTS simule des parties durant lesquelles les joueurs jouent de manière quasi-aléatoire. Concrètement, cela signifie que lors de ces simulations, l'algorithme partitionne l'ensemble des coups valides qu'un joueur peut jouer en trois sous-ensembles contenant :

  1. les coups qui remplissent totalement une ligne de motif, c.-à-d. dont les tuiles jouées remplissent exactement les cases encore vides de la ligne de motif choisie comme destination, sans aucune tuile excédentaire,
  2. les coups qui ne remplissent que partiellement une ligne de motif,
  3. les autres coups.

Ensuite, si le premier sous-ensemble n'est pas vide, alors un des coups qu'il contient est choisi aléatoirement pour être joué. Sinon, si le second sous-ensemble n'est pas vide, alors un des coups qu'il contient est choisi aléatoirement pour être joué. Sinon, un des coups du dernier sous-ensemble, qui en contient forcément un, est choisi aléatoirement pour être joué.

Il faut noter que ce choix de coup peut être mis en œuvre de manière élégante au moyen de la technique d'échantillonnage par réservoir décrite à la §2.2.2 de l'étape 2. En effet, pour choisir le coup à jouer on peut créer 3 réservoirs d'une capacité de 1 élément chacun, utilisés pour stocker l'élément actuellement retenu de chacun des trois sous-ensembles. Une fois ces réservoirs créés, les coups valides sont parcourus et chacun d'eux est ajouté au réservoir correspondant au sous-ensemble auquel il appartient. Lorsque tous les coups ont été parcourus, celui contenu dans le premier réservoir non vide est choisi.

2.4. Classement des joueurs

Nous avons dit précédemment que l'algorithme MCTS utilise les points obtenus par les différents joueurs à la fin des parties simulées aléatoirement pour évaluer les coups qu'ils ont joué. Cela n'est toutefois pas rigoureusement exact, car ce qui est encore plus important que les points pour un joueur d'Ajul est la position qu'il occupe dans le classement final. Il est en effet préférable de remporter une partie avec 50 points que de la perdre avec 60 points.

Dès lors, notre mise en œuvre de MCTS utilisera une notion particulière de points, qui combinera la position des joueurs dans le classement final et leurs points effectifs. Il importe donc de savoir comment classer les joueurs à la fin d'une partie d'Ajul.

Selon les règles, le vainqueur d'une partie d'Ajul est le joueur ayant le plus grand nombre de points à la fin de la partie. Lorsque deux joueurs (ou plus) ont le même nombre de points, le nombre de lignes horizontales complètes dans leur mur est utilisé comme second critère pour tenter de les départager. Si deux joueurs (ou plus) ont le même nombre de points et le même nombre de lignes horizontales complètes dans leur mur, alors ils sont ex æquo.

En d'autres termes, à la fin d'une partie d'Ajul, on peut établir la liste des joueurs triés par ordre décroissant de leur nombre de points (premier critère) et du nombre de lignes horizontales complètes dans leur mur (second critère). Une fois cette liste établie, on peut l'utiliser pour déterminer le rang (rank) de chaque joueur, qui vaut :

  • le rang de son prédécesseur dans la liste, s'il en a un et que son nombre de points et de lignes horizontales complètes dans le mur sont identiques à ceux de ce prédécesseur,
  • son index dans la liste sinon.

Par exemple, admettons qu'à la fin d'une partie à quatre joueurs (P1 à P4) :

  • P1 ait 45 points et 3 lignes horizontales complètes,
  • P2 ait 55 points et 2 lignes horizontales complètes,
  • P3 ait 55 points et 1 ligne horizontale complète,
  • P4 ait 55 points et 2 lignes horizontales complètes.

La liste des joueurs, triée par ordre décroissant de leurs points/nombre de lignes horizontales, est soit [P2,P4,P3,P1], soit [P4,P2,P3,P1]. Dès lors, les joueurs P2 et P4 ont le rang 0 (vainqueurs ex æquo), P3 a le rang 2 et P1 a le rang 3. Notez bien qu'aucun joueur n'a le rang 1 dans cet exemple.

3. Mise en œuvre Java

Cette étape est la première de la seconde partie du projet, durant laquelle vous serez plus libres et moins guidés que durant la première.

En particulier, vous avez maintenant le droit de modifier ou augmenter l'interface publique des classes et interfaces proposées, pour peu bien entendu que vous ayez une bonne raison de le faire. Pour faciliter la correction, nous vous demandons néanmoins de respecter les noms de paquetages et de classes, interfaces, enregistrements et types énumérés donnés.

D'autre part, nous nous attendons à ce que vous lisiez et compreniez la documentation des parties de la bibliothèque Java que vous devez utiliser.

3.1. Classe MctsNode

La classe MctsNode du sous-paquetage mcts, publique et finale, représente un nœud de l'arbre de jeu construit par l'algorithme MCTS. Elle possède trois attributs :

  • un de type int contenant le coup empaqueté (10 bits) et le compteur de parties simulées \(N\) (22 bits),
  • un de type int contenant le nombre total de points \(S\),
  • un de type MctsNode[] contenant les enfants du nœud.

Comme d'habitude les deux premiers attributs sont privés, mais pour faciliter les choses, le dernier est visible dans tout le paquetage mcts (package-private). De cette manière, il pourra être librement modifié par l'algorithme MCTS, donc le code se trouvera dans le même paquetage mais dans une classe séparée. De plus, cet attribut sera toujours null à la construction d'un nœud. Il ne sera initialisé que plus tard, par l'algorithme MCTS, lorsqu'il décidera que les fils du nœud méritent de faire partie de l'arbre de jeu.

MctsNode n'offre pas de constructeur public, mais les deux méthodes fabriques suivantes :

  • une nommée p. ex. newRoot qui permet de créer une nouvelle racine, qui n'a aucun coup associé, un nombre total de points \(S\) valant 0, un compteur de parties simulées \(N\) valant 1, et un tableau d'enfants valant null,
  • une nommée p. ex. newMoveNode qui prend en argument un coup empaqueté et retourne un nœud ayant ce coup associé, un nombre total de points \(S\) et un compteur de parties simulées \(N\) valant 0, et un tableau d'enfants valant null.

La raison pour laquelle la racine a initialement un compteur de parties simulées valant 1 est expliquée dans les conseils de programmation plus bas.

En plus de ces méthodes fabriques, MctsNode offre :

  • des méthodes d'accès permettant d'obtenir :
    • le coup empaqueté de l'arête menant au nœud, nommée p. ex. pkMove,
    • le compteur de parties simulées du nœud, nommée p. ex. gameCount,
    • le nombre total de points, nommée p. ex. totalPoints,
    • le nombre moyen de points, nommée p. ex. averagePoints,
  • une méthode, nommée p. ex. registerEvaluation, qui prend en argument un nombre de points et les ajoute au total puis incrémente le compteur de parties simulées,
  • une méthode, nommée p. ex. indexOfChildToExplore, qui retourne l'index du fils du nœud à explorer, qui est celui dont la priorité, calculée avec la formule donnée à la §2.2.1, est maximale.

Prenez garde au fait que averagePoints doit effectuer le calcul du nombre de points moyen avec des nombres à virgule flottante (de type double), et retourner une valeur de ce même type.

3.1.1. Conseils de programmation

Pour représenter le fait que la racine n'a aucun coup associé, vous pouvez utiliser une valeur de 10 bits qui ne soit pas une représentation valide d'un coup empaqueté, p. ex. celle dont tous les bits valent 1.

Pour écrire la méthode indexOfChildToExplore, il est possible de faire mieux que de « bêtement » appliquer la description ci-dessus, c.-à-d. parcourir les enfants à la recherche de celui maximisant la formule de la §2.2.1. En effet, vu la manière dont l'algorithme MCTS fonctionne, la méthode indexOfChildToExplore peut distinguer deux cas :

  1. si le nombre de parties simulées du nœud est inférieur ou égal à son nombre d'enfants, alors elle peut simplement retourner ce nombre de parties simulées moins 1,
  2. sinon, elle doit effectivement parcourir les enfants à la recherche de celui ayant la priorité maximale.

Intuitivement, cela est dû au fait que MCTS va d'abord explorer tous les enfants d'un nœud avant de commencer à explorer les enfants de l'un d'entre eux. Et la raison pour laquelle le compteur de parties simulées de la racine est initialisé à 1 est que cela permet de garantir que la distinction des cas décrite ci-dessus est valable aussi pour la racine.

3.2. Classe HeuristicMoveSelector

La classe HeuristicMoveSelector du sous-paquetage mcts, publique et finale, représente un « sélectionneur de coup » qui utilise la technique décrite à la §2.3 pour choisir un coup à jouer.

Elle ne possède qu'une seule méthode publique, statique et nommée p. ex. selectMove, qui prend en arguments :

  • un générateur aléatoire de type RandomGenerator, qui doit être utilisé pour obtenir les éventuelles valeurs aléatoires nécessaires au choix du coup,
  • un état de partie (en lecture seule),
  • un tableau des coups empaquetés parmi lesquels choisir,
  • le nombre de coups empaquetés valides présents au début du tableau précédent,

et qui retourne l'index (!) du coup choisi, compris entre 0 (inclus) et le nombre de coups valides présents dans le tableau (exclu).

La méthode selectMove doit être appelé avec des arguments cohérents, dans le sens où les coups empaquetés passés dans le tableau doivent effectivement être des coups jouables par le joueur courant de l'état de jeu donné. Normalement, ces coups auront été obtenus au moyen de la méthode uniqueValidMoves ou de la méthode validMoves de l'état de partie passé en argument.

3.2.1. Conseils de programmation

Il peut valoir la peine de définir une classe privée et imbriquée statiquement dans HeuristicMoveSelector représentant un « échantillonneur par réservoir » avec un réservoir de taille 1.

3.3. Classe RankComputer

La classe RankComputer du paquetage principal, publique et finale, permet de calculer le rang des différents joueurs à la fin d'une partie d'Ajul.

Elle n'offre qu'une seule méthode publique, statique et nommée p. ex. playersRank, qui prend en argument un état de partie (en lecture seule) et un tableau d'entiers d'une taille égale au nombre de joueurs dans la partie. Elle remplit ce tableau avec les rangs des différents joueurs, compris entre 0 (inclus) et le nombre de joueur (exclu).

3.3.1. Conseils de programmation

Pour déterminer le rang des joueurs, il faut les trier par ordre décroissant de points (critère principal) et de nombre de lignes complètes du mur (critère secondaire).

Il y a plusieurs manières de faire cela, l'une d'entre elles consistant à combiner les deux critères en un seul « score de rang », obtenu p. ex. en multipliant les points par 5 — ou par 8, au moyen d'un décalage à gauche de 3 bits — puis en y ajoutant le nombre de lignes complètes. Ce score peut ensuite être utilisé pour créer une paire empaquetée de 13 bits dont :

  • les 11 bits de poids fort sont le score (8 bits pour les points, 3 pour le nombre de lignes), et
  • les 2 bits de poids faible sont l'index de l'identité du joueur auquel ce score correspond.

En stockant ces paires empaquetées dans un tableau puis en le triant par ordre décroissant, on peut ensuite en déterminer assez facilement les rangs des différents joueurs.

3.4. Interface Player

L'interface Player du paquetage principal, publique, représente un joueur d'une partie d'Ajul.

Player ne possède qu'une seule méthode, abstraite et nommée p. ex. nextMove, qui prend en argument l'état de la partie (en lecture seule) et retourne le coup que le joueur auquel on applique la méthode désire jouer. On fait bien entendu l'hypothèse que le joueur courant de l'état de la partie passé en argument à la méthode est le joueur auquel on applique la méthode.

Comme Player ne possède qu'une seule méthode abstraite, vous pouvez lui attacher l'annotation FunctionalInterface, et vous pourrez dans le futur utiliser des lambdas pour définir des joueurs.

3.5. Tests

En plus de tests unitaires, vous pouvez pour cette étape augmenter la version textuelle de votre jeu (AjulTUI), si vous l'avez écrite dans le cadre de l'étape précédente.

Vous pouvez en effet y intégrer une instance de HeuristicMoveSelector comme une espèce d'IA très basique, en l'utilisant pour sélectionner les coups d'un ou de plusieurs joueurs. Si vous faites cela, vous constaterez que même si cette « IA » reste très facile à battre, elle n'est toutefois pas dénuée d'intérêt.

4. Résumé

Pour cette étape, vous devez :

  • écrire les classes et interfaces RankComputer, HeuristicMoveSelector, MctsNode et Player selon les indications données plus haut,
  • tester votre code,
  • documenter la totalité des entités publiques que vous avez définies.

Vous n'avez pas l'obligation de rendre cette étape avant le rendu final, mais nous vous conseillons néanmoins de le faire afin de sauvegarder votre travail.