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.


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.


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 :


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 :


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


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 :


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.


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 !


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 !)


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.


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


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 :


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/