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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

משפט ספרג-גרונדי הוא משפט יסודי בתורת המשחקים הקומבינטורית הקובע שכל משחק שוויוני (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(\left\{ G^{L_{1}}+H,G^{L_{2}}+H,...\right\} \cup\left\{ G+H^{L_{1}},G+H^{L_{2}},...\right\} \right)|\left(\left\{ G^{R_{1}}+H,G^{R_{2}}+H,...\right\} \cup\left\{ G+H^{R_{1}},G+H^{R_{2}},...\right\} \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.