Joueur simulé
Javass – étape 6

Mettre en œuvre un joueur de Jass simulé ayant un bon niveau est loin d'être évident. Pour ce projet, nous utiliserons un algorithme offrant un bon compromis entre la complexité de la mise en œuvre et la qualité du jeu.

L'algorithme que nous utiliserons pour réaliser le joueur simulé se nomme Monte Carlo Tree Search (abrégé MCTS). Comme son nom l'indique, il effectue une recherche dans l'arbre de jeu — qui représente les possibilités d'évolution de la partie — et utilise une technique basée sur le hasard pour évaluer chacune d'entre elles¹.

Avant de détailler le fonctionnement de cet algorithme, il est utile de voir comment il se comporte sur un exemple simple afin de saisir les idées principales.

Soit la situation suivante : un tour vient de débuter, et l'atout est pique (♠). Le premier joueur a joué le valet de pique (♠J), et c'est au second joueur de jouer. Il possède trois atouts en main (8, 9 et 10), qui sont les seules cartes qu'il peut jouer car les six restantes sont d'autres couleurs.

Un joueur expérimenté n'aurait aucun problème à savoir qu'il doit poser le 8. En effet, comme le premier joueur a posé le valet d'atout, qui est la carte la plus forte du jeu, il remportera forcément le pli. Étant donné que ce joueur appartient à l'équipe adverse, il vaut mieux lui donner la carte qui est à la fois la moins forte et la moins valable, à savoir le 8.

L'algorithme MCTS permet d'arriver à la même conclusion, mais sans utiliser aucune connaissance particulière au sujet du Jass, si ce n'est les règles. L'idée est d'examiner petit à petit les évolutions possibles de la partie, et de déterminer le nombre de points que chaque équipe peut espérer gagner, en moyenne, dans chacun des cas. Cela fait, il suffit de jouer la carte permettant à l'équipe du joueur 2 (dans cet exemple) d'espérer remporter le plus grand nombre de points.

Pour représenter les évolutions possibles de la partie, l'algorithme MCTS utilise un arbre. Les nœuds de cet arbre sont les différents états du jeu, et les arêtes représentent les cartes jouées, comme nous le verrons ci-dessous.

Au début de l'exécution de l'algorithme, l'arbre est très simple puisqu'il ne contient qu'un seul nœud, qui représente l'état initial. Dans notre exemple, il s'agit de l'état décrit plus haut, à savoir : l'atout est pique, et le pli courant est constitué d'une seule carte, le valet de pique. Cet arbre initial est présenté ci-dessous, l'atout n'étant pas indiqué pour alléger la présentation.

A partir de l'état initial, étant donné que c'est au joueur 2 de jouer, il n'y a que trois évolutions possibles puisque ce dernier n'a que 3 cartes jouables en main. La première d'entre elles est le 8 de pique, et si le joueur 2 la joue, un nouvel état de jeu est créé et le nœud correspondant est ajouté à l'arbre, qui devient :

Notez que le nœud initial est en gras pour indiquer qu'il correspond à un état dans lequel c'est à l'équipe 2, à laquelle appartient le joueur 2, de jouer. Cette information sera utile plus tard. De plus, l'arête allant de la racine à l'autre nœud est annotée avec la carte jouée, ici le 8 de pique.

Après avoir ajouté ce nœud à l'arbre, l'algorithme MCTS l'évalue, c-à-d qu'il essaie d'estimer le nombre de points que l'équipe du joueur 2 peut espérer obtenir, en moyenne, s'il joue le 8 de pique. Pour ce faire, la fin du tour est simulée en admettant que les joueurs jouent de manière totalement aléatoire (!) et les points obtenus à la fin du tour par chacune des équipes sont examinés.

Admettons que le résultat de ce tour joué aléatoirement soit que l'équipe 1 remporte 55 points, l'équipe 2 en remportant 102. Ces résultats sont stockés dans les nœuds de l'arbre, de manière à ce que chaque nœud contienne le nombre de points obtenu par l'équipe qui a joué la carte qui a produit l'état auquel le nœud correspond. Pour notre exemple, on obtient donc l'arbre suivant — le 1 entre parenthèses signifiant que ces nombres de points ont été obtenus en jouant un seul tour :

Pour bien comprendre la signification du 102 apparaissant dans le nœud du bas, il faut regarder l'arête qui mène à ce nœud, qui nous apprend que le 8 de pique à été joué, et le nœud à la source de cette arête, qui nous apprend que cette carte a été jouée par un joueur de l'équipe 2 — le nœud source étant en gras. En d'autres termes, on peut conclure en consultant l'arbre ci-dessus que, à ce stade du déroulement de l'algorithme, l'équipe 2 peut espérer gagner en moyenne 102 points en jouant le 8 de pique.

Bien entendu, ce nombre de points est probablement très loin de la réalité puisqu'il est basé sur un seul tour dans lequel les joueurs ont de plus joué de manière totalement aléatoire ! Donc à ce stade, il ne signifie pas grand chose, mais on peut imaginer qu'en simulant un très grand nombre de tours aléatoires, on finisse par avoir une idée assez raisonnable du nombre de points que l'équipe 2 peut espérer obtenir en jouant le 8 de pique.

Toutefois, avant de simuler plus de tours, l'algorithme MCTS va ajouter successivement les deux nœuds correspondants aux deux autres cartes jouables — le 9 et le 10 de pique — et terminer également aléatoirement le tour pour chacun d'eux, afin d'avoir une estimation initiale du nombre de points que l'équipe 2 peut espérer gagner dans chacun des cas. Cela fait, l'arbre de jeu pourrait ressembler à ceci :

Dans l'état actuel des choses, la carte qui semble la plus avantageuse à jouer est le 8 de pique. Toutefois, cela demande à être confirmé, au vu du fait qu'un seul tour aléatoire a été joué pour estimer sa valeur.

Pour ce faire, l'algorithme MCTS examine maintenant comment le tour pourrait évoluer après que le joueur 2 ait joué le 8 de pique. Comme il ne sait rien des mains des autres joueurs, il doit faire l'hypothèse qu'ils peuvent posséder n'importe quelle carte qui n'a pas encore été jouée et qui ne fait pas partie de la main du joueur 2. La première de ces cartes qui pourrait — selon les règles — être jouée est le 6 de pique, et l'algorithme ajoute donc un nœud correspondant à cette possibilité à l'arbre, qui devient :

Pour résumer, le nouveau nœud correspond à la situation dans laquelle le joueur 1 a joué le valet de pique, le joueur 2 a joué le 8 de pique, et le joueur 3 a joué le 6 de pique.

Afin d'évaluer ce nouveau nœud, l'algorithme a procédé comme d'habitude et a terminé le tour de manière aléatoire en partant de l'état correspondant au nœud. Les scores obtenus dans ce tour étaient : 106 points pour l'équipe 1, 51 pour l'équipe 2. Les 106 points ont donc été attribués au nouveau nœud, mais ce n'est pas tout ! Les 51 points obtenus par l'équipe 2 ont été ajoutés aux 102 points obtenus précédemment pour le nœud parent du nouveau nœud, pour un total de 153 points. Toutefois, ces 153 points étant la somme des points obtenus durant deux tours par l'équipe 2, la valeur moyenne d'un tour est 153/2 = 76.5. C'est cette nouvelle valeur qui est désormais mémorisée pour le nœud parent.

En examinant ce nouvel arbre, l'algorithme MCTS constate que le 8 de pique est toujours la carte la plus prometteuse à jouer pour le joueur 2, car son équipe peut espérer gagner 76.5 points en moyenne, contre 76 pour le 10 et 58 pour le 9.

Toutefois, comme la différence entre le 8 et le 10 de pique est très faible, et qu'un seul tour a été joué pour ce second nœud, il décide maintenant de lui ajouter un nouveau fils à lui. Là encore, ce fils correspond au cas où le joueur 3 joue le 6 de pique. Un nouveau tour aléatoire est joué à partir de ce nouveau fils, dont les scores sont 96/61 (96 points pour l'équipe 1, 61 pour l'équipe 2). Les 96 points sont stockés dans le nouveau nœud, et le score moyen de son parent mis à jour, car il vaut désormais (76+61)/2 = 68.5 points. L'arbre est alors:

L'algorithme MCTS peut s'exécuter ainsi soit jusqu'à ce qu'un certain nombre de nœuds aient été ajoutés à l'arbre, soit jusqu'à ce qu'un temps de jeu limite se soit écoulé. Par exemple, en décidant de s'arrêter après 100 000 itérations du processus décrit ci-dessus, c-à-d après que ce nombre de nœuds aient été ajoutés à l'arbre, les deux premiers niveaux de ce dernier sont :

(Les niveaux suivants n'ont pas été dessinés pour des raisons de place, l'arbre contenant un total de 100 000 nœuds. Ils sont suggérés par les nœuds triangulaires traitillés.)

En consultant les nœuds du second niveau de cet arbre, il est facile de voir que la meilleure carte à jouer est le 8 de pique, car l'équipe 2 peut dans ce cas espérer remporter en moyenne 76.29 points ; la deuxième meilleure carte est le 10 de pique, avec une moyenne de 68.30 points ; et la dernière est le neuf de pique, avec 58.57 points.

Notez que cet ordre est aussi celui qu'un joueur expérimenté choisirait, mais il ne faut pas en conclure que l'algorithme MCTS se comporte toujours aussi bien. Étant donné sa simplicité et un certain nombre de limitations de la manière dont nous le mettons en œuvre dans ce projet, son niveau est malheureusement assez moyen. Mais dans un certain nombre de situations, comme cet exemple, il se comporte remarquablement bien.

L'exemple ci-dessus permet d'avoir une bonne idée du fonctionnement de l'algorithme MCTS, mais il omet certains détails importants qui sont discutés ici.

Sous forme de pseudo-code, l'algorithme MCTS ressemble à ceci :

1: A := arbre constitué d'un nœud unique, avec l'état courant
2: tant que le nombre maximum d'itérations n'est pas atteint
3:   N := nouveau nœud ajouté à l'arbre A
4:   S := scores d'une fin de tour aléatoire jouée depuis N
5:   propager S aux nœuds sur le chemin de N à la racine de A
6: fin
7: jouer la carte du meilleur fils de la racine de A

Deux aspects de cet algorithme méritent une discussion plus approfondie : le choix du nœud à ajouter, et la manière dont les scores du tour aléatoire sont propagés aux nœuds situés sur le chemin menant du nouveau nœud à la racine de l'arbre.

La classe MctsPlayer du paquetage ch.epfl.javass.jass, publique et finale, représente un joueur simulé au moyen de l'algorithme MCTS. Étant donné que cette classe représente un joueur, elle implémente l'interface Player définie à l'étape précédente.

MctsPlayer n'offre qu'un seul constructeur public :

• MctsPlayer(PlayerId ownId, long rngSeed, int iterations), qui construit un joueur simulé avec l'identité, la graine aléatoire et le nombre d'itérations donnés, ou lève IllegalArgumentException si le nombre d'itérations est inférieur à 9.

La raison pour laquelle le nombre d'itérations minimal accepté est 9 est que c'est la taille de la main initiale du joueur. Il faut donc au minimum 9 itérations de l'algorithme MCTS pour évaluer une fois chacune des cartes d'une telle main.

En plus du constructeur susmentionné, la classe MctsPlayer redéfinit bien entendu la méthode cardToPlay de Player, mais n'offre sinon aucune méthode publique.

Comme d'habitude, nous vous fournissons un fichier de vérification de signatures contenu dans une archive Zip à importer dans votre projet.

Pour tester votre code, nous vous conseillons d'une part d'écrire un petit programme permettant de vérifier que vous obtenez les mêmes valeurs que nous pour l'exemple de la §1.3, sachant qu'il a été obtenu en passant la graine 0 au constructeur de MctsPlayer et la main suivante à la méthode cardToPlay :

CardSet hand = CardSet.EMPTY
  .add(Card.of(Color.SPADE, Rank.EIGHT))
  .add(Card.of(Color.SPADE, Rank.NINE))
  .add(Card.of(Color.SPADE, Rank.TEN))
  .add(Card.of(Color.HEART, Rank.SIX))
  .add(Card.of(Color.HEART, Rank.SEVEN))
  .add(Card.of(Color.HEART, Rank.EIGHT))
  .add(Card.of(Color.HEART, Rank.NINE))
  .add(Card.of(Color.HEART, Rank.TEN))
  .add(Card.of(Color.HEART, Rank.JACK));

D'autre part, il n'est à ce stade plus très difficile d'écrire un programme simulant une partie entre quatre joueurs simulés, et de vérifier qu'ils respectent les règles et que leur style de jeu n'est pas totalement incohérent. Souvenez-vous toutefois que l'algorithme MCTS tel que nous le mettons en œuvre ici est trop simple pour que les joueurs simulés jouent véritablement bien, et il leur arrive de faire des erreurs grossières.