Back
Close

Recueil d'exercices pour apprendre Python au lycée

M_C
132.5K views

Exemple d'IA sur le jeu 2048

Voici un autre exemple complet utilisant les modules dans le projet IA et jeux sur mobiles de la page précédente.

Présentation du jeu

Le jeu est simple : Dans une grille se trouve des cases contenant des puissances de 2 (qu'on va appeler tuiles) et des cases vides. On choisit une direction selon laquelle toutes les tuiles vont glisser jusqu'à ne plus pouvoir bouger. Si deux tuiles de même valeur se retrouve collée selon cette direction, elles fusionnent en une tuile de valeur double. De plus, à chaque direction choisie, il apparait une nouvelle tuile de valeur 2 ou 4. Le but est de réussir à obtenir 2048.

Les règles sont simples mais atteindre le but peut être difficile et très long.

On pourra trouver les fichiers du projet ici : GitHub

Récupération des données

Ici, pas de reconnaissance de caractères mais simplement de l'astuce : chaque valeur correspon à une tuile d'une couleur particulière. On a donc juste à regarder la couleur de la tuile (un pixel suffit) pour en déduire la valeur. Voici ce que ça donne :

capture.py
"""
Script de capture graphique des données pour le 2048
Le principe est simple, on regarde la couleur d'un seul pixel par case pour savoir à quelle valeur il correspond.
"""

from PIL import Image, ImageGrab # Pour faire la capture d'ecran

# Couleur qu'il faudra peut-être modifier selon la version utilisée
# Il faut au moins les couleurs des cases vides, 1 et 2. Le reste sert uniquement à pouvoir reprendre une partie en cours
couleur_to_valeur={(214, 205, 196):0,(238, 228, 218):1,(237, 224, 200):2,(242, 177, 121):3,(245, 149, 99):4,(246, 124, 95):5,(246, 94, 59):6,(237, 207, 114):7,(237, 204, 97):8,(237, 200, 80):9,(237, 197, 63):10,(237, 194, 46):11}

def capturer(x0,y0,x1,y1,intercase,decalage,N=4):
    """
    Fait la capture d'ecran entre les points de coordonnées (x0,y0) et (x1,y1). Attention à bien prendre la zone autour des cases (pas au ras)
    Calcule automatiquement les coordonnées des pixels à regarder (c'est pour ca qu'il faut l'intercase entre les cases)
    decalage correspond à quelle distance de l'angle haut gauche de chaque case se trouve le pixel qu'on souhaite observer pour la couleur
    N correspond à la dimension de la grille (4 de base)
    Donne en sortie une grille contenant les puissances de 2
    Comme les couleurs pour des puissances élevées sont les mêmes, il faut sauvegarder les cases déjà connues.
    Du coup, on ne va chercher en réalité que les cases contenant des 2 ou des 4

    """


    # On capture l'image dans la zone
    image =ImageGrab.grab(bbox=(x0,y0,x1,y1))

    # Sauvegarde de l'image pour debugguer
    image.save("capture.png")

    #  Prétraitement de l'image
    #image = image.convert('L')    # Echelle de gris

    grille=[]
    # On prélève les couleurs
    delta =(x1-x0-intercase)//N
    for i in range(N):
        ligne=[]
        for j in range(N):
            couleur=image.getpixel((intercase+decalage+j*delta,intercase+decalage+i*delta))
            if couleur in couleur_to_valeur:
                ligne.append(couleur_to_valeur[couleur])
            else:
                print("Nouvelle couleur",couleur)
                ligne.append(0)

        grille.append(ligne)
    return grille

if __name__ == '__main__': # Pour le debug
    print(capturer(515,250,842,578,7,10))

IA

L'IA est basée sur un algorithme de type Monte Carlo. L'idée est la suivante : On choisit un direction et on joue le reste de la partie au hasard. On regarde le score obtenu au final et on le note. On répète cette opération de nombreuses fois puis on regarde au final quelle direction nous donne le meilleur score en moyenne et c'est celle ci qu'on décide de jouer.

IA.py
"""
Script d'IA pour le 2048
Prend en entrée une matrice (normale, pas numpy) de nombres qui correspondent à la puissance de 2 (donc entre 1 et 16).
Le 0 correspond à une case vide.
La sortie donne le mouvement à effectuer sous la forme de 0 pour la droite
puis on tourne dans le sens trigo : 1 pour le haut, 2 pour la gauche et 3 pour le bas.

Le principe de l'IA est en gros un algorithme à la Monte Carlo :
On teste au hasard des parties jusqu'à la fin et on compte quelle direction donne le meilleur score en moyenne
"""
from random import randint


# Seuil de profondeur de recherche (On ne va pas jusqu'à être bloqué, on s'arrete après ce nombre de coup)
seuil_profondeur=50

#-------------------------- Fonctions auxiliaires

def suppr0(liste):
    """
    Supprime les 0 d'une liste
    """
    return [n for n in liste if n!=0]

def conc(liste):
    """
    Concatene les valeurs identiques selon la direction
    """
    for i in range(len(liste)-1,0,-1):
        if liste[i]==liste[i-1]:
            liste[i]+=1
            liste[i-1]=0
    return liste

def arranger(liste,renverser=False):
    if renverser: liste=liste[::-1]
    liste_reduite=suppr0(conc(suppr0(liste)))
    liste_reduite=[0]*(len(liste)-len(liste_reduite))+liste_reduite
    if renverser : liste_reduite.reverse()
    return liste_reduite


def appliquer_mvt(grille,mvt,N=4):
    """
    Fonction qui donne la grille obtenue après avoir effectué un mouvement.
    On fait chaque cas séparément pour optimiser en temps car les astuces risquent d'être gourmandes en temps
    (Il faut faire ENORMEMENT de test pour une méthode Monte Carlo donc il faut optimiser autant que faire se peut)
    Si j'ai bien compris : A chaque mouvement on pousse tout le monde, on regroupe les adjacentes identiques et on repousse.
    """
    # Si le mouvement ne fait rien, alors il n'apparait pas de nouvelle case
    au_moins_une_modif=False
    # On regarde les 4 cas
    if mvt==0: # A droite
        for i,ligne in enumerate(grille):
            arr=arranger(ligne)
            for j in range(N):
                if not au_moins_une_modif and grille[i][j]!=arr[j] : au_moins_une_modif=True
                grille[i][j]=arr[j]
    elif mvt==2: # A gauche
        for i,ligne in enumerate(grille):
            arr=arranger(ligne,True)
            for j in range(N):
                if not au_moins_une_modif and grille[i][j]!=arr[j] : au_moins_une_modif=True
                grille[i][j]=arr[j]
    elif mvt==1: # En haut
        for j in range(N):
            arr=arranger([grille[i][j] for i in range(N)],True)
            for i in range(N):
                if not au_moins_une_modif and grille[i][j]!=arr[i] : au_moins_une_modif=True
                grille[i][j]=arr[i]
    elif mvt==3: # En Bas
        for j in range(N):
            arr=arranger([grille[i][j] for i in range(N)])
            for i in range(N):
                if not au_moins_une_modif and grille[i][j]!=arr[i] : au_moins_une_modif=True
                grille[i][j]=arr[i]
    return au_moins_une_modif

def est_complete(grille):
    """
    Fonction qui renvoie true s'il n'y a plus de 0 dans la grille, false sinon
    """
    for ligne in grille:
        for n in ligne:
            if n==0 : return False
    return True


def ajouter_case(grille):
    """
    Fonction qui ajoute un 1 ou un 2 aléatoirement dans la grille (ce qui se passe après chaque mouvement)
    90% de chance d'avoir un 1, 10% d'avoir un 2
    Modifie la grille directement
    """
    # S'il reste au moins un 0
    if not est_complete(grille):
        N=len(grille)
        # On cherche une case au hasard jusqu'à tomber sur 0
        l,c=randint(0,N-1),randint(0,N-1)
        while grille[l][c]!=0:
            l,c=randint(0,N-1),randint(0,N-1)
        if randint(1,10) <= 9: grille[l][c]=1
        else : grille[l][c]=2

def donner_score(grille):
    """
    Donne le score
    Surement optimisable avec du calcul bit à bit mais au final, elle ne sert que nb_essais fois
    """
    return sum([sum([2**n for n in ligne]) for ligne in grille])

def est_fini(grille,N=4):
    """
    Renvoie True si plus aucun mouvement est possible
    """
    # Si elle n'est pas complete, ce n'est pas fini
    if not est_complete(grille): return False
    # S'il y a deux nombres egaux à coté, ce n'est pas fini
    for ligne in range(N):
        for col in range(N):
            try:
                if grille[ligne][col]==grille[ligne][col+1]: return False
                if grille[ligne][col]==grille[ligne+1][col]: return False
            except : pass
    return True


def afficher_grille(grille):
    """
    pour debug : Affiche juste les nombres dans la grille
    """
    for ligne in grille:
        print(" ".join([str(n) for n in ligne]))

#------------------------- Fonction principale

def donner_direction(grille,nb_essais):
    """
    Fonction qui cherche la meilleur direction à prendre
    """
    # Liste des scores et du nombre d'essais effectués par direction
    scores=[0]*4
    essais=[0]*4
    score_max=0

    compteur=0
    N=len(grille)

    while compteur<nb_essais :
        compteur+=1
        # Pour sortir de la boucle de recherche
        fini = False
        # On choisit la première direction (dont il faudra se souvenir pour le score)
        premiere_direction=randint(0,3)
        # On fait une copie de notre grille d'origine
        grille_temp=[ligne.copy() for ligne in grille]
        # On applique le changement.
        if appliquer_mvt(grille_temp,premiere_direction,N):
            fini=est_fini(grille_temp,N)
            ajouter_case(grille_temp)
            compteur_seuil=0
            while not fini and compteur_seuil<seuil_profondeur :
                compteur_seuil+=1
                # On joue au hasard tant qu'on n'a pas fini
                if appliquer_mvt(grille_temp,randint(0,3),N) :
                    ajouter_case(grille_temp)
                fini=est_fini(grille_temp,N)
            # On modifie le tableau des scores et du nombre d'essais
            score=donner_score(grille_temp)
            if score>score_max:
                score_max=score
            scores[premiere_direction]+=score
            essais[premiere_direction]+=1

        #afficher_grille(grille_temp)

    # Maintenant qu'on a fait nos essais aleatoires, on choisit la direction ayant le plus gros score en moyenne
    maximum=0
    direction=-1
    for i in range(4):
        try:
            temp = scores[i]/essais[i]
            if temp > maximum:
                maximum = temp
                direction = i
        except: pass

    #print(scores)
    #print(essais)
    print("Score max atteint pendant les simulations :",score_max)
    return direction





if __name__ == '__main__': # Pour le debug
    pass
    """
    # Simule une partie
    grille=[[0 for _ in range(4)] for __ in range(4)]
    ajouter_case(grille)
    ajouter_case(grille)
    afficher_grille(grille)
    print("------------------------")
    compteur = 0
    while not est_fini(grille):
        print("Coup n°",compteur)
        compteur+=1
        direction=donner_direction(grille,500)
        print(direction)
        appliquer_mvt(grille,direction)
        ajouter_case(grille)
        afficher_grille(grille)
        print("------------------------")
    """

Sorties souris

Le projet a été testé sur un émulateur d'android Memu Play et le jeu classique de 2048. Autrement dit, les sorties simulent un glissé de doigt avec la souris. Il suffit de le modifier pour utiliser les flèches par exemple, selon le gameplay du jeu utilisé. Ici aussi, j'ai regroupé la gestion des sorties dans le fichier principal pour ne pas multiplier les fichiers car cette gestion est vraiment simple.

main.py
"""
Script principal
"""
from  IA import * # module perso contenant l'IA du jeu
import capture # module perso contenant les fonctions permettant la recupération graphique des données
import pyautogui as ag # Gestion de la souris et du clavier
import time
from random import randint

#-------------- Constantes à modifier en fonction de la configuration graphique
# Pour obtenir ces valeurs on peut par exemple prendre un screenshot de la fenetre de jeu puis avec Paint, lire les coordonnées en placant la souris dessus
# Coordonnées de l'angle haut gauche de la grille (y compris rebord)
x0,y0= 515,250
# Coordonnées de l'angle bas droit de la grille (y compris rebord)
x1,y1= 842,578
# Distance entre les cases
intercase=7
# Décalage par rapport au bord de la case pour prélever la couleur
decalage=10
# Nombre de parties aléatoires qu'on teste avant de choisir la meilleur direction
nb_essais=5000
# Dimension de la grille
N=4
# Distance sur laquelle on fait bouger la souris pour jouer un coup
balayage_souris=100
# Temps d'attente entre le coup joué et la capture d'écran suivante (en seconde)
attente=0.3
# Pour traduire le nombre en direction (0 pour droite etc.)
trad_direction=["Droite","Haut","Gauche","Bas"]

#--------------------------- Gestion des mouvements

def jouer(direction):
    """
    Déplace la souris sur l'ecran dans la direction indiquée pour jouer
    """
    # On place la souris au centre
    ag.moveTo((x0+x1)//2,(y0+y1)//2)
    if direction==0: ag.drag(100,0)
    elif direction==2: ag.drag(-100,0)
    elif direction==1: ag.drag(0,-100)
    elif direction==3: ag.drag(0,100)


# -------------------------- Fonction aux

def est_vide(grille):
    for ligne in range(N):
            for col in range(N):
                if grille[ligne][col]!=0: return False
    return True

#--------------------------- Fonction principale

def lancer(grille=None,dim=N):
    """
    Fonction à lancer pour démarrer l'IA
    On peut rentrer une grille à la main comme point de départ pour reprendre une partie arretée par exemple
    dim est la dimension de la grille (de base 4)
    """
    if grille is None: grille=[[0]*N for _ in range(N)]

    while not est_fini(grille): # Tant qu'on peut jouer, on joue
        # On recupère graphique la grille (seulement les 2 et 4)
        grille_capturee=capture.capturer(x0,y0,x1,y1,intercase,decalage,N)

        #!!!
        print("Grille capturée")
        afficher_grille(grille_capturee)

        # Si il n'y a que des 0, on s'arrete
        if est_vide(grille_capturee):
            print("Grille vide, c'est fini")
            break

        compteur_de_0=0
        # On rajoute les 2 et les 4 présents
        for ligne in range(N):
            for col in range(N):
                if grille_capturee[ligne][col]!=0:
                    # Pour voir s'il y a un probleme:
                    if grille[ligne][col]>2 :
                        if grille[ligne][col]!=grille_capturee[ligne][col]  and grille[ligne][col]<13:
                            print("Problème !!!!!!!!!!!!!!!!!!!")
                    else:
                        grille[ligne][col]=grille_capturee[ligne][col]
                if grille[ligne][col]==0: compteur_de_0+=1

        print("Grille utilisée")
        afficher_grille(grille)
        # On cherche le coup à jouer
        # Version à nombre d'essais fixe :
        direction_a_jouer=donner_direction(grille,nb_essais)

        # Seconde version : moins il y a de zéros dans la grille, plus on fait d'essais
        #direction_a_jouer=donner_direction(grille,5000-332*compteur_de_0)


        # Et on le joue virtuellement pour mettre à jour notre grille
        appliquer_mvt(grille,direction_a_jouer,N)

        print("Direction jouée :",trad_direction[direction_a_jouer])


        # On joue le coup
        jouer(direction_a_jouer)

        #On attend un peu le temps que la grille se stabilise
        time.sleep(attente)

Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants