נים (משחק)
 |
נים הוא משחק אסטרטגיה מופשט לשני שחקנים שמשוחק עם ערמות גפרורים. חוקי המשחק הם שבכל תור יכול שחקן לקחת כל מספר גפרורים שהוא אבל רק מערמה אחת. המנצח במשחק הוא מי שלוקח את הגפרור האחרון. מקורות המשחק כנראה עתיקים מאוד. לנים תפקיד חשוב בתורת המשחקים הקומבינטורית הנובע ממשפט ספרג-גרונדי הקובע שכל משחק אסטרטגיה שוויוני שקול אליו.
היסטוריה
מקורות המשחק עלומים, אך הוא כנראה שוחק כבר מימי קדם.
האזכור הראשון שלו בספרות האירופאית בא מהמאה ה-16, ושמו ניתן לו כנראה על ידי המתמטיקאי צ'ארלס ל. בולטון שגם ניסח את אסטרטגיית הניצחון במשחק.
אסטרטגיית הניצחון בנים
אסטרטגית הזכייה במשחק נים היא דוגמה יפה לשעשועי המתמטיקה החבויים במשחקי חשיבה, והיא גם בסיס לפתרון של משחקים נוספים רבים. האסטרטגיה מבוססת על כך שבמשחקים מסוגו של נים, שבהם לשני השחקנים יש אותן אפשרויות, אזי כל מצב משחק ניתן לסווג בתור מצב מנצח (השחקן שהתור שלו ינצח בוודאות אם ישחק כהלכה), או מצב מפסיד (השחקן שהתור שלו יפסיד בוודאות אם יריבו ישחק כהלכה). כדי לאבחן אם מצב במשחק נים הוא מנצח או מפסיד, יש לכתוב בשלב הראשון את מספר הגפרורים שבכל ערמה בבסיס בינארי, כלומר באמצעות החזקות של 2 שמהם המספר כתוב. לדוגמה אם כרגע יש שלוש ערימות שבהם 3, 7, 8 גפרורים אזי נכתוב זאת כך:
3=1+2 (בכתיב בינארי 0011)
7=1+2+4 (בכתיב בינארי 0111)
8=8 (בכתיב בינארי 1000)
בשלב הבא יש לבצע פעולת או מוציא (XOR) שבה חזקה שמופיעה פעמיים תימחק, ואז יש לסכם את החזקות שנותרו:
0=1+2 (בכתיב בינארי 0000)
4=1+2+4 (בכתיב בינארי 0100)
8=8 (בכתיב בינארי 1000)
סכום הנים של המצב בדוגמה הוא 12=4+8. אם סכום הנים של מצב הוא 0, אז זהו מצב מפסיד, אחרת זהו מצב מנצח. המהלך המנצח הוא המהלך שמביא את המצב למצב בעל סכום נים 0. בדוגמה זו, המהלך המנצח הוא להוריד 4 גפרורים מהערמה השלישית ולהביא את המשחק למצב:
3=1+2 (בכתיב בינארי 011)
7=1+2+4 (בכתיב בינארי 111)
4=4 (בכתיב בינארי 100)
תחפושות ווריאציות
למשחק נים ישנן מספר תחפושות - כלומר משחקים שלכאורה נראים שונים אך למעשה הם אנלוגיים לו.
- נים חיילים - על גבי לוח שחמט מונחים בכל טור חייל לבן וחייל שחור. השחקן הלבן בתורו יכול להזיז את החייל שלו כמה מהלכים שהוא רוצה למעלה באותו טור כל עוד הוא לא מתנגש בחייל השחור. השחקן השחור יכול לבצע את אותה פעולה בכיוון ההפוך (למטה). המשחק אנלוגי לנים, כאשר כל טור מהווה ערמת גפרורים ומספר הגפרורים בערמה נקבע לפי מספר המשבצות שבין החייל הלבן לחייל השחור.
- נים כיס - על שורת משבצות מונחים מטבעות. בכל תור שחקן יכול להזיז מטבע כל מספר של משבצות ימינה כל עוד הוא לא מתנגש במטבע אחר. כאשר המטבע מגיע לקצה הימני המטבע נופל לתוך כיס. השחקן שמפקיד את המטבע האחרון בכיס מנצח.
למשחק אין ספור וריאציות, הבולטות ביניהן:
- גרסת המיזר (Misere) - בגרסה זו השחקן שלוקח את הגפרור האחרון מפסיד. הצעצוע פופיט נמכר תחילה כמשחק בגרסה זו של נים, בשם "אחרון מפסיד".
- פוקר נים - בגרסה הזאת שחקן שומר את הגפרורים שהוא לקח, ובכל תור הוא יכול, במקום לקחת גפרורים, להוסיף לאחת הערמות מספר כלשהו מהגפרורים שהוא לקח.
- הנים של ויתופ - במשחק זה ישנן שתי ערמות ובכל תור מותר לקחת כל מספר גפרורים שהוא מערמה אחת, או מספר זהה של גפרורים משתי הערמות.
- משחקי ערמות נוספים - ישנן וריאציות שבהן ניתן לפצל ערמה על ידי לקיחת גפרורים מאמצע הערמה, וכן משחקים שבהם מותר רק לקחת לכל היותר מספר מסוים של גפרורים מתוך הערמה.
ראו גם
קישורים חיצוניים
- המאמר המקורי של בולטון מ-1901
- גדי אלכסנדרוביץ', המשחק נים, באתר "לא מדויק", 30 במרץ 2011
- נים, באתר אנציקלופדיה בריטניקה (באנגלית)
- נים, באתר MathWorld (באנגלית)
38044318נים (משחק)