Algorithme min-max et accélération alpha-beta
Contents
1. 6 5 parcours indiqu en vert Algorithme 2 Algorithme min max pour calculer v version brute fonction eval e sie F alors Dans un tat final on calcule le quotient des scores resultat s4 e sg e sinon si J e A alors On calcule a le max des v e parmi les fils e de e a0 pour e S e faire a max a eval e fin pour resultat a sinon On calcule B le min des v e parmi les fils e de e B pour e S e faire B min B eval e fin pour resultat 6 fin si fin si retourner resultat fin fonction 2 5 Calcul profondeur fix e et heuristique d valuation La complexit de l algorithme min max dans sa version brute est videmment exponentielle en le nombre de coups qu il faut jouer pour terminer la partie Aussi en pratique il n est souvent pas possible d aller explorer toutes les possibilit s qui sont en nombre trop grand On arr te donc le calcul une profondeur fix e p permettant que ce calcul se fasse en temps raisonnable Le probl me c est qu a priori la notion de score n existe que pour les tats finaux et qu on ne peut donc pas appliquer le calcul tel que pr c demment Il va donc falloir d finir des scores temporaires s e et s s e qui permettront de dire tout moment si l tat e est plut t favorable par rapport B ou pas Ces scores temporaires devront co ncider avec les scores r els dans le cas2. o un tat est final Dans certains jeux la notion de score temporaire est tr s claire dans d autre moins checs et il faut trouver exp rimentalement une mesure satisfaisante Puissance 4 on peut d finir les scores temporaires de plusieurs mani res par exemple en prolongeant les fonctions scores d finies dans les exemples pr c dents pour les fin de partie toute configuration interm diaire car c est possible ici ex1 s e oo resp s e 00 si la configuration e pr sente quatre ronds align s respectivement quatre croix align es et s 4 e 0 resp s e 0 sinon ex2 s 4 e resp s4 e est le maximum du nombre de ronds align s pr sents resp croix align es pr sentes dans la configuration finale e ex3 on d finit 1 s 4 e 1 resp sh e 1 si la configuration ne fait appara tre de des ronds isol s resp croix isol es 2 s e 2 resp sle 2 si la configuration fait appara tre au mieux deux ronds contigus resp deux croix contigu s 3 s i e 3 resp sn e 3 si la configuration fait appara tre au mieux trois ronds align s resp trois croix align s 4 s 4 e o resp s4 e 00 si la configuration fait appara tre quatre ronds align s resp quatre croix align s ou encore d autres mani res On d finit ensuite une fonction w dite heuristique c est dire une fonction dont le comporte ment sera raisonnablement
3. v 2 pour toute position e E la valeur v e soit d autant plus grande que la configuration est favorable A et d autant plus petite que la configuration est favorable gt B Le fait qu un tat e soit favorable signifie que le joueur J e peut raisonnablement esp rer pouvoir aboutir une position finale gagnante partir de e Reste encore d finir plus pr cis ment ce qu on entend par l 2 2 Hypoth se de travail et d finition de la fonction d valuation Il est possible qu une position soit favorable sans l ombre d un doute si quoi que fasse l adver saire on finira par gagner En revanche dans la plupart des cas le fait qu une position soit favo rable ou pas d pend norm ment de la mani re dont l adversaire va se comporter En d finissant la fonction v par le fait que pour tout e sa e sg e sieeF v e 4 a e si J e A avec a e ni A ble si J e B avec Be an LC une fa on simple de mod liser le point 2 de la Section 2 1 consiste supposer que les adversaires se comportent de la mani re suivante partir d une position e A choisit toujours un tat e S e qui atteint le maximum a e lorsque c est lui de jouer B choisit toujours un tat e S e qui atteint le minimum Se lorsque c est lui de jouer 2 3 Comment joue t on Si l on dispose d une fonction v d finie comme pr c demment une machine imp
4. Algorithme min max et acc l ration alpha beta Lancelot Pecquet 25 novembre 2004 1 Mod lisation des jeux de r flexion On consid re un jeu de r flexion ou deux joueurs et B jouent alternativement L ensemble des tats possibles du jeu est not E chaque configuration du jeu e est associ e la valeur J e qui vaut si le coup pr c dent a t jou par B et B si le coup pr c dent a t jou par en convenant que J eo o eo est l tat initial de la partie On notera galement S e l ensemble des configurations qui jouables partir de e ce tour Une configuration e est dite finale si S e On notera F l ensemble de ces configurations finales En d but de partie le joueur choisit une configuration e dans S eo puis c est au tour du joueur B de choisir une configuration ez dans S e et ainsi de suite La partie se termine lorsque le coup de l un des joueurs conduit une configuration finale Une fois la partie termin e dans l tat f F le joueur a un score s4 f et le joueur B a un score sg f Les scores sont des r els positifs ou nuls ou bien 00 Le gagnant est celui des deux joueurs qui a le plus haut score Si les scores sont gaux les joueurs sont ex quo Puissance 4 on peut d finir les scores de fin de partie de plusieurs mani res par exemple exl s4 e 00 resp sp e 00 si la configuration e pr sente quatre ronds align s respectivement qua
5. es v e o e d crit les tats qui tiqu tent les fils de e si J e le minimum des v e o e d crit les tats qui tiqu tent les fils de e si J e B et de recommencer ainsi de suite jusqu atteindre la racine de l arbre ainsi que cela est indiqu dans la Fig 1 6 5 1 5 4 5 8 14 17 22 31 34 OOO Go A a a Go a a C3 G2 G3 G5 Go 7 5 6 5 7 5 4 5 1 1 5 7 5 9 5 1 5 0 2 5 14 5 1 5 1 5 24 26 28 29 4 5 1 5 3 5 3 5 FIG 1 On crit v e s4 e sg e pour chaque tat final e correspondant une feuille de l arbre On propage ensuite alternativement le maximum et le minimum de ces valeurs en remontant le long de l arbre jusqu la racine Les sommets sont num rot s dans l ordre du parcours en pronfondeur de l arbre qui sera fait par l Algorithme 2 Une fois faits tous les calculs la strat gie de jeu consiste pour choisir toujours le coup e qui maximise v e et pour B choisir toujours le coup e qui minimise v e Si le joueur joue contre la machine B il peut gagner en choisissant l tat 2 qui maximise v puis la machine B choisirai l tat 3 qui minimise v ensuite joue dans l tat 5 pour maximiser v puis la machine B choisira l tat 7 pour minimiser v Au final A gagnera sur B avec un rapport des scores s4 e sp e
6. et qui r ussit clairement mettre en vidence les qualit s du programme dans le temps imparti a une note qui peut tendre vers 20 20 13
7. gage appliqu l exemple pr sent est d fini dans la Fig 4 On formalise cette astuce avec l Algorithme 5 lequel utilise une fonction auxiliaire calcul e dans l Algorithme 6 Une version profondeur fix e peut galement tre d finie Algorithme 5 Algorithme alpha beta pour calculer v fonction principale Seules les valeurs inint ressantes gt ne sont pas calcul es fonction eval approx e retourner eval approx aux e 0 00 fin fonction 6 5 4 S 8 14 17 29 el 34 do T an ron SY ror OOO Go ad ad a Go Gs A G3 7 G2 G3 G5 Go 7 5 6 5 7 5 4 5 1 1 5 7 5 9 5 1 5 0 215 1455 15 15 24 26 28 29 ul 4 5 1 5 3 5 3 5 F1G 4 En appliquant les lagages alpha beta la Fig 1 devient celle ci De m me une fois faits tous les calculs la strat gie de jeu consiste pour choisir toujours le coup e qui maximise v e et pour B choisir toujours le coup e qui minimise v e Si le joueur joue contre la machine B il peut gagner en choisissant l tat 2 qui maximise v puis la machine B choisirai l tat 3 qui minimise v ensuite joue dans l tat 5 pour maximiser v puis la machine B choisira l tat 7 pour minimiser v Au final gagnera sur B avec un rapport des scores s4 e sp e 6 5 parcours indiqu en vert la strat gie est bien la m me que da
8. l mentant l algorithme min max joue selon l Algorithme 1 Algorithme 1 Algorithme permettant de choisir un tat de jeu en exploitant une fonction d valuation v e fonction choix depuis e si J e alors r sultat e parmi les Se tel que v e est maximal sinon r sultat e parmi les S e tel que v e est minimal fin si retourner r sultat fin fonction Dans le cas o plusieurs tats conduisent au maximum respectivement au minimum la machine pourra choisir al atoirement parmi ceux l Si la machine joue contre un humain celle ci n aura qu faire ses choix par rapport l tat dans lequel l humain l aura plac au coup pr c dent 2 4 Algorithme de calcul de la fonction d valuation v Bien que l arbre suivant ne doive pas tre construit explicitement il peut tre utile de le d finir pour comprendre la situation Consid rons donc T l arbre des configurations du jeu c est dire l arbre dont les n uds sont tiquet s par E avec les propri t s que 1 la racine de T est tiquet e par eo 2 tant donn un n ud tiquet par e ses fils sont tiquet s par les l ments de S e corres pondant aux configurations accessibles en jouant un coup partir de e Le principe consiste tiqueter chaque feuille correspondant un tat e dans l arbre T par la valeur v e puis d tiqueter le n ud p re correspondant un tat e par le maximum d
9. le texte suit un cheminement logique la grammaire et l ortho graphe sont respect es la qualit de la r alisation mise en page illustrations par des dessins photos captures d crans En gros on peut dire que 1 2 3 4 un mode emploi qui ne respecte pas la structure demand e a moins de 08 20 un mode d emploi qui ne permet pas d utiliser le programme en quelques minutes sans avoir besoin de regarder ailleurs a moins de 10 20 un mode d emploi qui satisfait ces crit res peut avoir une note entre 10 et 20 selon le degr de respect des crit res pr c dents Calcul de la note du programme La note de votre programme consistera en une mesure de l ensemble des crit res suivants 1 conformit avec le cahier des charges chacune des fonctionnalit s demand es est r alis e 2 structures de donn es celles ci doivent tre pertinentes et claires 3 algorithmique les m thodes r pondent au probl me pos de mani re efficace 4 robustesse le programme ne plante pas m me si on ne rentre pas les bonnes valeurs l utilisateur est invit modifier ses choix s il s est tromp 12 5 modularit le probl me est bien d coup en fonctions et proc dures voire packages pertinentes pour l initialisation l affichage les diff rentes t ches r aliser 6 clart le code source est lisible et judicieusement comment les variables ont des noms pertinent
10. n 2 6 Acc l ration alpha beta en bornant la fonction d valuation En fait lors du calcul de v ou de w on fait des calculs inutiles En effet on peut souvent savoir qu on a d j trouv un maximum cf Fig 2 ou un minimum cf Fig 3 sans avoir besoin d explorer tout l arbre des possibilit s alpha beta beta FIG 2 Alors qu on est en train de calculer un maximum q au niveau interm diaire le minimum B qui est en train d tre calcul au niveau inf rieur prend une valeur inf rieure ou gale a D s lors il n est plus n cessaire de continuer car toutes les autres valeurs de B seront inf rieures ou gales la valeur actuelle et la valeur de a sera donc inchang e On remonte donc au niveau interm diaire et on lague les branches qui n ont plus tre explor es en bleu beta alpha M S alpha FIG 3 Alors qu on est en train de calculer un minimum 8 au niveau interm diaire le maximum a qui est en train d tre calcul au niveau inf rieur prend une valeur sup rieure ou gale 5 D s lors il n est plus n cessaire de continuer car toutes les autres valeurs de a seront sup rieures ou gales la valeur actuelle et la valeur de 8 sera donc inchang e On remonte donc au niveau interm diaire et on lague les branches qui n ont plus tre explor es en bleu Le r sultat de cet la
11. ns la Fig 1 bien que par exemple dans la case 20 soit ici tiquet e par la valeur 3 5 alors qu elle l tait par 2 5 dans la Fig 1 peu importe car le maximum est toujours 6 5 Un ph nom ne analogue a lieu dans la case 8 Algorithme 6 Algorithme alpha beta pour calculer v fonction auxilliaire fonction eval approx aux e a 8 sie F alors Dans un tat final on calcule le quotient des scores resultat s4 e sg e sinon si J e alors On calcule a le max des v e parmi les fils e de e pour e S e faire si lt f alors a max a eval approx aux e a B sinon on lague comme dans la Fig 3 sortir de la boucle fin si fin pour resultat a sinon On calcule B le min des v e parmi les fils e de e pour e S e faire si lt f alors B min B eval approx aux e a B sinon on lague comme dans la Fig 2 sortir de la boucle fin si fin pour resultat fin si retourner resultat fin fonction 2 7 Optimisation de la m thode alpha beta Il est clair que si les l ments de S e sont tri s par ordre croissant de v e pour J e le max et le min se calculent en temps constant et on pourrait aussi savoir gr ce une recherche dichotomique en temps logarithmique en S e les l ments partir desquels la recherche doit se poursuivre et ceux liminer En pratique on ne peut pas forc ment attendre d avoir tous les n uds te
12. proche de ce qu on veut mais qu on ne peut pas atteindre exactement valant s e s e pour les tats e qui sont profondeur Pmax ou bien qui sont finaux et qu on d finit de mani re analogue v Ainsi de la m me fa on pour toute position e E la valeur w e soit d autant plus grande que la configuration est favorable gt et d autant plus petite que la configuration est favorable gt B On d finit donc s i e sn e sie F ou sie est profondeur pmax w e 4 a e si J e A avec a e e w e ble si J e B avec Be min w e e ES e que l on calcule gr ce l Algorithme 3 qui utilise lui m me la fonction auxilliaire calcul e par PAlgorithme 4 Algorithme 3 Algorithme min max profondeur fix e fonction principale fonction eval e pmax retourner eval aux e 0 fin fonction Algorithme 4 Algorithme min max profondeur fix e fonction auxiliaire fonction eval aux e i sie F ou si i Pmax alors Dans un tat final on calcule le quotient des scores resultat w e sinon si J e A alors On calcule a le max des v e parmi les fils e de e a0 pour e S e faire a max a eval aux e i 1 fin pour resultat a sinon On calcule B le min des v e parmi les fils e de e B pour e S e faire B min 8 eval aux e i 1 3 fin pour resultat fin si fin si retourner resultat fin fonctio
13. ravail r alis 3 la clart de la d marche les explications sur les aspects th oriques et pratiques sont claires 11 4 5 la clart d expression le texte suit un cheminement logique la grammaire et l ortho graphe sont respect es la qualit de la r alisation mise en page illustrations par des dessins photos captures d crans En gros on peut dire que 1 2 3 3 3 un rapport qui ne respecte pas la structure demand e a moins de 08 20 un rapport qui ne d crit pas bien ce qui a vraiment t fait a moins de 10 20 un rapport qui satisfait les trois premiers points pr c dents peut avoir une note entre 10 et 20 selon le respect des crit res pr c dents Calcul de la note du mode d emploi Le mode d emploi doit faire de une deux pages Il a pour objectif de permettre une personne de tester le logiciel en une ou deux minutes Il pr sentera 1 2 un r sum des r gles du jeu la liste des fichiers n cessaires la compilation et l ex cution du logiciel et la mani re de compiler les sources la syntaxe requise pour lancer le programme avec ses ventuelles options 4 la syntaxe requise l int rieur du programme pour utiliser celui ci 5 la syntaxe de sortie du programme Les crit res d valuation sont 1 2 3 le respect de la structure demand e pour le document l aspect synth tique du document la clart d expression
14. rminaux pour pou voir les trier puisque pr cis ment on essaie de ne pas tous les calculer Dans une version plus sophistiqu e on pourrait utiliser des calculs pr c dents et l heuristique pour faire un pr tri Une version profondeur fix e se d duit de mani re analogue celle d finie pr c demment Une bonne utilisation d alpha beta permet de doubler la profondeur de recherche en g n ral 10 3 Crit res d valuation du projet 3 1 Calcul de la note globale Chaque bin me aura 10 min pour pr senter son travail et 5 min de questions La note du projet sera calcul e de la mani re suivante round note du rapport note du mode d emploi 2 note du programme 3 note d oral 7 note N o round est la fonction qui arrondit l entier le plus proche c est dire que round x est l entier n tel que x n est minimal si x k 2 pour k N et qui vaut n k 2 sinon le coefficient 3 l oral permet de discriminer au sein d un bin me ceux qui ont plus ou moins travaill et ou compris le coefficient 2 au programme permet de donner une importance plus grande celui ci par rapport au mode d emploi et au rapport qui sont tout de m me importants 3 2 Calcul de la note du rapport Le rapport a pour objectif de pr senter l ensemble du travail r alis Il comportera une douzaine de pages maximum hors annexe et sera structur de la mani re suivante 1
15. s 7 adaptabilit le code est facilement adaptable des situations voisines pas de constantes num riques 8 ergonomie le logiciel est d un maniement ais et naturel En gros on peut dire que 1 un programme qui ne compile pas a moins de 08 20 2 un programme qui ne satisfait pas le cahier des charges a moins de 10 20 3 un programme qui satisfait le cahier des charges peut avoir entre 10 et 20 selon le degr de respect des crit res cit s et de l efficacit des m thodes retenues 3 5 Calcul de la note d oral L oral consistera en une d monstration du logiciel On notera 1 aisance dans la manipulation du programme 2 la compr hension du fonctionnement interne du programme 3 la mise en vidence des qualit s du programme dans l ordre pr vu la section pr c dente respect du cahier des charges adaptabilit 4 le respect du timing 5min par candidat 5 la ma trise des aspects th oriques du sujet en particulier la lecture du rapport 6 la clart de l expression En gros on peut dire que sous r serve que le programme satisfasse le cahier des charges 1 un tudiant qui ne sait pas manipuler son programme a moins de 08 20 2 un tudiant qui ne comprend pas l essentiel de son programme a moins de 10 20 3 un tudiant qui sait manipuler son programme qui comprend la mani re dont il fonctionne du point de vue de la programmation et du point de vue th orique
16. tre croix align es et s4 e 0 resp sg e 0 sinon ex2 sA e resp sg e est le maximum du nombre de ronds align s pr sents resp croix align es pr sentes dans la configuration finale e ex3 on d finit 1 sale 1 resp sp e 1 si la configuration ne fait appara tre de des ronds isol s resp croix isol es 2 safe 2 resp sg e 2 si la configuration fait appara tre au mieux deux ronds contigus resp deux croix contigu s 3 sA e 3 resp sp e 3 si la configuration fait appara tre au mieux trois ronds align s resp trois croix align s 4 sA e resp sp e 00 si la configuration fait appara tre quatre ronds align s resp quatre croix align s ou encore d autres mani res 2 Algorithme min max 2 1 Fonction d valuation L algorithme min max permet un ordinateur de jouer de mani re performante ce type de jeu en anticipant sur ce que sera la situation plusieurs coups l avance L id e initiale consiste d finir une fonction d valuation v E R U 00 telle que 1 pour toute position finale f F on ait v f s4 f sp f L objectif du joueur A revient donc maximiser v f celui de B est de minimiser v f Si v f gt 1 le joueur a gagn si v f lt 1 c est le joueur B qui a gagn Si v f 1 les joueurs sont ex quo on prendra donc la convention que 0 0 1 et que 0 00 1 dans la d finition de
17. un r sum d une demi page reprenant la probl matique g n rale et vos r sultats celui ci permet au lecteur de comprendre de quoi il s agit en moins d une minute 2 une table des mati res 3 une introduction d une ou deux pages pr sentant bri vement le contexte jeu de r flexion r gles la probl matique diff rents points du cahier des charges le travail r alis et le plan du rapport 4 le corpus d crivant en d tail en une dizaine de pages maximum votre travail Vous prendrez soin en particulier de pr ciser a la description th orique des structures de donn es et des algorithmes retenus b l organisation pratique du programme structures de donn es proc dures et fonctions c les r sultats d exp riences permettant de montrer les limites de votre travail 5 une conclusion d une page dans laquelle apr s avoir bri vement rappel l objectif at teindre vous pr senterez les r sultats obtenus et les perspectives sur une suite ventuelle de ces travaux 6 un index ventuellement 7 une bibliographie ventuellement 8 des annexes comprenant en particulier a les listings complets b le mode d emploi not part voir section suivante Les crit res d valuation sont 1 le respect de la structure demand e r sum introduction 2 la pr cision des r sultats on sait exactement quoi on a vraiment abouti et o sont les limites du t
Download Pdf Manuals
Related Search