IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Python Discussion :

Problème Negamax dans morpion


Sujet :

Python

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Futur Membre du Club
    Homme Profil pro
    Responsable des études
    Inscrit en
    Décembre 2017
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Responsable des études

    Informations forums :
    Inscription : Décembre 2017
    Messages : 5
    Par défaut Problème Negamax dans morpion
    Bonjour à tous.

    Depuis quelque temps je bloque sur un programme de morpion utilisant un negamax (donc un humain contre une IA). Toutes les parties du code fonctionnent hormis la recherche 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 position, 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 : 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
     
    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()

  2. #2
    Membre Expert

    Homme Profil pro
    Ingénieur calcul scientifique
    Inscrit en
    Mars 2013
    Messages
    1 229
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur calcul scientifique

    Informations forums :
    Inscription : Mars 2013
    Messages : 1 229
    Par défaut
    Bonjour

    Ce n'est pas le seul problème que vous avez. On peut jouer une même case plusieurs fois par exemple ...
    Faire un "HumanPrint" serait pas mal (remplacé les 0 par des espaces, les -1 par des rond (des zéros), et les +1 par des croix (des X)), car j'avoue qu'à la première exécution j'ai juste rien compris !

    Concernant votre problème je pense qu'il y a des incohérences dans l'IA.
    Dans get_evaluation, votre variable analyse vous donne la somme des lignes, colonnes et diagonales.
    Vous vous servez de cette même variable pour 2 choses distinctes :
    - Donner une évaluation de votre grille
    - Déterminer si la partie est finie

    Sauf que si la partie n'est pas finie, il faudrait être capable tout de même d'évaluer si un coup donné est meilleur qu'un autre...
    Et là ben ca va etre compliqué vu que votre fonction get_evaluation, va juste vous renvoyé un outcome de 1 quelquesoit la configuration non terminale donnée.

    Donc pour moi il faut :
    - Séparer le test de finalité du jeu de l'évaluation d'une grille.
    - L'évaluation d'une grille (ou d'un coup) va être un score. Il n'aura pas de valeur défini à l'avance. Juste un score de 0, c'est un coup pour du beurre, un score négatif c'est un coup qui avantage le joueur -1, et un score positif avantage le joueur +1. Et la valeur du score va dire si ca avantage beaucoup ou pas. Ca pourrait etre un réel entre 0 et 1 même (la probabilité de gagner en jouant ce coup).
    - Cette probabilité vous pouvez :
    a) la calculer de manière exacte, en parcourant toutes les noeuds fils de votre noeud, en attribuant un score au configuration terminale (-3,0, ou +3 par exemple), et puis faire remonter ces scores à votre noeud courant en les moyennant par exemple pour noter le noeud au dessus.
    Les noeuds fils ne sont à priori pas connu puisqu'on ne sait pas ce que l'humain va jouer. Il faut alors se fixer un nombre N d'analyses à faire, puis tirer au hasard des coups que l'humain ferait. Plus N est grand, plus votre IA sera balaise (voire imbattable puisqu'à un moment donné N pourrait être plus grand que le nombre de configuration totale offerte par la grille)
    b) l'estimer, mais là il faut trouver des astuces pour dire pourquoi un coup est meilleur qu'un autre sans aller explorer plus loin l'arbre.

  3. #3
    Futur Membre du Club
    Homme Profil pro
    Responsable des études
    Inscrit en
    Décembre 2017
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Responsable des études

    Informations forums :
    Inscription : Décembre 2017
    Messages : 5
    Par défaut
    @lg_53



    1/ Effectivement l'humain peut jouer plusieurs fois au même endroit. Le programme ne fait pas de test sur le remplissage. Ce n'est pas un bug. Le programme est en chantier.

    2/ La méthode "show()" permet d'afficher la grille. Il suffit de passer une grille sous la forme d'une liste de taille 9 et les "1" sont remplacés par des "X", les 0 (case vide) par des "." et les -1 (coup de l'IA) par des "0" :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     
    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 :
    Nom : exemple_grille.PNG
Affichages : 161
Taille : 1,9 Ko

    3/ Concernant l'algorithme je souhaite implémenter un DFS (Depth First Search). Il n'est pas prévu de faire un autre mode de recherche (Éventuellement ajouter un élagage AlphaBeta quand le negamax fonctionnera). Je note la proposition alternative qui ressemble à l'approche "Monte Carlo Tree Search" utilisée dans AlphaGo. Si vous ne connaissiez pas cette méthode votre créativité est Gouguelesque.

    La méthode "get_evaluation" retourne un nombre qui prend 4 valeurs :
    - "0" : la partie est nulle : la grille est remplie
    - "3" : l'humain a gagné
    - "-3" : l'IA a gagné
    - "1" : partie en cours

    Je l'utilise dans le negamax pour valoriser la position et l'algorithme (enfin c'est ce que je souhaite) doit fait remonter la valeur de la feuille dans les noeuds pères. C'est donc un parcours quasi exhaustif de l'arbre sauf que la récursivité s'arrête quand une feuille (c-à-d gain ou grille remplie) est rencontrée.

    Voici un arbre qui représente une partie :

    Nom : Exemple_Arbre_Morpion.JPG
Affichages : 163
Taille : 42,0 Ko

    Avez-vous une autre idée ?

  4. #4
    Expert éminent
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 741
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 741
    Par défaut
    Salut,

    Citation Envoyé par jb75009 Voir le message
    Je l'utilise dans le negamax pour valoriser la position mais l'algorithme (enfin c'est ce que je souhaite) fait remonter la valeur de la feuille dans les noeuds pères. C'est donc un parcours quasi exhaustif de l'arbre sauf que la récursivité s'arrête quand une feuille (i.e. gain ou grille remplie) est rencontrée.
    Les bons forums pour les algorithmes dans différents domaines sont dans la rubrique algorithmique.

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  5. #5
    Futur Membre du Club
    Homme Profil pro
    Responsable des études
    Inscrit en
    Décembre 2017
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Responsable des études

    Informations forums :
    Inscription : Décembre 2017
    Messages : 5
    Par défaut
    Merci
    je déplace

Discussions similaires

  1. Problème heure dans un formulaire
    Par Faro dans le forum Access
    Réponses: 7
    Dernier message: 15/09/2005, 11h11
  2. [ZEOSLIB] Problème Insertion dans une table
    Par moscovisci dans le forum Bases de données
    Réponses: 1
    Dernier message: 09/06/2005, 12h05
  3. problème debodybackground dans une page php
    Par bertrand_declerck dans le forum Balisage (X)HTML et validation W3C
    Réponses: 4
    Dernier message: 04/02/2005, 22h39
  4. Problème alinéa dans textarea
    Par guitaros dans le forum Balisage (X)HTML et validation W3C
    Réponses: 7
    Dernier message: 23/12/2004, 00h07
  5. Problème formatage dans balise title / alt
    Par jflebegue dans le forum Mise en page CSS
    Réponses: 9
    Dernier message: 09/12/2004, 15h18

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo