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
| class Node():
"""
Classe contenant les attributs et méthodes d'un noeud dans un arbre d'un morpion
Attributs :
- 'board' : grille contenant les choix de chaque joueur. Liste de taille 9 remplie de 0 si la case
est vide, de 1 pour le premier joueur et de -1 pour le second
- 'player' : joueur qui a le trait. Codé à 1 pour l'humain et -1 pour l'IA
- 'children' : liste contenant les noeuds (class Node()) qui peuvent découler de la position
- 'best_child' : meilleur noeud suivant (class Node()).
- 'outcome' : état du jeu (-3 : IA gagne, 3 : humain gagne, 1 : partie non terminée, 0 : partie nulle et None
si la méthode get_evaluation() n'a pas été appelée.
Méthodes :
- 'get_evaluation()' : méthode pour déterminer l'état du jeu (valorise l'attribut 'outcome')
- 'is_terminal()' : méthode qui renvoie True si la partie est terminée
- 'get_children()' : générateur des noeuds suivants (profondeur 1 soit les réponses directes possibles).
Cette méthode alimente l'attribut 'children'
- 'set_best_child()' : méthode pour alimenter l'attribut 'best_child'
"""
def __init__(self, board, player):
self.board = board
self.player = player
self.children = []
self.outcome = None
def get_evaluation(self):
analyse = []
analyse.append(sum(self.board [0:3]))
analyse.append(sum(self.board [3:6]))
analyse.append(sum(self.board [6:9]))
analyse.append(sum(self.board [::3]))
analyse.append(sum(self.board [1::3]))
analyse.append(sum(self.board [2::3]))
analyse.append(sum(self.board [::4]))
analyse.append(sum(self.board [2:7:2]))
if 3 in analyse:
self.outcome = 3
elif -3 in analyse:
self.outcome = -3
elif 0 not in self.board:
self.outcome = 0
else:
self.outcome = 1
def is_terminal(self):
self.get_evaluation()
if self.outcome != 1:
return True
else:
return False
def get_children(self):
for idx, val in enumerate(self.board):
if val==0:
board_tmp = self.board[:]
board_tmp[idx] = self.player
self.children.append(Node(board_tmp, -self.player))
def set_best_child(self, node):
self.best_child = node
class Game():
"""
Classe contenant les attributs et méthodes d'un jeu de morpion
Attributs :
- 'partie' : liste contenant les positions successives (class Node()) de la partie
Méthodes :
- show() : méthode permettant d'afficher la grille de jeu.
- run() : méthode permettant de demander un coup à l'humain, d'appeler l'IA, d'appeler l'affichage
et d'indiquer l'issu du jeu.
- negamax() : algorithme de type DFS quand c'est au tour de l'IA de jouer.
"""
def __init__(self):
pass
def negamax(self, node):
if node.is_terminal():
return -node.player * node.outcome
node.get_children()
best_value = float('-inf')
for child in node.children:
value_tmp = -self.negamax(child)
if value_tmp > best_value:
best_value = value_tmp
node.set_best_child(child)
return best_value
def show(self, board, depth):
dico = {0:' . ', 1:' X ', -1:' 0 '}
for i in range(3):
ligne_codee = board[i*3:(i*3)+3]
ligne_explicite = ' | '.join([dico.get(n, n) for n in ligne_codee])
print(" "*depth, ligne_explicite)
def run(self, start_board=None, start_player=None):
# On initialise ici la partie et non dans le constructeur pour permettre de rejouer sans réinstancier
self.partie = []
# Joueur au trait (possibiliter de forcer pour debug)
if start_player == None:
import random as rd
player = rd.choice([-1, 1])
else:
player = start_player
# Position de depart (si option non remplie on prend une matrice vide)
if start_board == None:
start_board = [0 for _ in range(9)]
# Premier coup
if player == 1:
print("Vous avez le trait.")
self.partie.append(Node(start_board, 0)) # Initialisation d une grille vide
else:
print("J'ai le trait.\nVoici mon coup :")
self.partie.append(Node([0,0,0,0,-1,0,0,0,0], 1)) # Heuristique : on joue au centre
player = 1
# Premier affichage
print('-*'*20)
self.show(self.partie[-1].board, 0)
# Boucle jusqu à la fin de la partie
while True:
# Demande des coups
if player == 1:
# Branchement pour sortir quand on en a marre
go_on = input("Continuer (o/n) ?")
if go_on == "n":
break
# On boucle tant que le coup n est pas légal
while True:
print("\nQuel est votre coup ?")
l = int(input(" --> ligne : "))
c = int(input(" --> colonne : "))
last_board = self.partie[-1].board[:]
if last_board[(3*(l-1)) + (c-1)] != 0:
print("\nCase déjà occupée")
elif min(l, c)<1 or max(l,c)>3:
print("\nCoup hors limites (1-3)")
else:
last_board[(3*(l-1)) + (c-1)] = 1
self.partie.append(Node(last_board, -player))
break
else:
self.negamax(self.partie[-1])
best_next_board = self.partie[-1].best_child.board[:]
self.partie.append(Node(best_next_board, -player))
print("\nVoici mon coup :")
# Affichage de la matrice après chaque coup joué
print('-*'*20)
self.show(self.partie[-1].board, 0)
# Test pour savoir si la partie est terminée
self.partie[-1].get_evaluation()
if self.partie[-1].outcome == 0:
print("Partie nulle !")
break
elif self.partie[-1].outcome == 3:
print("Vous avez gagné. Félicitations !")
break
elif self.partie[-1].outcome == -3:
print("J'ai gagné !")
break
# On change de joueur
player = -player
g = Game()
g.run(start_board=[-1, 0, 1, 1, 0, 0, 1, -1, -1], start_player=-1) |
Problème Negamax dans morpion
Répondre avec citation
Partager