Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.
La shoutbox n'est pas chargée par défaut pour des raisons de performances. Cliquez pour charger.

Forum Casio - Actualités


Index du Forum » Actualités » IA Synchro-donjon #3: Optimisations locales
Lephenixnoir En ligne Administrateur Points: 24574 Défis: 170 Message

IA Synchro-donjon #3: Optimisations locales

Posté le 16/10/2021 20:52

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

Voilà le code entier qu'on va disséquer.

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.


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 :

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 :

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 :

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


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 :

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.

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)



LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v4.3 © créé par Neuronix et Muelsaco 2004 - 2024 | Il y a 227 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd