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)
