---
tags: corrTD, info, jeux, 2425
---
# <center>TD7 : jeux sur un graphe</center>
> :books: Documents de base : le [cours](http://demeslay.maths.free.fr/fichiers/info/spe/04_Jeux_graphe.pdf) et le [TD3](http://demeslay.maths.free.fr/fichiers/info/spe/TD07_Jeux.pdf). [color=red]
[TOC]
## Exercice 2 : Coloration graphe biparti avec un algorithme
```python=
def est_biparti(graphe: dict, depart: int) -> list:
explores = [] # liste des sommets déjà explorés
a_visiter = [] # pile des sommets à explorer
a_visiter.append(depart)
couleurs = {s: -1 for s in graphe} # tous les sommets sans couleur
c = 0
couleurs[depart] = c # coloriage du départ
while len(a_visiter) > 0:
sommet = a_visiter.pop()
explores.append(sommet)
c = 1 - couleurs[sommet] # changement couleur
for voisin in graphe[sommet]:
if voisin not in explores:
a_visiter.append(voisin)
couleurs[voisin] = c
else:
if couleurs[voisin] != c:
return False
return True
```
Pour tester l'algorithme, voici les dictionnaires représentant les graphes de l'exercice 1 :
```python
graph1 = {0: [1, 5], 1: [2, 4], 2: [3], 3: [4], 4: [], 5: [2, 4]}
graph2 = {0: [1], 1: [2, 5], 2: [], 3: [0, 4], 4: [1, 6], 5: [3], 6: [], 7: [0]}
graph3 = {0: [1], 1: [2, 5], 2: [5], 3: [0, 4], 4: [6], 5: [3, 7], 6: [2], 7: []}
```
---
## Exercice 3 : Représenter un jeu
**Q1.**
```mermaid
flowchart TD
A(("(1,0)")) --> B["(2,1)"]
A --> C["(2,2)"]
A --> D["(2,3)"]
B --> E(("(1,2)"))
B --> F(("(1,4)"))
C --> G(("(1,5)"))
D --> G
D --> F
E --> H["(2,5)"]
F --> H
```
**Q2.** Comme d'habitude, les clés sont les sommets et la valeur associée est la liste des voisins.
Ainsi le graphe ci-dessus est représenté par
```python
chomp = {(1,0): [(2,1), (2,2), (2,3)],
(2,1): [(1,2), (1,4)],
...
(1,2): [(2,5)],
(2,5): []}
```
:::info
:bulb: Il ne faut pas oublier les sommets qui n'ont pas de voisin car ils jouent un rôle crucial, comme le montre la question suivante.
:::
**Q3.** Les états finaux sont les sommets de degré sortant nul, donc ici (2,5) et (1,5). D'après les règles du jeu, le perdant est celui qui prend le dernier carré donc :
- (2,5) est un état final perdant pour J2 et donc gagnant pour J1,
- (1,5) est un état final perdant pour J1.
**Q4.** Il suffit de suivre un chemin dans le graphe menant, d'après la question précédente, à l'état final (2,5).
Par exemple
(1,0) -> (2,1) -> (1,4) -> (2,5).
## Exercice 4 : Arène d’un jeu de Nim
**Q1.**
```mermaid
flowchart TD
A(("(1,4)")) --> B["(2,3)"]
A --> C["(2,2)"]
B --> D(("(1,2)"))
B --> E(("(1,1)"))
C --> E
C --> F(("(1,0)"))
D --> G["(2,1)"]
D --> H["(2,0)"]
E --> H
G --> F
```
**Q2.**
Comme d'habitude, voir exercices précédents.
**Q3.**
D'après Q1, on voit que s'il reste au moins 2 bâtonnets, le sommet à deux voisins : l'autre joueur jouera avec un ou deux bâtonnets de moins.
Il faut ensuite continuer le jeu à partir de ces deux voisins.
En revanche, s'il ne reste qu'un bâtonnet, un seul coup est possible et s'il n'en reste aucun, il n'y a pas de voisin et il n'y a plus rien à construire.
```python=
def nim(j: int, n: int, G: dict) -> None:
"""
Construction récursive du graphe du jeu de Nim.
n = nombre de bâtonnets,
j = numéro du joueur.
"""
if n >= 2:
# ajout des deux voisins
G[(j, n)] = [(3-j, n-2), (3-j, n-1)]
# construction à partir de ces deux voisins
nim(3-j, n-1, G)
nim(3-j, n-2, G)
elif n == 1:
# ajout de l'unique voisin
G[(j, n)] = [(3-j, 0)]
# construction à partir de celui-ci
nim(3-j, n-1, G)
else:
# le sommet n'a pas de voisin
G[(j, n)] = []
```
## Exercice 5 : Déterminer une stratégie gagnante
**Q1.** J1 gagne lorsqu'il a pris le dernier bâtonnet donc lorsque c'est à J2 de jouer quand il ne reste aucun bâtonnent. Ainsi (2,0) est l'unique état final gagnant pour J1.
**Q2.** En dessinant le graphe du jeu (comme à l'exercice 4), on voit que J1 peut gagner s'il est en (1,2) ou en (1,1). Ainsi, si J2 est en (2,3), il est forcé de jouer vers l'un de ces deux sommets, et J1 gagnera donc la partie.
**Q3.** En (1,4), si J1 prend un bâtonnet, on va en (2,3) qui est perdant pour J2. En (1,5), si J1 prend deux bâtonnets, on va de même en (2,3).
Ces deux sommets sont donc gagnants pour J1.
**Q4.** On continue le même raisonnement que Q2 / Q3 : en (2,6), J2 est forcé d'aller vers (1,5) ou (1,4) et donc de perdre la partie d'après les questions précédentes.
On a ainsi la stratégie gagnante :-1:
- au départ en (1,7), J1 prend un peu bâtonnet pour aller vers (2,6) (et alors J2 ira vers (1,5) ou (1,4)) ;
- si on est en (1,5), J1 prend 2 bâtonnets et si on est en (1,4), il prend 1 bâtonnet. Dans tous les cas, on arrive en (2,3) (et alors J2 ira vers (1,2) ou (1,1)) ;
- J1 prend alors l'unique ou les deux bâtonnets restant et gagne.
**Q5.** Avec le même type de raisonnement, on se rend compte que c'est J2 qui a une stratégie gagnante, en suivant le même raisonnement que dans la question précédente.