![\"Awele\"](\"http:\/\/www.blaess.fr\/christophe\/wp-content\/uploads\/2011\/03\/awele.jpg\" "\\"Awele\\"")
<\/a><\/p>\nLe jeu d’Aw\u00e9l\u00e9<\/h2>\n
<\/p>\n
L’Aw\u00e9l\u00e9<\/em> fait partie de la famille des jeux de semaille, o\u00f9 des graines circulent alternativement sur les domaines des deux adversaires, et o\u00f9 la victoire revient \u00e0 celui dont la r\u00e9colte est la plus avantageuse. Appartenant \u00e0 une culture de tradition orale, l’Aw\u00e9l\u00e9 est un jeu vivant, dont les r\u00e8gles \u00e9voluent selon les r\u00e9gions et selon les \u00e9poques. Nous utiliserons les r\u00e8gles les plus commun\u00e9ment admises, mais des variations sont donc tout \u00e0 fait imaginables.<\/p>\n L’Aw\u00e9l\u00e9 se joue sur un plateau o\u00f9 sont creus\u00e9s douze trous, organis\u00e9s en deux rang\u00e9es appartenant aux deux adversaires. On place initialement quatre graines dans chaque trou. Les trous peuvent \u00eatre simplement creus\u00e9s dans le sable et les graines figur\u00e9es par de petits cailloux, ou au contraire le plateau peut \u00eatre une oeuvre d’art richement d\u00e9cor\u00e9e. Alternativement, chaque joueur saisit tout le contenu de l’un de ses propres trous et le s\u00e8me, graine par graine, dans le sens inverse des aiguilles d’une montre, dans chaque trou – y compris ceux de son adversaire. La seule exception est le trou de d\u00e9part qui, st\u00e9rile pendant une saison, doit rester vide. Il est donc saut\u00e9 lors de la semaille. Lorsque la derni\u00e8re graine est pos\u00e9e dans un trou de l’adversaire comportant pr\u00e9alablement une ou deux graines, le contenu de ce trou peut \u00eatre captur\u00e9, c’est-\u00e0-dire mis en r\u00e9serve hors du jeu. De plus tous les trous pr\u00e9c\u00e9dents de l’adversaire r\u00e9pondant aux m\u00eames crit\u00e8res (contenant apr\u00e8s semis deux ou trois graines) peuvent \u00e9galement \u00eatre captur\u00e9s. Les graines ne ressortent pas de la r\u00e9serve, elles seront seulement comptabilis\u00e9es pour d\u00e9terminer le vainqueur.<\/p>\n Le but de l’Aw\u00e9l\u00e9 est une domination \u00e9conomique et non pas une victoire guerri\u00e8re, contrairement aux autres principaux jeux de strat\u00e9gie comme le Go ou les \u00e9checs. Aussi est-il interdit d’affamer l’adversaire\u00a0: on doit toujours lui laisser au moins une graine dans son camps. Si c’est impossible, la partie se termine. Le vainqueur est le joueur qui a mis le plus de graines en r\u00e9serve. En pratique, la fin de la partie est g\u00e9n\u00e9ralement d\u00e9termin\u00e9e bien avant d’en arriver \u00e0 cette extr\u00e9mit\u00e9, puisque d\u00e8s qu’un joueur poss\u00e8de plus de vingt-quatre graines dans sa r\u00e9serve, il ne peut plus \u00eatre d\u00e9pass\u00e9.<\/p>\n L’Aw\u00e9l\u00e9 est un jeu complexe, comportant des retournements de situation tr\u00e8s rapides, et n\u00e9cessitant une dose importante de calculs et de strat\u00e9gies, reposant entre autres sur la constitution de \u00ab\u00a0greniers\u00a0\u00bb, c’est-\u00e0-dire de trous comportant un nombre important de graines (une vingtaine par exemple). Pour un joueur d\u00e9butant toutefois, l’ordinateur peut repr\u00e9senter un adversaire int\u00e9ressant par sa facult\u00e9 d’explorer rapidemment un nombre important de combinaisons.<\/p>\n L’Intelligence Artificielle<\/em> est une branche de l’informatique recouvrant de tr\u00e8s nombreux domaines d’application, (reconnaissance des formes, expertise et diagnostique automatiques, mod\u00e9lisation, logiques, traitement du langage, etc.) mais l’un de ses sujets de pr\u00e9dilection fut d\u00e8s ses d\u00e9buts la r\u00e9solution des jeux de r\u00e9flexion. Des m\u00e9canismes divers ont \u00e9t\u00e9 mis au point \u00e0 cette fin, mais le plus courant, et le plus simple \u00e0 comprendre, est l’exploration en force brute. Il s’agit, partant d’une position de jeu, de tester successivement tous les mouvements possibles, puis pour chacun d’eux tous les mouvements de l’adversaire, en it\u00e9rant le processus pour d\u00e9terminer quel mouvement imm\u00e9diat est le plus \u00e0 m\u00eame de nous apporter finalement la victoire.<\/p>\n Pour certains jeux, comme le tic-tac-toe \u00e0 neuf cases, le nombre de situations est suffisament faible pour \u00eatre explor\u00e9 enti\u00e8rement par un ordinateur (et m\u00eame par un humain compte tenu des sym\u00e9tries r\u00e9duisant consid\u00e9rablement le nombre de branches \u00e0 \u00e9tudier). En revanche, pour un jeu offrant une certaine complexit\u00e9, l’exploration exhaustive est impossible pour des raisons d’explosion combinatoire. On a recours alors \u00e0 une\u00a0fonction d’\u00e9valuation<\/em>. On commence l’exploration de tous les mouvements possibles, puis de tous ceux de l’adversaire, et ainsi de suite jusqu’\u00e0 une profondeur maximale. La situation r\u00e9sultante est soumise \u00e0 une fonction qui va la noter, lui affectant une valeur positive si elle nous est favorable, ou n\u00e9gative si elle est favorable \u00e0 l’adversaire.<\/p>\n L’id\u00e9e consiste alors \u00e0 faire \u00ab\u00a0remonter\u00a0\u00bb jusqu’\u00e0 la position de d\u00e9part les notes obtenues pour chaque s\u00e9quence de mouvements, afin de d\u00e9terminer le mouvement initial le plus int\u00e9ressant. Consid\u00e9rant que l’adversaire joue aussi bien que nous, la remont\u00e9e des notes s’effectue en utilisant un algorithme nomm\u00e9\u00a0minimax<\/em>, qui prend alternativement le coup le plus favorable (lorsque nous jouons) et le plus d\u00e9favorable (lorsque l’autre joue). Cet algorithme peut s’exprimer de diff\u00e9rentes mani\u00e8res, en voici une repr\u00e9sentation r\u00e9cursive\u00a0:<\/p>\n En supposant que la fonction d’\u00e9valuation accepte un argument indiquant pour quel joueur elle doit \u00eatre calcul\u00e9e (et donc le sens positif ou n\u00e9gatif qu’elle doit prendre), on peut simplifier l’expression de l’algorithme ainsi\u00a0:<\/p>\n En fait, toute l’intelligence du syst\u00e8me repose finalement dans la fonction d’\u00e9valuation, qui doit indiquer – avec la meilleure pr\u00e9cision possible – l’avantage qu’offre une position pour un joueur donn\u00e9. Nous reviendrons sur ce sujet.<\/p>\n Comme c’est fr\u00e9quemment le cas en IA, on repr\u00e9sente usuellement le principe de r\u00e9solution des jeux par un arbre. On d\u00e9place ainsi les probl\u00e8mes, en les ramenant \u00e0 des manipulations (parcours, tri, etc.) de graphes pour lesquels on dispose de nombreux algorithmes. Chaque noeud de l’arbre repr\u00e9sente une position du jeu, et chaque arc qui en sort est assimil\u00e9 \u00e0 un mouvement menant \u00e0 une nouvelle position. \u00e0 chaque tour de jeu, il y a, au plus, six mouvements possibles (chacun des six trous). Ceci est tr\u00e8s faible en regard d’autres jeux comme les \u00e9checs qui peuvent en proposer plusieurs dizaines, ou le Go qui peut atteindre plusieurs centaines\u00a0! L’arbre \u00e0 explorer sera donc relativement \u00ab\u00a0pointu\u00a0\u00bb, et l’on essayera de privil\u00e9gier la profondeur de la descente.<\/p>\n Pour cela, il existe une technique nomm\u00e9e\u00a0\u00e9lagage alpha-b\u00e9ta<\/em>. Il s’agit d’am\u00e9liorer l’algorithme en renon\u00e7ant \u00e0 \u00e9tudier les mouvements ne permettant pas d’am\u00e9liorer le r\u00e9sultat d\u00e9ja obtenu pour une position donn\u00e9e. Sachant qu’\u00e0 partir d’une position, on a d\u00e9j\u00e0 atteint une certaine valeur gr\u00e2ce aux mouvements explor\u00e9s, il est inutile d’examiner plus longuement les mouvements ne permettant pas de monter au-dessus de cette valeur. Or, au tour suivant c’est l’adversaire qui joue, et en tentant de maximiser son avantage, il diminue le n\u00f4tre, et l’exploration de ce niveau ne pourra que faire diminuer l’avantage obtenu au niveau sup\u00e9rieur.<\/p>\n Il est facile d’exprimer l’\u00e9lagage alpha-b\u00e9ta dans un algorithme utilisant une fonction d’\u00e9valuation sym\u00e9trique comme nous l’avons fait plus haut. En effet, lorsqu’on invoque\u00a0 Pour bien saisir le fonctionnement de l’algorithme minimax et l’\u00e9lagage alpha-b\u00e9ta, il est recommand\u00e9 de le faire \u00ab\u00a0tourner\u00a0\u00bb manuellement sur un arbre construit pour l’occasion. On trouvera \u00e9galement des explications plus claires et plus d\u00e9taill\u00e9es dans de nombreux ouvrages d’introduction \u00e0 l’IA comme [WINSTON 92] ou \u00e0 l’algorithmique, comme [GOLDSCHLAGER 86] par exemple.<\/p>\n L’impl\u00e9mentation d’un algorithme minimax est relativement simple. Il faut d’abord trouver une bonne repr\u00e9sentation de l’\u00e9tat du jeu. Pour l’Aw\u00e9l\u00e9, il suffit d’employer un tableau de deux fois six cases, plus deux cases contenant les graines captur\u00e9es. Il faut ensuite choisir un langage de d\u00e9veloppement. Ici, nous ferons preuve d’originalit\u00e9, en nous tournant vers le langage Tcl, ceci pour trois raisons\u00a0:<\/p>\n Pour les lecteurs d\u00e9sireux de s’initier au langage Tcl ou \u00e0 l’utilisation de la biblioth\u00e8que Tk, je ne peux que vous conseiller la lecture de [BLAESS 01]\u00a0!<\/p>\n L’interpr\u00e9teur Tcl \u00e9tant livr\u00e9 avec toutes les distributions Linux, aucun probl\u00e8me ne devrait se poser pour tester les routines ci-dessous. La premi\u00e8re routine que nous examinerons est le coeur m\u00eame de l’algorithme minimax. On peut d’ailleurs presque reconna\u00eetre ligne-\u00e0-ligne son expression ci-dessus.<\/p>\n La premi\u00e8re instruction de cette routine –\u00a0 Il est important de remarquer que les premi\u00e8res routines que nous d\u00e9veloppons consid\u00e8rent la variable\u00a0 Nous pouvons remarquer l’existence des variables globales suivantes\u00a0:<\/p>\n La routine\u00a0 Nous savons donc \u00e9valuer un mouvement donn\u00e9. Nous devrons utiliser une routine permettant de d\u00e9terminer le meilleur mouvement pour une position de d\u00e9part donn\u00e9. Cette fonction s’\u00e9crit de mani\u00e8re assez \u00e9vidente.<\/p>\n On notera que si aucun mouvement n’est acceptable, elle renvoie la valeur d’ Nous pouvons \u00e0 pr\u00e9sent \u00e9crire les routines encadrant le d\u00e9roulement la partie. Il nous faut disposer d’une variable globale stockant le num\u00e9ro du joueur en cours. La premi\u00e8re routine correspond au jeu de l’ordinateur.<\/p>\n Nous voyons qu’elle invoque plusieurs routines concernant l’interface graphique (comme \u00a0 La derni\u00e8re ligne de cette routine lance la r\u00e9flexion de l’ordinateur au bout de 10 millisecondes. Cet intervalle permet \u00e0 la biblioth\u00e8que Tk de traiter sa boucle d’\u00e9v\u00e8nements, rafraichissant ainsi l’affichage graphique.<\/p>\n Nous avons besoin d’une routine permettant de basculer d’un joueur \u00e0 l’autre. Elle met \u00e0 jour la variable globale concern\u00e9e et invoque la fonction d’interface s’occupant de l’affichage du nom du joueur attendu.<\/p>\n Jusqu’\u00e0 pr\u00e9sent, les fonctions d\u00e9velopp\u00e9es sont totalement ind\u00e9pendantes du jeu impl\u00e9ment\u00e9, nous pourrions les employer pour un grand nombre de jeux de r\u00e9flexion. Voyons maintenant les fonctions sp\u00e9cifiques au jeu d’Aw\u00e9l\u00e9. Tout d’abord, la fonction initialisant toutes les donn\u00e9es du jeu, conform\u00e9ment au tableau suivant\u00a0:<\/p>\n La routine suivante r\u00e9alise v\u00e9ritablement le mouvement propos\u00e9, en distribuant les graines extraites d’un trou. Il s’agit probablement de la fonction n\u00e9cessitant le plus d’adaptation d’un jeu \u00e0 l’autre. N’oublions pas qu’elle doit renvoyer une valeur n\u00e9gative si le mouvement indiqu\u00e9 conduit \u00e0 une position inacceptable (dans d’autres circonstances cela pourrait repr\u00e9senter une mise en \u00e9chec-au-roi).<\/p>\n Nous avons invoqu\u00e9 pr\u00e9c\u00e9demment une routine\u00a0 Enfin, avant d’aborder l’interface graphique du jeu, nous devons \u00e9crire la fonction d’\u00e9valuation. Comme nous l’avons sugg\u00e9r\u00e9 plus haut, c’est un \u00e9l\u00e9ment crucial pour l’intelligence du syst\u00e8me. C’est justement parce que le jeu est complexe qu’il est impossible de l’explorer int\u00e9gralement et que l’on doit avoir recours \u00e0 une fonction capable d’estimer avec pr\u00e9cision l’avantage d’un joueur par rapport \u00e0 l’autre.<\/p>\n Nous allons \u00e9crire une fonction d’\u00e9valuation simple, mais chacun pourra facilement l’adapter pour exp\u00e9rimenter de nouveaux param\u00e8tres. Notre routine prendra en argument le nom du joueur pour lequel l’\u00e9valuation doit \u00eatre faite. En r\u00e9alit\u00e9, les m\u00eames calculs seront ex\u00e9cut\u00e9s pour les deux joueurs, mais cet argument permettra de d\u00e9terminer dans quel sens soustraire les deux valeurs obtenues.<\/p>\n Le premier param\u00e8tre permettant de d\u00e9crire l’avantage d’un joueur est le nombre de graines qu’il a captur\u00e9es. Le contenu de sa r\u00e9serve va \u00eatre multipli\u00e9 par une valeur arbitraire (300) afin de lui donner un poids important par rapport aux autres graines pr\u00e9sentes dans le jeu. On constate rapidement que les trous se trouvant \u00e0 droite de la rang\u00e9e d’un joueur ont une importance strat\u00e9gique plus \u00e9lev\u00e9e que ceux de gauche. En effet, ils sont plus difficilement touch\u00e9s par l’adversaire pour les captures, et \u00e0 l’inverse offrent un acc\u00e8s plus facile vers le jeu de l’opposant. Nous allons donc pond\u00e9rer leur contenu par une valeur croissante de gauche \u00e0 droite (1, 2, 3\u20266).<\/p>\n Lorsqu’on veut \u00e9crire une fonction d’\u00e9valuation, il est difficile de savoir o\u00f9 s’arr\u00eater. Nous n’avons pris en consid\u00e9ration que les param\u00e8tres les plus \u00e9vidents. D’autres pourraient \u00e9galement \u00eatre utilis\u00e9s (\u00ab\u00a0y a-t-il des graines menac\u00e9es de capture\u00a0?\u00a0\u00bb, \u00ab\u00a0dispose-t-on de greniers suffisants pour faire deux fois le tour du jeu\u00a0?\u00a0\u00bb, etc.) Le probl\u00e8me est d’arriver \u00e0 distinguer les \u00e9l\u00e9ments qui rel\u00e8vent v\u00e9ritablement de l’\u00e9valuation et ceux qui tentent de pr\u00e9voir les coups suivants. V\u00e9rifier si des graines sont menac\u00e9es de capture revient simplement \u00e0 essayer de repousser l’horizon de l’exploration d’un demi-coup suppl\u00e9mentaire.<\/p>\n Notons que l’on se rapproche du domaine de l’apprentissage automatique, et que l’on pourrait imaginer un syst\u00e8me o\u00f9 la fonction d’\u00e9valuation \u00e9voluerait en s’appuyant sur les m\u00e9canismes auto-adaptatifs habituels (r\u00e9seaux connexionistes, algorithmes g\u00e9n\u00e9tiques, etc.), d’autant que le nombre de param\u00eatres d’entr\u00e9e dans le jeu d’Aw\u00e9l\u00e9 est relativement restreint.<\/p>\n Pour construire l’interface graphique de notre programme, nous nous appuyons sur la biblioth\u00e8que Tk. Ceci nous permettra de r\u00e9aliser une interface tout \u00e0 fait acceptable en quelques lignes de code. La premi\u00e8re proc\u00e9dure sert \u00e0 construire la fen\u00eatre du jeu.<\/p>\nR\u00e9solution de jeux<\/h2>\n
minimax (position, joueur, profondeur)\n\u00a0 si profondeur = profondeur_maximale\n\u00a0\u00a0\u00a0 renvoyer evaluation (position)\n\u00a0 pour tous les mouvements possibles\n\u00a0\u00a0\u00a0\u00a0\u00a0 nouvelle = appliquer_mouvement (position, mouvement)\n\u00a0\u00a0\u00a0\u00a0\u00a0 valeur = minimax (nouvelle, adversaire(joueur), profondeur+1)\n\u00a0 si joueur = \"nous\"\n\u00a0\u00a0\u00a0 renvoyer maximum des valeurs\n\u00a0 sinon\n\u00a0\u00a0\u00a0 renvoyer minimum des valeurs<\/pre>\n
minimax (position, joueur, profondeur)\n\u00a0 si profondeur = profondeur_maximale\n\u00a0\u00a0\u00a0 renvoyer evaluation(position, joueur)\n\u00a0 maximum = -infini\n\u00a0 pour tous les mouvements possibles (adversaire(joueur))\n\u00a0\u00a0\u00a0 nouvelle = appliquer_mouvement(position, mouvement)\n\u00a0\u00a0\u00a0 valeur = - minimax(nouvelle, adversaire(joueur), profondeur+1)\n\u00a0\u00a0\u00a0 si valeur > maximum\n\u00a0\u00a0\u00a0\u00a0\u00a0 maximum = valeur\n\u00a0 renvoyer maximum<\/pre>\n
minimax()<\/code>, on lui transmet un argument suppl\u00e9mentaire correspondant \u00e0 l’oppos\u00e9 de la meilleur valeur d\u00e9ja obtenue \u00e0 notre niveau. Si l’exploration au niveau suivant d\u00e9passe cet argument, son oppos\u00e9 sera n\u00e9cessairement inf\u00e9rieur \u00e0 la valeur d\u00e9j\u00e0 obtenue, et il n’est pas utile d’\u00e9tudier les autres mouvements.<\/p>\nminimax (position, joueur, profondeur,alpha)\n\u00a0 si profondeur = profondeur_maximale\n\u00a0\u00a0\u00a0 renvoyer evaluation(position, joueur)\n\u00a0 maximum = -infini\n\u00a0 pour tous les mouvements possibles (adversaire(joueur))\n\u00a0\u00a0\u00a0 nouvelle = appliquer_mouvement(position, mouvement,maximum)\n\u00a0\u00a0\u00a0 valeur = - minimax(nouvelle, adversaire(joueur), profondeur+1, -maximum)\n\u00a0\u00a0\u00a0 si valeur > maximum\n\u00a0\u00a0\u00a0\u00a0\u00a0 maximum = valeur\n\u00a0\u00a0\u00a0 si valeur > alpha\n\u00a0\u00a0\u00a0\u00a0\u00a0 sortir boucle pour\n\u00a0 renvoyer maximum<\/pre>\n
Impl\u00e9mentation<\/h2>\n
Algorithme minimax<\/h3>\n
\n
proc evaluation_mouvement {ref_jeu joueur profondeur mvt alpha} {\n\u00a0 upvar $ref_jeu jeu\n\u00a0 global profondeur_maxi liste_mouvements erreur\n\u00a0 if {[effectuer_mouvement jeu $joueur $mvt] < 0} {return $erreur}\n\u00a0 if {[incr profondeur] >= $profondeur_maxi} {\n\u00a0\u00a0\u00a0 return [evaluation_position jeu $joueur]\n\u00a0 }\n\u00a0 set joueur [expr 1 - $joueur]\n\u00a0 set meilleure_evaluation $erreur\n\u00a0 foreach mvt $liste_mouvements {\n\u00a0\u00a0\u00a0 array set copie_jeu\u00a0 [array get jeu]\n\u00a0\u00a0\u00a0 set valeur [evaluation_mouvement copie_jeu $joueur $profondeur $mvt [expr - $meilleure_evaluation]]\n\u00a0\u00a0\u00a0 if {$valeur == $erreur} {continue}\n\u00a0\u00a0\u00a0 set valeur [expr - $valeur]\n\u00a0\u00a0\u00a0 if {$valeur > $meilleure_evaluation} {\n\u00a0\u00a0\u00a0\u00a0\u00a0 set meilleure_evaluation $valeur\n\u00a0\u00a0\u00a0\u00a0\u00a0 if {$valeur > $alpha} {break}\n\u00a0\u00a0\u00a0 }\n\u00a0 }\n\u00a0 return $meilleure_evaluation;\n}<\/pre>\nupvar<\/code> – indique que le premier argument est une r\u00e9f\u00e9rence symbolique, ou plus pr\u00e9cis\u00e9ment le nom d’une variable appartenant \u00e0 la routine appelante. C’est donc le moyen employ\u00e9 en Tcl pour passer des arguments par r\u00e9f\u00e9rence. Le tableau\u00a0jeu<\/code>repr\u00e9sente le contenu des diff\u00e9rents trous.\u00a0jeu(0,\u2026)<\/code> correspond au joueur Nord (par d\u00e9faut l’ordinateur) et\u00a0jeu(1,\u2026)<\/code> au joueur Sud. Pour chacun d’eux,\u00a0jeu(\u2026,i)<\/code> avec i dans [0,6[ correspondent aux six trous, num\u00e9rot\u00e9s dans l’ordre inverse des aiguilles d’une montre. Enfinjeu(0,6)<\/code> et\u00a0jeu(1,6)<\/code> correspondent aux deux r\u00e9serves de graines captur\u00e9es. La num\u00e9rotation des trous est repr\u00e9sent\u00e9e sur le tableau ci-dessous.<\/p>\n\n\n
\n jeu(0,6)<\/td>\n jeu(0,5)<\/td>\n jeu(0,4)<\/td>\n jeu(0,3)<\/td>\n jeu(0,2)<\/td>\n jeu(0,1)<\/td>\n jeu(0,0)<\/td>\n jeu(1,6)<\/td>\n<\/tr>\n \n jeu(1,0)<\/td>\n jeu(1,1)<\/td>\n jeu(1,2)<\/td>\n jeu(1,3)<\/td>\n jeu(1,4)<\/td>\n jeu(1,5)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n jeu<\/code> dans son ensemble comme une repr\u00e9sentation de la situation, sans faire r\u00e9f\u00e9rence \u00e0 son contenu. Nous pourrons r\u00e9utiliser ces fonctions directement avec d’autres jeux de r\u00e9flexion.<\/p>\n\n
profondeur_maxi<\/code> : le nombre de niveaux \u00e0 explorer dans l’arbre des possibilit\u00e9s, chaque niveau de cet arbre correspondant \u00e0 un\u00a0demi-coup<\/em> ;<\/li>\nliste_mouvements<\/code> : une liste contenant tous les mouvements possibles pour chaque joueur. Ici il ne s’agit que de la liste\u00a0{0 1 2 3 4 5}<\/code> correspondant aux six trous\u00a0;<\/li>\nerreur<\/code> : il s’agit d’une valeur num\u00e9rique qui doit \u00eatre inf\u00e9rieure \u00e0 la pire des \u00e9valuations possibles. Nous choisissons arbitrairement -100000.<\/li>\n<\/ul>\neffectuer_mouvement<\/code> devra appliquer le mouvement d\u00e9sir\u00e9 au jeu, et renvoyer une valeur n\u00e9gative en cas d’impossibilit\u00e9. Nous voyons que le reste de la fonction est assez proche de l’algorithme pr\u00e9c\u00e9dent, avec quelques remarques\u00a0:<\/p>\n\n
foreach<\/code> permet de balayer la liste des mouvements de mani\u00e8re plus lisible qu’une boucle\u00a0for<\/code> ;<\/li>\narray<\/code> permet de manipuler les tableaux, nous l’utilisons ici pour dupliquer la table repr\u00e9sentant le jeu.<\/li>\n<\/ul>\nproc meilleur_mouvement {ref_jeu joueur} {\n\u00a0 upvar $ref_jeu jeu\n\u00a0 global liste_mouvements erreur\n\u00a0 set meilleure_evaluation $erreur\n\u00a0 set meilleur $erreur\n\u00a0 foreach mvt $liste_mouvements {\n\u00a0\u00a0\u00a0 array set copie_jeu\u00a0 [array get jeu]\n\u00a0\u00a0\u00a0 set valeur [evaluation_mouvement copie_jeu $joueur 0 $mvt [expr - $erreur]]\n\u00a0\u00a0\u00a0 if {$valeur == $erreur} {continue}\n\u00a0\u00a0\u00a0\u00a0\u00a0 if {$valeur > $meilleure_evaluation} {\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 set meilleure_evaluation $valeur\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 set meilleur $mvt\n\u00a0\u00a0\u00a0 }\n\u00a0 }\n\u00a0 return $meilleur\n}<\/pre>\nerreur<\/code>.<\/p>\nRoutines de jeu<\/h3>\n
proc ordinateur_joue {ref_jeu} {\n\u00a0 upvar $ref_jeu jeu\n\u00a0 global joueur_en_cours erreur\n\u00a0 set mvt [meilleur_mouvement jeu $joueur_en_cours]\n\u00a0 if {$mvt == $erreur} {\n\u00a0\u00a0\u00a0 afficher_resultats jeu\n\u00a0 } else {\n\u00a0\u00a0\u00a0 effectuer_mouvement jeu $joueur_en_cours $mvt\n\u00a0\u00a0\u00a0 afficher_jeu jeu\n\u00a0\u00a0\u00a0 indiquer_coup_joue $joueur_en_cours $mvt\n\u00a0\u00a0\u00a0 passer_la_main\n\u00a0\u00a0\u00a0 if [partie_terminee jeu] {afficher_resultats jeu\u00a0; return}\n\u00a0 }\n}<\/pre>\nafficher_resultats<\/code>, \u00a0afficher_jeu<\/code>, \u00a0indiquer_coup_joue<\/code>, \u00a0passer_la_main<\/code>). Elles seront d\u00e9velopp\u00e9es plus bas. La routine suivante est invoqu\u00e9e lorsque l’humain demande \u00e0 jouer un certain trou. Elle v\u00e9rifie que le mouvement soit correct en passant par une copie interm\u00e9diaire du jeu.<\/p>\nproc humain_joue {ref_jeu j c} {\n\u00a0 upvar $ref_jeu jeu\n\u00a0 global joueur_en_cours\n\u00a0 if {$j\u00a0!= $joueur_en_cours} { bell; return }\n\u00a0 array set copie [array get jeu]\n\u00a0 if {[effectuer_mouvement copie $j $c] < 0} {bell; return}\n\u00a0 array set jeu [array get copie]\n\u00a0 afficher_jeu jeu\n\u00a0 passer_la_main\n\u00a0 if [partie_terminee jeu] {afficher_resultats jeu\u00a0; return}\n\u00a0 after 10 ordinateur_joue jeu\n}<\/pre>\nproc passer_la_main {} {\n\u00a0 global joueur_en_cours\n\u00a0 set joueur_en_cours [expr 1 - $joueur_en_cours]\n\u00a0 afficher_joueur_en_cours $joueur_en_cours\n}<\/pre>\nJeu d’Aw\u00e9l\u00e9<\/h3>\n
\n\n
\n jeu(j,i)<\/td>\n i=0<\/td>\n i=1<\/td>\n i=2<\/td>\n i=3<\/td>\n i=4<\/td>\n i=5<\/td>\n i=6
\n(r\u00e9serve)<\/td>\n<\/tr>\n\n j=0
\n(Nord)<\/td>\n4<\/td>\n 4<\/td>\n 4<\/td>\n 4<\/td>\n 4<\/td>\n 4<\/td>\n 0<\/td>\n<\/tr>\n \n j=1
\n(Sud)<\/td>\n4<\/td>\n 4<\/td>\n 4<\/td>\n 4<\/td>\n 4<\/td>\n 4<\/td>\n 0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n proc reinitialiser {ref_jeu} {\n\u00a0 upvar $ref_jeu jeu\n\u00a0 global joueur_en_cours\n\u00a0 foreach j {0 1} {\n\u00a0\u00a0\u00a0 foreach c {0 1 2 3 4 5} {\n\u00a0\u00a0\u00a0\u00a0\u00a0 set jeu($j,$c) 4\n\u00a0\u00a0\u00a0 }\n\u00a0\u00a0\u00a0 set jeu($j,6) 0\n\u00a0 }\n\u00a0 afficher_jeu jeu\n\u00a0 set joueur_en_cours 1\n\u00a0 afficher_joueur_en_cours $joueur_en_cours\n}<\/pre>\nproc effectuer_mouvement {ref_jeu joueur mvt} {\n\u00a0 upvar $ref_jeu jeu\n\u00a0 set j $joueur\n\u00a0 set c $mvt\n\u00a0 set nb $jeu($joueur,$mvt)\n\u00a0 set jeu($joueur,$mvt) 0\n\u00a0 if {$nb < 1} {return -1}\n\u00a0 while {$nb > 0} {\n\u00a0\u00a0\u00a0 incr c\n\u00a0\u00a0\u00a0 if {$c > 5} { # Passage de l'autre c\u00f4t\u00e9\n\u00a0\u00a0\u00a0\u00a0\u00a0 set c 0\n\u00a0\u00a0\u00a0\u00a0\u00a0 set j [expr 1 - $j]\n\u00a0\u00a0\u00a0 }\n\u00a0\u00a0\u00a0 if {($c\u00a0!= $mvt) || ($joueur\u00a0!= $j)} {\n\u00a0\u00a0\u00a0\u00a0\u00a0 # on saute le trou de d\u00e9part\n\u00a0\u00a0\u00a0\u00a0\u00a0 incr nb -1\n\u00a0\u00a0\u00a0\u00a0\u00a0 incr jeu($j,$c)\n\u00a0\u00a0\u00a0 }\n\u00a0 }\n\u00a0 if {$j\u00a0!= $joueur} { # captures dans le terrain adverse\n\u00a0\u00a0\u00a0 while {$c >= 0} {\n\u00a0\u00a0\u00a0\u00a0\u00a0 if {($jeu($j,$c) < 2) || ($jeu($j,$c) > 3)} { break }\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 incr jeu($joueur,6) $jeu($j,$c)\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 set jeu($j,$c) 0\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 incr c -1\n\u00a0\u00a0\u00a0 }\n\u00a0 }\n\u00a0 # il faut laisser au moins une graine chez l'adversaire\n\u00a0 set j [expr 1 - $joueur]\n\u00a0 foreach c {0 1 2 3 4 5} {\n\u00a0\u00a0\u00a0 if {$jeu($j,$c) > 0} {return 0}\n\u00a0 }\n\u00a0 return -1\n}<\/pre>\npartie_terminee<\/code>, qui v\u00e9rifiera simplement si un joueur a atteint les vingt-quatre graines en r\u00e9serve.<\/p>\nproc partie_terminee {ref_jeu} {\n\u00a0 upvar $ref_jeu jeu\n\u00a0 if {($jeu(0,6)>=24) || ($jeu(1,6)>=24)} {return 1}\n\u00a0 return 0\n}<\/pre>\nproc evaluation_position {nom_jeu joueur} {\n\u00a0 upvar $nom_jeu jeu\n\u00a0 foreach j {0 1} {\n\u00a0\u00a0\u00a0 set evaluation($j) [expr 300 * $jeu($j,6)]\n\u00a0\u00a0\u00a0 foreach i {0 1 2 3 4 5} {\n\u00a0\u00a0\u00a0\u00a0\u00a0 set n $jeu($j,$i)\n\u00a0\u00a0\u00a0\u00a0\u00a0 incr evaluation($j) [expr $n * ($i + 1)]\n\u00a0\u00a0\u00a0 }\n\u00a0 }\n\u00a0 return [expr $evaluation($joueur) - $evaluation([expr 1 - $joueur])]\n}<\/pre>\nInterface graphique<\/h3>\n