משחק הנסיכה והמפלצת

משחק נסיכה ומפלצת הוא משחק חתול-ועכבר המשוחק על ידי שני שחקנים בתחום סגור.

 הגדרה פורמלית 
תיאור המשחק מופיע בספר Differential Games של :

השאלה הייתה בעיה פתוחה ידועה, עד שנפתרה על ידי שמואל גל בסוף שנות ה-70.S. Gal, SEARCH GAMES, Academic Press, New York (1980). האסטרטגיה האופטימלית שלו עבור הנסיכה היא לעבור למיקום אקראי בתחום ולהישאר במנוחה לפרק זמן, שאינו קצר מדי ולא ארוך מדי, לפני שהיא עוברת למיקום אקראי אחר, בלתי תלוי, וחוזר חלילה. אסטרטגיית החיפוש האופטימלית המוצעת עבור המפלצת מבוססת על חלוקת החדר למספר רב של מלבנים צרים, בחירת מלבן באקראי וחיפוש בו באופן מסוים. לאחר זמן מה בחירת מלבן אחר באקראי ובאופן בלתי תלוי, וחוזר חלילה.

ניתן לשחק במשחק הנסיכה והמפלצת על גרף שנקבע מראש. ניתן להוכיח כי עבור כל גרף סופי קיימת אסטרטגיית חיפוש מעורב אופטימלית. המשחק הזה נפתר באופן בלתי תלוי על ידי  ו עבור הגרף הפשוט המורכב מלולאה אחת (מעגל). קיים אומדן מקורב לערך המשחק על מרווח היחידה (גרף עם שני צמתים עם קישור ביניהם). המשחק אינו פשוט כפי שניתן שנראה ממבט ראשון. אסטרטגיית החיפוש האינטואיטיבית שבה מתחילים בקצה אקראי ו"מטאטאים" את כל התחום במהירות מרבית מבטיחה תוחלת זמן לכידה של 0.75, אך אינה אופטימלית. על ידי שימוש באסטרטגיית חיפוש מתוחכמת יותר, ניתן להפחית את זמן הלכידה הצפוי בכ-8.6%S. Alpern, R. Fokkink, R. Lindelauf, and G. J. Olsder. Numerical Approaches to the 'Princess and Monster' Game on the Interval. SIAM J. control and optimization 2008.L. Geupel. The 'Princess and Monster' Game on an Interval.

 ראו גם
 תורת המשחקים

 הערות שוליים 

*
קטגוריה:חקר ביצועים