המשחק של גנרל בלוטו
| יש לשכתב ערך זה. הסיבה היא: טעויות תרגום רבות, לרבות הקידום הלא מוסבר של קולונל בלוטו. | |
המשחק של גנרל בלוטו הוא משחק מוכר בתורת המשחקים. זהו משחק סכום אפס, בו על השחקנים לחלק משאבים מוגבלים על פני מספר טריטוריות (שדות קרב).
רקע עריכה
משחק מסוג זה, הוצע על ידי בורל כבר בשנת 1921[1].
המשחק קרוי על שמו של גנרל בלוטו, דמות דמיונית שעלתה מכתביהם של גרוס וואגנר (1950)[2].
הגרסה הקלאסית של המשחק (שהתפתחה בשלב מאוחר יותר), מתארת קרב בין הכוחות הכחולים, בראשם גנרל בלוטו, לבין הכוחות האדומים, שמנהיגם הוא קפטן קיז'ה.
חוקי המשחק והסברים עריכה
הכוחות נאבקים על כיבוש שטח המורכב מ-K שדות קרב שונים. גנרל בלוטו מפקד על N חיילים, בעוד שקפטן קיז'ה מפקד על M חיילים.
אם המשחק סימטרי (כאשר N=M), ערך המשחק הוא אפס.
- על כל גנרל להקצות במקביל את חייליו בין K שדות הקרב השונים. כל חייל יכול להיות מוקצה לשדה קרב אחד בלבד. בתום הקצאת החיילים מתקיים קרב בין הצבאות.
- כל שדה קרב נכבש על ידי הצבא שמחזיק במספר חיילים גבוה יותר באותו שדה קרב. התוצאה בשדה קרב i מסומנת בki, ותלויה בכוחות הממוקמים באותו שדה קרב בלבד.
- עבור כיבוש כל שדה קרב, זוכה הצבא הכובש בנקודה, ואילו הצבא המפסיד מאבד נקודה. עבור תוצאת תיקו, אף שחקן אינו מקבל נקודה. לדוגמה: אם שחקן 1 מציב בשדה קרב i שלושה חיילים, ואילו שחקן 2 מציב באותו שדה הקרב חייל אחד, שחקן 1 מנצח ומקבל נקודה אחת. שחקן 2, מפסיד בקרב זה – ומאבד נקודה אחת.
- מנצח במשחק – הצבא שבתום העימות, קיבל את מספר הנקודות (שדות הקרב) הרב יותר.
אם כן, כל שחקן מנסה למקסם את מספר שדות הקרב בהם יזכה, תחת אי הידיעה של חלוקת הקצאת יריבו.
דוגמה למשחק בלוטו עריכה
קיימים 3 שדות קרב (K=3). ברשותו של גנרל בלוטו 4 חיילים (N=4) ולקפטן קיז'ה 4 חיילים (M=4).
נבחן את ההקצאה הבאה:
הכוחות הכחולים של בלוטו: (4,0,0)
הכוחות האדומים של קיז'ה: (2,1,1)
ניתן לראות שהחלוקה הנ"ל מביאה לניצחון 1:2 לטובת הצבא האדום.
פתרונות אפשריים למשחק עריכה
נבחן מהם הפתרונות האפשריים למשחק, עבור הדוגמה הנ"ל. אם כל אחד מן המפקדים משחק בצורה אסטרטגית, כיצד עליהם לחלק את חייליהם?
ניתן לראות שלכל שחקן יש חמש עשרה אסטרטגיות אפשריות:
(4,0,0),(2,2,0),(3,1,0),(2,1,1),(0,4,0),(0,0,4),(2,0,2),(0,2,2),(3,0,1),(1,0,3),(1,0,3),(1,3,0),(0,1,3),(0,3,1),(1,2,1),(1,1,2).
כל האסטרטגיות הן למעשה פרמוטציות של ארבע האסטרטגיות הימניות ביותר: (4,0,0),(2,2,0),(3,1,0),(2,1,1).
נראה את האסטרטגיות האפשריות במטריצה הבאה (ב - ניצחון לבלוטו, ק - ניצחון לקיז'ה, ת - תיקו):
מכיוון שבדוגמה שלנו לשני השחקנים אותו מספר חיילים, מסימטריה, ערך המשחק הוא 0. התבוננות במטריצה לעיל, מראה שאין אסטרטגיה טהורה המבטיחה תשלום 0 (כלומר, ניצחון או תיקו) ולכן בדוגמה זו אין אסטרטגיה אופטימלית טהורה. עובדה זו אינה מפתיעה, שכן - לעיתים קרובות, לא קיים שיווי משקל נאש באסטרטגיות טהורות. לרוב, כמו בדוגמה לעיל, עבור מספר גדול של שדות קרב ומספר חיילים גבוה, לכל אסטרטגיה טהורה ניתן למצוא אסטרטגיה טהורה אחרת שמנצחת אותה. במקרים כאלו, האסטרטגיה האופטימלית נתונה באסטרטגיות מעורבות ולא באסטרטגיות טהורות.
בדוגמה זו, שיווי משקל באסטרטגיות מעורבות מתקבל אם נבחר בהסתברות 1/9 בכל אחת מן האסטרטגיות הבאות: (2,2,0),(2,0,2),(0,2,2),(3,1,0),(3,0,1), (1,0,3),(1,3,0),(0,1,3),(0,3,1).
בנוסף, אפילו אם קיים שיווי משקל באסטרטגיות טהורות, ככל שמספר החיילים גדול יותר, כך יהיה קשה יותר לחשב אותו, וזאת בשל מספר האסטרטגיות האפשריות הרבות העומדות בפני כל שחקן. עבור K=3, כאשר N=M=8, לכל שחקן 45 אסטרטגיות אפשריות. כאשר N=M=13, קיימות 105 אפשרויות ועבור N=M=20 קיימות 231 אסטרטגיות אפשריות.
מספר האסטרטגיות עבור כל שחקן עם n חיילים ו-k שדות קרב אפשריים הוא:
