במשך מאות שנים תהו שחקנים, מתמטיקאים וחובבי משחקי לוח בכל העולם בשאלה פשוטה לכאורה אך עמוקה להפליא: האם תוצאתו של משחק לוח ידועה מראש עוד מן המסע הראשון? כאשר שני רבי־אמנים יושבים משני עברי לוח של שישים וארבע משבצות ואינם שוגים אפילו פעם אחת, האם השחקן הפותח נהנה מיתרון שמבטיח לו ניצחון בלתי נמנע? האם על השחקן השני נגזר להפסיד? או שמא המשחק, כאשר הוא משוחק בדיוק ללא פשרות, מגיע לשיווי משקל מתמטי מושלם שמסתיים בתיקו?
ביולי 2007 פורסם בכתב העת המדעי היוקרתי Science מאמר מחקרי מקיף ששם קץ לתהיות אלו[1]. צוות חוקרים מאוניברסיטת אלברטה שבקנדה, בהובלת מדען המחשב ג׳ונתן שפר, הכריז כי משחק הדמקה האנגלית (המוכר ברחבי העולם בשם checkers) נפתר חישובית באופן מלא. בתום פרויקט חישובי אדיר ממדים שנמשך 18 שנים והחל עוד ב־1989, תוכנת המחשב שלהם, צ׳ינוק (Chinook), סיפקה הוכחה מוחלטת: כאשר שני הצדדים בוחרים במסעים המיטביים, משחק דמקה מסתיים תמיד בתוצאת תיקו.
אולם פריצת הדרך המדעית הזו לא גרמה לשחקנים לנטוש את הלוח. כדי להבין מדוע המשחק נותר מהנה, מרתק ומלא הפתעות, עלינו לבחון תחילה מה המשמעות המתמטית של משחק פתור.
שלושת סוגי הפתרונות בתורת המשחקים
בשפת היומיום אנחנו נוהגים לומר שחידה נפתרה כאשר גילינו את הרעיון שעומד מאחוריה. אולם במתמטיקה בדידה ובבינה מלאכותית, למונח יש הגדרה פורמלית מדויקת שנוסחה ב־1994 בידי החוקר ויקטור אליס[2]. אליס חילק את הפתרונות למשחקים בעלי ידיעה שלמה ל־3 רמות מובחנות:
- פתרון חלש במיוחד (Ultra-weakly solved). הוכחה מתמטית הקובעת את התוצאה התאורטית של עמדת הפתיחה (ניצחון לשחקן הראשון, לשני, או תיקו), מבלי לספק אלגוריתם או סדרת מסעים מעשית למימושה. הדוגמה המובהקת היא משחק הקס, שבו הוכיחה תורת המשחקים כי לשחקן הראשון יש ניצחון כפוי, אך מבלי למפות את המסעים המנצחים על לוחות גדולים.
- פתרון חלש (Weakly solved). אלגוריתם מעשי או עץ הוכחה מוכח המבטיח אסטרטגיה מלאה המובילה לתיקו או לניצחון מעמדת הפתיחה כנגד כל מסע אפשרי של היריב. התוכנה אינה חייבת לדעת את הערך של כל עמדה משונה שנוצרה משגיאות חמורות, אך מעמדת הפתיחה היא בלתי מנוצחת לחלוטין. הדמקה שייכת בדיוק לקטגוריה זו[1].
- פתרון חזק (Strongly solved). אלגוריתם המחשב בזמן אמת את הערך המדויק ואת המסע המושלם מכל עמדה חוקית הניתנת להשגה, ללא תלות במסעים שקדמו לה. המשחק ארבע בשורה נפתר חזק ב־1988: השחקן הראשון יכול לכפות ניצחון מכל מצב בעזרת מסעים מדויקים[2].
הדמקה האנגלית נפתרה חלש ולא חזק מפני ששמירת כל עמדה חריגה הייתה דורשת נפחי אחסון בלתי נתפסים. צוות המחקר התרכז בהוכחת הנתיב מנקודת הפתיחה הרשמית. המשחק נפתח עם 12 אבנים כהות מול 12 אבנים בהירות על גבי 32 המשבצות הכהות, ובסך הכול 24 אבנים פעילות על הלוח[3].
18 שנות מחקר: כיצד פתחה צ׳ינוק את סודות הדמקה?
מרחב המצבים החוקיים בדמקה עצום בהרבה מכפי שמדמיינים שחקנים חובבים. על לוח תקני של 8×8 משבצות, מספר העמדות החוקיות מגיע לכ־5 × 10^20 מצבים[1]. מדובר בחצי טריליון מיליארד עמדות שונות. אילו היה מחשב ביתי מנסה לבדוק כל אחת מהעמדות הללו בזו אחר זו, החישוב היה אורך אלפי שנים.
כדי להתגבר על האתגר, חילקו החוקרים את המשימה לשני מאמצים משולבים: חישוב לאחור מסיומי המשחק, וסריקה קדימה מעמדת הפתיחה.
ניתוח נסוג ומאגר סיומים של 39 טריליון מצבים
אבן הראשה של ההוכחה הייתה מאגר נתוני הסיומים. במקום להתחיל מהמסע הראשון ולהתפזר בעץ ענקי של אפשרויות, החלו החוקרים מסוף המשחק, כאשר על הלוח נותרו כלים ספורים בלבד. עמדה של דמקה מול דמקה יחידה היא עמדת תיקו פשוטה. שתי דמקות הלוכדות אבן בפינה מבטיחות ניצחון כפוי.
באמצעות שיטת הניתוח הנסוג, בחנה צ׳ינוק כל עמדה אפשרית עם מעט אבנים. אם מסע מסוים מוביל לעמדת ניצחון ידועה, העמדה הנוכחית מתויגת כניצחון. אם כל המסעים החוקיים מובילים לעמדה מפסידה, היא מסומנת כהפסד. ואם משחק מדויק שומר על האיזון, העמדה מסומנת כתיקו.
בין 1989 ל־2007 השלים הצוות את חישוב כל העמדות המכילות 10 אבנים או פחות על הלוח[1]. מאגר סיומים ענקי זה כולל 39 טריליון עמדות שונות. מרגע שבמשחק נותרו 10 אבנים או פחות, צ׳ינוק אינה מחשבת דבר: היא שולפת את התוצאה המדויקת ישירות מן הזיכרון.
גשר ההוכחה: מן הפתיחה אל מאגרי הסיומים
לאחר השלמת מאגר עשר האבנים, נותר האתגר המרכזי: לבנות גשר חישובי יציב שיחבר בין עמדת הפתיחה בת 24 האבנים אל סף מאגר הסיומים[1].
לשם כך שילבו החוקרים אלגוריתמים מתקדמים של חיפוש מספרי הוכחה יחד עם גיזום אלפא־בטא. האלגוריתם בחן ענפים מרכזיים, תוך מתן עדיפות להחלפות כפויות ולמצבים המובילים במהירות למאגר הסיומים, תוך גיזום ענפים חלשים שהופרכו מיד.
על פני מאות מחשבים שפעלו במקביל במשך שנים, נופו מיליארדי ענפים מיותרים כדי לגבש עץ הוכחה מוכח המונה עשרות מיליוני עמדות מפתח. כל ענף מרכזי מן הפתיחה הוביל למבצר הגנתי בלתי עביר או התחבר ישירות לעמדת תיקו ממאגר 39 הטריליון. ב־2007 הושלמה ההוכחה במלואה: משחק הדמקה מוביל תמיד לתיקו[1].
מריון טינסלי: המוח האנושי מול כוח המחשב
שנים רבות לפני שהאלגוריתמים הוכיחו את תוצאת המשחק, אדם אחד התקרב לשלמות בעזרת אינטואיציה יוצאת דופן. ד״ר מריון טינסלי, פרופסור למתמטיקה מפלורידה, נחשב בעיני רבים לשחקן הדמקה הגדול ביותר שחי אי פעם.
הישגיו התחרותיים של טינסלי נשמעים כמעט דמיוניים. לאורך קריירה בת 45 שנים בתחרויות בינלאומיות, הפסיד טינסלי ב־9 משחקים בלבד מתוך אלפים רבים ששיחק[1]. הוא החזיק בתואר אלוף העולם לאורך עשרות שנים, וויתר עליו רק כאשר חש שהתחרות אינה מאתגרת אותו עוד. כדי להעמיד את צ׳ינוק במבחן מול שיא היכולת האנושית, ארגן ג׳ונתן שפר דו־קרב רשמי על אליפות העולם ב־1992 נגד טינסלי.
הדו־קרב ב־1992 הפך לאירוע מכונן. על פני 39 משחקים מותחים, הפגין טינסלי שליטה עמוקה והביס את צ׳ינוק בתוצאה של 4 ניצחונות, 2 הפסדים ו־33 תוצאות תיקו[1]. זו הייתה הפעם הראשונה בהיסטוריה שתוכנת מחשב התמודדה על תואר אליפות עולם רשמי מול אלוף עולם אנושי מכהן במשחק לוח מסורתי.
ב־1994 נערך משחק הגומלין. לאחר 6 תוצאות תיקו רצופות נאלץ טינסלי לפרוש בעקבות מחלה קשה, ונפטר ב־1995[1]. צ׳ינוק הוכתרה לאלופת העולם בין אדם למכונה. בדיקות מאוחרות של משחקיו של טינסלי הדהימו את החוקרים: החלטותיו תאמו בדיוק כמעט מושלם את המסעים המומלצים במאגרי הסיומים המדויקים של המחשב.
סולם המורכבות: מארבע בשורה ועד שחמט
כדי להבין את ממדי ההישג של פתרון הדמקה, מועיל להשוותה למשחקים מוכרים אחרים.
כבר ב־1950 ניתח המתמטיקאי קלוד שנון את מורכבות השחמט במאמרו ההיסטורי על תכנות מחשבים[4]. שנון העריך כי בשחמט יש כ־10^44 עמדות חוקיות, ומספר המשחקים האפשריים מגיע ל־10^120 לכל הפחות – נתון המוכר כיום כמספר שנון[4].
הבה נבחן את סולם המשחקים:
- ארבע בשורה: נפתר חזק ב־1988[2]. המשחק מונה טריליוני מצבים ונפתר כיום במחשב נייד בתוך שניות ספורות.
- דמקה אנגלית 8×8: נפתרה חלש ב־2007 במרחב של כ־5 × 10^20 עמדות[1]. נדרשו 18 שנות חישוב מבוזר ומאגר של 39 טריליון סיומים.
- שחמט: אינו פתור כלל. עם 10^44 עמדות ו־10^120 הסתעפויות[4], השחמט חורג מכל יכולת חישוב כוללת. נכון להיום חושבו מאגרי סיומים לשחמט עד 7 כלים בלבד. הגעה ל־8 כלים תדרוש נפחי אחסון בלתי נתפסים, ופתרון המשחק המלא בן 32 הכלים אינו בהישג יד במחשבים הקלאסיים.
- דמקה בינלאומית 10×10: אינה פתורה. משוחקת על לוח של 100 משבצות עם עשרים אבנים לכל צד, ומרחב המצבים שלה מוערך בכ־10^30 עמדות. הדמקה המעופפת וחובת ההכאה המרבית יוצרות עץ משחק מורכב להפליא.
מדוע הפתרון המתמטי שומר על חיות המשחק?
כאשר הוכרז הפתרון ב־2007, היו שחששו כי הדמקה איבדה את עוקצה. אם המחשב יודע שמשחק מושלם מסתיים בתיקו, מדוע שבני אדם ימשיכו לשחק?
תפיסה זו שגויה ביסודה. פתרון מתמטי מתאר מפגש בין שתי ישויות מושלמות שאינן שוגות לעולם לאורך עשרות מסעים. אולם שחקנים אנושיים אינם מחשבים. איש אינו מסוגל לזכור בעל פה 39 טריליון עמדות סיום או להחזיק בראשו עצי הוכחה בני עשרות מיליוני ענפים.
ליד הלוח, הדמקה נותרה קרב טקטי מרתק ומלא מתח. הכלל המרכזי של חובת ההכאה מחייב אתכם לקחת כלי כאשר ישנה הכאה חוקית. כלל זה מוליד צירופים מרהיבים, שבהם שחקנים מקריבים אבנים במכוון כדי למשוך את כלי היריב לאלכסונים פגיעים ולבצע הכאות מרובות מוחצות.
בפועל, תוצאת המשחק מוכרעת בידי 3 גורמים:
- דיוק בפתיחה. על אף שהנתיב המרכזי שומר על שוויון, ההסתעפויות מלאות במלכודות מסוכנות. חוסר דיוק במסע מוקדם עלול לחרוץ את גורל המשחק בתוך מסעים בודדים.
- תמרון עמדתי. שליטה במרכז הלוח, הגנה על שורת ההכתרה ובניית מערכי אבנים דורשות הבנה עמוקה. שחקנים המכירים את עקרונות אסטרטגיה בדמקה מנצחים בעקביות יריבים המסתמכים רק על חישוב שטחי.
- דיוק בסיומים. כאשר מספר האבנים שווה, חוק האופוזיציה (התנגדות) מכריע את המשחק. צעד מוטעה אחד עלול להפוך ניצחון בטוח לתיקו, כפי שאנחנו מפרטים במדריך המקיף שלנו על סיומי משחק בדמקה.
בתחרויות רשמיות נהוג להגריל את מסעי הפתיחה כדי להרחיק את השחקנים מקווים ידועים ולהובילם לשטחים חדשים. הדמקה חיה ותוססת; ההוכחה המדעית רק איששה את האיזון הנפלא ואת היופי המבני של המשחק.
חובת ההכאה ועושר התחבולות על הלוח
הדינמיקה המיוחדת של הדמקה נובעת מן הכלל המחייב ביצוע לכידה. ברגע שבו נפתחת אפשרות הכאה, השחקן אינו רשאי לבחור במסע שקט אחר. מנגנון זה מאפשר תכנון מארבים מתוחכמים: שחקן מנוסה מקריב לעיתים קרובות אבן אחת או שתיים כדי למשוך את כלי היריב לערוגות פגיעות, ואז מנחית סדרת דילוגים מהירה שהופכת את יחסי הכוחות בבת אחת.
חובבי המשחק מגלים במהירות כי הלוח הקטן טומן בחובו גמישות טקטית עצומה. הבנת התפקיד של אבני השוליים, מניעת פריצה של דמקה עוינת ובניית שרשראות הגנה מלוכדות מעניקות יתרון מובהק למי שמשקיע בלמידה מעמיקה. שליטה באלכסונים המרכזיים מאלצת את היריב לפתח מסעים מאולצים באגפים. כאשר אתם שומרים על מבנה מבוצר בשורת הבסיס, ליריב קשה מאוד לפרוץ לעבר שורת ההכתרה ולהשיג דמקה חופשית.
ההיבט הפסיכולוגי של המשחק האנושי
בניגוד למכונות חישוב חסרות רגש, בני אדם הפועלים תחת מגבלת זמן חשופים ללחץ נפשי ולעייפות. שחקן דמקה נדרש לשמור על דריכות לאורך עשרות מסעים, לחזות את תוכניות היריב ולהימנע מהסחות דעת. דווקא במרחב הזה של חולשות אנושיות, גילויי יצירתיות ואומץ לב תחרותי, הדמקה ממשיכה לשגשג.
הפתרון המתמטי סיפק לנו ודאות מדעית לגבי התוצאה הסופית של משחק אידיאלי, אך הדרך אל היעד נותרה מלאת חיים, יופי ומתח ספורטיבי מענג.
מורשת המשחק והיופי של החקירה האנושית
הדמקה מלמדת אותנו שיעור חשוב על היחסים בין המוח האנושי לעוצמת המחשוב. בעוד שהמחשב זקוק לטריליוני חישובים ולבסיסי נתונים כבירים כדי להגיע לוודאות, שחקנים גדולים מצליחים לנווט במרחב האינסופי הזה בעזרת אינטואיציה, הבנת מבנים עמוקה ופיתוח תוכניות אסטרטגיות אלגנטיות.
ההוכחה המתמטית של שנת 2007 אינה סוף פסוק עבור חובבי הדמקה, אלא עדות לאיזון הפנימי המופלא של המשחק. המחשב אמנם סימן את נקודת הסיום הבלתי נמנעת של משחק מושלם, אך הלוח נותר מרחב בלתי נדלה של מאבקים טקטיים, יצירתיות והנאה צרופה.
בין אם אתם לומדים כעת את חוקי הדמקה, סוקרים את שלל גרסאות דמקה בעולם, או בוחרים לשחק דמקה אונליין מול שחקנים מכל קצוות תבל, לוח הדמקה נותר כר נרחב ליצירתיות ולתחבולה. המדע הוכיח את נקודת הסיום התאורטית, אך הדרך על גבי המשבצות הכהות שייכת כולה לשחקנים.
שאלות נפוצות
האם הדמקה פתורה עבור כל שגיאה אפשרית?
לא, הדמקה האנגלית נפתרה חלש ולא חזק. ההוכחה מבטיחה אסטרטגיה לתיקו מעמדת הפתיחה התקנית בת 24 אבנים על גבי 32 משבצות כהות[1]. כמו כן, כל העמדות עם 10 אבנים ומטה פתורות במאגר 39 הטריליון. אך עמדות כאוטיות שנוצרו מסדרת שגיאות גסות בריבוי אבנים אינן ממופות במלואן.
האם שחקן אנושי יכול לנצח כיום את צ׳ינוק?
מול גרסה מלאה של צ׳ינוק המחוברת לספר הפתיחות ולמאגר הסיומים של 10 אבנים, אף אדם אינו יכול לנצח. מאחר שהוכח כי המשחק הוא תיקו, המחשב לעולם לא יפסיד. אם היריב ישחק במושלמות מלאה יסתיים המשחק בתיקו; בכל שגיאה קלה, המחשב יעניש וינצח.
האם לאבנים הכהות יש יתרון בדמקה אנגלית?
בדמקה אנגלית השחקן בעל האבנים הכהות פותח במסע הראשון. יתרון זה מאפשר מאבק על המרכז, אך הוכחתו של שפר קבעה כי אין בו די כדי לכפות ניצחון מול הגנה מדויקת[1]. במשחק מושלם משני הצדדים, יתרון הפתיחה מתפוגג בהדרגה והמשחק נחתם בתיקו.
מקורות
- Schaeffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., Lu, P., & Sutphen, S. (2007). Checkers Is Solved. Science, 317(5844), 1518–1522.
- Allis, L. V. (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. thesis, University of Limburg, Maastricht.
- Boardgammon. “Checkers Rules: How to Play, Movement, and Captures.”
- Shannon, C. E. (1950). Programming a Computer for Playing Chess. Philosophical Magazine, Ser. 7, 41(314), 256–275.
- Boardgammon. “Checkers Crown: Play Online Checkers and Regional Draughts Variants.”
- Boardgammon. “Play Checkers Online: Free Browser and Mobile Draughts.”
- Boardgammon. “Checkers Variants: The Kinds of Draughts Played Around the World.”
מצאתם טעות או ניסוח צורם? כתבו לנו
