IA Synchro-donjon #2 : Recherche de chemin

→ **MyCalcs** profile · by **Lephe** » 28 Sep 2021, 20:08

Dans le cadre de notre concours de rentrée 2021 avec TI-Planet, nous te proposons de résoudre deux jeux codés en Python avec ta calculatrice graphique : La geste d'Alrys et Synchro-donjon.

Pour t'aider à aborder Synchro-donjon et à apprendre des choses nouvelles sur la programmation et l'intelligence artificielle, je te présente en détail les IAs groupées avec le programme, de la plus simple à une modérément perfectionnée. Aujourd'hui, on regarde ia2_path.py !

N'oublie pas de lire les règles de Synchro-donjon et de tester le programme sur ta calculatrice avant de lire cet article, sinon tu seras vite perdu·e !

Allez voilà, je te mets le code entier ici si tu veux tenter de le lire tout seul, et puis on va expliquer ce qui se passe et le tester ensemble.

Code: Select all: from polycal4 import get_infos from synchrod import * # Joueur qu'on veut sortir joueur_courant = 0 # Chemin pour le sortir chemin = [] def tour(plateau, joueurs, evenements): global joueur_courant, chemin # Réinitialisation en début de partie for (x, y, ev, joueur) in evenements: if ev == NOUVELLE_PARTIE: joueur_courant = 0 chemin = [] # Si le joueur est arrivé à sa destination, on passe au suivant. # Il arrive que plusieurs joueurs sortent en un seul tour, si ça se produit # on continue de passer au joueur suivant (il en reste forcément un qui # n'est pas sorti sinon la partie serait finie). while joueurs[joueur_courant] == -1: joueur_courant += 1 chemin = [] # Chemin du joueur actuel vers sa sortie if chemin == []: case_sortie = plateau.index(SORTIE + joueur_courant) chemin = calculer_chemin(plateau, joueurs[joueur_courant], case_sortie) # Prochaine étape mouvement = chemin[0] chemin = chemin[1:] return mouvement play_game(tour, blind=True)

Le principe de cette IA est tout simple : on fait sortir chaque joueur dans l'ordre.

D'abord on détermine le chemin pour emmener Jaune de sa position initiale à sa sortie.
À chaque tour on donne une étape du chemin jusqu'à ce que Jaune soit sorti.
À ce moment-là, on détermine le chemin pour emmener Rouge de sa position courante jusqu'à sa sortie, et on refait pareil.
Une fois Rouge sorti, on fait la même chose pour Bleu et Vert.

Trouver un chemin n'est pas évident, mais synchrod.py peut le faire à ta place avec la fonction calculer_chemin(). Tu n'as pas donc à t'en soucier !

Voyons comment on code cette IA !

Conserver des informations entre chaque tour

Notre IA a une stratégie "globale" qui dure toute la partie : elle traite les joueurs dans un ordre défini : Jaune, Rouge, Bleu, Vert. Elle doit donc se souvenir d'où elle en est quand on lui demande sa prochaine action.

Il faut donc avoir des variables qui gardent leur valeur entre deux appel à notre fonction tour(), et pour ça on va utiliser des variables globales.

Ton professeur d'informatique/NSI t'as probablement enseigné qu'utiliser des variables globales est souvent un mauvais choix. Il/elle a raison ! Ici je m'en sers parce que les autres options compliqueraient beaucoup le code.

Code: Select all: joueur_courant = 0 chemin = [] def tour(plateau, joueurs, evenements): global joueur_courant, chemin # ... Notre IA ...

Comme tu peux le voir, j'ai créé deux variables joueur_courant et chemin, et elles sont globales parce qu'elles ne sont pas dans une fonction. Dans la fonction tour() où je vais coder notre IA, j'indique à Python que je veux les utiliser avec la commande global, sinon Python refuserait de les modifier.

Avec ça, on peut commencer à jouer !

Trouver et exploiter un chemin pour sortir Jaune

Pour trouver un chemin, on peut utiliser la fonction calculer_chemin() qui est fournie par synchrod.py. Son fonctionnement est le suivant :

Code: Select all: chemin = calculer_chemin(plateau, case_de_depart, case_d_arrivee)

Le plateau est celui qui est donné en premier paramètre de tour() (il n'y en a qu'un de toute façon !). Les cases de depart et d'arrivée sont des nombres entiers, comme on a vu dans la présentation du problème.

La réponse de calculer_chemin() est une liste de directions qui emmène de le case de départ à la case d'arrivée (et c'est le plus court chemin possible !). Mais comme une image vaut 1000 mots, voici le premier niveau que synchrod.py te donne (si tu ne changes pas la génération aléatoire) :

On veut emmener Jaune de sa position initiale (ligne 1, colonne 1, de valeur 16×1+1=17) à sa sortie (ligne 2, colonne 15, de valeur 16×2+15=47). On appelle donc :

Code: Select all: chemin = calculer_chemin(plateau, 17, 47)

Et la liste qu'on récupère est la suivante :

Code: Select all: chemin # [ALLER_DROITE, ALLER_DROITE, ALLER_DROITE, ALLER_DROITE, # ALLER_DROITE, ALLER_DROITE, ALLER_DROITE, ALLER_BAS, # ALLER_BAS, ALLER_DROITE, ALLER_DROITE, ALLER_DROITE, # ALLER_DROITE, ALLER_HAUT, ALLER_DROITE, ALLER_DROITE, # ALLER_DROITE]

On peut visualiser le chemin comme ceci (cette visualisation utilise une version modifiée de synchrod.py).

Voilà une base solide ! Maintenant, comment est-ce qu'on utilise la liste ?

Voilà l'idée : la variable globale chemin va indiquer quelle chemin il nous reste à parcourir. Comme ça, à chaque tour, on peut choisir comme action le premier mouvement du chemin, retirer ce mouvement de la liste, et tout sera prêt pour le prochain tour !

C'est ce qu'on fait à la fin de la fonction :

Code: Select all: mouvement = chemin[0] chemin = chemin[1:] return mouvement

Maintenant, il reste à agencer tout ça pour que tout le monde puisse sortir, pas juste Jaune.

Traiter tous les joueurs dans l'ordre

On a quatre joueurs à faire sortir : Jaune, Rouge, Bleu et Vert (qui sont représentés par quatre entiers 0, 1, 2 et 3). C'est pour ça qu'on a deux variables globales :

joueur_courant indique quel joueur on est en train de faire sortir.
chemin indique quels mouvements ils restent pour qu'il sorte. Si chemin est vide c'est qu'on ne l'a pas encore calculé.

On commence donc avec joueur_courant=0 (Jaune) et chemin=[] (pas encore calculé), jusque-là c'est cohérent !

Au début du tour, la première chose à faire est de tester si le joueur courant vient de sortir. On peut le savoir en inspectant la liste joueurs (le deuxième paramètre de tour()), qui indique la position de chaque joueur. Cette position est un nombre entre 0 et 127 si le joueur est sur le plateau, et vaut -1 si le joueur est sorti.

Donc, si le joueur courant est sorti, on passe au suivant et on réinitialise chemin pour bien le recalculer.

Code: Select all: if joueurs[joueur_courant] == -1: joueur_courant += 1 chemin = []

Il y a une subtilité, cela dit : parfois deux joueurs peuvent sortir en même temps (si Vert et Bleu sont tous les deux à gauche de leur sortie et qu'on choisit ALLER_DROITE par exemple). Dans ce cas, joueur_courant+=1 n'est pas suffisant, parce que joueur_courant+1 est peut-être déjà sorti !

Pour éviter ça, on change le if en while, comme ça si joueur_courant+1 est déjà sorti, eh bien on passe au suivant !

Code: Select all: while joueurs[joueur_courant] == -1: joueur_courant += 1 chemin = []

Il ne reste plus qu'à calculer le chemin à prendre quand chemin=[]. (On pourrait le calculer à chaque tour, mais c'est inutile : le chemin reste le même jusqu'à ce que le joueur courant soit sorti !)

Code: Select all: if chemin == []: case_sortie = plateau.index(SORTIE + joueur_courant) chemin = calculer_chemin(plateau, joueurs[joueur_courant], case_sortie)

Comme précédemment, j'utilise calculer_chemin(). Comme case de départ, on prend la position du joueur courant, et comme case d'arrivée, la position sur le plateau de sa sortie. .index() est une méthode de liste qui te donne la position dans la liste d'une valeur choisie, ce qui te permet ici de chercher des objets sur le plateau.

Avec ça, l'IA est presque complète !

Rénitialiser à chaque nouvelle partie

La fonction play_game() réalise toute une série de parties en une seule exécution du programme (par défaut, 100). Il faut donc s'assurer que l'IA est nettoyée entre chaque partie sinon les variables seront fausses.

Pour ça, on peut utiliser le troisième et dernier paramètres de la fonction tour : la liste evenements. Cette liste indique ce qui se passe sur le plateau, et t'informe de quand les nouvelles parties commencent (et des effets des pièges).

Au début de l'IA, on prend donc soin de réinitialiser nos deux variables globales à chaque début de partie, pour pas que les valeurs de la partie précédente ne viennent perturber le code.

Code: Select all: for (x, y, ev, joueur) in evenements: if ev == NOUVELLE_PARTIE: joueur_courant = 0 chemin = []

Et voilà ! Avec tout ça, le code est complet. Tu peux le voir de nouveau en entier :

Code: Select all: from polycal4 import get_infos from synchrod import * # Joueur qu'on veut sortir joueur_courant = 0 # Chemin pour le sortir chemin = [] def tour(plateau, joueurs, evenements): global joueur_courant, chemin # Réinitialisation en début de partie for (x, y, ev, joueur) in evenements: if ev == NOUVELLE_PARTIE: joueur_courant = 0 chemin = [] # Si le joueur est arrivé à sa destination, on passe au suivant. # Il arrive que plusieurs joueurs sortent en un seul tour, si ça se produit # on continue de passer au joueur suivant (il en reste forcément un qui # n'est pas sorti sinon la partie serait finie). while joueurs[joueur_courant] == -1: joueur_courant += 1 chemin = [] # Chemin du joueur actuel vers sa sortie if chemin == []: case_sortie = plateau.index(SORTIE + joueur_courant) chemin = calculer_chemin(plateau, joueurs[joueur_courant], case_sortie) # Prochaine étape mouvement = chemin[0] chemin = chemin[1:] return mouvement play_game(tour, blind=True)

L'IA en action

Il est temps de lancer cette IA et de voir de quoi elle est capable. Ce qui est sûr c'est que la méthode de faire sortir chaque joueur dans l'ordre doit permettre de résoudre toutes les plateaux (pas forcément rapidement).

Lançons ia2_path.py... voilà ce que ça donne en interactif !

C'est pas mal du tout. Et voilà le résultat dans la console :

Code: Select all: #0: 12648430 Bravo! 39T 50D -> 61 #1: 594213422 Bravo! 75T 90D -> -15 #2: 236840551 Bravo! 80T 50D -> 20 #3: 2464859390 Bravo! 73T 90D -> -13 #4: 3280879791 Bravo! 87T 70D -> -7 #5: 3426230116 Bravo! 92T 120D -> -62 #6: 2269403964 Bravo! 64T 140D -> -54 #7: 1618746239 Bravo! 77T 30D -> 43 #8: 1236680090 Bravo! 80T 60D -> 10 #9: 3351370485 Bravo! 68T 80D -> 2 #10: 553563167 Bravo! 68T 10D -> 72 #11: 2315605486 Bravo! 72T 30D -> 48 #12: 1036554885 Bravo! 74T 30D -> 46 #13: 1875589748 Bravo! 62T 40D -> 48 #14: 2184596687 Bravo! 64T 80D -> 6 #15: 541455511 Bravo! 71T 80D -> -1 #16: 167669688 Bravo! 81T 70D -> -1 #17: 4207823168 Bravo! 97T 120D -> -67 #18: 1105457756 Bravo! 82T 50D -> 18 #19: 2614210402 Bravo! 58T 50D -> 42 #20: 2529202849 Bravo! 81T 50D -> 19 #21: 3055039143 Bravo! 68T 60D -> 22 #22: 2127226719 Bravo! 83T 130D -> -63 #23: 3082902456 Bravo! 41T 90D -> 19 #24: 4205257665 Bravo! 82T 30D -> 38 #25: 199407319 Bravo! 72T 30D -> 48 #26: 3746711289 Bravo! 83T 40D -> 27 #27: 878032796 Bravo! 74T 30D -> 46 #28: 4092570800 Bravo! 64T 30D -> 56 #29: 2286764744 Bravo! 66T 130D -> -46 #30: 1171391719 Bravo! 64T 110D -> -24 #31: 2776227355 Bravo! 78T 20D -> 52 #32: 894346068 Bravo! 63T 20D -> 67 #33: 4198606884 Bravo! 72T 90D -> -12 #34: 1999695195 Bravo! 72T 60D -> 18 #35: 3064761848 Bravo! 77T 70D -> 3 #36: 1746501463 Bravo! 60T 70D -> 20 #37: 3486740195 Bravo! 76T 160D -> -86 #38: 1456243622 Bravo! 70T 70D -> 10 #39: 4011916507 Bravo! 90T 40D -> 20 #40: 3151169566 Bravo! 80T 60D -> 10 #41: 940545148 Bravo! 71T 40D -> 39 #42: 3446077346 Bravo! 64T 80D -> 6 #43: 883263786 Bravo! 78T 70D -> 2 #44: 394521061 Bravo! 67T 20D -> 63 #45: 3141843215 Bravo! 66T 40D -> 44 #46: 1333750067 Bravo! 83T 90D -> -23 #47: 596029757 Bravo! 64T 60D -> 26 #48: 4053873450 Bravo! 81T 40D -> 29 #49: 716746680 Bravo! 64T 90D -> -4 #50: 1252794865 Bravo! 79T 70D -> 1 #51: 3501098597 Bravo! 78T 50D -> 22 #52: 3328255349 Bravo! 77T 20D -> 53 #53: 1238029435 Bravo! 85T 80D -> -15 #54: 3864774413 Bravo! 70T 50D -> 30 #55: 1518239785 Bravo! 85T 30D -> 35 #56: 91852842 Bravo! 64T 100D -> -14 #57: 3878397276 Bravo! 69T 100D -> -19 #58: 782363206 Bravo! 90T 20D -> 40 #59: 1793375283 Bravo! 85T 50D -> 15 #60: 3387026551 Bravo! 59T 40D -> 51 #61: 1748811549 Bravo! 66T 190D -> -106 #62: 2533799161 Bravo! 64T 50D -> 36 #63: 404853182 Bravo! 74T 60D -> 16 #64: 3616886901 Bravo! 66T 50D -> 34 #65: 2377478389 Bravo! 74T 80D -> -4 #66: 520238391 Bravo! 81T 50D -> 19 #67: 3718574493 Bravo! 96T 110D -> -56 #68: 832990622 Bravo! 81T 30D -> 39 #69: 428843202 Bravo! 79T 30D -> 41 #70: 769357530 Bravo! 75T 30D -> 45 #71: 3649605739 Bravo! 66T 80D -> 4 #72: 3740321927 Bravo! 66T 120D -> -36 #73: 3852969101 Bravo! 79T 80D -> -9 #74: 3256289293 Bravo! 64T 70D -> 16 #75: 3038448294 Bravo! 63T 90D -> -3 #76: 904654193 Bravo! 87T 40D -> 23 #77: 2018615892 Bravo! 75T 80D -> -5 #78: 2794925654 Bravo! 66T 110D -> -26 #79: 3312369991 Bravo! 71T 100D -> -21 #80: 241453064 Bravo! 70T 20D -> 60 #81: 109767354 Bravo! 68T 20D -> 62 #82: 4168036525 Bravo! 83T 100D -> -33 #83: 2534421228 Bravo! 85T 40D -> 25 #84: 2185394352 Bravo! 86T 10D -> 54 #85: 3553770696 Bravo! 108T 150D -> -108 #86: 2393592041 Bravo! 76T 70D -> 4 #87: 1625609068 Bravo! 64T 60D -> 26 #88: 3540367519 Bravo! 64T 50D -> 36 #89: 2216609637 Bravo! 66T 100D -> -16 #90: 2291443810 Bravo! 68T 60D -> 22 #91: 4284680541 Bravo! 72T 40D -> 38 #92: 3688132900 Bravo! 70T 30D -> 50 #93: 4091713635 Bravo! 68T 10D -> 72 #94: 4216499651 Bravo! 76T 110D -> -36 #95: 1079331201 Bravo! 70T 130D -> -50 #96: 2738161974 Bravo! 73T 60D -> 17 #97: 2206455251 Bravo! 85T 30D -> 35 #98: 3529942408 Bravo! 83T 140D -> -73 #99: 2009880399 Bravo! 80T 20D -> 50 Games solved: 100 Score: 2171

Bingo ! Comme tu peux le voir, tous les plateaux ont été résolus. Il y a plein de plateaux où le résultat est très mauvais (négatif, ce qui ajoute 0 au score), et on prend beaucoup de dégâts à cause des pièges et des monstres, mais c'est un bon début !

Le score de cette IA n'est pas moins de 2171, soit presque 22 points par plateau. La prochaine fois, on verra comment de toutes petites améliorations sur ce code permettent de faire un score beaucoup, beaucoup plus élevé. o/