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
|
from copy import deepcopy
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 set_evaluation(self, value):
self.outcome = value
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.
- abnegamax() : algorithme de recherche du meilleur de coup quand c'est au tour de l'IA de jouer.
"""
def __init__(self):
self.partie = []
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(deepcopy(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):
# Tirage au sort du joueur qui débute
import random as rd
player = rd.choice([-1, 1])
player = 1
if player == 1:
print("Vous avez gagné le tirage au sort.")
# self.partie.append(Node([0 for _ in range(9)], 0))
# Position artificiellement avancée dans le jeu pour tenter de debugger
self.partie.append(Node([-1, 0, 0, 1, 0, 0, 1, -1, -1], 0))
else:
print("J'ai gagné le tirage au sort.\nVoici mon coup :")
self.partie.append(Node([0,0,0,0,-1,0,0,0,0], 1))
player = 1
# Affichage première fois (vide si trait humain ou avec la case centrale remplie si c'est l'IA qui vient de jouer)
print('-*'*20)
self.show(self.partie[-1].board, 0)
# Boucle jusqu'à la fin de la partie
while True:
# Demande des coups
if player == 1:
go_on = input("Continuer ?")
if go_on == "n":
break
print("\nQuel est votre coup ?")
l = int(input(" --> ligne : "))
c = int(input(" --> colonne : "))
last_board = self.partie[-1].board[:]
last_board[(3*(l-1)) + (c-1)] = 1
self.partie.append(Node(last_board, -player))
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 si partie 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() |
Problème Negamax dans morpion
Répondre avec citation
Partager