Bonjour à tous.


Je programme en Python (je ne connais pas d'autre langage. Je ne suis pas informaticien) un morpion utilisant un algorithme DFS / negamax (donc humain vs IA). Toutes les parties du code fonctionnent hormis la recherche negamax dans l'arbre des variantes.

L'idée du code est la suivante :
- Une classe Node() qui contient les attributs et méthodes d'une position : la grille, savoir qui a le trait, connaître l'issue...
- Une classe Game() pour donner le trait aux joueurs, rechercher la meilleure réponse, afficher le résultat...

Est-ce qu'une âme charitable pourrait me sortir de cette impasse ?

D'avance merci

Code Python :Sélectionner tout -Visualiser dans une fenêtre à part
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)


Même si j'ai fait en sorte de commenter le code. Toutefois il peut rester des points obscurs. Voici les points importants :
  • La grille est codée sous une forme de liste contenant 9 valeurs (0 : case vide, 1 : coup humain, -1 : coup IA)
  • L'humain est codé 1 et l'IA est codé -1. Pour connaître l'issue il faut sommer une ligne/colonne/diagonale (si elle vaut 3 c'est l'humain qui a gagné...)
  • La méthode show() prend en paramètre une liste représentant la grille et retourne un affichage "humain friendly" dans la console (cf. ci-après)
  • Pour faciliter le debug j'ai ajouté la possibilité de partir d'une grille donnée (paramètre "start_board" de run())


Focus sur la méthode "show()" :
Code Python :Sélectionner tout -Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
def show(board):
    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(ligne_explicite)
 
print("Affichage de la grille :")
print("--"*12)
show([0,0,1,-1,1,0,1,-1,-1])


Le résultat :


D'avance merci

PS : c'est un exercice de style. Je ne souhaite pas remplacer l'algorithme Negamax par un MinMax() plus explicite ni ajouter un élagage alpha/béta ni faire du Monte Carlo Tree Search comme AlphaZero ni ajouter une interface graphique...