Proposition de TER.
Master 1 Informatique,
année 2006 - 2007.
Ange et Démon : Le jeu de Conway.
- Titre:
Ange et Démon : Le jeu de Conway.
- Encadrant:
Stéphane Bessy et Stéphan Thomassé.
- Parcours: ACR.
- Modules connexes:
Algorithmique et éventuellement Calculabilité-complexité.
- Résumé:
Introduit par Conway (l'inventeur du jeu de la vie), le jeu de
l'ange et du démon se déroule sur la grille :
- A chaque tour, Ange se déplace d'une case.
- Puis, Démon supprime une case non occupée par Ange.
Si au cours du jeu, Démon parvient à bloquer Ange (en supprimant toutes
les cases voisines), il gagne. Sinon Ange gagne.
Dans cette version du jeu, Démon possède une stratégie gagnante. Le problème
posé par Conway en 1996 était de determiner si Ange pouvait gagner lorsqu'il
peut bouger de n cases a chaque tour.
Quatre solutions indépendantes viennent d'etre proposées très récemment. Ange gagne
s'il peut bouger de deux cases.
Le but de ce TER est tout d'abord d'implémenter le jeu initial avec la stratégie de
Démon, puis de faire un petit état de l'art du domaine, et enfin de tenter d'implémenter les stratégies de Ange récemment proposées.