Peliteoriassa The Princess and the Beast on takaa - ajopeli , jossa kaksi pelaajaa pelaa jollain alueella. Rufus Isaacsin kehittämä ja julkaistu kirjassaan Differential Games (1965) seuraavasti: "Hirviö etsii prinsessaa, etsimiseen käytetty aika on pelin hinta. Molemmat ovat täysin pimeässä huoneessa (mikä tahansa muoto), mutta molemmat tietävät sen rajat. Prinsessan löytäminen tarkoittaa, että prinsessan ja hirviön välinen etäisyys on sieppaussäteen sisällä, jonka pitäisi olla suhteellisen pieni huoneen kokoon nähden. Hirviö on tarpeeksi älykäs ja liikkuu tunnetulla nopeudella. Prinsessalle annetaan täydellinen liikkumisvapaus .
Tämä peli pysyi hyvin tunnettuna avoimena ongelmana, kunnes Gal ratkaisi sen 1970-luvun lopulla [2] [3] . Hänen optimaalinen strategiansa prinsessalle on seuraava: prinsessa menee satunnaiseen kohtaan huoneessa ja odottaa siinä tietyn ajan, ei liian lyhyen eikä liian kauan. Sitten prinsessa siirtyy toiseen (riippumattomaan) satunnaiseen pisteeseen ja niin edelleen [3] [4] [5] . Hirviölle ehdotetaan optimaalista hakustrategiaa, jossa koko huoneen tila on jaettu moniin pieniin suorakulmioihin . Hirviö valitsee suorakulmion satunnaisesti ja etsii ympäriinsä jollain tavalla, sitten valitsee toisen suorakulmion satunnaisesti ja itsenäisesti ja niin edelleen.
Prinsessa-hirviöpeliä voidaan pelata ennalta valitulla kaaviolla (mahdollinen yksinkertainen kaavio on ympyrä , jota Isaacs ehdotti ponnahduslautaksi mielivaltaisella alueella pelattaviin peleihin). Voidaan osoittaa, että mille tahansa äärelliselle kaaviolle on olemassa optimaalinen sekoitettu strategia , joka johtaa tasaiseen pelihintaan. Pelin ratkaisi Steve Alpern ja itsenäisesti Mikhail Zelikin vain hyvin yksinkertaiselle kaaviolle, joka koostuu yhdestä silmukasta (ympyrästä) [6] [7] . Tämä peli näyttää yksinkertaiselta, mutta on itse asiassa melko monimutkainen. Yllättäen ilmeinen strategia aloittaa yhdestä satunnaisesta päästä ja harsittaa leikkaus mahdollisimman nopeasti ei ole optimaalinen. Tämä strategia takaa 0,75 odotetun sieppausajan. Käyttämällä monimutkaisempaa sekastrategiaa voit lyhentää aikaa noin 8,6 %. Itse asiassa tämä luku voi olla lähellä pelin hintaa, jos joku osoittaa, että vastaava strategia on prinsessalle optimaalinen [8] [9] .