Jouez avec les diagrammes de Voronoï

Piste bleue Le 9 septembre 2013  - Ecrit par  Chris Poultney, Monty Faidley, Dennis Shasha Voir les commentaires (2)

Cet article a été écrit en partenariat avec Interstices

Cet article a été écrit en partenariat avec L’Institut Henri Poincaré

L’IHP et INRIA ont présenté un stand commun au festival Futur en Seine qui a eu lieu du 13 au 16 juin 2013 à Paris. Cet article — publié initialement ici dans la revue en ligne Interstices — détaille une des animations qui a été présentée sur ce stand. Images des maths remercie Interstices et les auteurs de l’article d’avoir permis cette reprise.

Bienvenue dans le jeu de Voronoï : affrontez l’ordinateur ou jouez entre amis, pour conquérir le plus vaste territoire.

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 !

Animation HTML5/JS réalisée par Corentin Wallez, d’après l’applet Java réalisée par Chris Poultney et Monty Faidley, sur une idée de Dennis Shasha.
Accéder aux sources

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. L’image ci-contre montre un diagramme de Voronoï (en vert) et sa triangulation de Delaunay associée (en bleu).

Pour en savoir plus, vous pouvez consulter cet autre article de la revue Interstices.

...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 \geq 3$ avec $r > \frac{\sqrt 2} n$n et pour $n = 2$ avec $r > \frac{\sqrt 3} 2$. Dans tous les autres cas, c’est le premier joueur qui va gagner.

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 ci-dessous (attention, articles en anglais, nettement plus difficiles).

Références

[1] Ahn H.K., Cheng S.W., Cheong O., Golin M., Oostrum R.V., Competitive Facility Location along a Highway, 9th Annual International Computing and Combinatorics Conference, Vol. 2108, pages 237-246, 2001, téléchargeable en PDF.

[2] Cheong O., Linal N., Har-Peled S., Matousek J., The One-Round Voronoi Game, 18th Annual ACM Symposium on Computational Geometry, pages 97-101, 2002, téléchargeable en PDF.

[3] Fekete S.P., Meijer H., The One-Round Voronoi Game Replayed, Workshop on Algorithms and Data Structures. Springer Lecture Notes in Computer Science, vol.2748, pages 150-161, 2003, téléchargeable en PDF.

Post-scriptum :

Nous remercions Grégoire Dubost pour sa relecture et ses commentaires sur une version préliminaire de cet article.

Article édité par Xavier Caruso

Partager cet article

Pour citer cet article :

Chris Poultney, Monty Faidley, Dennis Shasha — «Jouez avec les diagrammes de Voronoï» — Images des Mathématiques, CNRS, 2013

Commentaire sur l'article

  • Jouez avec les diagrammes de Voronoï ... sur un tore ?

    le 17 septembre 2013 à 01:56, par Arnaud Lionnet

    Raaaah. J’ai commencé à jouer un peu contre l’ordinateur. En mode Poly Majeur (pour l’ordi, mais en fait je faisais essentiellement de même la plupart du temps), car je me disais que c’était probablement la stratégie la plus efficace (peut-être pas en multi-joueurs en fait, je sais pas). J’ai bien essayé de jouer au millimètre près, mais rien à faire, l’ordi gagne tout le temps ---je l’avais mis en 2e joueur ! Il ne gagne pas de beaucoup, en fait il y a moyen de frôler les 15000 (comme décrit dans l’article), mais pas moyen de le feinter.

    Il y avait eu un billet sur Images des Maths fut un temps qui parlait d’une série de jeux, les Torus Games, où l’on pouvait jouer aux échecs ou au billard ... mais sur un tore. Je me demande si ce serait facile de reprogrammer le jeu de Voronoï ci-dessus mais avec pour surface le tore au lieu du carré ?

    Répondre à ce message
  • Jouez avec les diagrammes de Voronoï

    le 26 août à 08:58, par orion8

    Une application inattendue des diagrammes de Voronoï : Les plus gros trous perdus de France (datamix, 25/08/2016)

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM