Forum |  HardWare.fr | News | Articles | PC | Prix | S'identifier | S'inscrire | Aide | Shop Recherche
588 connectés 

  FORUM HardWare.fr
  Programmation
  Python

  [python] 2048 intelligence artificielle

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[python] 2048 intelligence artificielle

n°2252362
clemfrr
Posté le 05-03-2015 à 17:13:07  profilanswer
 

Bonjour à tous !  
 
Je viens vers vous car j'ai besoin d'aide sur un projet à rendre sous peu.
Je doit coder sous Python un algorithme intelligent qui résout le jeu 2048 à 100%.
 
Pour ce faire, j'ai tout d'abord codé les déplacements du jeu
Il a fallu ensuite concevoir une fonction d'évaluation (c'est cette partie qui est à ameliorer) basée sur divers arguments afin de choisir la matrice (gauche, droite, haut ou bas) pour l'état suivant :
 
Un algorithme minmax doit aussi être établi mais ma fonction d'évaluation est trop faible pour y penser :p
 
# -*- coding: utf-8 -*-
"""
Created on Sat Jan 31 12:15:55 2015
 
@author: Clem
 
"""
#=============================================================================#
 
                                   # CODE JEU
import random, sys, copy
 
matrice = [[2,0,0,0],
           [0,0,0,0],
           [0,0,0,0],
           [0,0,0,2]]
 
 
def tourner_matrice(matrice):
    n = []    
    for i in range(4):
        n.append([matrice[3][i], matrice[2][i], matrice[1][i], matrice[0][i]])
    return n
         
def glisser_droite(matrice):  
    nouvelle_matrice = []  
    for ligne in matrice :  
        ligne = [elem for elem in ligne if elem!=0]  
        for i in range(len(ligne)-1,0,-1):  
            if ligne[i]==ligne[i-1]:  
                ligne[i] = ligne[i]+ligne[i-1]  
                ligne[i-1] = 0  
        ligne = [elem for elem in ligne if elem!=0]  
        ligne = [0]*(4-len(ligne))+ligne  
        nouvelle_matrice.append(ligne)  
    return nouvelle_matrice      
 
def glisser_gauche(matrice):  
    nouvelle_matrice = []  
    for ligne in matrice :  
        ligne = [elem for elem in ligne if elem!=0]  
        for i in range(0,len(ligne)-1,1):  
            if ligne[i]==ligne[i+1]:  
                ligne[i] = ligne[i]+ligne[i+1]  
                ligne[i+1] = 0  
        ligne = [elem for elem in ligne if elem!=0]  
        ligne = ligne+[0]*(4-len(ligne))
        nouvelle_matrice.append(ligne)  
    return nouvelle_matrice
 
   
def glisser_haut(matrice):
    matrice = tourner_matrice(matrice)
    nouvelle_matrice = glisser_droite(matrice)
    for i in range(3):
        nouvelle_matrice= tourner_matrice(nouvelle_matrice)
    return nouvelle_matrice
 
def glisser_bas(matrice):
    for i in range(3):
        matrice = tourner_matrice(matrice)
    nouvelle_matrice = glisser_droite(matrice)
    nouvelle_matrice = tourner_matrice(nouvelle_matrice)
    return nouvelle_matrice
 
def aleatoire(nouvelle_matrice):
    liste = []
    for i in range(4):
        for j in range(4):
            if nouvelle_matrice[i][j] == 0:
                liste.append((i,j))
     
    if liste== []:
        return nouvelle_matrice
    bite = random.choice(liste)    
    nouvelle_matrice[bite[0]][bite[1]] = random.choice([2,4])
    return nouvelle_matrice
     
#=============================================================================#
     
                              # EVALUATION    
     
def maximum(m):
    h=2
    for i in range (4):
        for j in range (4):
            if m[i][j]>h:
                h=m[i][j]
    return h
     
def nbre_zero(m):  
    k=0
    for i in range (4):
        for j in range (4):
            if m[i][j]==0:
                k=k+1
    return k
     
def nombre_addition_ligne (m):
    f=0
    for ligne in m :  
        ligne = [elem for elem in ligne if elem!=0]  
        for i in range(len(ligne)-1,0,-1):  
            ligne[i-1]==ligne[i]
            f=f+1
        return f
             
def nombre_addition_colonne(m):
    g=0
    m=tourner_matrice(m)
    for ligne in m :  
        ligne = [elem for elem in ligne if elem!=0]  
        for i in range(0,len(ligne)-1,1):  
            ligne[i]==ligne[i+1]
            g=g+1
        return g
 
def sousmax(m):          
    h=2
    for i in range (4):
        for j in range (4):
            if m[i][j]>h and m[i][j]< maximum(m):
                h=m[i][j]
    return h
 
def sous_sousmax(m):
    h=2
    for i in range (4):
        for j in range (4):
            if m[i][j]>h and m[i][j]<sousmax(m):
                h=m[i][j]
    return h          
     
def sous_sous_sousmax(m):
    h=2  
    for i in range (4):
        for j in range(4):
            if m[i][j]>h and m[i][j]<sous_sousmax(m):
                h=m[i][j]
    return h
 
 
     
def c_pleine (m):
 if m[0][0]!=0 and m[1][0]!=0 and m[2][0]!=0 and m[3][0 ]!=0:  
  return True
 else:
  return False    
     
     
def evaluation (matrice, etat_actuel):
     
    if matrice==etat_actuel:
        return -sys.maxsize
    score=0
     
    if maximum(matrice)==matrice[0][0]:
        score += pow(matrice[0][0],5)
         
    else:
        score += 0
 
    score += pow(maximum(matrice),4)        
         
    o = nbre_zero(matrice)  
    score += pow(o,3)
     
    for i in range (4):
        for j in range (4):        
            if matrice[0][0]==maximum(matrice) and matrice[0][1]==sousmax(matrice):
                score += pow(sousmax(matrice),2.5)
            if matrice[0][1]==sousmax(matrice) and matrice[0][2]==sous_sousmax(matrice):
                score += pow(sous_sousmax(matrice),2.5)
            if matrice[0][2]==sous_sousmax(matrice) and matrice[0][3]==sous_sous_sousmax(matrice):
                score+= pow(sous_sous_sousmax(matrice),2.5)
 
    return score    
     
    if c_pleine (matrice) == True :
        score+=pow(matrice[1][0],2)
    else :
        score+=0
 
    if matrice[1][0]>matrice[2][0] and matrice[2][0]>matrice[3][0] and matrice[3][0]>0:
        score +=pow(matrice[1][0],2.5)
    else:
        score +=0        
     
'''  
  a = nombre_addition_ligne(matrice)
    if a==0:
        score += 0
    else:      
        score += pow(a,10)
     
    e = nombre_addition_colonne(matrice)
    if e==0:
        score += 0  
    else:
        score += pow(e,10)
'''
 
     
   
###############################################################################
   
                                #JEU#    
 
def jouer(matrice):
     
    matrice_gauche = glisser_gauche(matrice)
    matrice_droite = glisser_droite(matrice)
    matrice_haut = glisser_haut(matrice)
    matrice_bas = glisser_bas(matrice)
    if matrice_gauche==matrice_droite==matrice_haut==matrice_bas:
        print "************************************************************************************"
        return "aucune", None
   
    score_gauche = evaluation(matrice_gauche, matrice)
    score_droite = evaluation(matrice_droite, matrice)
    score_haut = evaluation(matrice_haut, matrice)
    score_bas = evaluation(matrice_bas, matrice)
 
    print score_gauche
    print score_droite
    print score_haut
    print score_bas
 
    score_max = max(score_gauche, score_droite, score_haut, score_bas)
 
    if(score_max == score_gauche):
        return "gauche", matrice_gauche
    elif(score_max == score_droite):
        return "droite", matrice_droite
    elif(score_max == score_haut):
        return "haut", matrice_haut
    else:
        return "bas", matrice_bas
 
 
 
for i in range(1000):
    print("tour",i)
    nouvelle_direction, nouvelle_matrice = jouer(matrice)
    if nouvelle_direction=="aucune":
        print "                                       You failed - Try again (Gautier suce)"
    matrice = aleatoire(nouvelle_matrice)
    print(nouvelle_direction,nouvelle_matrice)
     
     
     
###############################################################################
     
                                    #MINMAX#
'''
def minmax(etat_jeu):
    matrice_gauche = glisser_gauche(etat_jeu)
    matrice_droite = glisser_droite(etat_jeu)
    matrice_haut = glisser_haut(etat_jeu)
    matrice_bas = glisser_bas(etat_jeu)
    mon_tour=[matrice_gauche, matrice_droite, matrice_haut,matrice_bas]
    tour_ordinateur=[]
    for tour in mon_tour:
        for i in range (4):
            for j in range (4):
                if matrice[i][j]==0:
                    matrice[i][j]=2
                    nouvelle_matrice = copy.deepcopy(matrice)
                    tour_ordinateur.append(nouvelle_matrice)
        mon_tour[i]=(tour, tour_ordinateur)
        i= i+1
             
 
Voilà voilà, il me faudrait donc de l'aide pour aboutir :) ! Merci d'avance !!


Message édité par clemfrr le 05-03-2015 à 17:52:50
mood
Publicité
Posté le 05-03-2015 à 17:13:07  profilanswer
 

n°2252390
lasnoufle
La seule et unique!
Posté le 05-03-2015 à 20:46:31  profilanswer
 

Salut
 
Python j'y connais rien mais j'ai quelques remarques quand meme.
 
Deja 2048 si je ne m'abuse c'est un jeu a un seul joueur, donc je vois pas trop comment tu vas pouvoir faire un minimax avec ca.
A la limite, tu pourrais considerer que le "drop" aleatoire du "2" quelque part sur la matrice apres avoir joue un coup represente le coup du joueur 2, mais par definition, si c'est aleatoire, tu ne peux pas t'en servir pour le minimax puisque celui-ci implique que chaque joueur joue le mieux qu'il peut. Bref ca m'a l'air compromis. Le plus intuitif serait plutot de faire un arbre avec chaque demi-coup evalue sur la moyenne des scores des positions atteintes par les demi-coups aleatoires.
 
Ensuite, resoudre un jeu a 100%, par definition, l'algo va pas etre tres intelligent; on parle de force brute ou assimile, vu qu'il faut envisager tous les coups possibles. Et la ca va coincer assez vite. En gros a chaque coup tu as entre 2 et 4 options qui debouchent chacune sur le drop aleatoire d'un "2" sur le damier soit entre 1 et 15 possibilites suivant la matrice apres avoir joue le coup. Si je ne m'abuse, pour taper 2048 il faut au moins 1024 "coups"... ca donne donc un arbre absolument monstrueux.
 
Bref, tu t'es surement mal exprime; au final, c'est assez clair que tu ne cherches pas la resolution a 100%. Pour en revenir a ta fonction d'evaluation, c'est plus un probleme d'algo que de python; si tu expliques en francais (ou en algo "de base" ) comment tu donnes un score a une position, tu auras peut-etre plus de reponses sur comment l'ameliorer vu que meme les non-pythonneux (comme moi) pourront comprendre.
 
A+


---------------
C'était vraiment très intéressant.
n°2252422
rufo
Pas me confondre avec Lycos!
Posté le 06-03-2015 à 11:00:44  profilanswer
 

La méthode de résolution de ce jeu est connue depuis longtemps :
- tu choisis un coin (perso, je prend le coin inférieur gauche) et tu te débrouilles pour faire en sorte que s'y trouve la case à la plus grande valeur
- les cases au-dessus et à sa droite doivent avoir les 2èmes valeurs les plus élevées et ainsi de suite.
 
En gros, ça te fait une sorte de triangle. Plus tu t'éloignes du coin choisi, plus les valeurs des cases sont petites.


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Cantine Calandreta : http://sourceforge.net/projects/canteen-calandreta

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Python

  [python] 2048 intelligence artificielle

 

Sujets relatifs
aide pour programme python !Débutant python dictionnaire sérialisé
[Python] Occurence d'une listeCréer une animation en python
[RESOLU (et toute seule en plus)] Python 3.2 Comment utiliser les set?[Python] Django et sessions
[python] syntaxe execution programme externe[Python] Checkbox et condition - Récupération de variable
projet de programmation (ISN) (python 3.4)Problème avec tuple sur Python 3.4.1
Plus de sujets relatifs à : [python] 2048 intelligence artificielle


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite) / Groupe LDLC / Shop HFR