π
<-
Chat plein-écran
[^]

IA Synchro-donjon #3: Optimisations locales

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

IA Synchro-donjon #3: Optimisations locales

Unread postby Lephe » 16 Oct 2021, 19:52

Dans le cadre de notre concours de rentrée 2021 avec Planète Casio, 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
ia3greed.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.
ia3greed.py
est une amélioration de
ia2_path.py
qui a déjà un article explicatif, je te conseille de commencer par là. ^^

Code: Select all
from polycal4 import get_infos
from synchrod import *

# Ordre des joueurs à sortir
ordre_de_sortie = [0, 2, 1, 3]
# Position du joueur qu'on veut sortir dans ordre_de_sortie
joueur_courant_id = 0
# Chemin pour le sortir
chemin = []

def tour(plateau, joueurs, evenements):
    global joueur_courant_id, chemin

    for (x, y, ev, joueur) in evenements:
        if ev == NOUVELLE_PARTIE:
            joueur_courant_id = 0
            chemin = []

    # Si le joueur est arrivé à sa destination, on passe au suivant
    while joueurs[ordre_de_sortie[joueur_courant_id]] == -1:
        joueur_courant_id += 1
        chemin = []

    joueur_courant = ordre_de_sortie[joueur_courant_id]

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

    # S'il y a des monstres autour mais pas de piège, attaquer
    monstres_autour = False
    pieges_autour = False

    for joueur in joueurs:
        # On ne compte pas les joueurs qui ont déjà sortis
        if joueur != -1:
            if est_un(plateau[joueur-1], MONSTRE) or \
               est_un(plateau[joueur+1], MONSTRE) or \
               est_un(plateau[joueur-16], MONSTRE) or \
               est_un(plateau[joueur+16], MONSTRE):
                monstres_autour = True
            if est_un(plateau[joueur-1], PIEGE) or \
               est_un(plateau[joueur+1], PIEGE) or \
               est_un(plateau[joueur-16], PIEGE) or \
               est_un(plateau[joueur+16], PIEGE):
                pieges_autour = True

    if monstres_autour and not pieges_autour:
        return ATTAQUER

    # Prochaine étape
    mouvement = chemin[0]
    chemin = chemin[1:]

    return mouvement

play_game(tour, blind=True)

Comme tu peux le voir, le début ressemble beaucoup à
ia2_path.py
. Le principe est toujours le même : on commence par sélectionner un premier joueur, on cherche un chemin pour le faire sortir avec
calculer_chemin()
et on le suit ; puis on passe à un autre joueur jusqu'à avoir fini. ;)

Sortir les joueurs dans le bon ordre



Si tu regardes la position initiale des joueurs sur le plateau ci-dessus, tu verras que les faire sortir dans l'ordre 0, 1, 2, 3 (à savoir Jaune, Rouge, Bleu, Vert) n'est pas optimal.

Image

C'est parce que pour faire sortir Jaune il faut déjà traverser tout l'écran vers la droite ; puis pour faire sortir Rouge il faut retraverser tout l'écran vers la gauche ; et on recommence encore une fois avec Bleu puis Vert.

Clairement, il est plus rentable d'emmener à la fois Jaune et Bleu vers la droite puis Rouge et Vert vers la gauche. Autrement dit, de faire sortir les joueur dans l'ordre 0, 2, 1, 3. C'est ce qu'on commence à prévoir dès le début du code :

Code: Select all
ordre_de_sortie = [0, 2, 1, 3]

Pour suivre notre progrès, on ne regarde du coup pas le numéro du joueur actuel mais plutôt la position où on en est dans l'ordre de sortie. C'est le rôle de la variable
joueur_courant_id
. Quand on démarre une nouvelle partie ou qu'on passe au joueur suivant, on modifie
joueur_courant_id
, et ensuite on détermine de quel joueur il s'agit en indexant la liste :

Code: Select all
joueur_courant = ordre_de_sortie[joueur_courant_id]

Avec ça, le score augmente déjà beaucoup !

  • On faisait
    2171 points
    avec `ia2_path.py` et l'ordre moins bon ;
  • Et là on fait
    3730 points
    rien qu'en évitant des allers-retours.
Et on n'a pas fini !

Attaquer les ennemis quand ce n'est pas dangereux



Actuellement le programme prend encore beaucoup de dégâts, ce qu'on peut voir juste en regardant les premiers plateaux :

Code: Select all
#0: 12648430
Bravo! 39T 50D -> 61
#1: 594213422
Bravo! 67T 90D -> -7
#2: 236840551
Bravo! 70T 40D -> 40
#3: 2464859390
Bravo! 62T 60D -> 28

Il y a au moins un type de dégâts qu'on peut éviter facilement : les monstres. C'est parce que si on rentre dedans c'est qu'on était à côté au tour précédent, et si on est à côté... on peut les détruire. ;)

Attaquer les monstres a cependant l'effet secondaire gênant d'activer les pièges à proximité des joueurs, ce qui peut faire des dégâts ou faire apparaître d'autres pics, monstres et pièges. Donc on va essayer
d'attaquer s'il y a des monstres à côté d'un joueur, mais pas de pièges
.

Pour ça, on prend tous les joueurs qui sont sur le plateau et on regarde les cases autour d'eux. On peut identifier les cases autour d'un joueur en regardant comment elles sont numérotées :

Image

On peut voir si le joueur est sur la case
n
, les cases de gauche et droite sont numérotées
n-1
et
n+1
, et les cases au-dessus et en-dessous sont numérotées
n-16
et
n+16
. Il suffit donc de tester si un monstre se trouve à chacune de ces positions :

Code: Select all
monstres_autour = False
pieges_autour = False

for joueur in joueurs:
    # On ne compte pas les joueurs qui ont déjà sortis
    if joueur != -1:
        if est_un(plateau[joueur-1], MONSTRE) or \
           est_un(plateau[joueur+1], MONSTRE) or \
           est_un(plateau[joueur-16], MONSTRE) or \
           est_un(plateau[joueur+16], MONSTRE):
            monstres_autour = True
        if est_un(plateau[joueur-1], PIEGE) or \
           est_un(plateau[joueur+1], PIEGE) or \
           est_un(plateau[joueur-16], PIEGE) or \
           est_un(plateau[joueur+16], PIEGE):
            pieges_autour = True

if monstres_autour and not pieges_autour:
    return ATTAQUER

Alors que donne cette astuce ? Pas moins de
5475 points
, ce qui la place bien au-delà des IAs précédentes.

  • 2171 points avec
    ia2_path.py
    ;
  • 3730 points en évitant des allers-retours ;
  • 5475 points en tuant les monstres sur le chemin.
Les plus observateurs d'entre vous auront remarqué que cette dernière astuce est en fait commentée dans
ia3greed.py
, ce qui a à un moment détrôné plusieurs participations soumises. :p

Autres pistes d'améliorations



Cette IA montre que de petites améliorations intuitives peuvent faire une grosse différence. Voici quelques idées !

  • Actuellement on n'essaie même pas d'esquiver les piques... on pourrait le faire même sans modifier `calculer_chemin()`.
  • On consomme un tour pour attaquer les monstres même si on ne fait que passer à côté d'eux sans les toucher ou si le joueur qui les croise est immunisé.
  • On pourrait trouver encore un meilleur ordre de sortie.
  • On ne tient pas comptes des piques qui peuvent apparaître quand un piège est activé.
Bon courage pour explorer ces pistes (ou d'autres) :)
User avatar
LephePartenaire
Niveau 10: GR (Guide de Référence)
Niveau 10: GR (Guide de Référence)
Level up: 48.4%
 
Posts: 364
Joined: 15 Jun 2018, 19:53
Gender: Male

Return to Choses relatives à TI-Planet

Who is online

Users browsing this forum: No registered users and 3 guests

-
Search
-
Social
-
Featured topics
Concours de l'Avent 2021 "l'énigme des 3 portes". Viens prendre connaissance des indices et bouts de code Python chaque jour. Sois parmi les 7 premiers à trouver et franchir l'une des 3 portes pour remporter de superbes lots : équipements complets en calculatrices Python couleur et/ou accessoires exclusifs !
Concours Geometry Dash - 2 équipements complets en calculatrices TI (+ goodies et accessoires) à gagner pour les 2 meilleurs niveaux créés
Concours de dessin de Noël 2021 Jusqu'au 7 janvier 2022 inclus par Casio. Dessine ta liste au Père Noël sur calculatrice/émulateur Graph 90/35+E II en Python ou fx-92+ Spéciale Collège. Ouvert aux élèves et enseignants, classement séparé. À gagner 2 consoles Nintendo Switch, 2 trottinettes électriques, 10 calculatrices Graph 90/35+E II au choix, 72 montres Casio G-Shock ou Vintage. Pas de perdant, goodies Casio pour tous les autres !
Coque NumWorks édition limitée Décembre 2021 à gagner.
Comparaisons des meilleurs prix pour acheter sa calculatrice !
12345
-
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.
682 utilisateurs:
>642 invités
>34 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)