UNIVERSITE DES SCIENCES ET TECHNOLOGIE DE LILLE

& UNIVERSITE CHARLES-DE-GAULLE

Maîtrise des Sciences Cognitives

I.

II.

III.

IV.

V.

VI.

VII.

Le Q-Learning

appliqué aux

Mind Reading Machines

Julie Delzons

Responsable universitaire: Fabien Torre

Soutenu le 18 juin 2004

VIII.Table des matières

IX.Introduction

L’intelligence artificielle est incluse dans un cadre d’application très vaste. Quand ces mots sont prononcés, les images qui viennent à l’esprit sont liées au futur sans rapport au monde actuel. Or, dans les années 50, des machines pouvant gagner contre des joueurs humains à des jeux où le match nul seul peut être espéré, ont été créées. Ce sont des jeux comme le dilemme des prisonniers ou encore le pile ou face.

Ainsi pour ce type de jeu, une machine est capable de battre systématiquement un joueur humain. L’explication avancée et acceptée est que l’être humain n’est pas capable véritablement de produire de l’aléatoire et finit par répéter ces choix. Il est alors facile de prévoir les coups du joueur humain pour une machine car celle-ci a une mémoire infaillible.

Dans un premier temps, nous catégoriserons les jeux grâce aux informations qu’ils fournissent ou non aux joueurs, en intelligence artificielle.

Par la suite nous nous intéresserons aux Mind Reading Machines ainsi qu'à leurs applications au jeu Pile ou Face, avant de définir les processus de Markov, le Q-Learning et sa mise à jour. Enfin, nous finirons par l’application de l’algorithme du Q-Learning au Pile ou Face.

X.I. Les jeux en Intelligence Artificielle

1. Les jeux à informations complètes imparfaites

   2. Ce sont des jeux dans lesquels la prise de décision des joueurs se fait simultanément c’est-à-dire que les joueurs connaissent l’ensemble des choix possibles et leurs conséquences mais ne connaissent pas le comportement immédiat des autres joueurs.

   3. Ils doivent donc, afin de gagner la partie, deviner le comportement de l’autre joueur. Ce sont des jeux comme « Pierre/Ciseaux/feuille », « Pile/Face », « Le dilemme des prisonniers », etc.

   5. Le jeu « Pierre/Ciseaux/Feuille » est le jeu que nous connaissons tous. Il se joue à deux joueurs J1 et J2, l’un contre l’autre. Les joueurs doivent dire simultanément leur choix entre la Pierre, le Ciseau et la Feuille. Si le joueur J1 choisit la Feuille et que le joueur J2 choisit la Feuille également, il y a égalité et pas de point. Par contre si le joueur J2 choisit une Pierre alors la Feuille recouvre la Pierre et le joueur J1 remporte le point. Si cette fois, le joueur J2 choisit les Ciseaux, cette fois c’est le joueur J2 qui remporte le point. On joue ainsi jusqu’à ce qu’un des joueurs ait atteint le nombre de points définis au départ. Généralement on joue trois fois et le joueur ayant gagné deux fois est le vainqueur.

   7. Le jeu du « dilemme des prisonniers » est également un jeu itéré. C’est en fait un dilemme qui se présente à deux complices d’un larcin arrêtés en même temps sur les lieux du crime. Ces deux prisonniers sont séparés et isolés l’un de l’autre. Ils se voient offrir une opportunité : soit ils peuvent avouer soit ils n’avouent pas le larcin. Si les deux avouent, ils effectuent chacun deux années de prison. Si l’un avoue mais pas l’autre, celui qui avoue effectue cinq années de prison alors que l’autre est libéré immédiatement. Si aucun n’avoue, ils effectuent, tous les deux, quatre années de prison. Ce jeu présente un intérêt au niveau des relations humaines qui peuvent agir en fonction du passé. Si l’un des joueurs à tendance à trahir, l’autre joueur en tiendra compte dans son comportement. Il permet de juger un comportement, de détecter une attitude particulière chez l’adversaire et il peut alors être utilisé en sociologie ou alors pour les échanges commerciaux et pour les affrontements avec les arsenaux nucléaires.

   9. Le jeu « Pile ou Face » est en quelque sorte une version simplifiée des deux jeux précédents. Sa simplicité permet une analyse des résultats plus facile. Il se joue avec deux joueurs J1 et J2. Le joueur J1 doit deviner ce que le joueur J2 va jouer. Si le joueur J1 choisit Pile et que le joueur J2 aussi, le joueur J1 a un point. Si le joueur J2 choisit Face : le joueur J2 a le point. On joue ainsi jusqu’à ce que le nombre de coups soit épuisé ou alors jusqu’à ce qu’un joueur ait atteint un certain nombre prédéfinit au départ.

2. Les jeux équitables

   1. Un jeu est dit équitable lorsque tous les joueurs ont des rôles interchangeables ou symétriques, c’est-à-dire qu’aucun joueur n’est favorisé par rapport aux autres. C’est le cas des jeux « Pile ou face », « Pair ou Impair » ou encore « Pierre/Ciseaux/ Feuille ».

   3. Les jeux à information complète et parfaite ne sont, a priori, pas équitables dans la mesure où le fait que les coups soient consécutifs introduit une dissymétrie dans le rôle des joueurs (aux échecs, le joueur qui joue avec les pièces blanches joue en premier et, a, de ce fait, un avantage sur l’autre joueur). Dans de tels jeux, le premier joueur n’est pas systématiquement avantagé (dans le jeu « puissance quatre », c’est le second joueur qui est avantagé).

3. Les jeux itérés

   2. Les jeux non itérés sont des jeux qui se disputent en partie unique c'est-à-dire que la partie se déroule en plusieurs coups mais il n’y a qu’une partie. Les conséquences sont :

• soit les gains

• soit les pertes éventuelles des différents joueurs.

  1. Ce sont, en général, des jeux comme les Echecs, le Go ou encore les Dames. Mais on peut considérer une partie de « Pile ou Face » comme un jeu non itéré si on considère chaque coup dans un ensemble et non pas individuellement.

  3. Les jeux itérés sont des jeux constitués d’un ensemble (finis ou infinis) de parties d’un même jeu. Le résultat de chaque partie peut avoir des conséquences sur le comportement des différents joueurs lors des parties suivantes. Ici, si on considère les coups de « Pile ou face » individuellement, alors ce jeu fait partie des jeux itérés. Les jeux « Pairs ou Impairs » et « Pierre/Ciseaux/Feuille » sont aussi des jeux itérés.

  5. Il existe une ambiguïté entre jeux itérés et non itérés. L’itération permet d’apprendre des informations sur le comportement du joueur adverse au fur et à mesure.

1. La théorie des jeux

L’étude de ces jeux implique de raisonner en termes de rationalité, de modélisation et d’anticipation des comportements. En effet, pour vaincre un adversaire à un tel jeu, il est nécessaire de se donner les moyens d’anticiper ses choix. Pour cela, il faut être capable de construire un modèle de son comportement en fonction de la rationalité qu’on lui prête.

Contrairement aux jeux à information complète et parfaite, les stratégies les meilleures contre un adversaire particulier ne sont pas nécessairement celles qui supposent que cet adversaire soit parfaitement rationnel ni parfaitement adapté à d'autres adversaires.

De tous ces différents jeux, le jeu le plus simple est le « Pile ou Face » (ou encore le « pair ou Impair »). Ce jeu si simple a suscité l’intérêt de Claude Shannon qui a inventé une machine efficace contre les joueurs humains [Shannon, 1953]. « Minasi », un autre algorithme, fut également créé et il est, lui aussi, efficace contre les humains. Mais, lorsque les deux algorithmes jouent l’un contre l’autre, Shannon est plus performant.

• La machine de « Shannon » fonctionne suivant huit situations. Si une des situations est sélectionnée, « Shannon » joue selon cette situation sinon « Shannon » joue au hasard. Une seule des huit situations peut être activée c'est-à-dire que c’est une des huit ou aucune.

• La machine de « Minasi » enregistre tous les coups joués et regarde s’il y a une répétition de la plus grande séquence possible. Si la répétition existe, « Minasi » va jouer ce qui a été le plus joué jusqu’à présent. « Minasi » joue au hasard dans deux situations : au début de la partie (les deux premières fois) et s’il ne peut pas distinguer deux situations identiques.

La Théorie des jeux permet de déterminer la stratégie optimale théorique, lorsque celle-ci existe. Mais dans les jeux à information complète et imparfaite la solution optimale est différente de celle de la Théorie des jeux. En effet une solution optimale se présente sous la forme d’une répartition probabiliste des coups à jouer en fonction des situations de jeux. Mais une telle stratégie garantie la partie nulle.

Dans le cas du jeu « Pile ou Face », la théorie des jeux nous donnerait comme théorie optimale de jouer au hasard. Mais, il est connu que le joueur humain n’est pas capable de produire de l’aléatoire, c’est pourquoi on peut faire ressortir un comportement répétitif au cours du temps. C’est d’ailleurs sur ce principe que sont basés « Shannon » et « Minasi ». Le Q-Learning va capturer également ce paramètre.

XI.II. Mind Reading Machines, ce qui existe déjà avec le jeu « Pile ou Face »

1. Shannon (1953)

0. Son fonctionnement

Shannon considère que deviner ce que joue l’adversaire se résume à huit situations. Ces huit situations sont :

• j’ai gagné, puis j’ai rejoué la même chose et j’ai encore gagné

• j’ai gagné, puis j’ai rejoué la même chose et j’ai alors perdu

• j’ai gagné, puis j’ai changé mon jeu et j’ai encore gagné

• j’ai gagné, puis j’ai changé mon jeu et j’ai alors perdu

• j’ai perdu, puis j’ai rejoué la même chose et j’ai alors gagné

• j’ai perdu, puis j’ai rejoué la même chose et j’ai encore perdu

• j’ai perdu, puis j’ai changé mon jeu et j’ai alors gagné

• j’ai perdu, puis j’ai changé mon jeu et j’ai encore perdu

  2. Pour chacune de ces 8 situations, « Shannon » mémorise si le joueur a, au coup suivant, rejoué comme à son dernier coup ou si le joueur a changé de choix. Il mémorise aussi, si ce choix est le même que celui fait lors de la précédente rencontre de la situation. Le jeu de « Shannon » consiste à parier que le joueur qui s’est montré constant vis-à-vis d’une situation le restera à la prochaine rencontre de cette situation.

  3. Par exemple, dans le jeu « Pile ou Face » si le joueur humain a joué Pile, qu’il gagne, qu’il rejoue Pile et qu’il regagne alors la première règle sera incrémenter de un. Cela donne pour la situation VVV. La prochaine fois que « Shannon » rencontrera cette situation, il verra si l’humain a un comportement constant ou non et jouera en conséquence. Par exemple si le joueur humain gagne, qu’il joue Face et qu’il regagne alors Shannon jouera Face car il retrouve le comportement VVV.

  4. Si le joueur a changé d’attitude confrontée à une situation donnée, « Shannon » choisit au hasard son coup, de même qu’en début de série lorsque les informations disponibles sont insuffisantes.

  6. « Shannon » joue en fonction du contenu des 8 mémoires si le contenu de la mémoire est supérieur à deux. S’il est inférieur à deux, « Shannon » joue au hasard. Si une prédiction s’avère non fondée, le contenu de la mémoire correspondante est effacé même si cette prédiction a été juste de nombreuses fois avant. « Shannon » a un comportement adaptatif dans le sens où il s’adapte au joueur humain et utilise l’aléatoire de nombreuse fois. Le contenu d’un élément de mémoire contient la conséquence du coup, l’attitude au coup suivant et la répétition du coup.

0. Résultats obtenus

Graphique 1 : courbes représentant les résultats d’une partie de 100 coups entre « Shannon » et un joueur humain.

Source : https://fabien-torre.fr/Recherche/MRM/resultats.php

Ici, « Shannon » gagne contre l’humain 56 à 44. A partir de 40 coups « Shannon » prend l’avantage sur le joueur humain.

Graphique 2 : courbe représentant la progression des coups aléatoires de « Shannon » lors d’une partie de 100 coups.

Source : https://fabien-torre.fr/Recherche/MRM/resultats.php

On peut remarquer que le joueur « Shannon » joue la plupart du temps au hasard. En effet, au départ il joue totalement aléatoirement, ce qui est normal car il lui faut un certain temps afin d’appréhender quelques caractéristiques du joueur humain. Mais à la fin, il joue encore énormément au hasard. Le fait d’effacer totalement le contenu de la mémoire correspondant à une situation, lorsque celle-ci fait perdre le point à « Shannon », ne permet pas de nuancer ces situations. En effet, deux situations qui se ressemblent comme « j’ai gagné, puis j’ai rejoué la même chose et j’ai encore gagné » (VVV) et « j’ai gagné, puis j’ai rejoué la même chose et j’ai alors perdu » (VVF) ne peuvent pas avoir une mémoire, associée à ces situations, supérieure à zéro en même temps. Il peut y en avoir une valant quinze et l’autre zéro. Mais si la situation associée à la mémoire valant quinze s’avère fausse, celle-ci passe à zéro et par contre celle de la deuxième situation passe à un.

Les coups de « Shannon » son conditionnés par les trois derniers coups. Il oublie au fur et à mesure qu’il y a une erreur mais il peut se souvenir d’une situation particulière pendant longtemps. Il parie que les joueurs humains font des répétitions mais qu’ils oublient.

Graphique 3 : courbes représentant le temps de calcul de « Shannon » et d’un joueur humain lors d’une partie de 100 coups.

Source : https://fabien-torre.fr/Recherche/MRM/resultats.php

Ce graphique montre le temps de calcul de « Shannon » et du joueur humain. Shannon a un temps de calcul très faible (moins de 1/10) du début de la partie à la fin. C’est intéressant car ainsi on peut faire des parties de 500 coups sans pour autant faire attendre longtemps le joueur humain entre chaque coup.

1. Minasi

0. Fonctionnement

« Minasi » analyse les patterns composés par les coups successifs des 2 joueurs. Dans cet algorithme, un pattern est une séquence de paires de coup (un par joueur). Dans une série, l’ensemble des paires de coups est enregistré en continues.

Exemple : P f P p F f P f P p F p F f F f F p P p

Majuscule => joueur Minasi ; Minuscule => joueur humain

P => pile ; F => face

Lorsque le système doit effectuer son choix pour le coup suivant, il recherche, dans l’enregistrement, la plus longue série de coups répétés au moins une fois, qui correspond à la situation actuelle. Mais il part des derniers coups.

Exemple : si l’enregistrement est :

P f P p F f P f P p F p F f F f F p P p F f P f P f

• La ligne 0 correspond à la recherche du pattern « f ». Il a été enregistré 7 fois, il est suivi 3 fois par le pattern « p » et 4 fois par le pattern « f ».

• La ligne 1 correspond à la recherche du pattern « P f ». Il a été enregistré 3 fois, il est suivi 2 fois par le pattern « p » et 1 fois par le pattern « f ».

• La ligne 2 correspond à la recherche du pattern « f P f ». Il a été enregistré 2 fois, il est suivi 1 fois par le pattern « p » et 1 fois par le pattern « f ».

• La ligne 3 correspond à la recherche du pattern « F f P f ». Il a été enregistré 1 fois, il est suivi 1 fois par le pattern « p » et 0 fois par le pattern « f ».

  2. Comme le pattern « F f P f » n’est localisé qu’une fois, il est impossible de trouver une séquence répétée plus grande qui soit suivie éventuellement d’un autre coup. La recherche s’interrompt et statue sur le fait que l’adversaire va jouer « f ».

  4. « Minasi » suppose que ses adversaires réitèrent un choix quand les circonstances sont explicitement les mêmes. Il ne tient aucun compte des conséquences créées par les choix effectués par chaque joueur. Il n’adapte pas sa stratégie en fonction des résultats obtenus et ne considère pas que l’humain le fasse pour lui-même.

  5. Pour « Minasi », le modèle de son adversaire consiste uniquement à l’enregistrement des coups. Ce modèle est idéal contre un adversaire déterministe [Meyer & Zucker]. La stratégie de « Minasi » est assez simple. Elle n’utilise pas les gains ou pertes de la partie. Elle s’adapte au comportement de l’adversaire et utilise l’aléatoire lorsque « Minasi » ne peut pas prévoir le coup à jouer c'est-à-dire en début de partie et lorsqu’il y a égalité sur les patterns. La taille de la mémoire est le nombre de coups joués. Il garde tous les coups joués en mémoire et chaque coup est le contenu d’un élément de mémoire.

0. Les résultats

La mémoire de « Minasi » étant tous les coups joués, à la fin d’une partie contre lui les temps de calculs prennent du temps, de ce fait le joueur « Minasi » devient long lors de parties où le nombre de coups est supérieur à deux cents.

Graphique 4 : courbes représentant la performance de « Minasi » et d’un joueur humain lors d’une partie de 100 coups.

Source : https://fabien-torre.fr/Recherche/MRM/resultats.php

On remarque que « Minasi » gagne contre le joueur humain. Au départ, le joueur prend l’ascendant sur « Minasi » mais à la moitié de la partie « Minasi » reprend l’ascendant.

Graphique 5 : courbe représentant la progression des coups aléatoires de « Minasi » lors d’une partie de 100 coups.

Source : https://fabien-torre.fr/Recherche/MRM/resultats.php

A la fin des cents coups « Minasi » a encore dix-sept pour cent de coups qui sont aléatoires. C’est beaucoup moins que « Shannon » mais c’est encore important.

Graphique 6 : courbes représentant la progression du temps de calcul de « Minasi » et d’un joueur humain lors d’une partie de 100 coups.

Source : https://fabien-torre.fr/Recherche/MRM/resultats.php

En ce qui concerne le temps de calcul de « Minasi » il est pratiquement nul (0.027).

1. Autres Mind Reading Machines

0. SAGACE (Solution Algorithmique Génétique pour l’Anticipation de Comportement Evolutifs)

  Pour définir le mode de fonctionnement de « S.A.G.A.C.E. », je me suis référencée à l’article de J.P. Delahaye dans le journal « Pour la science », à celui de Meyer & Zucker et aussi de la thèse de Meyer car les droits sur SAGACE sont privés.

C’est une méthode plus complexe que « Shannon » et « Minasi ». Il fonctionne en deux modules :

• Le premier module est la compréhension de l’adversaire c’est-à-dire l’élaboration de règles de comportement.

  1. Ex : si les coups précédents sont (pile, face), (face, pile), (pile, pile) alors jouer pile (humain, SAGACE).

  2. Beaucoup de règles sont créées et comparées au jeu de l’adversaire humain. Le modèle attribue aux règles, qui décrivent correctement le comportement de l’adversaire, un coefficient de validité plus fort qu’à celles qui le décrivent mal. La gestion des règles et des coefficients à chaque nouveau coup joué définit un « profil comportemental » de l’adversaire humain. Il permet de faire une prédiction du comportement humain au prochain coup. Dans la dernière version le nombre de coups passés susceptibles d’intervenir dans une règle est 16. Le dernier coup a plus d’importance que les plus anciens qui sont oubliés à la longue.

• Le second module est le choix du coup :

  1. Si l’une des règles s’appliquent, d’après le Module 1, alors SAGACE joue ce que prédit cette règle sinon il joue au hasard.

  3. Lorsqu’une règle est appliquée avec succès, le programme en augmente le coefficient de validité, ce qui rend plus probable son application future. Lorsque qu’une règle est appliquée avec échec, le programme en diminue le coefficient de validité, ce qui rend moins probable son application future. Lorsque plusieurs règles sont utilisables simultanément, on prend celle dont le coefficient de validité est le plus grand mais selon un principe probabiliste qui a pour effet de rendre non déterministe le comportement de « SAGACE » (face à une même série de coups, on a pas la même réaction à chaque fois). Il utilise le tirage roulette afin de déterminer la règle qu’il va appliquer.

  4. Un jeu de règles initiales est présent dans le système en début de partie (il a été mis au point soigneusement à la suite de longues séries de tests). En plus, à chaque étape du jeu, de nouvelles règles sont créées par les algorithmes génétiques. C’est-à-dire que l’on modifie légèrement une règle qui possède un bon coefficient de validité (mutation), ou on mélange 2 bonnes règles ensembles. Un programme simplifie plusieurs règles ayant une zone commune pour n’en garder qu’une. Des nouvelles règles sont aussi rajoutées par application de la « méthode du regret », c’est-à-dire après un coup perdu, « SAGACE » ajoute une règle indiquant ce qu’il aurait du faire pour gagner. Par conséquent cela déclenche une quantité importante de calcul à chaque coup et nécessite des parties longues (500 coups) afin que SAGACE puisse converger vers un modèle satisfaisant.

0. TitAfterTit

Le « TitAfterTit » est une allusion à la stratégie « TitForTat » utilisée dans le jeu du « dilemme du prisonnier ». Il joue (après le premier coup) toujours comme l’adversaire au coup précédent quelque soit le résultat. La prédiction du coup de l’adversaire est qu’il reproduit toujours son dernier coup sans tenir compte de ses conséquences : si (*, M) alors Coups_Suivants(B,M). La stratégie est implicite, non adaptative et pas aléatoire. Les résultats des coups ne sont pas tenus en compte. La mémoire des coups vaut 1 (seulement le dernier coup joué en mémoire). La longueur des patterns est donc de 1. La taille de la mémoire vaut également 1 (le dernier coup de l’adversaire). Le contenu d’un élément de la mémoire vaut un coup (pile ou face).

0. Machine purement aléatoire

C’est une fausse Mind Reading Machines. Elle consiste à jouer « Pile » ou « Face » suivant une répartition probabiliste uniforme ou pas (avec un poids p associé à Pile et (1-p) associé à Face).

0. Stratégie utilisant des automates à états finis.

Ce sont également des fausses Mind Reading Machines. Ces fausses Mind Reading Machines perdent systématiquement contre les vraies Mind Reading Machines si elles sont déterministes. Quand elles sont uniformément aléatoires, elles obtiennent l’espérance de gain (perdent aussi souvent qu’elles gagnent).

0. Stratégies mathématiques

Elles jouent au hasard avec une probabilité de cinquante pour cent des coups pour Pile et cinquante pour cent des coups pour Face.

0. Le 30/70

Elle joue trente pour cent des coups pour Pile et soixante-dix pour cent des coups pour Face.

Les stratégies mathématiques et le 30/70 peuvent être considérés comme des stratégies purement aléatoires avec comme poids p valant 0.5 et 0.3 respectivement.

0. Les stratégies périodiques

Elles jouent périodiquement une séquence « Pile, pile, face, face, hasard, pile, pile, pile, hasard, face, face, pile, hasard, face, face » prédéfinie au départ.

1. Récapitulatif

Tableau 1 : récapitulatif.

Source : [Delahaye Jean-Paul, « L’intelligence humaine à nouveau dominée ? » Pour la Science n° 263, Septembre 1999.]

Ce tableau correspond aux résultats de cinq algorithmes pour le jeu « Pile ou face ». Dans le tableau c’est le pourcentage des réussite de six stratégies de jeu confrontées deux a deux.

Le classement est : SAGACE, Shannon, Mathématique, Périodique et 30-70. Ce classement peut peut-être s’expliquer par le fait que « SAGACE » et « Shannon » savent exploiter le comportement répétitif des joueurs. « Mathématique », lui, assure le match nul car dans sa théorie c’est cinquante pour cent Pile et cinquante pour cent Face mais si un comportement se répète il n’est pas capable de le détecter.

Quand on compare « Shannon » et « Minasi », on trouve une différence qui est la mémoire des coups. « Minasi » retient tous les coups joués, pourtant celui-ci a des résultats moins bons que « Shannon » face à un joueur humain. L’oubli est peut être nécessaire pour permettre une adaptabilité plus grande. Après tout l’homme oublie ces coups et pourtant il peut lui arriver de faire match nul avec ces intelligences.

XII.III. Le Q-Learning

1. Processus de Markov

0. Définition

L’environnement Markovien est un environnement dans lequel l’état permet de déterminer l’action optimale.

Les états possibles (S) dans un environnement Markovien sont :

• Les positions de l’agent dans l’environnement

• La vitesse de l’agent dans l’environnement

• Les positions et la vitesse de l’agent dans l’environnement

• Les  « images », les « sons » de l’environnement

• Les coups joués dans un jeu comme le « Pile ou Face »

• Les conséquences des coups joués

• Les coups et leurs conséquences

  1. Il existe un état dit vrai. C’est un état dans lequel la perception est objective, c’est-à-dire que la chose est vraie telle qu’on la voit. Il y a aussi un état de perception / observation qui est différent de la perception subjective.

  3. L’ensemble des actions possibles (A) de l’agent sur son environnement sont :

• Bouger un bras

• Bouger la « rétine »

• Choisir une direction (comme dans le labyrinthe)

• Choisir un coup à jouer (comme dans « Pile ou Face « )

  1. Ces actions possibles peuvent avoir un environnement fini (c'est-à-dire, par exemple, que l’ensemble des actions pour le « Pile ou Face » est {Pile, Face}) et infini.

  3. Le problème de Markov peut être, ainsi, fini (c'est-à-dire que l’espace des états et des actions est fini) ou infini, déterministe (lorsqu’une action conduit toujours au même résultat) ou non déterministe (quand pour une même action, plusieurs résultats sont possibles). Cet environnement permet de déterminer une stratégie qui maximise R_t. Pour cela on utilise les équations de Bellman.

0. Application

• L’équation de Bellman:

  1. Elle permet de calculer la valeur de l’état « s » en fonction de l’action « a » selon la stratégie p. La stratégie peut être gloutonne (c'est-à-dire qu’on choisit le maximum), ou encore choisie à l’aide de la roulette.

  2. V^p(s) = ?_aÎA(s) p(s,a) ?_s’ P^a_s,s’ [ R^a_s,s’ + g V^p(s’) ]

  3. Avec :

  4. _?aÎA(s) p(s,a) ?_s’ P^a_s,s’ => c’est la probabilité de passer de l’état « s » en l’état « s’ par l’action  « a » .

  5. R^a_s,s’ => c’est le retour immédiat quand on passe de l’état « s » en l’état « s’ » par l’action « a » ( R appartient au Réelle).

  6. V^p(s’) = E [? _k=0 g^k r_t+2+k | s_t+1 = s’ ] => c’est le retour qui va suivre des transitions ultérieures.

  7. P^a_s,s’ => c ‘est la probabilité que l’environnement soit dans l’état « s’ » si l’action « a » est émise dans l’état « s » à l’instant « t ».

  8. g => appartient à [0,1], taux de dépréciation

  10. Par exemple, dans un labyrinthe de 3*3 :

On calcule la valeur de chaque case avec comme stratégie p : p(s,a) = 1/ (toutes actions possibles dans l’état « s »)

C’est-à-dire pour :

V^p(1) = ?_aÎA(s) p(1,a) ?_s’ P^a_s,s’ [ R^a_s,s’ + g V^p(s’) ] = ½*(1*(0+g V^p(0))+ ½*(1*(0+g V^p(4))

= g/2*( V^p(1)+ V^p(4))

V^p(3) = g/2*( V^p(3)+ V^p(6))

V^p(4) = g/3*( V^p(1)+ V^p(4)+ V^p(6))

V^p(5) = g/4*( V^p(4)+ V^p(5)+ V^p(6)+ V^p(8))

V^p(6) = g/4*( V^p(3)+ V^p(5)+ V^p(6))+((1+g V^p(9))/4)

V^p(8) = g/3*( V^p(5)+ V^p(8))+ ((1+g V^p(9))/3)

V^p(9) = g/3*( V^p(6)+ V^p(8))+ ((1+g V^p(9))/3)

On peut alors imaginer le labyrinthe sous cette forme :

Maintenant, on connaît la valeur de chaque état « s » dans tout le labyrinthe.

• L’équation de Bellman pour les qualités :

  1. Ici, on calcul la qualité de l’action pour passer de l’état « s » à l’état « s’ » par l’action « a ».

  2. Q^p(s,a) = ?_s’ P^a _s,s’( R^a_s,s’+g max_a’ Q^p(s’) )

  3. Avec:

  4. Q^p(s,a) = E [ R_t | s_t = s, a_t = a] => qualité d’une paire : « s » appartenant à « S » et « a » appartenant à « A ».

  5. Ici on prend en compte l’action qui va être exécutée.

• L’équation d’optimalité de Bellman :

  1. Ceci permet de calculer la valeur optimale de l’état « s ».

  2. V*(s) = max_a ?_s’ P^a_s,s’ ( R^a_s,s’ + g V*(s’) )

  3. Avec:

  4. V*(s) = max_a’ Q*(s, a’) => Ici on spécifie l’action, pas de somme des strategies (p)

• L’équation d’optimalité des qualités de Bellman :

  1. On calcule la qualité optimale de l’action « a » pour passer de l’état « s » à l’état « s’ ».

  2. Q^*(s,a) = ?_s’ P^a_s,s’( R^a_s,s’+g max_a’ Q^*(s’,a) )

  3. Le Q-Learning découle de ces équations.

1. L’application des Processus de Markov au Q-Learning classique

0. L’algorithme :

Initialisation Q(s,a) arbitrairement ;

Répéter

Initialisation de l’état initiale ;

Initialisation du temps t ;

Répéter

Sélectionner une action « a’ » à émettre dans l’état s_t ;

Effectuer cette action « a’ »;

Observer le retour et le nouvel état s’ ;

Mise à jour de la qualité de l’état « s » par rapport à l’action « a » en fonction de cette qualité, de la qualité de l’état « s’ » dans lequel on arrive par l’action « a », d’un retour et en fonction d’un taux de dépréciation (gamma) et d’un taux d’apprentissage (alpha) compris tous les deux entre zéro et un;

Incrémentation de t ;

Affectation du nouvel état « s’ » en état « s_t » ;

Jusque s_t état terminal ;

Jusque fin ;

0. Mise à jour du Q-Learning :

La formule est simple :

Q(s,a) := Q(s,a) + alpha*(retour + gamma*Max_a’Q(s’,a’) – Q(s,a))

Cette formule est la mise à jour de la qualité de l’état « s » par rapport à l’action « a » en fonction de cette qualité, de la qualité de l’état « s’ » dans lequel on arrive par l’action « a », d’un retour et en fonction d’un taux de dépréciation (gamma) et d’un taux d’apprentissage compris entre zéro et un.

On se trouve dans une situation « A1 ». On choisit la case suivante de façon aléatoire ou en fonction d’une stratégie bien définie. Nommons cette case « A2 ». Pour aller de la situation « A1 » à la situation « A2 », on emprunte une direction, qui peut être droite, gauche, haut ou bas. A chacune de ces directions, on a une valeur de qualité distincte. Ces qualités sont différentes d’une case à l’autre.

Tableau 2 : qualités des différentes actions initiales.

	A	B	C
1	{0,0,0,0}		{0,0,0,0}
2	{0,0,0,0}	{0,0,0,0}	{0,0,0,0}
3	{0,0,0,0}		{0,0,0,0}

Donc :

• Le Q(s,a) est la valeur de la qualité pour Q(A1,gauche) par exemple.

• Alpha est le taux d’apprentissage. Il est compris entre 0 et 1.

• Le retour  peut être éventuel !

• Gamma est le taux de dépréciation. Il est aussi compris entre 0 et 1.

• Le Q(s’,a) est, lorsqu’on regarde sur la possibilité B, la plus grande valeur de qualité des quatre directions possibles.

  3. En ce qui concerne la formule en elle-même, voici des explications plus en détail (de la droite vers la gauche).

• « gamma* Max_a’Q(s’,a) »

  1. Il prend la meilleure qualité de la case suivante. Il veut savoir en fait « à quel point est-ce intéressant de choisir » cette case. Il se sert donc de la meilleure valeur de qualité pour avoir une sorte d’approximation », de « jugement », sur la qualité de la case en elle-même. En fait, la qualité de la case suivante sert pour calculer la qualité de la case actuelle. En quelque sorte, les valeurs « remontent » de la possibilité gagnante à l’origine. Donc c’est le retour qui va, en quelque sorte, remonter le long du chemin.

  3. Dans notre exemple, lorsque l’agent atteint la sortie « C3 » il reçoit un retour valant 1 et la qualité Q(C3,droite) est modifiée.

  4. L’agent retourne au départ et il cherche, de nouveau, au hasard la sortie. Lorsqu’il se trouve en case « C2 », il remarque que la qualité de « C3 » est modifiée. Comme il a une stratégie gloutonne, il choisit la case qui a la qualité la plus grande, en l’occurrence « C3 ». La qualité Q(C2,bas) va alors se modifier également par :

  5. Q(C2,bas) = Q(C2,bas) + alpha * (retour + gamma * Q(C3,droite) - Q(C2, bas))

  6. = 0 + 0.5 * ( 0 + 0.5 * 1 - 0 )

  7. = 0.25.

  8. Ici le retour est nul car ce n’est pas la case qui permet de sortir du labyrinthe pour un cas de retour final. Si le retour est immédiat, la qualité de cette case sera modifiée par rapport à la case suivante.

  9. La case « C3 » est également modifiée par :

  10. Q(C3,droite) = Q(C3,droite) + alpha * (retour + gamma * Q(C3,droite) - Q(C3, droite))

  11. = 1 + 0.5 * ( 1 + 0.5 * 1 - 1 )

  12. = 1.

  13. Et on recommence ainsi jusqu’à l’obtention d’un chemin allant de la case départ « A1 » à la case sortie « C3 ».

  15. Tableau 3 : qualités des différentes actions lorsque l’agent a « appris » avec un retour final.

	A	B	C
1	{0,0,0,0.00390625}		{0,0,0,0}
2	{0.0390625,0,0,0}	{0.171875,0,0,0}	{0,0,0,0.46875}
3	{0,0,0,0}		{1,0,0,0}

Que choisir comme gamma ?

Le gamma est compris entre [0,1]. Il se nomme « paramètres de dépréciation ». En fait, à quel point cette valeur va-t-elle être dépréciée (de moins en moins d’importance) au fur et à mesure de la remontée. Ce qui « remonte » est principalement le retour. Donc plus le retour diminue plus le chemin est long !

Il existe deux points extrêmes :

- Gamma = 1 (plus généralement gamma important).

Quelle que soit la position de la case dans le chemin elle recevra toujours, indirectement, « le plein retour ».

- Gamma = 0 (plus généralement gamma faible).

Par exemple, gamma = 0.001. Quand l’agent choisit la bonne possibilité, la possibilité choisie est récompensée mais seulement un tout petit peu. Donc une fois la valeur remontée jusqu’en haut il ne reste pas grand chose. Cependant, même infime, il reste toujours quelque chose en général. Donc si on fait suffisamment d’itérations dans l’apprentissage, à force de « mini modifications » les possibilités du départ sont quand même modifiées de manière adéquate. Et même mieux, les valeurs finales de qualité auront une très grande précision vu qu’elles ont été modifiées par des toutes petites touches à la fois.

En fait, tout dépend de la nature du problème sur lequel on travaille. Si on prend un programme très grand, il ne restera vraiment rien du tout cette fois, au début, mais surtout le nombre d’itérations à faire pour l’apprentissage sera vraiment trop important pour être faisable sur un ordinateur actuel.

C’est donc une valeur à choisir en fonction de la taille du problème et/ou du temps que l’on a à disposition et/ou à la précision que l’on souhaite au final.

Par exemple :

Tableau 4 : gamma valant 1 & alpha valant 0,5.

	A	B	C
1	{0,0,0,0.0625}		{0,0,0,0}
2	{0.3125,0,0,0}	{0.6875,0,0,0}	{0,0,0,0.9875}
3	{0,0,0,0}		{1,0,0,0}

Tableau 5 : gamma valant 0,1 & alpha valant 0,5.

	A	B	C
1	{0,0,0,0.0000006255}		{0,0,0,0}
2	{0.002,0,0,0}	{0.02375,0,0,0}	{0,0,0,0.09875}
3	{0,0,0,0}		{1,0,0,0}

La comparaison entre les deux tableaux montre bien que lorsqu’on choisit un gamma petit, la qualité après l’apprentissage est plus petite. De ce fait, lorsque le labyrinthe est très grand, la qualité devient très petite. Cela permet une exploration plus importante du labyrinthe. Par contre, lorsque le labyrinthe est petit et que le gamma est grand, la qualité est grande et l’exploration est réduite lorsque la stratégie est gloutonne.

• « – Q(s,a) »

  1. On veut connaître la qualité d’aller dans la case suivante. C’est-à-dire que l’on fait la différence entre la qualité de la case « A1 » et la meilleure qualité de la case suivante.

• «  retour +... »

  1. C’est tout simplement notre fameux retour qui vient s’ajouter quand l’agent atteint la sortie. Et qui, par rappel, remontera au fur et à mesure des itérations suivantes de l’apprentissage de possibilité en possibilité. Mais attention, le retour peut être immédiat. Dans ce cas là, dans l’exemple ci-dessus, si l’agent choisit une direction que l’amène dans un mur, il a un retour négatif de -0.5 Si l’agent atteint le fanion il a un retour positif de 1.5. Sinon à chaque mouvement correct le retour est de 1. Dans ce labyrinthe le but est d’arriver au fanion.

  3. Tableau 6 : labyrinthe contenant les qualités des états en fonction des actions après une exploration totale.

Il y a peu de chance pour que l’agent choisisse une action ayant entraînée un retour négatif car il a une stratégie gloutonne. Par contre l’agent ira vers le fanion au fur et à mesure des passages.

• «  retour + gamma* Max_a’Q(s’,a) – Q(s,a) »

  1. On a donc la modification totale à apporter à la qualité actuelle. Cette modification vient s’ajouter, Mais pas entièrement.

• « alpha »

  1. Alors que le gamma servait localement à choisir telle ou telle possibilité, et donc, influencer localement sur la qualité et la précision de l’apprentissage à l’intérieur d’une même itération, le « alpha », lui, sert plutôt à la qualité globale de l’apprentissage. Mais cette fois, d’une itération à une autre.

  2. En effet, si on ne fait pas intervenir ce coefficient, et que l’on modifie par « retour +... » en entier, à chaque fois, alors lors de la première itération les modifications seront très importantes ! Cela va donner, de suite, l’importance à une case. Il aura donc trouvé une façon de gagner mais pas la « meilleure » façon de gagner (pas la plus optimale !!).

  4. En général, on choisit un alpha faible (par exemple 0.1), et l’on fait un grand nombre d’itérations. Comme cela, on modifie par « petites touches » à chaque passage.

  5. Attention, alpha est un paramètre à choisir selon la complexité du problème et le temps que l’on a à disposition. S’il se focalise sur les chemins qui ne sont pas les meilleurs, il faut diminuer cet alpha (l’idéal serait de pouvoir prendre un alpha infiniment petit et de faire un nombre d’itérations infinies..).

  7. On peut aussi faire varier alpha au cours de l’apprentissage, avec au début, un alpha fort (pour que les modifications soient importantes, pour « dégrossir » le travail plus rapidement), et sur la fin de l’apprentissage on préférera prendre un alpha faible afin d’affiner le résultat. Classiquement on choisit alpha valant 1/( le nombre de visite de la case) qui permet de converger vers la qualité optimale. Si on conserve un alpha fort jusqu’à la fin de l’apprentissage, il y a le risque que : même si l’algorithme a trouvé le meilleur chemin dès le milieu de l’apprentissage, il change complètement d’avis sur la fin car les modifications trop importantes viendront chambouler totalement les valeurs.

  9. Tableau 7 : gamma valant 0,5 & alpha valant 1.

	A	B	C
1	{0,0,0,0.0625}		{0,0,0,0}
2	{0.125,0,0,0}	{0.25,0,0,0}	{0,0,0,0.5}
3	{0,0,0,0}		{1,0,0,0}

Tableau 8 : gamma valant 0,5 & alpha valant 0.1.

	A	B	C
1	{0,0,0,0.00000625}		{0,0,0,0}
2	{0.0004625,0,0,0}	{0.13075,0,0,0}	{0,0,0,0.17195}
3	{0,0,0,0}		{1,0,0,0}

On remarque que plus alpha est grand et plus l’écart entre les différentes qualités est grand. Pour l’apprentissage global, on remarque que pour des petits changements des qualités et donc une plus grande précision, alpha doit être petit. Ici, le labyrinthe est petit, donc il vaut mieux un alpha un peu plus grand. Mais dans un grand labyrinthe si alpha est petit, il faudra faire un grand nombre d’itérations afin d’atteindre la sortie et ce sera le chemin le plus optimal possible.

1. Utilisation du Q-Learning

L’utilisation du Q-Learning peut être diverse. Les exemples classiques du Q-Learning sont les labyrinthes où l’agent doit sortir seul et trouver le chemin optimal. Pour cela, l’agent est dans le labyrinthe toujours au même endroit. Il explore les cases autour de lui de façon aléatoire et finit par trouver la sortie. A ce moment là, la dernière case avant la sortie est récompensée. Puis, l’agent est de nouveau au départ et explore au hasard les cases alentours. Lorsqu’il rencontre une case récompensée, l’agent choisit cette case et la case précédente est récompensée en fonction du retour de la case trouvée. Au fur et à mesure de ces explorations, l’agent trouve de plus en plus de cases récompensées et crée ainsi un chemin. Lorsque l’agent a le choix entre deux cases récompensées, l’agent choisit la case qui a le plus fort retour. Si les retours sont égaux, l’agent choisit au hasard entre ces cases récompensées.

XIII.IV. Application du Q-Learning au Mind Reading Machines : Prosper

Dans notre cas, on utilise le Q-Learning pour déterminer un coup à jouer. De ce fait l’exploration ne se fait pas dans les cases alentours mais sur la base des coups possibles.

1. Les paramètres du Q-Learning appliqués au « Pile ou Face »

0. Pourquoi peut-on utiliser le Q-Learning ?

On peut utiliser l’algorithme du Q-Learning car on se trouve dans un processus de décision de Markov non déterministe. C’est-à-dire que l’on a un état de départ, que l’on fait une action et que l’on se retrouve dans un nouvel état s’. Il est non déterministe car on a le choix entre plusieurs états d’arrivés, c'est-à-dire que le résultat dépend du choix du coup de l’adversaire.

0. Qu’est ce que l’état dans Pile ou Face ?

Pour définir l’état, je me suis inspirée de l’algorithme de « Shannon ». C’est-à-dire qu’il y a 8 états possibles :

• j’ai gagné, puis j’ai rejoué la même chose et j’ai encore gagné

• j’ai gagné, puis j’ai rejoué la même chose et j’ai alors perdu

• j’ai gagné, puis j’ai changé mon jeu et j’ai encore gagné

• j’ai gagné, puis j’ai changé mon jeu et j’ai alors perdu

• j’ai perdu, puis j’ai rejoué la même chose et j’ai alors gagné

• j’ai perdu, puis j’ai rejoué la même chose et j’ai encore perdu

• j’ai perdu, puis j’ai changé mon jeu et j’ai alors gagné

• j’ai perdu, puis j’ai changé mon jeu et j’ai encore perdu

  2. Ces états sont retenus dans une matrice et sont mémorisés par un F ou un V. Le F veut dire : perdu ou changement de comportement, et le V veut dire : gagné ou même comportement.

  4. Tableau 9 : la matrice des états.

Par exemple, si le joueur humain gagne, joue différemment et perd cela donne comme état : V F F soit la quatrième ligne du tableau.

0. Le retour dans Pile ou Face

Le retour s’obtient lorsque l’IA a supposé une action et que celle ci s’avère juste. Alors la qualité de l’état actuel et de l’action choisie (Q(s,a)) obtient le retour qui est de 1.

0. L’action dans Pile ou Face

L’action est de choisir entre le fait que le joueur humain réitère un comportement, c’est-à-dire qu’il joue la même chose que précédemment, ou alors il joue différemment.

0. Déroulement du Q-Learning avec un joueur humain stupide

Le joueur humain joue toujours la même chose, par exemple toujours Pile.

Tableau 10 : qualité des états suivants les actions.

ETATS ACTIONS

Si V alors gagné sinon perdu si V alors rejoué la même chose sinon joué différent

Coup 1 ; Etat = FVF

Q(FVF,F) = 0.5

Q(FVF,V) = 0.5

Roulette = 0.11361792

Coup Prosper = Face

Coup Humain = Pile

Retour = 0

Q(FVF,F) = Q(FVF,F) + alpha * ( retour + gamma * Q(FVF,F) - Q(FVF,F) )

= 0.5 + 0.5 * ( 0 + 0.5 * 0.5 - 0.5 )

= 0.375

Coup 2 ; Etat = VVF

Q(VVF,F) = 0.5

Q(VVF,V) = 0.5

Roulette = 0.1858F172

Coup Prosper = Face

Coup Humain = Pile

Retour = 0

Q(VVF,F) = Q(VVF,F) + alpha * ( retour + gamma * Q(VVF,F) - Q(VVF,F) )

= 0.5 + 0.5 * ( 0 + 0.5 * 0.5 - 0.5 )

= 0.375

Coup 3 ; Etat = FVF

Q(FVF,F) = 0.3125

Q(FVF,V) = 0.5

Roulette = 0.82863081

Coup Prosper = Pile

Coup Humain = Pile

Retour = 1

Q(FVF,V) = Q(FVF,V) + alpha * ( retour + gamma * Q(FVF,V) - Q(FVF,V) )

= 0.5 + 0.5 * ( 1 + 0.5 * 0.5 - 0.5 )

= 0.875

Coup 4 ; Etat = FVF

Q(FVF,F) = 0.375

Q(FVF,V) = 0.875

Roulette = 0.47599317

Coup Prosper = Pile

Coup Humain = Pile

Retour = 1

Q(FVF,V) = Q(FVF,V) + alpha * ( retour + gamma * Q(FVF,V) - Q(FVF,V) )

= 0.875 + 0.5 * ( 1 + 0.5 * 0.875 - 0.875 )

= 1.15625

Coup 5 ; Etat = FVF

Q(FVF,F) = F.375

Q(FVF,V) = V.V5625

Roulette = 0.38849259

Coup Prosper = Pile

Coup Humain = Pile

Retour = 1

Q(FVF,V) = Q(FVF,V) + alpha * ( retour + gamma * Q(FVF,V) - Q(FVF,V) )

= 1.15625 + 0.5 * ( 1 + 0.5 * 1.15625 - 1.15625 )

= 1.3671875

On constate que même si la roulette nous fait jouer par moment  « Face », Prosper joue « Pile » la plupart du temps. Sur une série de VFF coups, Prosper joue « Pile » tout le temps car il a « appris » que le joueur humain avait une stratégie répétitive.

Si le joueur humain a une stratégie répétitive, quelque soit cette stratégie (comme jouer « pile » et « face » en alternance ou encore jouer toujours la même chose tant que le joueur humain gagne….), « Prosper » la reconnaît et gagne la partie de VFF coups. Plus le joueur humain aura une stratégie compliquée et non répétitive et plus « Prosper » aura des difficultés à la reconnaître.

0. La roulette ou le choix de l’action

La roulette est un système qui permet de choisir proportionnellement entre différentes possibilités.

Par exemple dans notre cas, au départ elle est de 0.5 partout. Au fur et à mesure de l’apprentissage la roulette se modifie.

Exemple :

	F	V				F	V
Q(s,a)	0,5	0,5			Q(s,a)	0,5	0,9

Graphique 7 : roulette au début de partie. Graphique 8 : roulette en cours de partie.

On a préféré ce système pour choisir entre les 2 actions à faire, afin que « Prosper » essaie plus de combinaisons possibles. Ainsi « Prosper » ne part pas sur la qualité la plus grande tout de suite mais explore d’autres possibilités avant.

1. Comparaison entre « TitAfterTit » contre « Prosper » et « Shannon » contre « Prosper »

   1. Tableau 11 : la matrice de « Prosper » contre « TitAfterTit » pour une partie de cent coups.

   2. ETATS ACTIONS

Tableau 12 : la matrice de « Prosper » contre « Shannon » pour une partie de cent coups.

ETATS actions

Dans le tableau 9, on remarque que certaines valeurs sont très proches de un et que d’autres sont très proches de zéro. Par exemple Q(( perd, change, perd), change) vaut un et (Q(( perd, change, perd), continu)) vaut zéro. « Prosper » converge vers des valeurs très distinctes.

Par contre, dans le tableau 10, contre « Shannon », le comportement est totalement différent. Il n’y a pas de stabilisation car notre alpha vaut 0.3. Pour avoir une stabilisation il aurait fallu un alpha petit et les qualités convergeraient vers 0.5.

1. L’expérimentation

0. Protocole expérimental

Afin de déterminer les valeurs de alpha et de gamma, nous avons effectué plusieurs sessions de jeu entre « Prosper » contre « Shannon » et « Prosper » contre « Minasi », en faisant varier les paramètres alpha. Les Sessions se déroulent sur 100 coups.

Nous avons remarqué, lors de nos tests, que « Prosper » et « Shannon » obtiennent des résultats similaires.

On a donc choisi, arbitrairement, alpha valant 0.3 et gamma étant nul pour les tests contre les humains. Le gamma est nul car il n’y a pas de retour à long terme, c’est-à-dire que le retour est distribué tout de suite s’il y a lieu et non pas en fin de partie, on doit choisir alpha assez grand car, dans une partie de 100 coups, il faut que la mise à jour de la qualité Q(s,a) soit assez différente de celle d’origine. Mais de ce fait un inconvénient existe : notre qualité fait des sauts violents et ne converge pas.

Le protocole expérimental est donc :

• Alpha = 0.3, gamma = 0.0

• Les joueurs humains contre « Shannon » et contre « Prosper »

• Les parties sont de 100 coups

• On laisse le score des joueurs 

• Le message au début est « Bonne chance »

• Le nombre de joueurs humains est de 36

Nous voulons que les joueurs humains jouent contre les deux intelligences afin de pouvoir comparer leurs performances et ainsi pouvoir comparer « Shannon » et « Prosper ».

Nous avons choisi de faire des parties de 100 coups car les joueurs humains doivent jouer contre les deux intelligences et les joueurs humains se seraient lassés de jouer deux fois 200 coups. La lassitude des joueurs en fin de partie peut fausser les résultats ou, au contraire, faire ressortir un comportement répétitif inconscient.

Nous avons laissé le score afin que l’humain puisse modifier sa stratégie et qu’il essaie, ainsi, de vraiment gagner contre les deux intelligences.

Le message au début de la partie est neutre, ainsi il n’y a pas d’influence dans les jeux des différents humains. On remarque que les joueurs humains adoptent différentes stratégies comme essayer de jouer au hasard, essayer des répétitions jusqu’à ce qu’ils perdent et à ce moment là ils changent. Certains ont une idée du fonctionnement des algorithmes et essaient de les déstabiliser. Tous ces comportements peuvent être influencés au niveau du message du début de partie.

Nous avons eu 36 joueurs humains. Nous les avons contactés par mail (voir annexe 1).

0. Les résultats

Tableau 13 : Récapitulatif des données.

Source : https://fabien-torre.fr/Recherche/MRM/resultats.php

Tableau 14 : les scores moyens.

On remarque qu’on retrouve les mêmes résultats en moyenne et en prédictions correctes sur tous les coups. Les performances de « Shannon » et de « Prosper » sont équivalentes. Les cinq pour cent au dessus de cinquante veulent-ils dire que dans quatre-vingt-quinze pour cent des cas l’humain ferait de l’aléatoire ?

Le temps moyen de « Shannon » et « Prosper » est très petit. Cela veut dire que sur 100 coups les calculs ne sont pas longs. Cela est intéressant pour pouvoir effectuer des parties de plus de 100 coups. « Shannon » joue soixante pour cent des coups au hasard. « Prosper » joue au hasard en début de partie (les deux pour cent) puis il joue suivant l’algorithme. Or l’algorithme lui dit de jouer au hasard par la roulette. C’est-à-dire que même s’il y a une qualité pour l’action « même » Q(s, même) valant 0.9 et qu’il y a cette même qualité mais pour l’action « différent » Q(s, différent) valant 0.3, la roulette peut faire choisir l’action « différent ». « Prosper » joue donc au hasard.

Graphique 9 : les résultats des jeux par rapport au tableau 14.

La moyenne de « Prosper » est équivalente a celle de « Shannon » mais dans les deux cas elles sont supérieures a celles des joueurs humains. On retrouve les mêmes conclusions pour les minimums. « Prosper » a le maximum le plus important.

0. Interprétation

L’ordre d’apparition de « Shannon » et de « Prosper » peut avoir une incidence sur le résultat des différentes parties. En effet, le joueur humain peut être plus combatif à la première partie, il peut également mieux comprendre le jeu à la deuxième partie ou encore il peut être fatigué après la première partie.

La taille des parties peut également avoir une incidence sur le joueur. Plus elles sont courtes, plus le joueur humain est combatif et cherche à gagner. Par contre si les parties sont longues, le joueur humain aura certainement un comportement plus répétitif.

Les résultats de « Shannon et de « Prosper » ne nous permettent pas de conclure sur le fait que l’un des algorithmes est meilleur que l’autre. Ils nous montrent que « Prosper » est aussi efficace que « Shannon ». Il serait donc, intéressant de plus utiliser le Q-Learning dans les Mind Reading Machines.

XIV.Conclusion

Plusieurs points sont mis en évidence par l’expérimentation.

Tout d’abord, l’ordre de rencontre de « Prosper » et de « Shannon » avec le joueur humain. Lorsque le joueur humain rencontre d’abord l’un des algorithmes puis l’autre son niveau de performance peut être différent. En effet, le joueur humain peut avoir mal compris la consigne et c’est lors de la deuxième série qu’il est le plus performant. Il peut également ressentir une fatigue lors de la deuxième série et développer un comportement répétitif sans s’en rendre compte. Cela peut être intéressant pour essayer de comprendre le comportement humain et développer un algorithme simulant ce comportement. Le joueur humain peut aussi être plus combatif et changer de stratégie afin de gagner contre les algorithmes. Pour observer ce comportement, le score doit être accessible au joueur.

Ensuite, la taille des parties par rapport au Q-Learning. L’expérience ne comporte que des séries de 100 coups. « Prosper » n’a pas été testé avec des parties supérieures à ces 100 coups. Donc on ne connaît rien du comportement du Q-Learning sur des parties de 500 coups ou plus.

La valeur de alpha par rapport à la taille des parties est notre troisième point. Plus les séries sont importantes et plus le alpha devait être petit afin de pouvoir observer un comportement judicieux face au joueur humain. Il est possible d’envisager un alpha grand en début de partie, afin de faire ressortir une ou quelques actions, puis de le diminuer au fur et à mesure de la partie. Alpha serait modulable en fonction des actions du joueur humain. De plus si le joueur humain change subitement de stratégie, alpha redevient important afin de pouvoir isoler ce nouveau comportement.

Le dernier point serait de tester différentes stratégies (comme la stratégie de la roulette, la stratégie gloutonne, ou encore une stratégie qui sélectionne grâce a des probabilité proportionnelle ou non) afin de voir laquelle est la meilleure. On pourrait également associer un alpha grand à la stratégie de la roulette afin d’explorer toute les possibilités, puis lorsque alpha diminue, on pourrait l’associer à une stratégie gloutonne (c'est-à-dire une stratégie qui prend la meilleure qualité de l’état à venir).

Le Q-Learning est un algorithme qui gagne contre les joueurs humains. Il est équivalent, avec les données que nous avons, à Shannon. Doit on dire que le fait de mémoriser est inutile ? La mémoire joue-t-elle un rôle important ? Et l’oubli est-il nécessaire ?

Pour pouvoir répondre complètement à ces questions, il faudrait :

• refaire les tests avec des paramètres différents et les faire varier au cours du temps.

• refaire des parties de plus de 100 coups afin de voir si Prosper ne prend pas l’avantage sur Shannon.

• faire ces expériences contre Minasi.

• jouer sur la représentation d’un état en prenant plus ou moins de coups afin de trouver le Q-Learning le plus efficace.

Ce stage m’a permis d’approfondir mes connaissances sur le fonctionnement du Q-Learning. En effet, nous l’avions développé en travaux pratiques mais avec une stratégie gloutonne et un retour en fin de partie. De plus, ce stage m’a fait découvrir les Mind Reading Machines et les différentes applications qui peuvent en découler comme l’approche sociale des comportements humains.

La première difficulté a été de comprendre le principe de « Shannon » et de « Minasi » par le biais des articles référencés dans la bibliographie. C’est en les programmant que l’on voit surgir toute la complexité de ces algorithmes.

La seconde difficulté fut de trouver les paramètres du Q-Learning afin que celui-ci puisse concurrencer « Shannon » et « Minasi ». En effet, si l’action fut assez simple à paramétrer, la tâche pour déterminer un état correct et satisfaisant fut plus ardue. C’est pour cela que nous nous sommes inspiré de « Shannon » pour définir notre état.

Enfin, l’expérimentation nous a permis de valider nos choix de paramètres mais nous avons réalisé qu'il était nécessaire de les tester d’avantage.

XV.Annexe 1

«Bonjour,

Pour mon mémoire, je dois faire des comparaisons entre deux intelligences artificielles. Pour cela vous devez impérativement jouer 2 parties de Pile ou Face : une contre Shannon et une contre Prosper.

On voit contre qui on joue sur la page d'accueil, sous "commencer la partie"

 Lorsque vous avez joué avec l'un, vous devez relancer la page jusqu'a ce que l'autre IA apparaisse.

 Voici le lien sur lequel vous trouverez le jeu Pile ou Face

 https://fabien-torre.fr/Recherche/MRM/partie.php

Attention: faites bien attention de jouer une fois contre Shannon et une autre fois contre Prosper !! il se peut qu'il faille réouvrir le lien plusieurs fois avant d'avoir l'autre IA.

D'avance je vous remercie tous.

Julie »

XVI.

XVII.Bibliographie

[Delahaye Jean-Paul, 1999]

« L’intelligence humaine à nouveau dominée ? » Une nouvelle catégorie de jeux où la machine « psychologue » apprend à prévoir le comportement des joueurs humains. Pour la Science n° 263, Septembre 1999.

[Kaelbling, Littman & Moore, 1996]

« Reinforcement Learning : A Survey ». Journal of Artificial Intelligence Research 4. P 237 à 285. Mai 1996.

[Meyer & Zucker, 199?]

« Mind-Reading Machines », modélisation des adversaires et anticipations dans les jeux à informations complètes et imparfaites. LIPG-CNRS, Pôle IA Université Pierre et Marie Curie.

[Meyer C., Ganascia J.G., Zucker J.D., 1997b]

« Modélisation de stratégie par Apprentissage et Anticipation génétique ». Acte de conférence des Journées ingénierie des connaissances et Apprentissages automatiques. LIP6-IBP-CNRS, Université Paris 6, 1997.

[Meyer, 1999]

« S.A.G.A.C.E, Solution Algorithmique Génétique pour l’Anticipation de Comportement Evolutif ». Application aux jeux à information complète et imparfaite. Thèse de doctorat de l’université de Paris 6. Juin 1999.

[Meyer, 1999]

« S.A.G.A.C.E, Solution Algorithmique Génétique pour l’Anticipation de Comportements Evolutifs ». PowerPoint. Paris 6. Juin 1999.