Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

M1–Master d’informatique – 2008/2009 Apprentissage ` a Partir d’Exemples janvie

M1–Master d’informatique – 2008/2009 Apprentissage ` a Partir d’Exemples janvier 2009 Apprendre la strat´ egie de l’adversaire 1 But Soit un jeu ` a deux joueurs quelconque. Supposons que l’un des deux joueurs suive une strat´ egie simple (r´ ep´ etitive par exemple). Peut-on d´ eﬁnir un joueur ’apprenant’ qui, en regardant les coups jou´ es pr´ ec´ edemment par son adversaire, serait capable de pr´ edire ` a coup sˆ ur, ou avec une bonne probabilit´ e de succ` es, le prochain coup de son adversaire? Si la r´ eponse est oui, on peut alors se poser d’autres questions : par exemple, concernant les strat´ egies ` a deviner : – Existe-t-il des strat´ egies ’non devinables’ ? – Certaines strat´ egies sont-elles plus dures ` a apprendre que d’autres ? – Existe-t-il des strat´ egies diﬃciles ` a deviner ? Concernant le mode op´ eratoire du joueur qui doit deviner : – Quel algorithme (ou famille d’algorithmes) choisir ? – Quand faut-il apprendre, et quand faut-il utiliser ce que l’on a appris? 2 Un premier jeu Le jeu que nous allons consid´ erer est tr` es simple, sa programmation ne pose aucun probl` eme, ce qui permettra de se focaliser sur la programmation du joueur apprenant. Chifoumi, ou Ciseaux, Pierre, Feuille est un jeu ` a deux joueurs. Une partie se d´ eroule en n manches, o` u une manche consiste pour chaque joueur ` a annoncer (simultan´ ement) l’un des trois mots Ciseaux, Pierre ou Feuille. – Si les deux joueurs annoncent la mˆ eme chose, la manche est nulle, personne ne marque de points. – Les Ciseaux l’emportent sur la Feuille (ils la coupent). – La Pierre l’emporte sur les Ciseaux (elle les brise). – La Feuille l’emporte sur la Pierre (elle l’enveloppe). 3 Les impl´ ementations de base Les indications, exemples, et impl´ ementations d´ ecrites dans cette section sont fournies pour vous aider. Si vous pr´ ef´ erez les d´ eﬁnir diﬀ´ eremment ou les modiﬁer, libre ` a vous : le principal ´ etant que vous puissiez ´ evaluer la performance de votre joueur apprenant face ` a ses adversaires. 3.1 R´ ecup´ erer les sources Les paquetages chifoumi, clavier et partie sont fournis ’en entier’. Le paquetage joueurs contient la description de plusieurs types de joueurs (mais pas les joueurs utilisant les arbres de d´ ecision . . .). Le programme premierEssai.java contient un exemple d’utilisation des classes. Ces paquetages sont disponibles sur la page du cours d’APE sur le serveur du FIL (ﬁchier sources.tgz) 3.2 Compiler un programme Lorsque vous utiliserez des classes de Weka, vous devrez indiquer au compilateur o` u trouver ces classes : javac -d classes -classpath /opt/weka-3-4-11/weka.jar -sourcepath sources sources/premierEssai.java Pour l’ex´ ecution, c’est plus simple : java -cp classes premierEssai 3.3 Les coups possibles Le paquetage chifoumi ne contient que la classe Chifoumi.java, qui d´ eﬁnit les trois coups possibles et les m´ ethodes permettant de les comparer entre eux, de les transformer (entiers ou chaˆ ıne).. . 3.4 L’arbitre La classe Partie sert ` a faire s’aﬀronter deux joueurs, leur demande de jouer, informe chacun du coup jou´ e par l’autre, et aﬃche les scores. Le programme principal suivant se contente donc de cr´ eer une partie, de d´ eﬁnir les joueurs, et de lancer la comp´ etitions : import partie.Partie; import joueurs.*; public class competition{ public static void main(String argv[]){ Joueur j1=new JoueurReplique(); Joueur j2=new Joueurj48(100); Partie p=new Partie(j1,j2); p.setVerbosity(); p.Play(10000); } } 3.5 Les joueurs 3.5.1 L’interface On peut d´ eﬁnir l’interface Joueur minimale comme ´ etant compos´ ee de deux m´ ethodes : – L’une permettant d’annoncer le coup choisi. – L’autre permettant d’informer le joueur du coup jou´ e par son adversaire. package joueurs; import chifoumi.*; public interface Joueur{ public Chifoumi coupJoue(); public void memorise(Chifoumi coupAdverse); } 2 3.5.2 Les adversaires On peut d´ eﬁnir facilement plusieurs types de joueurs. Tout d’abord les joueurs qui ne s’occupent pas de leur adversaire : – Le joueur al´ eatoire : il est impossible d’apprendre sa strat´ egie. – Le joueur pr´ ef´ erentiel : il joue un coup plus souvent que d’autre. – Le joueur p´ eriodique : la succession des coups qu’il joue est p´ eriodique : la p´ eriode peut ˆ etre plus ou moins longue. – Le joueur markovien : la probabilit´ e qu’il joue un coup d´ epend du coup qu’il a jou´ e au coup pr´ ec´ edent. – . . . Les joueurs dont la strat´ egie d´ epend des coups jou´ es par leur adversaire : – Le joueur r´ eplicant : il joue le coup jou´ e au coup pr´ ec´ edent par son adversaire. – Le joueur r´ eplicant-m´ echant : il joue le coup qui aurait battu le coup pr´ ec´ edent de son adversaire. – Le joueur statisticien : il joue le coup qui gagne contre le coup le plus souvent jou´ e par son adversaire. – . . . Certaines de ces strat´ egies vous sont fournies dans le paquetage joueur, les autres peuvent s’en d´ eduire facilement. D’autres strat´ egies sont possibles, vous pouvez les d´ eﬁnir, les programmer et les diﬀuser . . . 3.5.3 Le joueur apprenant Un premier joueur apprenant pourrait ˆ etre d´ eﬁni de la mani` ere suivante : – Dans un premier temps, il joue au hasard (ou suivant une strat´ egie rigide), et observe le comportement de son adversaire. – Une fois qu’il a accumul´ e suﬃsamment d’informations sur son adversaire, il essaie de comprendre sa strat´ egie. – Une fa¸ con de comprendre le comportement de l’adversaire, c’est de construire un classiﬁeur qui, ´ etant donn´ es les n derniers coups de l’adversaire, lui retourne le coup suivant. – Pour cela, il d´ ecoupe la s´ equence des k derniers coups de son adversaire en k −n fenˆ etres de taille n + 1 : les n premi` eres valeurs sont les coups connus, la derni` ere valeur est celle qu’il faut deviner. – Il range ses exemples dans un ensemble d’apprentissage (classe Instances). – Il construit un arbre de d´ ecision (par exemple). – une fois qu’il a son classiﬁeur, il lui fournit en entr´ ee les n derniers coups de son adversaire, et attend la r´ eponse. – Il joue alors le coup qui peut vaincre cette pr´ ediction. En r´ esum´ e, le premier joueur apprenant que vous allez d´ eﬁnir : – Contiendra un arbre de d´ ecision – Maintiendra l’historique complet des coups jou´ es par son adversaire – D` es que possible, il construira le classiﬁeur. – Il utilisera ce classiﬁeur pour pr´ evoir le coup de l’adversaire. – L’arbre une fois construit est-il intangible ? – Quand et comment le modiﬁer ou le reconstruire? Question 3.1 : Construisez un joueur apprenant bas´ e sur un arbre de d´ ecision, contrˆ olez son eﬃcacit´ e contre divers adversaires. Aﬃchez et interpr´ etez l’arbre qu’il construit. 4 Evaluation du r´ esultat On peut suivre l’eﬃcacit´ e de l’apprentissage contre un joueur donn´ e en regardant l’´ evolution du nombre (ou de la proportion) de parties gagn´ ees, nulles, perdues : la classe Partie aﬃche ces r´ esultats, qu’on peut lire dans n’importe quel logiciel de trac´ e de courbes (gnuplot, par exemple). 3 Les courbes suivantes vous donnent quelques exemples de comportement. 0 50 100 150 200 250 300 350 400 0 100 200 300 400 500 600 700 800 900 1000 Nombre de parties Nombre de parties jouees Joueur aleatoire contre apprenant Aleatoire gagne Match nul Apprenant gagne Fig. 1 – Aleatoire vs Apprenant : on ne peut rien apprendre 5 Un pas plus loin Et quand le joueur adverse d´ ecide de son coup, non seulement en fonction de ses coups pr´ ec´ edents, mais aussi en fonction des coups du joueur apprenant ? Est-il possible encore ` a celui-ci de jouer gagnant sur le long terme ? Une premi` ere r´ eponse consiste ` a dire que puisque c’est comme ¸ ca, il va m´ emoriser non seulement les coups de son adversaire, mais aussi les siens. Question 5.1 : Construisez ce joueur. Est-il plus eﬃcace, moins eﬃcace ? Existe-t-il des strat´ egies adverses qu’il comprend mieux que son grand fr` ere? 4 0 100 200 300 400 500 600 700 800 900 0 100 200 300 400 500 600 700 800 900 1000 Nombre de parties Nombre de parties jouees Joueur repliquant mechant contre apprenant Periodique gagne Match nul Apprenant gagne Fig. 2 – Periodique vs Apprenant : Quand l’apprenant comprend, il ne perd plus jamais 0 500 1000 1500 2000 2500 3000 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 Nombre de parties Nombre de parties jouees Joueur markovien contre apprenant Markovien gagne Match nul Apprenant gagne Fig. 3 – Markovien vs Apprenant : l’apprenant ne gagne pas toujours. . . 5 0 1000 2000 3000 4000 5000 6000 7000 8000 0 1000 2000 3000 4000 5000 6000 7000 uploads/Sports/ apprendre-strategie.pdf