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