π
<-
Chat plein-écran
[^]

IA Synchro-donjon #2 : Recherche de chemin

Tout ce qui concerne le site en lui-même

IA Synchro-donjon #2 : Recherche de chemin

Unread postby 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. ;)

Image

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

Image

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

Image

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 !

Image

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 ! :D

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/
User avatar
LephePartenaire
Niveau 10: GR (Guide de Référence)
Niveau 10: GR (Guide de Référence)
Level up: 50.4%
 
Posts: 367
Joined: 15 Jun 2018, 19:53
Gender: Male

Re: IA Synchro-donjon #2 : Recherche de chemin

Unread postby Dubs » 28 Sep 2021, 21:19

Merci, j'ai commencé à regarder ce défi.
Il est très intéressant et je sens qu'il va bien me faire chauffer les neurones !
User avatar
DubsVIP++
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Level up: 4.7%
 
Posts: 103
Joined: 06 Jan 2016, 13:44
Gender: Male
Calculator(s):


Return to Choses relatives à TI-Planet

Who is online

Users browsing this forum: No registered users and 1 guest

-
Search
-
Social
-
Featured topics
Reprise de ton ancienne fx-92 Collège ou Graph 25/35/90 à 5€. Même non fonctionnelle ou ancien modèle. Etiquette de retour fournie, pas de frais de port à payer.
Coque NumWorks édition limitée Mai 2022 à gagner.
Comparaisons des meilleurs prix pour acheter sa calculatrice !
123
-
Donations / Premium
For more contests, prizes, reviews, helping us pay the server and domains...
Donate
Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partner and ad
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
672 utilisateurs:
>644 invités
>22 membres
>6 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)

-
Other interesting websites
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)