המשחק נים

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

המשחק מתנהל בתורות. בכל תור אחד מהשחקנים בוחר את אחת מהערימות, לוקח ממנה כמה גפרורים שהוא רוצה (החל מ-1 וכלה בכולם), והתור עובר לשחקן הבא. המנצח? מי שלוקח את הגפרור האחרון מהערימה האחרונה שנותרה. אפשר גם להגדיר שדווקא מי שלוקח את הגפרור האחרון מפסיד; לעת עתה נדבוק בגרסה הראשונה, ובהמשך נראה מה קורה עם השניה.

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

הטענה המתמטית הבסיסית שניתן לטעון לגבי המשחק הזה היא שתמיד, בכל מצב עניינים אפשרי במשחק, לאחד משני השחקנים יש אסטרטגיה שתבטיח לו ניצחון במשחק. אסטרטגיה פירושו “תוכנית פעולה” מכאן ועד לסיום המשחק - לכל מצב שהוא יגיע אליו בעתיד, האסטרטגיה אומרת לו כיצד כדאי לו לשחק כדי להבטיח ניצחון. זה אומר שהמשחק “מכור מראש” - כבר כשמתחילים אותו אפשר לדעת בודאות מי יהיה המנצח, אם שני השחקנים חכמים ומשחקים בצורה אופטימלית. התוצאה הזו היא מקרה פרטי של משפט צרמלו, שהצגתי בעבר בבלוג; היא תקפה לכל משחק בשני שחקנים בעל ידיעה שלמה, כמו שחמט. הבעיה עם שחמט היא שפשוט איננו יודעים מהי אסטרטגיית הניצחון המתאימה, ולכן נים נבדל משחמט בדיוק בכך שקל בו לדעת איך לשחק בפועל כדי להבטיח את הניצחון.

הבה ונכניס שיטת סימון מתמטית כלשהי לעמדות השונות במשחק. \( \left(1,2,3\right) \), למשל, פירושו “יש שלוש ערימות, באחת גפרור אחד, בשניה שני גפרורים ובשלישית שלוש”. את העמדה מתחילת הפוסט אפשר לתאר על ידי \( \left(7,3,12\right) \); ובדומה אפשר לתאר גם עמדות מורכבות יותר. כדי לא לשעמם, ניתן שמות מתמטיים גם לשחקנים - לאחת נקרא אליס, ולשני נקרא בוב.

כעת, הבה ננסה להבין קצת מה הולך במשחק. העמדה \( \left(1\right) \) מבטיחה ניצחון למי שישחק עכשיו; כך גם \( \left(2\right) \), ובעצם \( \left(n\right) \) לכל מספר \( n \). ומה עם \( \left(1,1\right) \)? ובכן, אם תורו של בוב לשחק אז הוא בודאות הפסיד - הוא חייב לקחת גפרור מאחת הערימות, ואז אליס תיקח את הגפרור שנותר ותנצח.

מה על העמדה \( \left(2,2\right) \)? ובכן, אם בוב הגיע לעמדה הזו, הוא הפסיד. כי אם הוא ירוקן את אחת הערימות, אליס תרוקן את הערימה השניה; ואם בוב יקח רק גפרור אחת מאחת הערימות ויעביר את המשחק לעמדה \( \left(1,2\right) \), אז אליס תיקח את הגפרור מהערימה השניה ותעביר את המשחק למצב \( \left(1,1\right) \) שבו כבר ראינו שבוב מפסיד. העמדות הללו, שבהן מי שמשחק כרגע בודאות מפסיד, הן המפתח לזכייה במשחק: אם אני אליס ואני נמצא בעמדה כלשהי, אני ארצה לדעת האם יש לי מהלך שיהפוך את העמדה הנוכחית שלי לעמדה “מפסידנית” שכזו (כי אחרי שאני משחק התור עובר לבוב, ואני רוצה שבוב יתחיל את תורו בעמדה “מפסידנית”). לצורך התעללות בשפה העברית, הבה ונקרא לעמדה מפסידנית שכזו בשם העברי הנאה “עמדה לוזרית”, ולעמדה שאינה מפסידנית - “עמדה וינרית”.

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

מה זה ייצוג עשרוני של מספר כולנו יודעים. המספר “עשרים ושבע” נכתב בתור \( 27 \) בבסיס עשרוני; זו דרך מקוצרת לומר “2 כפול 10 ועוד 7 כפול 1”. המספר “מאה חמישים ושלוש” נכתב בתור \( 153 \), שזו דרך מקוצרת לומר “1 כפול 100 ועוד 5 כפול 10 ועוד 3 כפול 1”. אתם מבינים את הרעיון - מציגים את המספר בתור סכום של חזקות של 10 שמוכפלת בספרות המספר. ייצוג בינארי זה אותו הדבר בדיוק, רק עם חזקות של 2. כך למשל \( 1011 \) פירושו “1 כפול שמונה ועוד 0 כפול ארבע ועוד 1 כפול 2 ועוד 1 כפול 1”, כלומר המספר שאנחנו מכירים בתור אחד עשרה. בבסיס בינארי יש רק שתי ספרות - אפס או אחד. או שחזקה מסויימת של 2 מופיעה בסכום, או שלא.

בהינתן עמדה במשחק, למשל \( \left(7,3,12\right) \), אפשר גם לכתוב את אבריה בבסיס בינארי - \( \left(111,11,1100\right) \). בואו נכתוב את כל המספרים הללו כך שיהיו בהם ארבע ספרות: \( \left(0111,0011,1100\right) \). כעת, בואו נכתוב אותם אחד מעל השני:

0111

0011

1100

וכעת, הבה ונספור כמה 1-ים יש בכל אחת מארבע העמודות. סיכום קצר יעלה שנקבל \( \left(1,2,2,2\right) \). איך כל המשחק הזה עזר לנו? הנה טענת המחץ: העמדות הלוזריות במשחק הן בדיוק אלו שבהן מספר ה-1-ים בכל העמודות הוא זוגי. כלומר, \( \left(7,3,12\right) \) איננה עמדה לוזרית כי בעמודה הרביעית היה מספר אי זוגי של 1-ים. לעומת זאת \( \left(7,13,4\right) \), שדומה ל-\( \left(7,3,12\right) \) מאוד פרט לכך שהעמודה השמאלית ביותר כולה 0-ים כעת (ולכן לא צריך בכלל לכתוב אותה) היא כן עמדה מפסידנית. זה אומר שאם אני אליס והגעתי ל-\( \left(7,13,12\right) \), ניצחתי - והשלב הראשון בדרך לניצחון יהיה לקחת 8 גפרורים מתוך ערימת ה-12.

טוב, אז למה הטענה הזו נכונה בכלל? הבה ונציג את ההוכחה בשלמותה. ההוכחה קלה למדי, אז אני מקווה שכולם יצליחו להישאר איתי - כל אלו ששרדו עד כה, זאת אומרת. כדאי לכם לשרוד - אחרי זה תוכלו לנצח את כולם בנים, תמיד! (כל עוד לא מרמים אתכם בעמדת הפתיחה).

האבחנה המרכזית בהוכחה היא זו: אם שחקן כלשהו נמצא בעמדה לוזרית, אז לא משנה מה יעשה - הצעד שלו יעביר את המשחק לעמדה וינרית; ואילו אם שחקן כלשהו נמצא בעמדה וינרית, אז יש לו צעד שמעביר את המשחק לעמדה לוזרית. במילים אחרות, אם אליס ובוב יודעים מה שהם עושים, אז משחק ביניהם יהיה פשוט פינג-פונג: רגע אחד המשחק יהיה בעמדה לוזרית, וברגע שלאחריו בעמדה לא וינרית, וחוזר חלילה. בכל צעד יתמעט מספר הגפרורים שעוד נותרו, ולכן הפינג-פונג הזה חייב להסתיים מתישהו; ומכיוון שהעמדה שבה כבר אין יותר גפרורים בכלל היא עמדה לוזרית (מספר ה-1-ים בכל העמודות הוא 0, ובפרט זוגי), המשחק יסתיים במהלך של השחקן שנמצא בעמדה וינרית והוא יהיה המנצח. זו עוד דוגמה אחת מני רבות לאופן שבו שמורות צצות במתמטיקה.

אז למה אם בוב נמצא בעמדה לוזרית, כל צעד שיבצע יעביר את המשחק לעמדה וינרית? כי עמדה לוזרית היא מאוד “לא יציבה” - התנאי שמגדיר אותה הוא שכל העמודות הן בעלות מספר זוגי של 1-ים. כעת, כל מהלך של בוב גורר שינוי של המספר שמופיע באחת מהשורות - ורק של השורה הזו. אין לנו מושג מהו השינוי, אבל אנחנו יודעים שיש שינוי - כלומר, שלפחות אחד מהביטים בשורה הזו מתהפך (0 הופך ל-1, או 1 הופך ל-0). זה כל מה שצריך, שכן שאר הביטים בעמודה של הביט המתהפך לא השתנו, ולכן אם קודם מספר הביטים בעמודה ששווים ל-1 היה זוגי, הרי שעכשיו הוא יהפוך בהכרח לאי זוגי, וחסל. שימו לב שהטיעון הזה עובד אפילו אם לבוב מותר להוסיף גפרורים לערימה שהוא בחר; הבעיה עם הוספה כזו היא שאם יורשה לבוב להוסיף גפרורים לא ברור אם המשחק יסתיים אף פעם.

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

101110

101101

010101

מה קורה כאן? ספירת ה-1-ים בעמודות נותנת לנו \( \left(2,1,2,3,1,2\right) \). כלומר, משמאל לימין העמודות המקולקלות הן 2,4,5. כדי לתקן אותן אליס נוקטת בתעלול הבא: ראשית, העמודה המקולקלת הראשונה (השמאלית ביותר מבין המקולקלות) בהכרח מכילה 1 אחד לפחות (כי מספר ה-1-ים הכולל הוא אי זוגי), אז אליס בוחרת להתעלל בשורה של אותו 1. במקרה שלנו, זו השורה השלישית.

כעת, מה אליס תעשה? היא תחליף את המספר שמופיע בשורה השלישית במספר קטן יותר. מה זה אומר? ראשית, ה-1 עושה הצרות יוחלף ב-0. שנית, כל שאר הספרות שמימין לאותו 1 יכולות להיבחר באיזה אופן שנוח לאליס. לא משנה איך היא תבחר אותן, היא תקבל מספר קטן יותר ממה שהיה קודם בשורה, בגלל שהחלפנו את ה-1 השמאלי ההוא ב-0. אם כן, אליס תבחר את שאר הספרות באופן כזה שבכל עמודה שבה היה מספר אי זוגי של 1-ים, הביט יתהפך; ובכל עמודה שבה היה מספר זוגי של 1-ים, הביט יישאר כמות שהוא. בדוגמה שלנו זה אומר שמחליפים את המספר 010101 במספר 000011 (נסו להבהיר לעצמכם למה). בפועל, בעולם האמיתי, בשורה השלישית היו 21 גפרורים, ואליס לקחה 18 והותירה 3 בלבד.

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

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

שנית, מה משתנה במשחק אם מי שלוקח את הגפרור האחרון דווקא מפסיד? המשחק קצת מסתבך - המצב \( \left(1\right) \) שעל פי ההגדרה שלנו הוא מצב וינר מעיד דווקא על הפסד; והמצב \( \left(1,1\right) \) שעל פי ההגדרה שלנו הוא לוזר דווקא מוביל לניצחון. עם זאת, \( \left(2,2\right) \), שעל פי ההגדרה שלנו הוא לוזר, אכן עדיין מוביל לתבוסה: אם בוב יחסל את אחת הערימות, אליס תיקח גפרור אחד מהערימה השניה; ואם בוב יקח גפרור אחד מאחת הערימות, אליס תחסל את הערימה השניה.

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

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

השאלה האחרונה והמהותית ביותר היא - רגע, זה אמור להיות פרקטי? כלומר, אם אנחנו משחקים נים עם מישהו, האם באמת נוכל להתחיל לעשות את כל החישובים הללו בכל מהלך? הוא בוודאי יצרח עלינו! לכך, יש לי כמה תשובות. ראשית, זה פרקטי אם אתם מחשב או מחשב אנושי - בפרט, אפשר לתכנת בקלות מחשב שינצח כך תמיד במשחק (אלא אם המשחק היה מכור מראש לרעתו). שנית, במקום לשחק נים תגידו למי שרוצה לשחק איתכם “עזוב, זה משחק מכור מראש - רוצה לדעת למה?” ותנו לינק לבלוג (פרסום חינם!) או שתסבירו בעצמכם. שלישית, למי שרוצה בכל זאת לשחק בפועל, ג’.ה. הארדי, בספרו הנפלא על תורת המספרים (שמציג את כל מה שאמרתי כאן בפרק שעוסק בבסיסי ספירה), נותן כמה טיפים מעשיים לטובת מי שמשחק “נגד יריב שאינו מכיר את התיאוריה של המשחק”. לדברי הארדי, “השחקן המנוסה יכול לשחק באקראי עד אשר הוא מזהה עמדה מנצחת מצורה פשוטה יחסית. זה די והותר לדעת ש-\( 1,2n,2n+1 \) ו-\( n,7-n,7 \) ו-\( 2,3,4,5 \) הן עמדות מנצחות; ש-\( 1,2n+1,2n+2 \) היא עמדה מפסידה; ושצירוף של שתי עמדות מנצחות היא עמדה מנצחת”. בהצלחה!