Le jeu Cops and Robber est un jeu de poursuite sur un graphe. On choisit un ensemble de sommets, certains reliés entre eux par des arêtes (c’est-à-dire un graphe). Le premier joueur (le policier) choisit alors un sommet de départ, puis le second joueur (le voleur) fait de même. Chacun leur tour, ils se déplacent sur un sommet voisin, jusqu’à ce qu’éventuellement le policier arrive sur la même case que le voleur. On dit alors que le policier a gagné.

Le (très chouette) livre ‘The Game of Cops and Robber on Graphs’, d’Anthony Bonato et Richard J. Nowakowski présente toute une théorie autour de ce jeu. On peut par exemple se demander si, pour un certain graphe fixé, le policier peut toujours gagner. Si non, on peut alors se demander combien de policiers il faudrait pour attraper le voleur à coup sûr.

Pour essayer ce jeu sur vos graphes favoris, une version Python du jeu est disponible ici.

Il dispose d’un éditeur de graphes, pour créer et modifier vos terrains de jeu.

Le jeu a été codé avec la librairie pygame.