TP : Jeu du morpion

TP : Jeu du morpion#

Pour programmer, vous pouvez soit utiliser Pyzo, soit Basthon.

Commandes Basthon :

  • Ctrl + Entrée : exécuter la cellule

  • Shift + Entrée : exécuter la cellule puis passer à la suivante

  • Entrée : passer en mode édition

  • Échap : sortir du mode édition

Les commandes suivantes sont valables uniquement hors du mode édition :

  • A : créer une nouvelle cellule (en haut)

  • B : créer une nouvelle cellule (en bas)

  • D D : supprimer la cellule

Présentation#

Dans le jeu du tic-tac-toe, ou morpion dans la langue de Molière, deux joueurs doivent remplir chacun à leur tour une case de la grille avec le symbole qui leur est attribué : X (joueur 1) ou O (joueur 2). Le gagnant est celui qui arrive à aligner trois symboles identiques, horizontalement, verticalement ou en diagonale. Le joueur 1 commence.

On représente une grille de morpion par une matrice (liste de listes) \(3\times 3\) contenant uniquement 0, 1, 2 :

  • 0 : case libre

  • 1 : croix posée par le joueur 1

  • 2 : rond posée par le joueur 2

Dictionnaire et fonction de hachage#

Nous aurons besoin d’utiliser un dictionnaire dont les clés sont des matrices (grilles de morpion). Cependant, nous avons vu dans le cours sur les dictionnaires que, étant représenté par table de hachage, un dictionnaire doit avoir des clés hachables. Un type mutable, les listes par exemple, n’étant pas hachable, il n’est donc pas possible d’en utiliser comme clé d’un dictionnaire :

d = { [1, 2, 3] : 4 } # on ne peut pas utiliser une liste comme clé d'un dictionnaire

---------------------------------------------------------------------------

TypeError                                 Traceback (most recent call last)

Cell In[1], line 1
----> 1 d = { [1, 2, 3] : 4 } # on ne peut pas utiliser une liste comme clé d'un dictionnaire


TypeError: unhashable type: 'list'

À la place, nous allons utiliser le type L suivant qui possède les mêmes opérations que les listes mais qui définit une fonction de hachage (en convertissant en tuple, qui est immutable). Le code ci-dessous utilise des notions de programmation objet largement hors-programme et n’est donc pas à lire (et encore moins à comprendre).

class L(list):
    # Methode de classe permettant de renvoyer un tuple représentant l'instance courante
    def to_tuple(self):
        def aux(l):
            # Si l est une liste
            if isinstance(l, list):
                # On cast en tuple ses élements recursivement, List étant un type récursif
                return tuple(map(aux, l))
            return l
        return aux(self)
    # On définit une methode de hachage en se basant sur la représentation en tuple de notre liste
    # C'est monInstanceDeL.__hash__() qui est appellée lorsque je demande hash(monInstanceDeL)
    def __hash__(self):
        return hash(self.to_tuple())

En pratique, on définira donc une grille de morpion avec L(...):

g_vide = L([[0, 0, 0], [0, 0, 0], [0, 0, 0]]) # grille initialement vide
g_vide

[[0, 0, 0], [0, 0, 0], [0, 0, 0]]

On peut ensuite utiliser toutes les opérations sur des listes, comme d’habitude.

Question : Définir une variable g1 représentant le morpion ci-dessous.

X|O|
 | |
 | |

Solution

Hide code cell content 
g1 = L([[1, 2, 0], [0, 0, 0], [0, 0, 0]])

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[1], line 1
----> 1 g1 = L([[1, 2, 0], [0, 0, 0], [0, 0, 0]])

NameError: name 'L' is not defined

Pour afficher une grille, on pourra utiliser la fonction suivante.

def afficher(g):
    for i in range(len(g)):
        for j in range(len(g[0])):
            if g[i][j] == 0:
                print(" ", end="")
            elif g[i][j] == 1:
                print("X", end="")
            else:
                print("O", end="")
            if j < 2:
                print("|", end="")
        print()

afficher(g1)

X|O|
 | |
 | |

Question : Écrire une fonction cases_libres(g) renvoyant la liste des positions (i, j) des cases vides de g (c’est-à-dire telles que g[i][j] vaut \(0\)).

Solution

Hide code cell content 
def cases_libres(g):
    cases = []
    for i in range(3):
        for j in range(3):
            if g[i][j] == 0:
                cases.append((i, j))
    return cases

cases_libres(g1)

[(0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]

Question : Écrire une fonction joueur(g) renvoyant le numéro du joueur qui doit jouer le prochain coup sur la grille g. On pourra compter le nombre de cases libres, par exemple. On rappelle que le joueur 1 commence.

Solution

Hide code cell content 
def joueur(grille):
    nb_cases_libres = len(cases_libres(grille))
    nb_cases_prises = 9 - nb_cases_libres
    if nb_cases_prises % 2 == 0:
        return 1
    else:
        return 2

joueur(g1)

1

Question : Écrire une fonction gagnant(g) renvoyant 1 si le joueur 1 est gagnant sur la grille g (c’est-à-dire si trois 1 sont alignés sur la grille), 2 si le joueur 2 est gagnant et 0 s’il n’y a pas encore de gagnant.
On pourra utiliser if ... == ... == ...: pour tester si trois valeurs sont égales.

Solution

Hide code cell content 
def gagnant(g):
    #test des lignes et colonnes
    for i in range(3):
        if g[i][0] == g[i][1] == g[i][2] and g[i][0] != 0:
            return g[i][0]
        if g[0][i] == g[1][i] == g[2][i] and g[0][i] != 0:
            return g[0][i]
    #test des diagonales
    if g[0][0] == g[1][1] == g[2][2] and g[0][0] != 0:
        return g[0][0]
    if g[0][2] == g[1][1] == g[2][0] and g[0][2] != 0:
        return g[0][2]
    return 0

afficher(g1)
print(gagnant(g1))

g2 = [[1, 2, 2], [0, 1, 0], [0, 0, 1]]
afficher(g2)
print(gagnant(g2))

X|O|
 | |
 | |
0
X|O|O
 |X|
 | |X
1

Question : Écrire une fonction successeurs(g) renvoyant la liste next_l des grilles que l’on peut obtenir à partir de g en jouant un coup.
Pour chaque coup possible, plutôt que modifier g, on en fera une copie (m = copy.deepcopy(g) après avoir importé avec import copy) que l’on modifiera pour jouer un coup et que l’on ajoutera à la liste next_l.

Solution

Hide code cell content 
import copy

def successeurs(g):
    next_l = []
    joueur_actuel = joueur(g)
    for i, j in cases_libres(g):
        m = copy.deepcopy(g)
        m[i][j] = joueur_actuel
        next_l.append(m)
    return next_l

afficher(g1)
successeurs(g1)

X|O|
 | |
 | |

[[[1, 2, 1], [0, 0, 0], [0, 0, 0]],
 [[1, 2, 0], [1, 0, 0], [0, 0, 0]],
 [[1, 2, 0], [0, 1, 0], [0, 0, 0]],
 [[1, 2, 0], [0, 0, 1], [0, 0, 0]],
 [[1, 2, 0], [0, 0, 0], [1, 0, 0]],
 [[1, 2, 0], [0, 0, 0], [0, 1, 0]],
 [[1, 2, 0], [0, 0, 0], [0, 0, 1]]]

Question : Écrire une fonction attracteurs(g) renvoyant la liste des grilles qui sont des attracteurs pour le joueur 1, sachant que g est la grille initiale. Une grille v est un attracteur si on a l’un des cas suivantes :

  • le joueur 1 est gagnant sur la grille v

  • c’est au joueur 1 de jouer et il existe un successeur de v qui soit un attracteur pour le joueur 1

  • c’est au joueur 2 de jouer et tous les successeurs de v sont des attracteurs pour le joueur 1

Sinon (si c’est le joueur 2 qui gagne, ou qu’il y a match nul, par exemple), v n’est pas un attracteur (d[v] = False dans le code ci-dessous).

On pourra compléter la fonction suivante, par mémoïsation :

def attracteurs(g):
    d = {} # d[v] = True si la grille v est attracteur pour le joueur 1
    def aux(v): # renvoie True si v est attracteur pour le joueur 1
        if v not in d:
            ... # calculer d[v] en utilisant la récurrence ci-dessus
        return d[v]
    aux(g)
    return [v for v in d if d[v]] # grilles v telles que d[v] == True

Solution

Hide code cell content 
def attracteurs(g):
    d = {}
    def aux(v):
        if v not in d:
            succ = [aux(w) for w in successeurs(v)]
            j = gagnant(v)
            if j == 1:
                d[v] = True
            elif j == 2 or len(succ) == 0:
                d[v] = False
            elif joueur(v) == 1:
                d[v] = any(succ)
            else:
                d[v] = all(succ)
        return d[v]
    aux(g)
    return [v for v in d if d[v]]

afficher(g1) # grille initiale
print() #Saute une ligne

for v in attracteurs(g1)[:5]: # affiche quelques attracteurs
    afficher(v)
    print() #Saute une ligne entre chaque grille

X|O|
 | |
 | |

X|O|X
O|X|O
X|O|X

X|O|X
O|X|O
X|O|

X|O|X
O|X|O
X|X|O

X|O|X
O|X|O
X| |O

X|O|X
O|X|O
X| |

Question : Le joueur 1 a t-il une stratégie gagnante à partir de la grille g1 ?

Solution

Oui, on pourra la récupérer grâce à la question suivante !

Question : Completer la fonction strategie(g) qui renvoie un dictionnaire d contenant une stratégie gagnante pour le joueur 1 à partir de la grille g. Si v est une grille accessible depuis g :

  • Si le joueur 1 a gagné sur la grille v, d[v] vaudra True.

  • S’il n’y a pas de stratégie gagnante depuis v, d[v] vaudra False.

  • Sinon, d[v] correspond à un coup possible pour le joueur 1 à partir de v correspondant à une stratégie gagnante.

def strategie(g):
    d = {}
    def aux(v):
        if v not in d:
            succ = ...
            if gagnant(v) == 1:
                d[v] = ...
            elif gagnant(v) == 2 or len(succ) == 0:
                d[v] = ...
            elif joueur(v) == 1:
                d[v] = ...
                for ...:
                    if ...:
                        ...
            else:
                d[v] = ...
        return d[v]
    aux(g)
    return d

Solution

Hide code cell content 
def strategie(g):
    d = {}
    def aux(v):
        if v not in d:
            succ = successeurs(v)
            if gagnant(v) == 1:
                d[v] = True
            elif gagnant(v) == 2 or len(succ) == 0:
                d[v] = False
            elif joueur(v) == 1:
                d[v] = False
                for w in succ:
                    if aux(w):
                        d[v] = w
            else:
                d[v] = all([aux(w) for w in succ])
        return d[v]
    aux(g)
    return d

d = strategie(g1)
afficher(g1)
afficher(d[g1])

X|O|
 | |
 | |
X|O|
 | |
X| |

Question : On vous fournit une fonction jeu(g) qui implémente le jeu du morpion à partir de la grille initiale g Trouver une séquence permettant de gagner contre l’ordinateur avec la fonction suivante (vous êtes le joueur 2).

def jeu(g):
    d = strategie(g)
    while gagnant(g) == 0:
        if joueur(g) == 2:
            afficher(g)
            i, j = map(int, input(f"{g}\nEntrez les coordonnées de votre coup : ").split())
            g[i][j] = 2
        else:
            if d[g] == False:
                print("Pas de stratégie gagnante")
                return
            g = d[g]
    print("Le joueur", gagnant(g), "a gagné !")
    afficher(g)

jeu(g1)

Solution

Hide code cell content 
    X|O|
     | |
    X| |


    [[1, 2, 0], [0, 0, 0], [1, 0, 0]]
    Entrez les coordonnées de votre coup :  0 1


    X|O|
     | |
    X| |


    [[1, 2, 0], [0, 0, 0], [1, 0, 0]]
    Entrez les coordonnées de votre coup :  0 0


    O|O|
     | |
    X| |


    [[2, 2, 0], [0, 0, 0], [1, 0, 0]]
    Entrez les coordonnées de votre coup :  0 2


    Le joueur 2 a gagné \!
    O|O|O
     | |
    X| |

Question : Améliorez la fonction jeu au regard de la question précédente. Un exemple de comportement vous est proposé ci-dessous.

Solution

Hide code cell content 
def jeu(g):
    d = strategie(g)
    while gagnant(g) == 0:
        if joueur(g) == 2:
            afficher(g)
            i, j = map(int, input(f"{g}\nEntrez les coordonnées de votre coup : ").split())
            if g[i][j]==0:
                g[i][j] = 2
            else:
                print("Coup invalide, tricher c'est mal !")
        else:
            if d[g] == False:
                print("Pas de stratégie gagnante")
                return
            g = d[g]
    print("Le joueur", gagnant(g), "a gagné !")
    afficher(g)

jeu(g1)

X|O|
 | |
X| |


[[1, 2, 0], [0, 0, 0], [1, 0, 0]]
Entrez les coordonnées de votre coup :  0 0


Coup invalide, tricher c'est mal !
X|O|
 | |
X| |


[[1, 2, 0], [0, 0, 0], [1, 0, 0]]
Entrez les coordonnées de votre coup :  1 0


X|O|
O| |
X| |X


[[1, 2, 0], [2, 0, 0], [1, 0, 1]]
Entrez les coordonnées de votre coup :  1 0


Coup invalide, tricher c'est mal !
X|O|
O| |
X| |X


[[1, 2, 0], [2, 0, 0], [1, 0, 1]]
Entrez les coordonnées de votre coup :  1 1


Le joueur 1 a gagné !
X|O|
O|O|
X|X|X

Question Bonus : Implémentez la fonction jeu2() vous permettant de jouer à deux à partir d’une grille vide

Solution

Hide code cell content 
def jeu2():
    g = L([[0, 0, 0], [0, 0, 0], [0, 0, 0]])
    while gagnant(g) == 0:
        afficher(g)
        i, j = map(int, input(f"{g}\nJoueur {joueur(g)}, entrez les coordonnées de votre coup : ").split())
        if g[i][j]==0:
            g[i][j] = joueur(g)
        else:
            print("Coup invalide, tricher c'est mal !")
    print("Le joueur", gagnant(g), "a gagné !")
    afficher(g)

jeu2()

 | |
 | |
 | |


[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
Joueur 1, entrez les coordonnées de votre coup :  0 0


X| |
 | |
 | |


[[1, 0, 0], [0, 0, 0], [0, 0, 0]]
Joueur 2, entrez les coordonnées de votre coup :  1 1


X| |
 |O|
 | |


[[1, 0, 0], [0, 2, 0], [0, 0, 0]]
Joueur 1, entrez les coordonnées de votre coup :  0 1


X|X|
 |O|
 | |


[[1, 1, 0], [0, 2, 0], [0, 0, 0]]
Joueur 2, entrez les coordonnées de votre coup :  1 0


X|X|
O|O|
 | |


[[1, 1, 0], [2, 2, 0], [0, 0, 0]]
Joueur 1, entrez les coordonnées de votre coup :  0 2


Le joueur 1 a gagné !
X|X|X
O|O|
 | |
Contents