משתמש:GalOren/משחק צ'ומפ

משחק צ'ומפ, אשר נוסח ע"י המתמטיאי האמריקאי דיוויד גייל (Gale ,1974), הינו משחק שני שחקנים, סופי, בעל ידיעה שלמה וללא מהלכי גורל המסתיים תמיד בניצחון של אחד השחקנים (כלומר קבוצת התוצאות האפשריות כוללת ניצחון לשחקן 1 או ניצחון לשחקן 2).
המשחק משויך לקבוצת משחקים המכונים משחקי "יחס סדר" (Poset Games), כאשר ה"קבוצה הסדורה" שעליה הוא מתנהל הינה סריג (מטריצה דו-מימדית).

חוקי המשחק

1. המשחק משוחק על לוח מטריציוני בגודל M*N (-המימדים Mו-N הם המגדירים את המשחק בצורה חח"ע), כאשר בתחילת המשחק הלוח מלא (מכיל את כל M*N המשבצות).

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

3. בנוסף למשבצת שבחר, מוחק השחקן גם את כל המשבצות שעדיין לא נמחקו מהלוח ושהקורדינאטות שלהן גדולות או שוות (כל אחת בהתאמה) מהקואורדינאטות של המשבצת שבחר (כלומר כל משבצת שנמצאת מעל ומימין למשבצת שנבחרה).

4. בצורה זו מצטמצם הלוח מתור לתור, עד אשר אחד השחקנים בוחר במשבצת השמאלית התחתונה (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.
לצורך המחשה, נניח שבלוח 6*3 (M=3, N=6) לשחקן 2 יש אסטרטגיה מנצחת.
אזי עבור בחירה של שחקן 1 במשבצת (3,6), נניח כי התגובה המובילה ללוח זכוי עבור שחקן 2 הינה בחירה במשבצת (2,4) בצורה הבא:

מצב התחלתי		פתיחה של שחקן 1		תגובה של שחקן 2		לוח זכוי לשחקן 2

אולם, אם שחקן 1 יבחר לפתוח במהלך התגובה (x,y), שכאמור בדוגמא שלנו הוא בחירה במשבצת (2,4), אזי הוא יזכה באותו "לוח משחק זכוי" שהיה קודם לכן לשחקן 2 בסיום תורו:

מצב התחלתי		פתיחה של שחקן 1		לוח זכוי לשחקן 1

מכאן, יוכל שחקן 1 להמשיך כפי ששחקן 2 היה ממשיך קודם לכן ולהבטיח לעצמו ניצחון, וזאת כמובן בסתירה להנחה כי לשחקן 2 "אסטרטגיה מנצחת" הכופה ניצחון עבורו.

מציאת אסטרטגיה מנצחת

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

לוח N*N

עבור לוח סימטרי מגודל N*N נסתכל על האסטרטגיה הבאה ונוכיח שהיא אסטרטגיית ניצחון- השחקן הראשון בוחר במהלך הפתיחה במשבצת (2,2) ויוצר את לוח המשחק הבא (לצורך המחשה נסתכל על לוח 4*4):

לוח התחלתי 4*4		פתיחה שחקן 1		לוח ר' מגודל 4

נשים לב כי הלוח שנוצר לאחר הפעולה, הינו לוח סימטרי שבו ישנן משבצות בשורה הראשונה והעמודה הראשונה בלבד ומספרן זהה. נכנה לוח כזה בכינוי לוח "ר".
בשלב הבא, בהינתן ששחקן 2 מקבל בתורו לוח "ר" סימטרי, שחקן 1 יגיב על כל בחירה של שחקן 2 בבחירה במשבצת הסימטרית לה, כלומר על בחירה במשבצת מהסוג (1,i) שחקן 1 יבחר במשבצת (i,1) ולהיפך.
בצורה כזו שחקן 2 יקבל בתור הבא שלו לוח "ר" סימטרי נוסף שבו i-1 משבצות בשורה הראשונה ו-i-1 משבצות בעמודה הראשונה.
לפיכך, על-מנת להוכיח שאסטרטגיה זו מביאה לניצחון עלינו להוכיח שלוח "ר" בסיסי (בגודל מינימאלי) גורר הפסד של שחקן 2 ואז באינדוקציה, נקבל שהאסטרטגיה המתוארת מהווה אסטרטגיית ניצחון לשחקן 1.
נשים לב, שמקרה הבסיס טריוויאלי, שכן "לוח ר" בגודל 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. שחקן 1 לא יקבל לוח Z.

2. שחקן 1 יוכל לכפות על שחקן 2 בתור הבא שלו, לוח Z מגודל K כאשר K<N .

הוכחה:

1. בחירה של שחקן 2 במשבצת מהשורה העליונה תותיר הפרש גדול מ-1 בין כמות המשבצות של כל אחת מהשורות, בחירה במשבצת מהשורה התחתונה לעומת זאת, תותיר מספר זהה של משבצות בכל אחת מהשורות. בכל אחד מהמקרים לא מדובר בלוח Z.

2. עבור בחירה של שחקן 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. עבור בחירה של שחקן 1 במשבצת ה-k של השורה העליונה, שחקן 2 יגיב בבחירת המשבצת ה-k+1 של השורה התחתונה.
בכך הוא ישאיר את שחקן 1 עם לוח Z מגודל k+1 הגורר כאמור הפסד (ראה לוח 2*N).

2. עבור פתיחה של של שחקן 1 שבה הוא בוחר במשבצת ה-k של השורה התחתונה, שחקן 2 ישיב בבחירת המשבצת ה-k-1 של השורה העליונה.
בכך הוא ייצור שוב לוח Z ויזכה בניצחון.

לוח K*אינסוף

לוח זה, כשמו כן הוא, מורכב מ-K שורות (בה"כ) ואינסוף עמודות. בלוח זה קיימת אסטרטגיה מנצחת לשחקן ה-1, שגורסת כי עליו לפתוח במהלך (3,1).
לאחר מהלך זה קיבלנו חזרה לוח 2*אינסוף שבו שחקן 1 במשחק המקורי הוא כעת "שחקן 2".
על-כן הוא יכול להמשיך לשחק באסטרטגיה המתוארת לעיל ולהבטיח את ניצחונו.

לוח אינסוף*אינסוף

לוח זה מתאר מצב פתיחה שבו שני המימדים אינסופיים. בלוח זה שחקן 1 יכול להבטיח את ניצחונו בשתי אסטרטגיות ניצחון שונות (לפחות):
1. לבחור במהלך הפתיחה במשבצת (3,1) ולהמשיך כ"שחקן 2" בלוח 2*אינסוף.

2. לבחור משבצת (2,2) במהלך הראשון, ועבור בחירה של שחקן 2 במשבצת מסוג (1,i) בחירה במשבצת (i,1) (ולהיפך).
במצב הזה, שחקן 1 הביא את שחקן 2 למשחק "בלוח ר" סימטרי מגודל i, שממנו כאמור הוא יכול לכפות ניצחון (ראה לוח N*N).

ראה גם

• משחק נים

לקריאה נוספת

• שמואל זמיר, מיכאל משלר ואילון סולן, תורת המשחקים, הוצאת מאגנס , 2008

קישורים חיצוניים

• מידע נוסף על המשחק
• משחק צ'ומפ ברשת