משחק צ'ומפ
משחק צ'ומפ הוא משחק סופי לשני שחקנים, בעל ידיעה שלמה וללא מהלכי גורל המסתיים תמיד בניצחון של אחד השחקנים (כלומר קבוצת התוצאות האפשריות כוללת ניצחון לשחקן 1 או ניצחון לשחקן 2). המשחק נוסח על ידי המתמטיקאי האמריקאי דייוויד גייל.
המשחק משויך לקבוצת משחקים המכונים משחק סדר (Poset Games), כאשר ה"קבוצה הסדורה" שעליה הוא מתנהל היא סריג (מטריצה דו-ממדית).
חוקי המשחק
- המשחק משוחק על לוח מטריציוני בגודל M*N (הממדים M ו-N הם המגדירים את המשחק בצורה חח"ע), כאשר בתחילת המשחק הלוח מלא (מכיל את כל M*N המשבצות).
- כל שחקן נקרא בתורו, לבחור משבצת שעדיין לא נמחקה מהלוח ולמחוק אותה.
- בנוסף למשבצת שבחר, מוחק השחקן גם את כל המשבצות שעדיין לא נמחקו מהלוח ושהקואורדינטות שלהן גדולות או שוות (כל אחת בהתאמה) מהקואורדינטות של המשבצת שבחר (כלומר כל משבצת שנמצאת מעל ומימין למשבצת שנבחרה).
- בצורה זו מצטמצם הלוח מתור לתור, עד אשר אחד השחקנים בוחר במשבצת השמאלית התחתונה (1,1). השחקן שבחר במשבצת זו מוגדר להיות "המפסיד" במשחק.
דוגמה למהלך משחק
להלן דוגמה של מהלך משחק עבור לוח 5*3 כאשר משבצת ההפסד (1,1) מסומנת באדום:
| מצב התחלתי | שחקן 1 | שחקן 2 | שחקן 1 | שחקן 2 | ||||
|---|---|---|---|---|---|---|---|---|
 |
 |
|
| |||||
|
|
|
| |||||
 |
|
|
|
|
הסבר:
- שחקן 1 בוחר במהלך הפתיחה במשבצת (2,5) ולכן מוחק את המשבצות (2,5) ו-(3,5) (נשים לב, כי כיוון האינדוקס הוא בהתאם לכיוונים החיוביים במערכת צירים קרטזית, אולם הכתיב הוא בצורה מטריציונית, כלומר קודם שורות ואז עמודות).
- בתגובה, שחקן 2 בוחר במשבצת (1,4) ומוחק את המשבצות המתאימות מהלוח שנותר.
- לאחר מכן שחקן 1 בוחר במשבצת (2,1) ושחקן 2 בוחר במשבצת (1,2).
במצב זה ניצחונו של שחקן 2 מובטח כי בתור הבא יאלץ שחקן 1 לבחור במשבצת ההפסד (1,1).
הכללה של המשחק לממדים גבוהים
ניתן להגדיר גרסה מורחבת של משחק צ'ומפ, המכלילה את חוקי המשחק עבור ממדים גבוהים יותר (כלומר משחקים בהם מטריצת המשבצות היא מממד גדול מ-2).
לדוגמה, במשחק התלת-ממדי (המשוחק על לוח תלת-ממדי), מהלך הוא בחירה במשבצת (I,j,k), שתגרור מחיקה של כל המשבצות שהקואורדינטות שלהן גדולות או שוות ל-I,k,j (בהתאמה). המפסיד במשחק זה יהיה השחקן אשר יבחר במשבצת (1,1,1).
בצורה כזו, ניתן להגדיר לוחות ומשחקים בכל מימד שנרצה.
קיומה של אסטרטגיה מנצחת
מעיון באפיון המשחק, ניתן לראות כי המשחק מקיים את תנאי משפט פון נוימן (Von Neumann, 1928, המכונה לעיתים גם משפט צרמלו), בהיותו משחק שני שחקנים, סופי, בעל ידיעה שלמה המסתיים תמיד בניצחון של אחד השחקנים.
לפיכך, בכל משחק צ'ומפ לאחד משני השחקנים קיימת אסטרטגיה מנצחת, שאם ינהג לפיה יזכה בניצחון עבור כל תגובה אפשרית של השחקן היריב.
זהות השחקן המנצח
מתברר, שבכל משחק צ'ומפ סופי (הנקבע על-פי ערכי N ו-M) השחקן המסוגל להבטיח לעצמו ניצחון הוא שחקן 1. ההוכחה לכך היא על דרך השלילה כדלקמן: נניח בשלילה כי קיים לוח משחק סופי (M*N) עבורו לשחקן 2 יש אסטרטגיה מנצחת המבטיחה לו ניצחון לכל אסטרטגיה של שחקן 1 (על-פי המשפט לאחד השחקנים חייבת להיות אסטרטגיה כזו, והנחת השלילה היא שלא מדובר בשחקן 1). בפרט, עבור בחירה של שחקן 1 במשבצת (M,N) כמהלך הפתיחה שלו, קיים מהלך תגובה כלשהו (x,y) של שחקן 2, שאחריו הוא יכול לכפות ניצחון לכל אסטרטגיה של שחקן 1.
אולם אם היה שחקן 1 פותח במהלך (x,y), היה מגיע לאותו הלוח בדיוק (שכן כל מהלך ובפרט (x,y) מוחק ממילא את המשבצת (M,N), ולכן מחיקתה בהתחלה לא משנה), ומכאן יכול היה לכפות ניצחון, בסתירה להנחת השלילה.
לצורך המחשה, נניח שבלוח 6*3 (M=3, N=6) לשחקן 2 יש אסטרטגיה מנצחת. אז עבור בחירה של שחקן 1 במשבצת (3,6), נניח כי התגובה המובילה ללוח זכוי עבור שחקן 2 היא בחירה במשבצת (2,4) בצורה הבאה:
| מצב התחלתי | פתיחה של שחקן 1 | תגובה של שחקן 2 | לוח זכוי לשחקן 2 | |||
|---|---|---|---|---|---|---|
|
|
|
| |||
|
|
|
| |||
|
|
|
|
אם היה שחקן 1 בוחר במשבצת (2,4), היה זוכה באותו "לוח משחק זכוי" שהיה קודם לכן לשחקן 2 בסיום תורו:
| מצב התחלתי | פתיחה של שחקן 1 | לוח זכוי לשחקן 1 | ||
|---|---|---|---|---|
|
|
| ||
|
|
| ||
|
|
|
מכאן, יוכל שחקן 1 להמשיך כפי ששחקן 2 היה ממשיך קודם לכן ולהבטיח לעצמו ניצחון, וזאת כמובן בסתירה להנחה כי לשחקן 2 "אסטרטגיה מנצחת" הכופה ניצחון עבורו.
הוכחה זו תקפה גם להכללות של המשחק לכל מספר סופי של ממדים.
מציאת אסטרטגיה מנצחת
כיום, עדיין לא ידועה אסטרטגיית ניצחון עבור M ו-N כלליים, ולמרות שניתן לחשב פתרון עבור כל לוח נתון בעזרת מחשב, הדבר יהיה קשה מבחינה חישובית עבור N ו-M גדולים. יחד עם זאת קיימים מספר לוחות שבהם ניתן להגדיר אסטרטגית ניצחון בצורה מפורשת.
לוח N*N
עבור לוח סימטרי מגודל N*N נסתכל על האסטרטגיה הבאה ונוכיח שהיא אסטרטגיית ניצחון- השחקן הראשון בוחר במהלך הפתיחה במשבצת (2,2) ויוצר את לוח המשחק הבא (לצורך המחשה נסתכל על לוח 4*4):
| לוח התחלתי 4*4 | פתיחה שחקן 1 | לוח L מגודל 4 | ||
|---|---|---|---|---|
|
|
| ||
|
|
| ||
|
|
| ||
|
|
|
נשים לב כי הלוח שנוצר לאחר הפעולה, הוא לוח סימטרי שבו ישנן משבצות בשורה הראשונה והעמודה הראשונה בלבד ומספרן זהה. נכנה לוח כזה בכינוי לוח "L". בשלב הבא, בהינתן ששחקן 2 מקבל בתורו לוח "L" סימטרי, שחקן 1 יגיב על כל בחירה של שחקן 2 בבחירה במשבצת הסימטרית לה, כלומר על בחירה במשבצת מהסוג (1,i) שחקן 1 יבחר במשבצת (i,1) ולהפך. בצורה כזו שחקן 2 יקבל בתור הבא שלו לוח "L" סימטרי נוסף שבו i-1 משבצות בשורה הראשונה ו-i-1 משבצות בעמודה הראשונה.
לפיכך, על-מנת להוכיח שאסטרטגיה זו מביאה לניצחון עלינו להוכיח שלוח "L" בסיסי (בגודל מינימלי) גורר הפסד של שחקן 2 ואז באינדוקציה, נקבל שהאסטרטגיה המתוארת מהווה אסטרטגיית ניצחון לשחקן 1. נשים לב, שמקרה הבסיס טריוויאלי, שכן "לוח L" בגודל 1, הוא לוח המכיל את המשבצת (1,1) בלבד. לוח זה מבטיח כמובן, הפסד של שחקן 2 המחויב לבחור במשבצת זו.
לוח 2*N
גם עבור לוח זה (-המורכב בה"כ משתי שורות ו-N עמודות) נתאר אסטרטגיית ניצחון עבור שחקן 1 בדרך אינדוקטיבית.
בהינתן N קבוע, המהלך הראשון של שחקן 1 יהיה בחירה במשבצת הימנית העליונה, כך שיתקבל הלוח הבא (לצורך המחשה נסתכל על לוח 5*2, בו N=5):
| לוח התחלתי 5*2 | פתיחה שחקן 1 | לוח Z מגודל 5 | ||
|---|---|---|---|---|
|
|
| ||
|
|
|
מטעמי נוחות נכנה לוח זה, שבו N-1 משבצות בשורה העליונה ו-N משבצות בשורה התחתונה בשם "לוח Z מגודל N" (בדוגמה שלעיל קיבלנו לוח Z מגודל 5).
הטענה האינדוקטיבית שלנו היא שבהינתן ששחקן 2 מקבל "לוח Z מגודל N" לכל תגובה שלו מתקיים:
- שחקן 1 לא יקבל לוח Z.
- שחקן 1 יוכל לכפות על שחקן 2 בתור הבא שלו, לוח Z מגודל K כאשר K<N .
הוכחה:
- בחירה של שחקן 2 במשבצת מהשורה העליונה תותיר הפרש גדול מ-1 בין כמות המשבצות של כל אחת מהשורות, בחירה במשבצת מהשורה התחתונה לעומת זאת, תותיר מספר זהה של משבצות בכל אחת מהשורות. בכל אחד מהמקרים לא מדובר בלוח Z.
- האפשרויות הקיימות הן:
- עבור בחירה של שחקן 2 במשבצת i מהשורה העליונה שחקן 1 יבחר במשבצת i+1 מהשורה התחתונה.
- עבור בחירה של שחקן 2 במשבצת i מהשורה התחתונה יבחר שחקן 1 במשבצת i-1 מהשורה העליונה.
- בשני המקרים הללו שחקן 2 יקבל בתור הבא שלו לוח Z מגודל i<N.
כעת משהוכחנו ששחקן 1 יכול להבטיח, על ידי שימוש באסטרטגיה הנ"ל, ששחקן 2 (ורק שחקן 2) יקבל תמיד בתורו לוח Z מגודל הולך וקטן, כל שנשאר להוכיח על-מנת להבטיח שזוהי אכן אסטרטגיית ניצחון עבור שחקן 1, הוא שבמקרה הבסיסי (הגודל המינימלי) "לוח Z" גורר הפסד של שחקן 2. אולם, נשים לב כי לוח Z מגודל 1 הוא למעשה הלוח בעל המשבצת הבודדת (1,1) הגורר בהכרח הפסד של שחקן 2, הנאלץ לבחור במשבצת זו.
לוחות אינסופיים
ניתן להרחיב את הגדרת המשחק גם עבור לוחות אינסופיים בני מנייה (שבהם לפחות אחד מממדי המטריצה הוא אינסופי). יש לציין כי במקרה כזה המשחק אינו מקיים את תנאי משפט פון נוימן ולפיכך המסקנות שלנו אודות קיום אסטרטגיה מנצחת בכלל, ולשחקן הפותח בפרט, אינן תקפות בהכרח. יחד עם זאת, נראה כי ניתן להוכיח מפורשות (בדרך קונסטרוקטיבית) את קיומה של אסטרטגיית ניצחון גם בלוחות אלו:
לוח 2*אינסוף
לוח 2*אינסוף הוא לוח המכיל 2 שורות ואינסוף עמודות (או באופן סימטרי 2 עמודות ואינסוף שורות).
לוח זה, הוא הלוח היחידי בו קיימת אסטרטגיה מנצחת לשחקן 2, הגורסת כי:
- עבור בחירה של שחקן 1 במשבצת ה-k של השורה העליונה, שחקן 2 יגיב בבחירת המשבצת ה-k+1 של השורה התחתונה. בכך הוא ישאיר את שחקן 1 עם לוח Z מגודל k+1 הגורר כאמור הפסד (ראה לוח 2*N).
- עבור פתיחה של שחקן 1 שבה הוא בוחר במשבצת ה-k של השורה התחתונה, שחקן 2 ישיב בבחירת המשבצת ה-k-1 של השורה העליונה. בכך הוא ייצור שוב לוח Z ויזכה בניצחון.
לוח K*אינסוף
לוח זה מורכב מ-K שורות (בה"כ) ואינסוף עמודות. בלוח זה קיימת אסטרטגיה מנצחת לשחקן ה-1, שגורסת כי עליו לפתוח במהלך (3,1). לאחר מהלך זה קיבלנו חזרה לוח 2*אינסוף שבו שחקן 1 במשחק המקורי הוא כעת "שחקן 2". על-כן הוא יכול להמשיך לשחק באסטרטגיה המתוארת לעיל ולהבטיח את ניצחונו.
לוח אינסוף*אינסוף
לוח זה מתאר מצב פתיחה שבו שני הממדים אינסופיים. בלוח זה שחקן 1 יכול להבטיח את ניצחונו בשתי אסטרטגיות ניצחון שונות (לפחות):
- לבחור במהלך הפתיחה במשבצת (3,1) ולהמשיך כ"שחקן 2" בלוח 2*אינסוף.
- לבחור משבצת (2,2) במהלך הראשון, ועבור בחירה של שחקן 2 במשבצת מסוג (1,i) בחירה במשבצת (1,i) (ולהפך). במצב הזה, שחקן 1 הביא את שחקן 2 למשחק "בלוח ר" סימטרי מגודל i, שממנו כאמור הוא יכול לכפות ניצחון (ראה לוח N*N).
ראו גם
לקריאה נוספת
- שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, מסת"ב 9654932946
קישורים חיצוניים
