משתמש:Liorgor/ארגז חול
המשחק של גנרל בלוטו, הינו משחק מוכר בתורת המשחקים.
זהו משחק סכום אפס, בו על השחקנים לחלק משאבים מוגבלים על פני מספר טריטוריות (שדות קרב).
רקע[עריכת קוד מקור | עריכה]
משחק מסוג זה, הוצע ע"י בורל כבר בשנת 1921.
המשחק קרוי על שמו של גנרל בלוטו, דמות דמיונית שעלתה מכתביהם של גרוס וואגנר (1950).
הגרסה הקלאסית של המשחק (שהתפתחה בשלב מאוחר יותר), מתארת קרב בין הכוחות הכחולים, בראשם גנרל בלוטו, לבין הכוחות האדומים, שמנהיגם הוא קפטן קיז'ה.
חוקי המשחק והסברים[עריכת קוד מקור | עריכה]
הכוחות נאבקים על כיבוש שטח המורכב מ-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 אסטרטגיות אפשריות.