משפט ספרג-גרונדי

משפט ספרג-גרונדי הוא משפט יסודי בתורת המשחקים הקומבינטורית הקובע שכל משחק שוויוני (impartial game) אשר משחקים בו באופן נורמלי שקול לנים.

המשפט התגלה באופן בלתי תלוי על ידי רונלד ספרג (1935) ופטריק גרונדי (1939).

הסבר אינטואטיבי

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

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

משחקים קומבינטורים

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

משחק

לצורך משפט ספרג-גרונדי משחק יוגדר להיות משחק שני שחקנים בעל ידיעה שלמה אשר משוחק בתורות, כאשר בכל תור משחק רק שחקן אחד. לשני השחקנים נקרא בשמות שחקן שמאל ושחקן ימין. מצב במשחק יוגדר באופן חד ערכי על ידי מצב הלוח ועל ידי זהות השחקן שתורו לשחק.
מצב לוח יוגדר באופן רקרוסיבי ויסומן על ידי $G=\left\{A,B,C...|D,E,F...\right\}$. מצב לוח מכיל את כל מצבי הלוח שניתן להגיע אליהם מהמצב הנוכחי, כאשר $A,B,C...$ הם מצבי הלוח שאליהם ניתן להגיע על ידי מהלך אחד של שחקן שמאל ו- $D,E,F...$ הם מצבי הלוח שאליהם ניתן להגיע על ידי מהלך אחד של שחקן ימין. משחק מתאים למצב הלוח בתחילת המשחק ולכן ניתן לכתיבה כ- $G=\left\{A,B,C...|D,E,F...\right\}$. כאשר אנו רושמים משחק בצורה זו, איננו אומרים מי הוא השחקן הראשון שמשחק (מי מבצע את מהלך הפתיחה). שחקן זה יכול להיות שחקן שמאל או שחקן ימין, וכפי שנראה בהמשך, זהות המנצח במשחק יכולה להיות תלויה בזהות השחקן שמבצע את מהלך הפתיחה. בערך זה, השחקן שמבצע את מהלך הפתיחה ייקרא שחקן מספר אחת והשחקן השני ייקרא שחקן מספר שתיים.

משחקים סופיים

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

מנצח המשחק

אנחנו נתמקד רק במשחקים בהם אחד מהשחקנים חייב לנצח. תוצאות תיקו אינה אפשרית. משחק נורמלי (normal game convention) הוא משחק בו המנצח הוא השחקן אשר שיחק אחרון (שחקן אשר אינו יכול לשחק מפסיד). משחק מיזר (Misere) הוא משחק הפוך, בו המפסיד הוא השחקן האחרון אשר משחק. לכל משחק ישנן ארבע תוצאות אפשריות: השחקן השמאלי תמיד ינצח, השחקן הימני תמיד ינצח, שחקן אחת (השחקן שמשחק ראשון) תמיד ינצח, שחקן שתיים (השחקן שמשחק שני) תמיד ינצח. חשוב לשים לב כי מדובר אך ורק בקיום אסטרטגיה אופטימלית לניצחון. כך לדוגמה משחק ארבע בשורה (אשר אינו חלק מערך זה, כי ניתן להגיע בו לתוצאת תיקו) הוא משחק פתור בו שחקן אחת (המתחיל) תמיד ינצח, אך כדי לעשות זאת בפועל הוא חייב לשחק את האסטרטגיה האופטימלית שלו.

חיבור משחקים

יהי $G_{1},G_{2}$ משחקים שונים. נחבר אותם למשחק חדש $G=G_{1}+G_{2}$ כך ששני המשחקים ישוחקו במקביל. בכל תור השחקן שמשחק יבחר האם לבצע מהלך או ב- $G_{1}$ או ב- $G_{2}$ והמנצח יהיה השחקן אשר משחק אחרון בשני המשחקים גם יחד (במקרה הנורמלי). פורמלית המשחק המחובר יהיה: $G+H=\left\{\left(G^{L_{1}}+H,G^{L_{2}}+H,...,G+H^{L_{1}},G+H^{L_{2}},...\right)|\left(G^{R_{1}}+H,G^{R_{2}}+H,...,G+H^{R_{1}},G+H^{R_{2}},...\right)\right\}$, כאשר $G^{L_{1}}$ הוא מהלך אפשרי לשחקן אחד במשחק $G$ וכו'. הגדרה זאת של חיבור משחקים מגדירה פעולה קומטטיבית ואסוציאטיבית, תחת משחק האפס, אשר מסומן ב- $*0$, שהוא המשחק אשר מייצג את קבוצת המהלכים הריקה. במשחק זה לשני השחקנים לא קיים מהלך אפשרי והשחקן אשר פותח את המשחק הוא גם המפסיד (עוד בהמשך).

חיסור משחקים

אינטואטיבית, $-G$ הוא המשחק ההופכי למשחק $G$, כלומר נהפוך את הלוח וניתן לשחקן אחת לשחק עם הכלים של שחקן שתיים ולהפך. כאשר מחברים משחק והמשחק ההופכי שלו מתקיים כי שחקן מספר שתיים תמיד ינצח במשחק. ניתן להוכיח זאת על ידי שימוש באסטרטגית הטווידלדם וטווידלדי - כל מה ששחקן אחת ישחק, שחקן שתיים ישחק את המהלך הזהה בלוח השני, מה שיוביל לניצחון וודאי של שחקן שתיים. פורמלית: חיסור יוגדר באופן זהה לחיבור, כאשר אם $G=\left\{A,B,C...|D,E,F...\right\}$ אז $-G=\left\{-D,-E,-F,...|-A,-B,-C,...\right\}$.

משחקים שוויונים

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

משחק שוויוני

משחק שוויוני (impartial game) הוא משחק בו כל אחד מהשחקנים יכול לשחק בדיוק את אותם המהלכים כמו השחקן השני באותו התור. לדוגמה, אם שני השחקנים יכולים לשחק $A,B,C$, אז נסמן משחק זה בקיצור באופן הבא: $G=\left\{A,B,C|A,B,C\right\}=\left\{A,B,C\right\}$. במשחקים שוויונים, בעקבות העובדה שהלוח זהה, זהות המנצח תקבע רק על ידי תור מי לשחק. המנצח תמיד יהיה או שחקן אחת או שחקן שתיים ולא קיים משחק שוויוני בו הניצחון מובטח לשחקן השמאלי (או הימני).

נים

נים משמש כדוגמה הסטנדרטית למשחק שוויוני. במשחק זה יש מספר ערימות של גפרורים. בכל תור השחקן שמשחק יכול להוציא כמה גפרורים שהוא רוצה, אבל רק מערימה אחת. כאשר המשחק משוחק באופן נורמלי השחקן שלוקח את הגפרור האחרון מנצח. בגרסת המיזר (Misere), המשחק משוחק באופן הפוך, ומי שלוקח את הגפרור האחרון מפסיד. משחק נים בעל ערמה בודדת עם $n>0$ גפרורים הוא טרוויאלי. במשחק זה השחקן שמתחיל תמיד ינצח - הוא יקח את כל הגפרורים בערימה (אם המשחק נורמלי) או יקח את כל הגפרורים מלבד האחרון (בגרסת המיזר). בשנת 1901 פרסם צ'ארלס בולטון אסטרטגית ניצחון כללית למשחק בכל גודל סופי של ערימות בעלות מספר סופי של גפרורים. למעשה, בולטון הראה שמנצח המשחק נקבע מראש על ידי סידור הלוח, כאשר לכל לוח קיימת אסטרטגיה אשר תבטיח ניצחון לאחד מהשחקנים, ורק לו.

מספר גרונדי

מספר גרונדי (או נימבר - nimber) הוא מספר שלם אי שלילי המשויך למצב במשחק. הוא ייצג משחק נים עם ערימה בודדת בגודל $n$, נסמן זאת על ידי $*n$, ומעתה ואילך נתייחס אליו בתור משחק שוויוני. נשתמש במספרי גרונדי כדי למיין מצבי משחק של משחקים שוויונים אחרים אשר שונים מנים ולהשוות אותם עם נים. באופן ישיר מנים, השחקן הראשון תמיד ינצח בכל משחק בעל מספר גרונדי שונה מאפס, ותמיד יפסיד כאשר מספר גרונדי שווה לאפס.

שקילות במשחקים שוויונים

שני משחקים שוויונים $G_{1},G_{2}$ יהיו שקולים אם ורק אם במשחק המחובר $G_{1}+(-G_{2})$ שחקן שתיים הוא המנצח. משמעות השקילות הינה שהתצאות האפשריות של המשחקים יהיו זהות לכל משחק $H$ אשר נחבר לשני המשחקים. נסמן את השקילות על ידי $G_{1}\approx G_{2}$. מכיוון שמשחק האפס על פי הגדרה הוא משחק בו השחקן השני תמיד מנצח וגם מתקיים במשחקים שוויונים כי $G=-G$, אז שני משחקים יהיו שקולים אם $G_{1}+(-G_{2})=G_{1}+G_{2}\approx *0$. שני משחקים שקולים יהיו בעלי מספר גרונדי זהה.
דוגמאות:

• במשחקים שוויוניים נורמלים $G+G\approx *0$. ניתן גם להראות זאת ישירות בעזרת אסטרטגית טווידלדם וטווידלדי. בגרסת המיזר זה לא מתקיים (ולכן משפט ספרג-גרונדי אינו תקף עבור משחקים שאינם נורמלים).
• עבור מספרי גרונדי, אשר בעצמם מהווים משחקים שוויונים, מתקיים: $*n\approx *k$ אם ורק אם $n=k$.

פונקציית (mex(G

ערך ה- $mex$ של קבוצה הוא השלם הלא שלילי הקטן ביותר, אשר לא שייך לקבוצה. הפונקציה הזאת משמשת לצורך חישוב מספר גרונדי. לדוגמה: $mex(\left\{0,1,2,7\right\})=3$ ואילו $mex(\left\{1,2,3,5,8\right\})=0$.

משפט ספרג-גרונדי

יהי $G$ משחק שוויוני סופי המשוחק בצורה נורמלית, אז קיים $n$ אשר מקיים $G\approx *n$, כלומר המשחק $G$ שקול למספר גרונדי $*n$. במקרה כזה לשחקן אחת יש אסטרטגיית ניצחון אם ורק אם מספר גרונדי של המשחק שונה מ- $*0$.

כללי

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

הוכחת משפט ספרג-גרונדי

נוכיח את המשפט בעזרת אינדוקציה על מספר המהלכים עד סיום המשחק. בסיס האינדוקציה מתקיים כאשר לשני השחקנים במשחק השוויוני $G$ נותרו אפס מהלכים עד סוף המשחק ואז $G\approx *0$. נניח את נכונות צעד האינדוקציה לכל משחק שוויוני בעל לא יותר מ- $n-1$ מהלכים עד סופו. לכל משחק כזה קיים מספר גרונדי מוגדר היטב.
יהי $G=\left\{G^{'},G^{''},..\right\}$ משחק שוויוני בעל $n$ מהלכים עד סופו. כל שחקן יכול לשחק $G^{'},G^{''},..$. נשים לב שמכיוון שהמשחק שוויוני וסופי, אז כל אחד מהמהלכים יוביל לתת-משחק בעל מספר קטן יותר של מהלכים אשר מקיים את הנחת האינדוקציה. לכן, כל אחד מהמהלכים שקול למשחק שוויוני בעל מספר גרונדי יחיד. לפיכך $G=\left\{*n_{1},*n_{2},...\right\}$. זאת היא קבוצה של מספרי גרונדי. על פי טענת העזר למטה, לקבוצה זאת יש מספר גרונדי יחיד אשר שווה ל- $G\approx mex(G)$ של הקבוצה.

טענת עזר

יהי $G=\left\{*n_{1},*n_{2},...\right\}$ משחק שוויוני, אז $G\approx mex(G)$.

הוכחת טענת העזר

נשים לב שהטענה משתמשת בכך שכל קבוצה של מספרי גרונדי היא בעצם משחק שוויוני, מה שנכון, מכיוון שהקבוצה הזאת שקולה למשחק בו השחקן הראשון בוחר ערימת נים כלשהי מתוך כל הערימות האפשריות. כדי להראות ש- $G\approx mex(G)$ נרצה להוכיח כי $G+mex(G)\approx *0$, כלומר במשחק המחובר בין השניים, השחקן שמשחק ראשון תמיד מפסיד. נראה זאת על ידי מציאת אסטרטגיה מנצחת לשחקן השני. ישנן שלוש אפשרויות למשחק:

• אם השחקן הראשון מבצע מהלך ב- $mex(G)=*n$ ומשחק איזשהו $*k<*n$, אז על פי הגדרת $mex(G)$, השחקן השני יכול לשחק $G=*k$, מה שיוביל לשתי ערימות נים זהות בגודל $*k+*k\approx *0$. במצב כזה שחקן שניים תמיד מנצח - על כל מהלך של שחקן מספר אחד, שחקן שניים ישחק מהלך זהה בערימה המקבילה, עד שהמשחק יגמר.
• אם השחקן הראשון מבצע מהלך ב- $G$ ומשחק לאיזשהו $*k$ כך ש- $mex(G)=*n>*k$, אז שחקן שתיים ישחק $mex(G)=*k$ ושוב נקבל שתי ערימות זהות $*k+*k\approx *0$.
• אם השחקן הראשון מבצע מהלך ב- $G$ ומשחק לאיזשהו $*k$ כך ש- $mex(G)=*n<*k$, אז שחקן שתיים ישחק בערימת הנים החדשה $*n$ מה שיתן לנו שתי ערימות זהות, $*n+*n\approx *0$.
• ראוי לציין כי לשחקן אחד אין אפשרות לשחק $G=*n$, מכיוון שעל פי הגדרת ה- $mex(G)$, זה הוא בדיוק המהלך המינימלי אותו לא ניתן לשחק במשחק.

ראו גם

• משחק אסטרטגיה מופשט
• נים
• תורת המשחקים הקומבינטורית
• תורת המשחקים

לקריאה נוספת

• Dierk Schleicher, Michael Stoll, "An Introduction to Conway's Games and Numbers", 2005.
• J.H. Conway, "On numbers and games", AK Peters, 2001.
• E.R. Berlekamp, J.H. Conway, and R. K Guy, "Winning ways for your mathematical plays", AK Peters, 2001.