Prințesa și Bestia (joc)

În teoria jocurilor, Prințesa și Bestia este un  joc de urmărire în care doi jucători joacă într-o anumită zonă. Dezvoltat de Rufus Isaacs și publicat în cartea sa Differential Games (1965) după cum urmează: „Monstrul caută prințesa, timpul petrecut căutând este prețul jocului. Ambele sunt într-o cameră complet întunecată (de orice formă), dar ambele îi cunosc limitele. Găsirea prințesei înseamnă că distanța dintre prințesă și monstru se află în raza de captură, care ar trebui să fie relativ mică în raport cu dimensiunea camerei. Monstrul este suficient de inteligent și se mișcă cu o viteză cunoscută. Prințesei i se permite libertate totală de mișcare .

Acest joc a rămas o problemă deschisă bine-cunoscută până când a fost rezolvat de Gal la sfârșitul anilor 1970 [2] [3] . Strategia lui optimă pentru prințesă este următoarea: prințesa merge într-un punct aleatoriu din cameră și așteaptă în acel moment un anumit interval de timp, nici prea scurt, nici prea lung. Apoi prințesa se mută într-un alt punct (independent) aleatoriu și așa mai departe [3] [4] [5] . Pentru monstru este propusă o strategie de căutare optimă, în care întregul spațiu al camerei este împărțit în multe dreptunghiuri mici . Monstrul selectează un dreptunghi aleatoriu și caută în jur într-un fel, apoi selectează un alt dreptunghi aleatoriu și independent și așa mai departe.

Jocul prințesei și monstrului poate fi jucat pe un grafic preselectat (un posibil grafic simplu este cercul , pe care Isaacs l-a propus ca o piatră de temelie pentru jocurile dintr-o zonă arbitrară). Se poate demonstra că pentru orice grafic finit există o strategie mixtă optimă care duce la un preț constant al jocului. Jocul a fost rezolvat de Steve Alpern și independent de Mikhail Zelikin doar pentru un grafic foarte simplu format dintr-o singură buclă (cerc) [6] [7] . Acest joc pare simplu, dar este de fapt destul de complex. În mod surprinzător, strategia evidentă de a începe de la un capăt aleatoriu și de a unge tăietura cât mai repede posibil nu este optimă. Această strategie garantează 0,75 din timpul de capturare așteptat. Folosind o strategie mixtă mai complexă, puteți reduce timpul cu aproximativ 8,6%. De fapt, acest număr poate fi apropiat de prețul jocului, dacă cineva dovedește că strategia corespunzătoare este optimă pentru prințesă [8] [9] .

Vezi și

• Joc de căutare
• Lista de jocuri de teoria jocurilor
• Teoria căutării garantate

Note

1. ↑ R. Isaacs. Jocuri diferențiale: o teorie matematică cu aplicații la război și urmărire, control și optimizare . - New York: John Wiley & Sons, 1965. - S.  349-350 .
2. ↑ S. Gal. CAUTĂ JOCURI. - New York: Academic Press, 1980.
3. ↑ 1 2 Gal Shmuel. Căutați jocuri cu ascunzător mobil și imobil // SIAM J. Control Optim. - 1979. - T. 17 , nr. 1 . — S. 99–122 . - doi : 10.1137/0317009 .
4. ↑ A. Garnaev. O observație despre jocul de căutare prințese și monștri  // Int. J. Teoria jocurilor. - 1992. - T. 20 , nr. 3 . - S. 269-276 . - doi : 10.1007/BF01253781 .  (link indisponibil)
5. ↑ M. Chrobak. O prințesă care înoată în ceață în căutarea unei vaci monstru // ACM SIGACT News. - 2004. - Vol. 35. - Problema. 2 . - S. 74-78 . - doi : 10.1145/992287.992304 .
6. ↑ S. Alpern. Jocul de căutare cu ascunzători mobile pe cerc // Proceedings of the Conference on Differential Games and Control Theory. — 1973.
7. ↑ Zelikin M.I. Despre un joc diferențial cu informații incomplete // Rapoarte ale Academiei de Științe a URSS. - 1972. - T. 202 , nr. 5 .
8. ↑ S. Alpern, R. Fokkink, R. Lindelauf și G. J. Olsder. Abordări numerice ale jocului „Prințesă și Monstru” pe interval. Arhivat 27 septembrie 2020 la Wayback Machine SIAM J. control and optimization 2008.
9. ↑ L. Geupel. Jocul „Prițesă și Monstru” pe un interval. Arhivat pe 30 noiembrie 2020 la Wayback Machine