TP : Jeu du tic-tac-toe

Présentation

Dans le jeu du tic-tac-toe (ou morpion), 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 (modifiable) comme une liste (ou un tableau numpy) 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)
/home/qfortier/repo/cours/cours/jeux/deux_joueurs/tp_morpion/tp_morpion.ipynb Cell 2 in 1
----> <a href='vscode-notebook-cell://wsl%2Bdebian/home/qfortier/repo/cours/cours/jeux/deux_joueurs/tp_morpion/tp_morpion.ipynb#W1sdnNjb2RlLXJlbW90ZQ%3D%3D?line=0'>1</a> d = { [1, 2, 3] : 4 }

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) :

class L(list):
    def to_tuple(self):
        def aux(l):
            if isinstance(l, list):
                return tuple(map(aux, l))
            return l
        return aux(self)
    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/matrices, comme d’habitude.

Question

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

X|O| 
 | | 
 | |

Solution

g1 = L([[1, 2, 0], [0, 0, 0], [0, 0, 0]])

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

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

def joueur(grille):
    nb_cases_libres = len(cases_libres(grille))
    nb_cases_vides = 9 - nb_cases_libres
    if nb_cases_vides % 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

def gagnant(g):
    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]
    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 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 L.

Solution

import copy

def successeurs(g):
    L = []
    joueur_actuel = joueur(g)
    for i, j in cases_libres(g):
        m = copy.deepcopy(g)
        m[i][j] = joueur_actuel
        L.append(m)
    return 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

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
for v in attracteurs(g1)[:5]: # affiche quelques attracteurs
    afficher(v)

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 ?

Question

Modifier attracteurs(g) en une fonction strategie(g) renvoyant 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.

Solution

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

Essayer de jouer 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)