{
"cells": [
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"# TP : Jeu du tic-tac-toe\n",
"\n",
"## Présentation\n",
"\n",
"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.\n",
"\n",
"
\n",
"\n",
"On représente une grille de morpion par une matrice (liste de listes) $3\\times 3$ contenant uniquement 0, 1, 2 :\n",
"- 0 : case libre \n",
"- 1 : croix posée par le joueur 1\n",
"- 2 : rond posée par le joueur 2\n",
"\n",
"## Dictionnaire et fonction de hachage\n",
"\n",
"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 :"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"ename": "TypeError",
"evalue": "unhashable type: 'list'",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)",
"\u001b[1;32m/home/qfortier/repo/cours/cours/jeux/deux_joueurs/tp_morpion/tp_morpion.ipynb Cell 2\u001b[0m in \u001b[0;36m1\n\u001b[0;32m----> 1\u001b[0m d \u001b[39m=\u001b[39m { [\u001b[39m1\u001b[39m, \u001b[39m2\u001b[39m, \u001b[39m3\u001b[39m] : \u001b[39m4\u001b[39m }\n",
"\u001b[0;31mTypeError\u001b[0m: unhashable type: 'list'"
]
}
],
"source": [
"d = { [1, 2, 3] : 4 } # on ne peut pas utiliser une liste comme clé d'un dictionnaire"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"À 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) :"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"class L(list):\n",
" def to_tuple(self):\n",
" def aux(l):\n",
" if isinstance(l, list):\n",
" return tuple(map(aux, l))\n",
" return l\n",
" return aux(self)\n",
" def __hash__(self):\n",
" return hash(self.to_tuple())"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"En pratique, on définira donc une grille de morpion avec `L(...)` :"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[0, 0, 0], [0, 0, 0], [0, 0, 0]]"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g_vide = L([[0, 0, 0], [0, 0, 0], [0, 0, 0]]) # grille initialement vide\n",
"g_vide"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"On peut ensuite utiliser toutes les opérations sur des listes/matrices, comme d'habitude."
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"````{admonition} Question\n",
" Définir une variable `g1` représentant le morpion ci-dessous. \n",
"\n",
"```\n",
"X|O| \n",
" | | \n",
" | |\n",
"``` \n",
"````"
]
},
{
"cell_type": "markdown",
"execution_count": 5,
"metadata": {
"tags": [
"cor"
]
},
"source": [
"````{admonition} Solution\n",
":class: tip, dropdown\n",
"``` python\n",
"g1 = L([[1, 2, 0], [0, 0, 0], [0, 0, 0]])\n",
"```\n",
"````"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour afficher une grille, on pourra utiliser la fonction suivante."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"def afficher(g):\n",
" for i in range(len(g)):\n",
" for j in range(len(g[0])):\n",
" if g[i][j] == 0:\n",
" print(\" \", end=\"\")\n",
" elif g[i][j] == 1:\n",
" print(\"X\", end=\"\")\n",
" else:\n",
" print(\"O\", end=\"\")\n",
" if j < 2:\n",
" print(\"|\", end=\"\")\n",
" print()"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"X|O| \n",
" | | \n",
" | | \n"
]
}
],
"source": [
"afficher(g1)"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"````{admonition} Question\n",
" É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$).\n",
"````"
]
},
{
"cell_type": "markdown",
"execution_count": 8,
"metadata": {
"tags": [
"cor"
]
},
"source": [
"````{admonition} Solution\n",
":class: tip, dropdown\n",
"``` python\n",
"def cases_libres(g):\n",
" cases = []\n",
" for i in range(3):\n",
" for j in range(3):\n",
" if g[i][j] == 0:\n",
" cases.append((i, j))\n",
" return cases\n",
"```\n",
"````"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cases_libres(g1)"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"````{admonition} Question\n",
" É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.\n",
"````"
]
},
{
"cell_type": "markdown",
"execution_count": 10,
"metadata": {
"tags": [
"cor"
]
},
"source": [
"````{admonition} Solution\n",
":class: tip, dropdown\n",
"``` python\n",
"def joueur(grille):\n",
" nb_cases_libres = len(cases_libres(grille))\n",
" nb_cases_vides = 9 - nb_cases_libres\n",
" if nb_cases_vides % 2 == 0:\n",
" return 1\n",
" else:\n",
" return 2\n",
"```\n",
"````"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"joueur(g1)"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"````{admonition} Question\n",
" É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. \n",
"On pourra utiliser `if ... == ... == ...:` pour tester si trois valeurs sont égales.\n",
"````"
]
},
{
"cell_type": "markdown",
"execution_count": 12,
"metadata": {
"tags": [
"cor"
]
},
"source": [
"````{admonition} Solution\n",
":class: tip, dropdown\n",
"``` python\n",
"def gagnant(g):\n",
" for i in range(3):\n",
" if g[i][0] == g[i][1] == g[i][2] and g[i][0] != 0:\n",
" return g[i][0]\n",
" if g[0][i] == g[1][i] == g[2][i] and g[0][i] != 0:\n",
" return g[0][i]\n",
" if g[0][0] == g[1][1] == g[2][2] and g[0][0] != 0:\n",
" return g[0][0]\n",
" if g[0][2] == g[1][1] == g[2][0] and g[0][2] != 0:\n",
" return g[0][2]\n",
" return 0\n",
"```\n",
"````"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"X|O| \n",
" | | \n",
" | | \n",
"0\n",
"X|O|O\n",
" |X| \n",
" | |X\n",
"1\n"
]
}
],
"source": [
"afficher(g1)\n",
"print(gagnant(g1))\n",
"\n",
"g2 = [[1, 2, 2], [0, 1, 0], [0, 0, 1]]\n",
"afficher(g2)\n",
"print(gagnant(g2))"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"````{admonition} Question\n",
" Écrire une fonction `successeurs(g)` renvoyant la liste `L` des grilles que l'on peut obtenir à partir de `g` en jouant un coup. \n",
"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`.\n",
"````"
]
},
{
"cell_type": "markdown",
"execution_count": 14,
"metadata": {
"tags": [
"cor"
]
},
"source": [
"````{admonition} Solution\n",
":class: tip, dropdown\n",
"``` python\n",
"import copy\n",
"\n",
"def successeurs(g):\n",
" L = []\n",
" joueur_actuel = joueur(g)\n",
" for i, j in cases_libres(g):\n",
" m = copy.deepcopy(g)\n",
" m[i][j] = joueur_actuel\n",
" L.append(m)\n",
" return L\n",
"```\n",
"````"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"X|O| \n",
" | | \n",
" | | \n"
]
},
{
"data": {
"text/plain": [
"[[[1, 2, 1], [0, 0, 0], [0, 0, 0]],\n",
" [[1, 2, 0], [1, 0, 0], [0, 0, 0]],\n",
" [[1, 2, 0], [0, 1, 0], [0, 0, 0]],\n",
" [[1, 2, 0], [0, 0, 1], [0, 0, 0]],\n",
" [[1, 2, 0], [0, 0, 0], [1, 0, 0]],\n",
" [[1, 2, 0], [0, 0, 0], [0, 1, 0]],\n",
" [[1, 2, 0], [0, 0, 0], [0, 0, 1]]]"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"afficher(g1)\n",
"successeurs(g1)"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"````{admonition} Question\n",
" É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 :\n",
"- le joueur 1 est gagnant sur la grille `v`\n",
"- c'est au joueur 1 de jouer et il existe un successeur de `v` qui soit un attracteur pour le joueur 1\n",
"- c'est au joueur 2 de jouer et tous les successeurs de `v` sont des attracteurs pour le joueur 1\n",
"\n",
"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).\n",
"\n",
"On pourra compléter la fonction suivante, par mémoïsation :\n",
"````"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [],
"source": [
"def attracteurs(g):\n",
" d = {} # d[v] = True si la grille v est attracteur pour le joueur 1\n",
" def aux(v): # renvoie True si v est attracteur pour le joueur 1\n",
" if v not in d:\n",
" ... # calculer d[v] en utilisant la récurrence ci-dessus\n",
" return d[v]\n",
" aux(g)\n",
" return [v for v in d if d[v]] # grilles v telles que d[v] == True"
]
},
{
"cell_type": "markdown",
"execution_count": 17,
"metadata": {
"tags": [
"cor"
]
},
"source": [
"````{admonition} Solution\n",
":class: tip, dropdown\n",
"``` python\n",
"def attracteurs(g):\n",
" d = {}\n",
" def aux(v):\n",
" if v not in d:\n",
" succ = [aux(w) for w in successeurs(v)]\n",
" j = gagnant(v)\n",
" if j == 1:\n",
" d[v] = True\n",
" elif j == 2 or len(succ) == 0:\n",
" d[v] = False\n",
" elif joueur(v) == 1:\n",
" d[v] = any(succ)\n",
" else:\n",
" d[v] = all(succ)\n",
" return d[v]\n",
" aux(g)\n",
" return [v for v in d if d[v]]\n",
"```\n",
"````"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"X|O| \n",
" | | \n",
" | | \n",
"X|O|X\n",
"O|X|O\n",
"X|O|X\n",
"X|O|X\n",
"O|X|O\n",
"X|O| \n",
"X|O|X\n",
"O|X|O\n",
"X|X|O\n",
"X|O|X\n",
"O|X|O\n",
"X| |O\n",
"X|O|X\n",
"O|X|O\n",
"X| | \n"
]
}
],
"source": [
"afficher(g1) # grille initiale\n",
"for v in attracteurs(g1)[:5]: # affiche quelques attracteurs\n",
" afficher(v)"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"````{admonition} Question\n",
" Le joueur 1 a t-il une stratégie gagnante à partir de la grille `g1` ?\n",
"````"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"````{admonition} Question\n",
" 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` :\n",
"- Si le joueur 1 a gagné sur la grille `v`, `d[v]` vaudra `True`.\n",
"- S'il n'y a pas de stratégie gagnante depuis `v`, `d[v]` vaudra `False`.\n",
"- Sinon, `d[v]` correspond à un coup possible pour le joueur 1 à partir de `v` correspondant à une stratégie gagnante. \n",
"````"
]
},
{
"cell_type": "markdown",
"execution_count": 19,
"metadata": {
"tags": [
"cor"
]
},
"source": [
"````{admonition} Solution\n",
":class: tip, dropdown\n",
"``` python\n",
"def strategie(g):\n",
" d = {}\n",
" def aux(v):\n",
" if v not in d:\n",
" succ = successeurs(v)\n",
" if gagnant(v) == 1:\n",
" d[v] = True\n",
" elif gagnant(v) == 2 or len(succ) == 0:\n",
" d[v] = False\n",
" elif joueur(v) == 1:\n",
" d[v] = False\n",
" for w in succ:\n",
" if aux(w):\n",
" d[v] = w\n",
" else:\n",
" d[v] = all([aux(w) for w in succ])\n",
" return d[v]\n",
" aux(g)\n",
" return d\n",
"```\n",
"````"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"X|O| \n",
" | | \n",
" | | \n",
"X|O| \n",
" | | \n",
"X| | \n"
]
}
],
"source": [
"d = strategie(g1)\n",
"afficher(g1)\n",
"afficher(d[g1])"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"````{admonition} Question\n",
" Essayer de jouer contre l'ordinateur avec la fonction suivante (vous êtes le joueur 2).\n",
"````"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def jeu(g):\n",
" d = strategie(g)\n",
" while gagnant(g) == 0:\n",
" if joueur(g) == 2:\n",
" afficher(g)\n",
" i, j = map(int, input(f\"{g}\\nEntrez les coordonnées de votre coup : \").split())\n",
" g[i][j] = 2\n",
" else:\n",
" if d[g] == False:\n",
" print(\"Pas de stratégie gagnante\")\n",
" return\n",
" g = d[g]\n",
" print(\"Le joueur\", gagnant(g), \"a gagné !\")\n",
" afficher(g)\n",
"\n",
"jeu(g1)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.2"
},
"vscode": {
"interpreter": {
"hash": "767d51c1340bd893661ea55ea3124f6de3c7a262a8b4abca0554b478b1e2ff90"
}
}
},
"nbformat": 4,
"nbformat_minor": 2
}