משחק הנסיכה והמפלצת
משחק נסיכה ומפלצת הוא משחק חתול-ועכבר המשוחק על ידי שני שחקנים בתחום סגור.
הגדרה פורמלית
תיאור המשחק מופיע בספר Differential Games של רופוס אייזקס (מתמטיקאי) (אנ'):
מפלצת אינטליגנטית מנסה ללכוד נסיכה בחדר חשוך לחלוטין, שצורתו אינה מוגבלת אך ידועה לנסיכה ולמפלצת. המפלצת מודעת לגבול הלכידה שלה, מרחק קטן יחסית לגודל החדר, שבו תוכל לתפוס את הנסיכה. המפלצת נעה במהירות קבועה, בעוד לנסיכה חופש תנועה מלא. המטרה: למצוא את הזמן הדרוש למפלצת ללכוד את הנסיכה.[1]
השאלה הייתה בעיה פתוחה ידועה, עד שנפתרה על ידי שמואל גל בסוף שנות ה-70.[2][3] האסטרטגיה האופטימלית שלו עבור הנסיכה היא לעבור למיקום אקראי בתחום ולהישאר במנוחה לפרק זמן, שאינו קצר מדי ולא ארוך מדי, לפני שהיא עוברת למיקום אקראי אחר, בלתי תלוי, וחוזר חלילה.[3][4][5] אסטרטגיית החיפוש האופטימלית המוצעת עבור המפלצת מבוססת על חלוקת החדר למספר רב של מלבנים צרים, בחירת מלבן באקראי וחיפוש בו באופן מסוים. לאחר זמן מה בחירת מלבן אחר באקראי ובאופן בלתי תלוי, וחוזר חלילה.
ניתן לשחק במשחק הנסיכה והמפלצת על גרף שנקבע מראש. ניתן להוכיח כי עבור כל גרף סופי קיימת אסטרטגיית חיפוש מעורב אופטימלית. המשחק הזה נפתר באופן בלתי תלוי על ידי סטיב אלפרן (אנ') ומיכאיל זליקין (אנ') עבור הגרף הפשוט המורכב מלולאה אחת (מעגל).[6][7] קיים אומדן מקורב לערך המשחק על מרווח היחידה (גרף עם שני צמתים עם קישור ביניהם). המשחק אינו פשוט כפי שניתן שנראה ממבט ראשון. אסטרטגיית החיפוש האינטואיטיבית שבה מתחילים בקצה אקראי ו"מטאטאים" את כל התחום במהירות מרבית מבטיחה תוחלת זמן לכידה של 0.75, אך אינה אופטימלית. על ידי שימוש באסטרטגיית חיפוש מתוחכמת יותר, ניתן להפחית את זמן הלכידה הצפוי בכ-8.6%[8][9]
ראו גם
הערות שוליים
- ^ R. Isaacs, Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization, John Wiley & Sons, New York (1965), PP 349-350.
- ^ S. Gal, SEARCH GAMES, Academic Press, New York (1980).
- ^ 3.0 3.1 Gal Shmuel (1979). "Search games with mobile and immobile hider". SIAM J. Control Optim. 17 (1): 99–122. doi:10.1137/0317009.
- ^ A. Garnaev (1992). "A Remark on the Princess and Monster Search Game" (PDF). Int. J. Game Theory. 20 (3): 269–276. doi:10.1007/BF01253781.(הקישור אינו פעיל, April 2018)
- ^ M. Chrobak (2004). "A princess swimming in the fog looking for a monster cow". ACM SIGACT News. 35 (2): 74–78. doi:10.1145/992287.992304.
- ^ S. Alpern (1973). "The search game with mobile hiders on the circle". Proceedings of the Conference on Differential Games and Control Theory.
- ^ M. I. Zelikin (1972). "On a differential game with incomplete information". Soviet Math. Dokl.
- ^ 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.
38803818משחק הנסיכה והמפלצת