IA Synchro-donjon #3: Optimisations locales
Posted: 16 Oct 2021, 19:52Dans 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. 
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à.
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.
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 :
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 :
Avec ça, le score augmente déjà beaucoup !
Actuellement le programme prend encore beaucoup de dégâts, ce qu'on peut voir juste en regardant les premiers plateaux :
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 :
Alors que donne cette astuce ? Pas moins de 5475 points, ce qui la place bien au-delà des IAs précédentes.
Cette IA montre que de petites améliorations intuitives peuvent faire une grosse différence. Voici quelques idées !
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.
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.
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 :
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.
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é.