Jeu de la princesse et du monstre
En théorie des jeux, un jeu de princesse et de monstres est un jeu de poursuite-évasion joué par deux joueurs dans une région. Le jeu a été conçu par Rufus Isaacs et publié dans son livre Differential Games (1965).
Ce jeu restait un problème ouvert bien connu jusqu’à sa résolution par Shmuel Gal à la fin des années 1970[1] - [2]. Sa stratégie optimale pour la princesse est de se déplacer à un endroit aléatoire de la pièce et de rester immobile pendant un intervalle de temps ni trop court ni trop long, avant de se rendre dans un autre emplacement aléatoire (indépendant) et de répéter la procédure[2] - [3] - [4]. La stratégie de recherche optimale proposée pour le monstre consiste à diviser la pièce en plusieurs rectangles étroits, à sélectionner un rectangle au hasard et à le rechercher de manière spécifique, après un certain temps en choisissant un autre rectangle de manière aléatoire et indépendante, etc.
Les jeux de princesse et de monstre peuvent être joués sur un graphe présélectionné. Il peut être démontré que pour tout graphe fini , il existe une stratégie de recherche mixte optimale qui produit un gain fini. Ce jeu a été résolu par Steve Alpern et de manière indépendante par Mikhail Zelikin uniquement pour le graphique très simple consistant en une seule boucle (un cercle)[5] - [6]. La valeur du jeu sur l'intervalle unitaire (un graphique à deux nœuds avec un lien intermédiaire) a été estimée approximativement.
Le jeu semble simple mais est assez compliqué. La stratégie de recherche évidente consistant à commencer de manière aléatoire et à "balayer" l'ensemble de l'intervalle aussi rapidement que possible garantit une espérance du temps de capture de 0,75 qui n'est pas optimale. En utilisant une stratégie plus sophistiquée de recherche mixte et de masquage, il est possible de réduire l'espérance du temps de capture d'environ 8,6 %. Ce nombre serait assez proche de la valeur du jeu si quelqu'un était capable de prouver l'optimalité de la stratégie correspondante de la princesse[7] - [8].
Notes et références
- S. Gal, SEARCH GAMES, Academic Press, New York (1980).
- Gal Shmuel, « Search games with mobile and immobile hider », SIAM J. Control Optim., vol. 17, no 1,‎ , p. 99–122 (DOI 10.1137/0317009, MR 0516859)
- A. Garnaev, « A Remark on the Princess and Monster Search Game », Int. J. Game Theory, vol. 20, no 3,‎ , p. 269–276 (DOI 10.1007/BF01253781, lire en ligne)
- M. Chrobak, « A princess swimming in the fog looking for a monster cow », ACM SIGACT News, vol. 35, no 2,‎ , p. 74–78 (DOI 10.1145/992287.992304)
- S. Alpern, « The search game with mobile hiders on the circle », Proceedings of the Conference on Differential Games and Control Theory,‎
- M. I. Zelikin, « On a differential game with incomplete information », Soviet Math. Dokl.,‎
- S. Alpern, R. Fokkink, R. Lindelauf, and G. J. Olsder.
- L. Geupel.