Mise en place d'une IA pour le Morpion

Bonjour à tous et à toutes.

J'essaie de mettre en place un algorithme permettant de mettre en place une IA sur un jeu de Morpion.

J'ai codé la majeure partie du jeu et je suis bloqué sur l'intelligence artificielle.

Voici mon code en entier:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
 
import tkinter as tk
from tkinter import messagebox
import random
import numpy as np
import copy
 
###############################################################################
# création de la fenetre principale  - ne pas toucher
 
LARG = 300
HAUT = 300
 
Window = tk.Tk()
Window.geometry(str(LARG)+"x"+str(HAUT))   # taille de la fenetre
Window.title("ESIEE - Morpion")
 
 
# création de la frame principale stockant toutes les pages
 
F = tk.Frame(Window)
F.pack(side="top", fill="both", expand=True)
F.grid_rowconfigure(0, weight=1)
F.grid_columnconfigure(0, weight=1)
 
# gestion des différentes pages
 
ListePages  = {}
PageActive = 0
 
def CreerUnePage(id):
    Frame = tk.Frame(F)
    ListePages[id] = Frame
    Frame.grid(row=0, column=0, sticky="nsew")
    return Frame
 
def AfficherPage(id):
    global PageActive
    PageActive = id
    ListePages[id].tkraise()
 
Frame0 = CreerUnePage(0)
 
canvas = tk.Canvas(Frame0,width = LARG, height = HAUT, bg ="black" )
canvas.place(x=0,y=0)
 
 
#################################################################################
#
#  Parametres du jeu
 
Grille = [ [0,0,1],
           [2,0,0],
           [0,0,0] ]  # attention les lignes représentent les colonnes de la grille
 
Grille = np.array(Grille)
Grille = Grille.transpose()  # pour avoir x,y
 
startGame = True
colorGrille = "blue" 
Score = 0
finIA = False
finJoueur = False
finCase = False
###############################################################################
#
# gestion du joueur humain et de l'IA
# VOTRE CODE ICI
 
def retartGame():
    global colorGrille, startGame
    for x in range(3):
        for y in range(3):
            Grille[x][y] = 0
    colorGrille = "blue"
    Dessine()
    startGame = False
 
 
def win():
    for x in range(3):
        for y in range(3):
            if(Grille[x][y] == 1 and (x==1 and y==1)):
                if(Grille[x-1][y] == 1 and Grille[x+1][y] == 1):
                    return 1
 
                if(Grille[x][y-1] == 1 and Grille[x][y+1] == 1):
                    return 1
 
                if(Grille[x-1][y-1] == 1 and Grille[x+1][y+1] == 1):
                    return 1
 
                if(Grille[x-1][y+1] == 1 and Grille[x+1][y-1] == 1):
                    return 1
 
            if((Grille[x][y] == 1 and (x==0 and y==1)) and (Grille[x][y-1] == 1 and Grille[x][y+1] == 1)):
                return 1
 
            if((Grille[x][y] == 1 and (x==2 and y==1)) and (Grille[x][y-1] == 1 and Grille[x][y+1] == 1)):
                return 1
 
            if((Grille[x][y] == 1 and (x==1 and y==0)) and (Grille[x-1][y] == 1 and Grille[x+1][y] == 1)):
                return 1
 
            if((Grille[x][y] == 1 and (x==1 and y==2)) and (Grille[x-1][y] == 1 and Grille[x+1][y] == 1)):
                return 1
 
            if(Grille[x][y] == 2 and (x==1 and y==1)):
                if(Grille[x-1][y] == 2 and Grille[x+1][y] == 2):
                    return 2
 
                if(Grille[x][y-1] == 2 and Grille[x][y+1] == 2):
                    return 2
 
                if(Grille[x-1][y-1] == 2 and Grille[x+1][y+1] == 2):
                    return 2
 
                if(Grille[x-1][y+1] == 2 and Grille[x+1][y-1] == 2):
                    return 2
 
            if((Grille[x][y] == 2 and (x==0 and y==1)) and (Grille[x][y-1] == 2 and Grille[x][y+1] == 2)):
                return 2
 
            if((Grille[x][y] == 2 and (x==2 and y==1)) and (Grille[x][y-1] == 2 and Grille[x][y+1] == 2)):
                return 2
 
            if((Grille[x][y] == 2 and (x==1 and y==0)) and (Grille[x-1][y] == 2 and Grille[x+1][y] == 2)):
                return 2
 
            if((Grille[x][y] == 2 and (x==1 and y==2)) and (Grille[x-1][y] == 2 and Grille[x+1][y] == 2)):
                return 2
 
def joueurSimuleIA():
    global colorGrille,Score,finIA,startGame
    if(win() == 2):
        startGame = True
        colorGrille = "yellow"
        if(Score>0):
            Score -= 0.5
        finIA = True
        Dessine()
    else:
        L = []
        for x in range(3):
            for y in range(3):
                if(Grille[x][y] == 0):
                    L.append((x,y))
        resultat = []
        for K in L:
            Grille[K[0]][K[1]] == 2
            print("avant")
            R = joueurSimuleHumain()
            print("apres")
            resultat.append(R,K)
            Grille[K[0]][K[1]] == 0
        return Grille[resultat[0]][resultat[1]]
 
 
def joueurSimuleHumain():
    global colorGrille,Score,finJoueur,startGame
    if(win() == 1):#fonction partie terminee
        startGame = True
        colorGrille = "red"
        Score += 1
        finJoueur = True
        Dessine()
    L = []
    for x in range(3):
        for y in range(3):
            if(Grille[x][y] == 0):
                L.append((x,y))
    resultat = []
    for K in L:
        Grille[K[0]][K[1]] == 1
        R = joueurSimuleIA()
        resultat.append(R,K)
        Grille[K[0]][K[1]] == 0
    return Grille[resultat[0]][resultat[1]]
 
def Play(x,y):
    global colorGrille,Score,finJoueur,finIA,finCase,startGame
    if(startGame):
        retartGame()
    #AfficheGrille()
    #Action du joueur 
    if(Grille[x][y] != 0):
        print("Case deja prise!!")
    else:
        Grille[x][y] = 1
        if(win() == 1):#fonction partie terminee
            startGame = True
            colorGrille = "red"
            Score += 1
            finJoueur = True
            Dessine()
        else:
            #Gestion de l'IA
            joueurSimuleIA()
            if(win() == 2):
                colorGrille = "yellow"
                Score -= 0.5
                finIA = True
                Dessine() 
            """
            print(L)
            L.clear()#Sert a rien!!!!
             
            else:
                print("Plus de case disponible!!")
                colorGrille = "white"
                finCase = True
                Dessine()
            """
 
    if(finJoueur):
        endGame = messagebox.askretrycancel("Gagner!!", "+1 point\nScore actuel: "+str(Score)+"\nVoulez-vous rejouer?")
        if(endGame == True):
            retartGame()
            finJoueur = False
        else:
            messagebox.showinfo("Fin", "Partie terminé")
            Window.destroy()
    elif(finIA):
        endGame = messagebox.askretrycancel("Perdu!!", "-0.5 point\nScore actuel: "+str(Score)+"\nVoulez-vous rejouer?")
        if(endGame == True):
            retartGame()
            finIA = False
        else:
            messagebox.showinfo("Fin", "Partie terminé")
            Window.destroy()
    elif(finCase):
        endGame = messagebox.askretrycancel("Egalité!!", "Score actuel: "+str(Score)+"\nVoulez-vous rejouer?")
        if(endGame == True):
            retartGame()
            finCase = False
        else:
            messagebox.showinfo("Fin", "Partie terminé")
            Window.destroy()
 
 
################################################################################
#   
# Dessine la grille de jeu
 
def Dessine(PartieGagnee = False):
    ## DOC canvas : http://tkinter.fdex.eu/doc/caw.html
    canvas.delete("all")
 
    for i in range(4):
        canvas.create_line(i*100,0,i*100,300,fill=colorGrille, width="4" )
        canvas.create_line(0,i*100,300,i*100,fill=colorGrille, width="4" )
 
    for x in range(3):
        for y in range(3):
            xc = x * 100
            yc = y * 100
            if ( Grille[x][y] == 1):
                canvas.create_line(xc+10,yc+10,xc+90,yc+90,fill="red", width="4" )
                canvas.create_line(xc+90,yc+10,xc+10,yc+90,fill="red", width="4" )
            if ( Grille[x][y] == 2):
                canvas.create_oval(xc+10,yc+10,xc+90,yc+90,outline="yellow", width="4" )
 
 
####################################################################################
#
#  fnt appelée par un clic souris sur la zone de dessin
 
def MouseClick(event):
    global fin, startGame
    x = event.x // 100  # convertit une coordonée pixel écran en coord grille de jeu
    y = event.y // 100
    if ( (x<0) or (x>2) or (y<0) or (y>2) ) : return
 
    print("clicked at", x,y)
 
    Play(x,y)  # gestion du joueur humain et de l'IA
    #joueurSimuleIA()
 
canvas.bind('<ButtonPress-1>',    MouseClick)
 
#####################################################################################
#
#  Mise en place de l'interface - ne pas toucher
 
AfficherPage(0)
if(startGame):
    retartGame()
Window.mainloop()

La partie concernant la gestion de l'IA:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
def joueurSimuleIA():
    global colorGrille,Score,finIA,startGame
    if(win() == 2):
        startGame = True
        colorGrille = "yellow"
        if(Score>0):
            Score -= 0.5
        finIA = True
        Dessine()
    else:
        L = []
        for x in range(3):
            for y in range(3):
                if(Grille[x][y] == 0):
                    L.append((x,y))
        resultat = []
        for K in L:
            Grille[K[0]][K[1]] == 2
            print("avant")
            R = joueurSimuleHumain()
            print("apres")
            resultat.append(R,K)
            Grille[K[0]][K[1]] == 0
        return Grille[resultat[0]][resultat[1]]
 
 
def joueurSimuleHumain():
    global colorGrille,Score,finJoueur,startGame
    if(win() == 1):#fonction partie terminee
        startGame = True
        colorGrille = "red"
        Score += 1
        finJoueur = True
        Dessine()
    L = []
    for x in range(3):
        for y in range(3):
            if(Grille[x][y] == 0):
                L.append((x,y))
    resultat = []
    for K in L:
        Grille[K[0]][K[1]] == 1
        R = joueurSimuleIA()
        resultat.append(R,K)
        Grille[K[0]][K[1]] == 0
    return Grille[resultat[0]][resultat[1]]

Je dois récupérer le meilleurs coup possible en faisant des simulations (récupérer les cases vides, insérer des pions et vérifier chaque résultat). Mais les appels sont récursifs et ne s'arrêtent jamais.

Je suis bloqué là-dessus depuis Lundi.

Pouvez-vous m'aiguiller là-dessus?

Ci-dessous, l'algorithme à implémenter:

JoueurSimuleIA() :

Si la partie est finie

retourner Résultat

L = liste des coups possibles (les cases vides)

Résultats = [ ]

Pour chaque coup K dans L

Jouer le coup K (on pose le pion)

R = JoueurSimuleHumain()

Stocker R et K dans Résultats

Annuler le coup K (on retire le pion)

Retourner le coup et le résultat le plus intéressant pour l’IA

JoueurSimuleHumain() :

Si la partie est finie

retourner Résultat

L = liste des coups possibles (les cases vides)

Résultats = [ ]

Pour chaque coup K dans L

Jouer le coup K (on pose le pion)

R = JoueurSimuleIA()

Stocker R et K dans Résultats

Annuler le coup K (on retire le pion)

Retourner le coup et le résultat le plus intéressant pour l’Humain

Merci d'avance pour votre aide

Salut,

Citation:

Envoyé par janaise36

Ci-dessous, l'algorithme à implémenter

Par définition, un algorithme est supposé se terminer au bout d'un nombre d'étapes définies.... si çà ne s'arrête jamais ce n'est pas un algorithme (et vous devez revoir les conditions qui font que çà se terminera un jour...).
Jusque là, il n'y a rien à coder avec Python (sans algorithme on ne sait pas trop quoi coder).

Après, plutôt que d'inventer un algorithme de votre cru, vous pourriez commencer par étudier ce qu'on fait les moins jeunes que vous et vous en inspirer (l'algorithme minmax par exemple est assez adapté ici). Si c'est trop compliqué vous pouvez aussi récupérer des codes qui ...

- W

Bonjour

Citation:

Envoyé par janaise36

Mais les appels sont récursifs et ne s'arrêtent jamais.

C'est là l'erreur. Quand on code un récursif, la première chose à laquelle on pense c'est la condition d'arrêt de récursivité. Ici ça serait par exemple quand le jeu est rempli ou bien quand 4 pions sont alignés (si c'est bien le morpion auquel je pense).

Accessoirement bien que ce soit un code écrit en Python, cela n'est pas un souci Python mais un souci d'algo. Donc peut-être poster dans la rubrique algo eut été plus adéquat.

Citation:

Envoyé par Sve@r

Ici ça serait par exemple quand le jeu est rempli ou bien quand 4 pions sont alignés (si c'est bien le morpion auquel je pense).

Salut !

"Mais kiki dit lui !" Le morpion c'est 3 "pions" !!

Je cite son code :
Code:

1 2 3 Grille = [ [0,0,1], [2,0,0], [0,0,0] ]
https://is5-ssl.mzstatic.com/image/t.../256x256bb.jpg

Le morpion est relativement simple, de mémoire je crois qu'il n'y a qu'une seule façon de gagner... Le premier joueur met dans un coin et le second fait l'erreur de mettre un pion autre part qu'au centre, donc ça ne devrait pas être tellement compliqué à algorithmer ! ^^

Citation:

Envoyé par LeNarvalo

"Mais kiki dit lui !" Le morpion c'est 3 "pions" !!

Ok j'avais pas regardé la grille (et il y a plusieurs sortes de "morpion"). D'autant plus que je ne pensais même pas que celui-là (qui est déjà résolu avant d'y jouer) pouvait faire l'objet d'un algo (il doit y avoir au maximum une cinquantaine de possibilités).
Et effectivement le coup gagnant est soit un coin, soit le centre (avec en second coup le centre ou le coin si l'adversaire fait l'erreur de ne pas répondre correctement). Sinon c'est la nulle.