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. 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. 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). 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.