Arbres de jeu, minmax et Tic-Tac-Toe

Objectif du TP

L'objectif du TP est d'écrire un programme en Python qui joue au Tic Tac Toe.

L'algorithme minmax

Pour un jeu comme Tic-Tac-Toe, on peut déterminer à la main une stratégie optimale sous forme de règles. Le nombre de combinaisons est tellement faible que ce n'est pas un gros travail.
Néanmoins, il est intéressant de considérer une approche générale de la résolution de ce genre de jeu déterministe à information complète (commes les dames, échecs, ...) : l'algorithme minmax.

Implantation

Préliminaires

On a besoin de définir une classe : 

class TTT (object):
    def __init__ (self):
        self. contenu = [[' ' for j in range(3)] for i in range(3)]

À la suite de quoi, on peut définir une méthode d'affichage : 

    def __str__ (self):
        res = ""
        for i in range (0, 3):
            res = res + "\n+---+---+---+\n| "
            for j in range (0, 3):
                res = res + str (self. contenu [i] [j]) + " | "
        res = res + '\n+---+---+---+\n'
        return (res)

et une méthode pour jouer un coup : 

    def joue (self, what, x, y):
        if x < 0 or x > 2:
            return ()
        if y < 0 or y > 2:
            return ()
        if what != 'o' and what != 'x':
            return ()
        if self. contenu [x] [y] == ' ':
            self. contenu [x] [y] = what

que l'on peut combiner comme suit : 

toto = TTT ()
toto. joue ('x', 1, 0)
toto. joue ('o', 0, 0)
toto. joue ('x', 1, 1)
print (toto)

Minmax

L'algorithme minmax est récursif. On peut définir l'en-tête d'une méthode de la manière suivante : 

    def minmax (self, joueur, autre, moi, coupsPossibles, racine):

où joueur est une lettre ('x' ou 'o'), autre est l'autre lettre, moi un booléen indiquant si le joueur est moi ou mon opposany, coupsPossibles la liste des cases où lo'n peut jouer dans la configucaoitn courante et racine indique si c'est le premier appel de la fonction (True dans ce cas) ou pas.

Cette méthode doit :

  1. déterminer si la configuration courante est terminale ; renvoyez -1, 0, ou 1 le cas échéant.
  2. Si non, pour chaque coup possible, le jouer et appeler récursivement minmax.
  3. Déterminer et renvoyer la valeur du meilleur coup ou le meilleur coup parmi les coups possibles.

On peut l'écrire comme suit : 

    def minmax (self, joueur, autre, moi, coupsPossibles, racine):
        if self. agagne (joueur):
            self.__str__ ()
            if moi:
                return (+1)
            else:
                return (-1)
        if self. agagne (autre):
            self.__str__ ()
            if moi:
                return (-1)
            else:
                return (+1)
        if coupsPossibles == []:
            return 0
        valeur = [0 for i in range (9)]
        for coup in coupsPossibles:
            newPos = deepcopy (self)
            newPos. joue (joueur, coup // 3, coup % 3)
            cp = deepcopy (coupsPossibles)
            cp. remove (coup)
            valeur [coup] = newPos. minmax (autre, joueur, not moi, cp, False)
        if moi:
            v = valeur [coupsPossibles [0]]
            which = coupsPossibles [0]
            for coup in coupsPossibles:
                if valeur [coup] > v:
                    v = valeur [coup]
                    which = coup
            if racine:
                return (which)
            else:
                return (v)
        else:
            v = valeur [coupsPossibles [0]]
            which = coupsPossibles [0]
            for coup in coupsPossibles:
                if valeur [coup] < v:
                    v = valeur [coup]
                    which = coup
            if racine:
                return (which)
            else:
                return (v)

Cette méthode utilise une méthode agagne(self, joueur) qui indique si le joueur a gagné (renvoi d'un booléen) : 

    def agagne (self, joueur):
        for i in range (0, 3):
            if (self. contenu [i] == [joueur, joueur, joueur]):
                return (True)
        for i in range (0, 3):
            if (self. contenu [0] [i] == joueur) and (self. contenu [1] [i] == joueur) and (self. contenu [2] [i] == joueur):
                return (True)
        if (self. contenu [0] [0] == joueur) and (self. contenu [1] [1] == joueur) and (self. contenu [2] [2] == joueur):
            return (True)
        if (self. contenu [0] [2] == joueur) and (self. contenu [1] [1] == joueur) and (self. contenu [2] [0] == joueur):
            return (True)
        return (False)

Jeu complet

Il reste à réaliser la boucle du jeu qui à partir d'une configuration vide, saisit la case dans laquelle vous jouez puis appelle minmax() pour que l'ordinateur joue, et ainsi de suite jusque la fin de la partie.
On peut l'écrire de la manière suivante : 

    jeu = TTT()
    joueur = 'x'
    autre = 'o'
    coupsPossibles = [0, 1, 2, 3, 4, 5, 6, 7, 8]
    while True:
        while True:
            case = int (input ("où jouez-vous ? "))
            if case in coupsPossibles:
                break
        jeu. joue (joueur, case // 3, case % 3)
        print (jeu)
        if jeu. agagne (joueur):
            print (joueur + " a gagné")
            break
        coupsPossibles. remove (case)
        if coupsPossibles == []:
            print ("partie nulle")
            break
        caseAjouer = jeu. minmax (autre, joueur, False, coupsPossibles, True)
        print (autre + " joue en " + str (caseAjouer))
        coupsPossibles. remove (caseAjouer)
        jeu. joue (autre, caseAjouer // 3, caseAjouer % 3)
        print (jeu)
        if jeu. agagne (autre):
            print (autre + " a gagné")
            break

En recollant tous ces morceaux dans un fichier, vous obtenez un programme qui joue au Tic-Tac-Toe.
Les cases sont numérotées dans l'ordre suivant :

012
345
678

Autres activités autour de l'arbre de jeu du tic-tac-toe