משחק בצורה רחבה

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

מרכיבים בתיאור המשחקעריכה

תיאור של משחק כולל את המרכיבים הבאים:

  1. שחקנים המשתתפים במשחק.
  2. המהלכים האפשריים לכל שחקן.
  3. כללים לסדר הפעולות של כל שחקן.
  4. כלל שקובע מתי המשחק יסתיים.
  5. כלל התוצאות האפשריות בסיום המשחק.

תיאור באמצעות עץ משחקעריכה

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

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

בנוסף לעץ המשחק עצמו לתיאור המשחק נחוצים המרכיבים הבאים:

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

דוגמה לעץ משחקעריכה

 
משחק המוצג בצורה גרפית

במשחק המוצג בתמונה יש שני שחקנים 1 ו-2. שחקן 1 פותח, יש לו שני מהלכים אפשריים: а או b. אחריו משחק שחקן 2 לו גם יש שני מהלכים אפשריים. שחקן 2 יודע מה שחקן 1 שיחק, ולכן במקרה ששחקן 1 שיחק a שחקן 2 יכול לשחק c או d. ואם שחקן 1 שיחק b אז שחקן 2 משחק e או f.

לאחר ששחקן 2 משחק מגיעים לאחד העלים לידו רשומה תוצאת המשחק, למשל אם שחקן 1 שיחק а ושחקן 2 שיחק d אז שחקן 1 מקבל 2 ושחקן 2 מקבל 3.

תוצאות אפשריות למשחקעריכה

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

  1. המשחק הסתיים בתיקו.
  2. שחקן 1 שילם 5 ש"ח לשחקן 2.
  3. שחקן 1 הלך לים עם שחקן 2 ושחקן 3 הלך לקולנוע לבד.

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

הגדרה פורמלית למשחק בצורה רחבהעריכה

משחק בצורה רחבה הוא השמינייה  

כאשר:

  • N הוא קבוצת מקבלי ההחלטות - השחקנים.
  •   הוא עץ המשחק.
  •   חלוקה של קודקודי הגרף שאינם עלים.
  •   התפלגות של הקשתות היוצאות מ-x כאשר x שייך ל  
  • O קבוצת כל התוצאות האפשריות.
  • u פונקציה המתאימה לכל עלה תוצאה מ-O.

המשחק שמתואר כאן הוא משחק בעל ידיעה שלמה.

ראו גםעריכה