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

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

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

מרכיבים בתיאור המשחק[עריכת קוד מקור | עריכה]

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

  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 הלך לקולנוע לבד.

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

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

משחק בצורה רחבה הוא השמינייה  \Gamma = \langle\mathcal{N}, \mathbf{V}, \mathbf{E}, \mathbf{v^0}, [ (\mathbf{V}_i)_{i \in \mathcal{N} \cup \{ 0 \}} ], (\mathbf{p}_x)_{i \in \mathcal{V}_0} , O , u \rangle

כאשר:

  • N הוא קבוצת מקבלי ההחלטות - השחקנים.
  •  \langle\mathbf{V}, \mathbf{E}, \mathbf{v^0} \rangle הוא עץ המשחק.
  •  [ (\mathbf{V}_i)_{i \in \mathcal{N} \cup \{ 0 \}} ] חלוקה של קודקודי הגרף שאינם עלים.
  •  \mathbf{p}_x התפלגות של הקשתות היוצאות מ-x כאשר x שייך ל  \mathbf{V}_0
  • O קבוצת כל התוצאות האפשריות.
  • u פונקציה המתאימה לכל עלה תוצאה מ-O.

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

ראו גם[עריכת קוד מקור | עריכה]