משפט צרמלו

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

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

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

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

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

הוכחה

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

עץ משחק

דוגמה לעץ משחק

ערך מורחב – עץ משחק

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

תוכן ההוכחה

המחשה להוכחה. במקרה זה השורש אפור, לכן כל שחקן יכול לכפות תיקו.

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

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

לפי הניתוח האחרון, ייתכנו שלוש אפשרויות התלויות בצבע של השורש של העץ:

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

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

דוגמאות על משחקים שונים

משחק הלוח רברסי

משפט צרמלו נשען על כמה תכונות מופשטות של המשחק:

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

להן דוגמאות אחדות למשחקים שעומדים בתנאי הסף של המשפט ועל כן הוא חל עליהם:

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

להן דוגמאות אחדות למשחקים של שני שחקנים שאינם עומדים בתנאי הסף של המשפט ועל כן לא חל עליהם:

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

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

• צ’ומפ צ’ומפ - באתר "לא מדויק".