Le jeu du gendarme et du voleur - Lycée Raynouard (Brignoles)

Certains plateaux de jeu (comme celui de Scotland Yard) peuvent se voir comme des graphes. Il y a des positions (sommets) qui sont reliées par des traits (des arêtes).
Le jeu des Gendarmes et du Voleur est le jeu à deux joueurs suivant :
Le premier joueur est la Gendarmerie et possède k gendarmes (k pions).
Le deuxième joueur est le Voleur (1 pion).
La Gendarmerie commence et place ses pions-gendarmes sur les sommets du graphe (deux pions peuvent être sur la même position); puis le Voleur place son pion sur un sommet.
Ensuite, la Gendarmerie et le Voleur déplacent leurs pions à tour de rôle. A chaque tour, un pion peut soit rester sur le sommet qu’il occupe soit aller sur un sommet voisin (relié au sommet actuel par une arête). Le but du jeu pour la Gendarmerie est d’attraper le Voleur, et le but pour le Voleur est de ne pas se faire attraper (soit durant un certain nombre de tour, soit parce qu’il ne pourra jamais se faire attraper)

Pour certains graphes particuliers fixés, on cherchera à savoir quelles sont les valeurs de k (nombre de gendarmes) pour lesquelles la Gendarmerie a une stratégie gagnante et pour quelles valeurs de k le Voleur a une stratégie gagnante. On pourra notamment étudier les grilles. On pourra aussi regarder des plateaux de jeux existants comme celui de Scotland Yard bien sur, mais aussi Les Aventuriers du Rail, etc ....
On pourra étudier deux variantes : une où la Gendarmerie sait à chaque instant où est le voleur, et une où la Gendarmerie ne sait pas où se trouve le voleur.
http://www-sop.inria.fr/members/Gregory.Hoareau/Terra-Numerica/game-mode-selection