משחק דיפרנציאלי

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

לדוגמה, שני שחקנים שולטים בתנועות של נקודה על מסך מחשב; האחד באמצעות חוגה הקובעת את התנועה למעלה או למטה, והשני באמצעות חוגה הקובעת תנועה ימינה או שמאלה. המסך כולל אזורים שבהם השחקן הראשון צובר נקודות, ואזורים אחרים שבהם השחקן השני צובר נקודות. דוגמה דומה, אך מורכבת יותר: שני טייסים אוחזים בהגאי מטוס, המגיב לתנועות שניהם. בין אם הטייסים תומכים זה בזה ובין אם מטרותיהם שונות, קיימת פונקציית מטרה המאפשרת לתאר את התהליך כמשחק דיפרנציאלי.

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

הגדרת המשחק

הסעיפים הבאים מתארים משחק בין שני שחקנים. נתונה מערכת דינמית, שמתוארת על ידי משוואת המצב הבאה: ${\dot {x}}=f(x,u,v),\ x(t_{0})=x_{0}$

כאשר במערכת הזאת:

• $x$ - וקטור המצב של המערכת, השייך לתחום אפשרי של וקטורי מצב $D\in R^{n}$
• $u$ - וקטור הבקרה שמפעיל שחקן 1, השייך לתחום מותר U. שחקן זה מנסה למזער את אינדקס הביצועים (ראו בהמשך).
• $v$ - וקטור הבקרה שמפעיל שחקן 2, השייך לתחום מותר V. שחקן זה מנסה להגדיל את אינדקס הביצועים (ראו בהמשך).

כדי לתאר את אילוצי המערכת בצורה מתמטית פשוטה משתמשים בפונקציית האילוצים הבאה: $\Phi (x,u,v)=0$

למערכת הזאת מוגדר אינדקס ביצועים באופן הבא: $J=G\{x(t_{f})\}+\int _{t_{0}}^{t_{f}}L_{i}(x,u,v)dt$

כאן $L_{i}$ היא פונקציה של וקטור המצב ווקטורי הבקרה.

למערכת יש משטח סיום בזמן t_f שהניצב אליו הוא n.

אופן הפתרון

ההמילטוניאן

בדומה לבקרה אופטימלית משתמשים בפונקציה הנקראת המילטוניאן, שמשלבת בתוכה את אינדקס הביצועים, את משוואות המערכת באמצעות כופלי לגראנז' ואת אילוצי המערכת. להלן ההמילטוניאן של המשחק המתואר:
$\ H(x,\lambda ,u,v)=L(x,u,v)+\lambda ^{T}f(x,u,v)+\mu ^{T}\Phi (x,u,v).$
ומכאן פותרים באופן דומה לפתרון של המילטוניאן בבקרה אופטימלית, כלומר גוזרים את ההמילטוניאן לפי וקטור המצב ולפי וקטור כופלי הלגראנז'. מקבלים סט של משוואות דיפרנציאליות, המורכב ממשוואות המערכת הדינמית וממשוואות דיפרנציאליות לכופלי הלגראנז' עם תנאי התחלה של וקטור המצב ותנאי סיום על וקטור כופלי הלגראנז' (שלא יתואר כאן).

המשוואות של אייזיקס Main Equations of Isaacs

המשוואה הראשונה עוסקת ביחס שבין ערכי ההמילטוניאן שנקבל כאשר u ישחק באסטרטגיה אופטימלית, שני השחקנים ישחקו כך, או רק v:
$\ H(x,\lambda ,u^{*},v)\leq H(x,\lambda ,u^{*},v^{*})\leq H(x,\lambda ,u,v^{*})$

משוואה זו אומרת, במילים פשוטות, שהערך של ההמילטוניאן אם רק u ישחק באופן אופטימלי יהיה קטן יותר מאשר הערך שיתקבל אם שני הצדדים ישחקו באופן אופטימלי. אם רק v ישחק באופן אופטימלי הערך של ההמילטוניאן יהיה גדול עוד יותר. זה מובן מראש, כיוון שההמילטוניאן תלוי באינדקס הביצועים, ותפקידו של u למזער את אינדקס זה בעוד v מנסה להגדיל את אינדקס הביצועים למקסימום.

המשוואה השנייה קובעת שאם שני השחקנים יפעלו באסטרטגיה אופטימלית אזי:
$\ H(x,\lambda ,u^{*},v^{*})=0$

האסטרטגיות האופטימליות של שני השחקנים הן: $u^{*},v^{*}=arg\{\min _{u\in U}\max _{v\in V}H(x,\lambda ,u,v)\}$

משחק דטרמיניסטי

כאמור, במשחק כזה אחד השחקנים מנסה למזער את אינדקס הביצועים והשני מנסה להגדילו. ניתן להסתכל על זה גם כך: אחד השחקנים מנסה למצוא את המינימום לאורך הטורים של הטבלה הבאה והשני מנסה למצוא את המקסימום לאורך השורות בטבלה.

a11	a12
a21	a22

כלומר, מתקיים: $L_{min}=max(min)\leq min(max)=L_{max}$
אם במשחק יש תור אזי אחד השחקנים קובע את הטור או השורה והשחקן השני בוחר את התא המתאים לו מהבחירה של הראשון. במקרה כזה נגיע לתוצאה ברורה. אם אין תור, עדיין יכול להיות ששני השחקנים יבחרו את אותו פתרון, על פי עקרון שיווי המשקל של נאש. למשחק בו min(max)=max(min) קוראים משחק דטרמיניסטי ותוצאתו שווה לשוויון הזה. זה נכון גם למשחקים דיפרנציאליים. לדוגמה, בטבלה הבאה שני הצדדים יבחרו את התא שערכו 1, כי המינימייזר מנסה להשיג את המקסימום הנמוך ביותר לאורך טור (והוא יבחר את הטור השני שהמקסימום שלו הוא 1) ואילו המקסימייזר ינסה להשיג את המינימום הגבוה ביותר מבין השורות (והוא יבחר את השורה הראשונה שבה הערך המינימלי גבוה יותר):

3	1
2	0

משחק סטוכסטי

כאשר אין פתרון ברור הערך הסופי של המשחק לא ברור, אבל ניתן לחסום אותו בין שני הערכים שתוארו קודם לכן. במשחק כזה לא שווה לשחקנים לשחק באסטרטגיה קבועה, כי הם יכולים להפתיע אחד את השני ולהשיג יותר. לכן, הם ישחקו באופן "סטוכסטי" והתוצאה הממוצעת של המשחק תהיה $L_{min}=max(min)\leq V_{avg}^{*}\leq min(max)=L_{max}$. לדוגמה:

4	0
2	6

במקרה הזה, המינימייזר בוחר את הטור הימני, בו הערך המקסימלי נמוך יותר, כלומר את התא בעל ערך 4. המקסימייזר בוחר את השורה התחתונה כי בה המינימום גבוה יותר, כלומר הוא בוחר בתא בעל הערך 2. פתרון המשחק ינוע בין ערכים אלה, כאשר הערך הממוצע תלוי בהסתברות שבה כל אחד מהשחקנים יבחר להפתיע את יריבו.

פתרון רגיל

מבצעים אינטגרציה לאחור בזמן מהנקודות במשטח הסיום עד לתנאי ההתחלה וכך מייצרים את המסלולים האופטימליים (ההיסטוריה של וקטורי המצב) ושל עוצמת הבקרה המופעלת על ידי כל שחקן. ניתן לבצע זאת כל עוד מסלולי המצב לא חותכים זה את זה. אם כל המסלולים שאינם חותכים זה את זה ממלאים את כל מרחב המצב המותר למשחק הפתרון מסתיים.

פתרון סינגולרי

אם מסלולי הפתרון האופטימלי חותכים זה את זה, לא ניתן להמשיך את הפתרון הרגיל ונקודת החיתוך הופכת לסינגולריות, כלומר הפתרון מגיע למשטח סינגולרי.

שימושים במשחקים דיפרנציאליים

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

• הנהג הדורסן - נהג מנסה לדרוס הולך רגל. לנהג מכונית מהירה יותר אולם הולך הרגל יכול לפנות מהר יותר. רדיוס הפנייה של המכונית ורדיוס הפגיעה נתונים.
• שתי המכוניות - בדומה למשחק הנהג הדורסן, אלא שכאן הולך הרגל מוחלף במכונית בעלת יכולות שונות.
• רדיפה מעבר לקיר - אסיר בורח לאורך קיר והשוטר מנסה לתפוס אותו מצדו השני של הקיר.
• הגבירה באגם - גבירה עירומה שוחה באגם ומעוניינת לצאת ממנו, מבלי שגבר הנמצא לחופיו של האגם יתפוס אותה. הגבר מהיר מהגבירה. קיימת גרסה של הבעיה שבה צורת האגם מעגלית (ראו גם חידת האסיר הבורח).
• האדם והאריה - אדם ואריה לכודים בזירה מעגלית, האריה מעוניין לתפוס את האדם והאדם כמובן רוצה להימלט.
• הנחיה של טילים - אם מגדירים את בעיית הנחיה של טיל כמשחק דיפרנציאלי בין הטיל הרודף, המנסה למזער את מרחק ההחטאה, לבין המטרה, המנסה להגדיל את מרחק ההחטאה, ניתן לקבל חוקי הנחיה המבוססים על טכניקות של פתרון משחקים דיפרנציאליים.

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

מקורות

• Isaacs, R. (1965). "Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization". John Wiley & Sons. New York. OCLC 489835778.{{cite journal}}: תחזוקה - ציטוט: ref duplicates default (link)

קישורים חיצוניים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

33800627משחק דיפרנציאלי