Metraipolis › archive › dc_b8ef349fcaf1
Jeu de la princesse et du monstre — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Jeu_de_la_princesse_et_du_monstre
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-09T07:33:57.167Z
- SHA-256 of the archived text
c1df0a5c7458f5ed990eb7646c6945a2dec34a551b7ee4432839792fa87818c2- Stable URL of this page
https://metraipolis.com/documento/dc_b8ef349fcaf1
How to cite
Jeu de la princesse et du monstre — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Jeu_de_la_princesse_et_du_monstre (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_b8ef349fcaf1 (Metraipolis archive dc_b8ef349fcaf1, sha256 c1df0a5c7458f5ed990eb7646c6945a2dec34a551b7ee4432839792fa87818c2)
BibTeX
@misc{dcb8ef349fcaf1,
title = {Jeu de la princesse et du monstre — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Jeu_de_la_princesse_et_du_monstre},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_b8ef349fcaf1; sha256 c1df0a5c7458f5ed990eb7646c6945a2dec34a551b7ee4432839792fa87818c2},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Jeu_de_la_princesse_et_du_monstre. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico). Fonte: Wikipedia in francese, voce «Jeu de la princesse et du monstre» — https://fr.wikipedia.org/wiki/Jeu_de_la_princesse_et_du_monstre Wikidata Q7244880: «pursuit-evasion game played by two players in a region» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q7244880 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Jeu_de_la_princesse_et_du_monstre?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 230275197, consultata il 2026-11-09T07:27:36.360Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 0f9b77e338d5acea98900b28c9b3d46cd19c37ddf8cca83a32c186c985dadfa2