Jouez avec les diagrammes de Voronoï

Les joueurs jouent tour à tour. À chaque tour, ils placent une « pierre » en cliquant dans l’aire de jeu. Chaque pierre prend la souveraineté sur la portion de territoire qui est plus proche d’elle que de toute autre pierre : cette zone prend la forme d’une cellule de Voronoï. Chaque fois qu’une nouvelle pierre est posée, la zone dépendant des pierres précédentes est recalculée. Au bout du nombre de tours fixé au départ, le joueur dont l’ensemble des cellules couvre la plus grande surface est déclaré vainqueur.

Ce jeu fonctionne avec deux à huit joueurs.
Quatre types de joueurs « informatiques » vous sont proposés. Par défaut, vous jouez seul contre « Bonne Pioche ».

Les quatre joueurs que nous avons programmés ont chacun une stratégie différente :
« Grosse Tête » joue totalement au hasard,
« Anti Gagnant » divise la plus grande cellule de Voronoï du joueur qui est en tête,
« Poly Majeur » divise la plus grande de toutes les cellules de Voronoï précédentes,
« Bonne Pioche » prend dix points au hasard puis sélectionne celui qui correspond à la plus grande surface.

Et vous, « Humain », vous vous adaptez…
Amusez-vous bien !

Au carrefour de la géométrie…

À l’origine de ce jeu de Voronoï, il y a bien sûr les diagrammes de Voronoï, ainsi nommés d’après le mathématicien russe Georgi Voronoï (1868-1908).

Étant donnés deux points dans le plan, la droite qui est à égale distance de ces deux points, la médiatrice, divise le plan en deux régions, chacune de ces régions contenant les points qui sont plus proches de l’un des points choisis au départ que de l’autre. Lorsqu’on ajoute des points, le même principe s’applique, et on obtient des cellules contenant les points plus proches de l’un des points fixés que de tous les autres. L’ensemble de ces cellules forment un diagramme de Voronoï dans le plan.

Les diagrammes de Voronoï sont des structures que l’on rencontre souvent dans la nature comme sur la peau des girafes ou la structure des cellules.

Ils ont été utilisés de façon informelle depuis fort longtemps, par exemple par Descartes dès 1644. Le physicien britannique John Snow a utilisé un diagramme de Voronoï pour montrer que la majorité des personnes décédées dans l’épidémie de choléra de Soho, à Londres, vivait plus près de la pompe infectée de Broad Street que de n’importe quelle autre pompe.

Les applications actuelles des diagrammes de Voronoï touchent des domaines très différents, comme les réseaux de téléphone ou la médecine dans l’étude de l’évolution des cellules cancéreuses. Les lois internationales déterminant les frontières sous-marines entre pays voisins sont basées sur les diagrammes de Voronoï. L’étude de ces diagrammes, de leurs propriétés mathématiques, de leur calcul et de leurs nombreuses variantes reste un sujet très important de géométrie.

Les diagrammes de Voronoï sont par exemple utilisés pour modéliser les réseaux téléphoniques. Aujourd’hui, quand nous téléphonons avec notre portable, notre demande est (en première approximation) transmise à la station la plus proche. Toutes les stations de la région sont reliées entre elles par un réseau filaire qui permet de faire circuler la communication jusqu’à la station la plus proche de notre correspondant. Où doit-on ajouter des stations et combien si le réseau grandit ?… tout cela n’est pas facile à gérer. Heureusement, les mathématiques et l’informatique sont là ! La zone précise où chaque abonné est plus proche d’une station que de n’importe quelle autre est la cellule de Voronoï de cette station.

Si on relie les stations voisines par des liens (les canaux de communication filaires), on obtient une autre mosaïque appelée triangulation de Delaunay. Dans les modèles les plus simples, lorsqu’on téléphone, l’appel est d’abord transmis à la station la plus proche, puis on utilise le chemin le plus court de la triangulation de Delaunay pour router la communication jusqu’à la station du correspondant.

Pour en savoir plus, vous pouvez consulter les autres documents de la thématique Géométrie et modélisation d’objets, en particulier Reconstruire des surfaces pour l’imagerie.

…et de la théorie des jeux

Mais un autre sujet d’intérêt est abordé ici : peut-on calculer sa chance de gagner ? Y a-t-il des stratégies imparables ? Cette problématique rejoint la théorie des jeux.

Dans sa version la plus simple, le jeu de Voronoï est joué à deux, un joueur rouge et un joueur vert par exemple, qui placent un point tour à tour dans l’aire de jeu.

Dans le cas d’un jeu de Voronoï à une dimension (où on placerait des points pour diviser un segment de droite et non une surface), Hee-Kap Ahn et ses collègues ont montré que le deuxième joueur, le joueur vert, est sûr de gagner lorsque les points sont placés tour à tour (sauf s’il y a un seul point par joueur, car celui qui joue en premier peut alors gagner en plaçant son point au milieu du segment). Mais le premier joueur, le joueur rouge, peut jouer de telle façon que l’écart soit infime.

Dans une variante du jeu de Voronoï, le premier joueur place tout d’abord l’ensemble de ses points, puis le deuxième joueur place ses points. On pourrait penser qu’en raison de la symétrie entre les deux joueurs, il n’est pas possible de trouver une stratégie gagnante, mais cela s’avère bien souvent faux. Les chercheurs ont montré qu’il existe alors un ensemble de positions stratégiques que le premier joueur doit occuper pour être sûr de gagner.

Pour cette variante du jeu, lorsqu’on passe à deux dimensions, il n’existe plus un tel ensemble de positions stratégiques. Au contraire, Otfried Cheong et ses collègues ont conclu que dans une aire de jeu carrée, pour un nombre de points suffisament élevé, c’est le deuxième joueur ou joueur vert qui peut avoir une stratégie gagnante, qui lui garantit d’obtenir plus de la moitié de la surface totale.

Sandor P. Fekete et Henk Meijer ont étudié les questions corollaires suivantes :
À partir de quel nombre de points n le deuxième joueur est-il assuré de gagner ?
Existe-t-il des valeurs de n qui garantissent la victoire à l’un ou l’autre des joueurs ?
De quelle façon la forme de l’aire de jeu a-t-elle une influence sur le résultat ?
Ils ont prouvé que pour des aires de jeu rectangulaires (dont le rapport r entre le petit côté et le grand côté est inférieur à 1), le deuxième joueur peut avoir une stratégie gagnante pour n supérieur ou égal à 3 avec r > √ 2 / n et pour n = 2 avec r > √ 3 / 2. Dans tous les autres cas, c’est le premier joueur qui va gagner : si n = 1, si n = 2 et que r est inférieur ou égal à √ 3 / 2, ou encore si n est supérieur ou égal à 3 avec r inférieur ou égal à √ 2 / n.

La question reste ouverte pour la version originale du jeu, que nous vous proposons ici. Un problème NP-complet ? Des similarités sont observées avec le jeu de Go…

Pour en savoir plus sur ces recherches, nous vous proposons les références de quelques articles scientifiques.