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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

הראשון להציג ולחקור את המשחקים הדיפרנציאלים היה רופוס איזאקס בספרו הקלאסי בנושא שהתפרסם ב-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_f}_{t_0}L_i(x,u,v)dt

כאן L_i היא פונקציה של וקטור המצב ווקטורי הבקרה.

למערכת יש משטח סיום בזמן tf שהניצב אליו הוא 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". New York: John Wiley & Sons. OCLC 489835778.