UCT et Intelligence Artificielle sur Jocly

UCT et Intelligence Artificielle sur Jocly

Jocly est un gros projet complexe qui a pour ambition de fournir des jeux de stratégie abstraite avec un certain nombre de fonctionalités communes à tous ces jeux.

Comme pour tout projet, nos ressources en terme de développement sont limitées et nous arrivons souvent à un point où il faut décider "et maintenant que fait-on pour faire avancer le projet?". Parfois nous répondons à cette question par "faisons un nouveau jeu" pour augmenter la diversité de notre offre, ou bien "ajoutons cette fonctionalité" comme nous l'avons récemment fait avec WebGL et WebRTC, ou encore "améliorons ça" car nous estimons qu'en regard des ambitions qualitatives de Jocly, la dite fonction est devenue un point faible et doit être traitée.

A ce jour nous avons identifié 2 points faibles que nous estimons en deçà des exigences de Jocly: 

  1. l'interface utilisateur générale (pas les jeux, l'application elle même)
  2. l'Intelligence Artificielle (AI) lorsqu'on joue contre l'ordinateur

Nous travaillons activement sur une nouvelle interface et nous en reparlerons très vite.

S'agissant de l'AI, les principales critiques sont "trop lent sur mon device" ou "ne joue pas assez bien", nous avons donc porté nos efforts sur ces sujets. 

Introduction à l'Intelligence Artificielle pour les jeux

On peut considérer la résolution du problème de cette façon: étant donné un état courant du plateau, il faut envisager tous les coups pouvant être joués. Cela nous donne la racine d'un arbre avec au bout de chaque branche un nouvel état du plateau considéré comme une feuille.

 
 
 
Figure 1 - à noter que traditionnellement l'arbre est représenté de haut en bas avec la racine au sommet et les feuilles en dessous

Depuis chaque feuille "état plateau" (sauf s'il s'agit d'une terminaison, i.e. le jeu est terminé) l'adversaire peut jouer des coups qui amènent à d'autres feuilles "état plateau", et ainsi de suite.
 

Figure 2

Evidemment si l'arbre total n'est pas infini, il est gigantesque et il n'y a pas moyen de le parcourir entièrement (sauf vers la fin de la partie). Il faut donc établir une limite dans l'exploration, comme par exemple choisir une profondeur maximum.

Minimax

Quand on est sur une feuille (on ne veut ou ne peut pas explorer les états suivants), on peut évaluer les états du plateau. Par exemple aux dames on peut compter le nombre de pièces restantes et calculer une évaluation: 

évaluation = <nombre de pièces blanches> - <nombre de pièces noires>

(Bien sûr on peut faire plus ingénieux et ajouter beaucoup d'autres critères dans l'évaluation)

Dans le cas présent plus l'évaluation est positive, meilleur c'est pour les blancs, et inversement pour les noirs.


 
 
Figure 3


Pour un état donné E du plateau, blanc va regarder les noeuds enfants et préfèrera le coup qui mènera à la plus haute évaluation, de sorte que l'évaluation de E est le maximum des évaluations de ses enfants. Si c'est à noir de jouer, l'évaluation est le minimum de ses enfants.

Chaque noeud de l'arbre peut donc être évalué par l'évaluation maximum des noeuds enfants, l'évaluation minimum des noeuds enfants ou une évaluation statique si on ne veut pas explorer les noeuds enfants.  Il y a alternance à chaque niveau de profondeur entre min et max.

Cette méthode de choix du meilleur coup (présumé) par l'ordinateur est connu sous le nom de Minimax et a été découvert dans les années 20.

Pour en savoir plus sur Minimax.

 

Alpha-beta

Depuis les débuts de Jocly, nous utilisons Minimax avec une amélioration connue sous le nom de Alpha-Beta.

Supposons que nous parcourons l'arbre ci-dessous dans l'ordre suivant: 
 


 

Figure 4


On peut constater qu'après avoir exploré le noeud 11 il n'est pas nécessaire d'explorer le noeud 12.


 

Figure 5

En effet, quelle que soit l'évaluation du noeud 12, si c'est plus que 4 cela ne sera pas propagé au parent car c'est un noeud 'min', et si c'est moins que 4 cela ne sera pas propagé au grand-parent qui est un noeud 'max' ayant déjà 5.

Au final, il y a toute une branche qu'il n'est pas nécessaire d'explorer puisque nous savons que le résultat n'affectera pas la décision. 
 
Alpha-Beta n'est pas très spectaculaire sur cet exemple mais lorsqu'il s'agit d'explorer des arbres très volumineux il peut facilement élaguer jusqu'à 80% de tout le feuillage. 

Plus d'info sur l'élagage Alpha-Beta.
 
Le problème avec alpha-beta c'est qu'on ne sait pas vraiment quand arrêter l'exploration de l'arbre. On peut par exemple décider d'explorer toutes les branches sur 5 niveaux à l'exception de celles qui auront été élaguées par alpha-beta. Dans Jocly nous avons assigné à chaque noeud un nombre potentiel de fils à explorer. Si un noeud a 4 enfants, chaque noeud enfant hérite d'un ¼ du potentiel de son père. Lorsque le potentiel atteint un niveau inférieur à 1 on arrête l'exploration. Cette méthode permet d'explorer plus profondément certaine situations comme pour des coups imposés par exemple.

Quoi qu'il en soit, le problème principal reste le temps perdu à explorer des branches sous des coups qui ont peu de chance d'être joués car ils se révèleront de mauvaises options, ce que nous ne savons pas encore.

UCT

Jocly implémente désormais l'algorithme d'IA UCT comme alternative à alpha-beta. Cela a produit des résultats spéctaculaires sur le jeu de Margo que nous venons de sortir et nous projetons d'utiliser cette IA dans tous nos autres jeux. 

UCT est fondamentalement différent d'Alpha-Beta au sens où au lien d'explorer l'arbre en profondeur, il procède par itérations afin de construire l'arbre progressivement, ajoutant une ou plusieurs branches à chaque itération. 

Les bénéfices sont très précieux:

  1. on peut donner une durée limite à l'ordinateur pour décider d'un coup: à la fin de ce délai le meilleur coup est choisi
  2. et/ou il est possible sur une CPU peu puissante de donner un nombre maximum d'itérations
  3. et/ou il est possible pour des devices ayant peu de mémoire de donner un nombre maximum de noeuds pouvant être créés

Et le meilleur de tout ça est que d'après nos tests la qualité du coup choisi est bien meilleure que celle trouvée par alpha-beta à temps de calcul égal. 

UCT fontionne par développement itératif de l'arbre:

Figure 6

 
Evidemment la branche qui est développée dépend de la qualité apparente du coup correspondant. Cela permet d'explorer plus profond des branches vers lesquelles le jeu tend à se développer. 

Si on ne privilégie que les meilleurs noeuds à développer, on passera à côté de sacrifices qui pourraient mener à de meilleurs résultats ultérieurs. Un coup de sacrifice a une qualité apparente basse, il pourrait donc être négligé bien que menant à une victoire plus profondément dans l'arbre.

Fort heureusement UCT a un mécanisme qui permet de rectifier ce comportement. Cela s'appelle UCB (pour Upper Confidence Bound).

Lorsqu'on s'enfonce dans l'arbre, on choisit le noeud enfant qui a le meilleur UCB. La valeur UCB est déterminée à partir du nombre de visites faites à ce noeud de sorte que quand un noeud est peu fréquenté, son UCB augmente, ce qui fait qu'à un certain moment, son UCB va devenir supérieur à celui de ses noeuds frères et donc qu'il sera choisi la prochaine fois.

Pour information, la formule de l'UCB est: 

UCB = V + C x sqrt ( ln ( visites noeud parent ) / ( visites noeud ) )

où V est la valeur intrinsèque du noeud (obtenue par une évaluation statique si noeud feuille, ou valeur maximisée à partir des noeuds enfants), et C une valeur constante à approximer manuellement pour chaque jeu.

Quand un noeud feuille est atteint, on décide d'avaluer le noeud ou de le développer (i.e. créer des noeuds enfants). L'évaluation du noeud est alors propagée en retour aux noeuds ascendants en utilisant la méthode minimax (ce qui est maintenant très rapide puisque nous calculons le minimax de bas en haut).

Avec l'UCT classique, lorsqu'on atteint un noeud feuille, on peut dérouler un 'playout' depuis le plateau courant afin d'améliorer l'avaluation statique du noeud. Un 'playout' consiste à finir la partie en jouant des coups aléatoires ou orientés par une heuristique jusqu'à la fin ou au moins pour un certain nombre de coups. Une fois qu'on a déroulé assez de 'playouts' pour un noeud, on peut finalement décider la prochaine fois que le noeud est intéressant à développer. Nous avons le code en place pour dérouler ces 'playouts' mais nos expérimentations sur Margo ont montré que le temps CPU utilisé pour ces 'playouts' était moins rentable que lorsqu'on l'utilisait pour le développement des noeuds, nous avons donc décidé d'inhiber les 'playouts'. Cela s'avèrera peut-être utile pour d'autres jeux où la génération de coups est moins couteuse que pour Margo.

Pour plus d'information à propos d'UCT, vous pouvez consulter ce site qui a d'ailleurs été écrit par Cameron Browne, l'inventeur du Margo.
 

Un peu de génétique

Une fois qu'un jeu est implémenté, on se retrouve généralement avec un certain nombre de paramètres à affiner pour la fonction d'évaluation d'un plateau. Pour reprendre l'exemple des dames, vous pouvez par exemple évaluer vos pièces de la façon suivante:

évaluation = <nb pions B> + P x <nb dames B> - <nb pions N> - P x <nb dames N>

On peut aisément compter le nombre de pions et de dames mais quelle valeur assigner à P? Bien sûr on peut essayer de deviner une valeur raisonnable, mais lorsqu'on a plusieurs paramètres à optimiser et que l'optimisation des uns dépend des autres, cela tourne vite au cauchemar. Pour exemple dans Margo nous utilisons 11 constantes différentes pour calculer l'évaluation d'un plateau. 

De plus lorsqu'on utilise l'AI UCT, il y a un autre jeu de paramètres qui influencent le jeu de l'ordinateur, à commencer par le paramètre C de la formule UCB. 

Pour résoudre ce problème que nous avons depuis le début de Jocly, nous avons développé un outil utilisant la programmation génétique pour trouver le meilleur jeu de paramètres possible.

Un algorithme génétique imite les régles de l'évolution de la vie: seuls les meilleurs survivent et se reproduisent.  

L'idée est de considérer des individus avec un jeu de chromosomes, chacun représentant un paramètre à optimiser (un entier, un float, un boolean ou une valeur discrète). On démarre avec une population d'individus dont les chromosomes ont pour démarrer une valeur aléatoire. A chaque itération on joue un grand tournoi entre tous les individus. On garde les vainqueurs et on tue les perdants. On croise ensuite aléatoirement les survivants en combinant leurs chromosomes et en autorisant certaines mutations (la valeur d'un chromosome peut être modifiée). Après un certain nombre d'itérations vous pouvez choisir les meilleurs et penser raisonnablement avoir trouvé les paramètres optimum.

Cet algorithme très simple fonctionne remarquablement bien. Le point négatif de la méthode est le temps nécessaire à son exécution. Mesurer la justesse de chaque individu nécessite de jouer un très grand nombre de parties et prend beaucoup de temps. Il n'est pas rare de devoir faire tourner ce sélectionneur génétique plus de 24h pour avoir un résultat satisfaisant.   

 

 

Commentaires

UCT et mémoire

d'après ce que j'ai lu sur la mailing list de computer go dans le cas d'UCT si on veut limiter la mémoire utilisée, on peut supprimer les noeuds avec le moins de visite sans que ca n'handicape trop le résultat

optimisation de paramètre

toujours sur la mailing list de computer go j'ai appris la connaissance de http://remi.coulom.free.fr/CLOP/ qui permet d'optimiser en limitant le nombre de parties joués le seul problème c'est qu'il est lent quand il y a beaucoup de paramètre