הצגת המקור של הדף "המשחק של גנרל בלוטו"

{{לשכתב|טעויות תרגום רבות, לרבות הקידום הלא מוסבר של קולונל בלוטו|נושא=מדעי הטבע|כל הערך=כן}}
'''המשחק של גנרל בלוטו''' הוא משחק מוכר ב[[תורת המשחקים]]. זהו [[משחק סכום אפס]], בו על השחקנים לחלק משאבים מוגבלים על פני מספר טריטוריות (שדות קרב). 

== רקע ==
משחק מסוג זה, הוצע על ידי [[אמיל בורל|בורל]] כבר בשנת 1921{{הערה|1=[http://www.jstor.org/discover/10.2307/1906946?uid=2134&uid=2&uid=70&uid=4&sid=21102125034471 "Econometrica", כרך 21 גיליון 1, ע' 91 ואילך], באתר [[JSTOR]].}}.

המשחק קרוי על שמו של גנרל בלוטו, דמות דמיונית שעלתה מכתביהם של גרוס וואגנר (1950){{הערה|[http://www.rand.org/content/dam/rand/pubs/research_memoranda/2006/RM408.pdf המאמר המקורי]}}.

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

== חוקי המשחק והסברים ==
הכוחות נאבקים על כיבוש שטח המורכב מ-K שדות קרב שונים.
גנרל בלוטו מפקד על N חיילים, בעוד שקפטן קיז'ה מפקד על M חיילים.

* על כל גנרל להקצות במקביל את חייליו בין K שדות הקרב השונים. כל חייל יכול להיות מוקצה לשדה קרב אחד בלבד. בתום הקצאת החיילים מתקיים קרב בין הצבאות.
* כל שדה קרב נכבש על ידי הצבא שמחזיק במספר חיילים גבוה יותר באותו שדה קרב. התוצאה בשדה קרב i מסומנת בki, ותלויה בכוחות הממוקמים באותו שדה קרב בלבד.
* עבור כיבוש כל שדה קרב, זוכה הצבא הכובש בנקודה, ואילו הצבא המפסיד מאבד נקודה. עבור תוצאת תיקו, אף שחקן אינו מקבל נקודה. לדוגמה: אם שחקן 1 מציב בשדה קרב i שלושה חיילים, ואילו שחקן 2 מציב באותו שדה הקרב חייל אחד, שחקן 1 מנצח ומקבל נקודה אחת. שחקן 2, מפסיד בקרב זה – ומאבד נקודה אחת.
* מנצח במשחק – הצבא שבתום העימות, קיבל את מספר הנקודות (שדות הקרב) הרב יותר.
אם כן, כל שחקן מנסה למקסם את מספר שדות הקרב בהם יזכה, תחת אי הידיעה של חלוקת הקצאת יריבו.

== דוגמה למשחק בלוטו ==
[[קובץ:דוגמא למשחק של גנרל בלוטו.png|ממוזער|דוגמה למשחק של גנרל בלוטו]]
קיימים 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).

נראה את האסטרטגיות האפשריות במטריצה הבאה (ב - ניצחון לבלוטו, ק - ניצחון לקיז'ה, ת - תיקו):

[[קובץ:Matrix Of Balotto's Example.png|600px]]

מכיוון שבדוגמה שלנו לשני השחקנים אותו מספר חיילים, מסימטריה, ערך המשחק הוא 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 שדות קרב אפשריים הוא:

<math>f(n,k)=\binom{n+k-1}{k-1} = \frac{(n+k-1)..(n+2)(n+1)}{(k-1)!}</math>

== ראו גם ==
* [[תורת המשחקים]]
* [[ג'ון פורבס נאש]]

==הערות שוליים==
{{הערות שוליים|יישור=ימין}}

[[קטגוריה:תורת המשחקים]]