צ'ינוק (תוכנה)

צ'ינוק
Chinook

מפתח	ג'ונתן שפר
מחזור חיים	1989–הווה (כ־35 שנים)
www.cs.ualberta.ca/~chinook/

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

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

אליפות העולם אדם נגד מחשב

צ'ינוק היא התוכנה הראשונה שזכתה בתואר אלופת העולם בתחרות נגד בני אדם. בשנת 1990 היא זכתה בזכות לשחק נגד אדם באליפות העולם לאחר שסיימה במקום השני אחרי מריון טינסלי באליפות ארצות הברית. אגודות הדמקה האמריקאית (ACF - American Checkers Federation) והבריטית (EDA - English Draughts Association) התנגדו בתחילה להשתתפותו של מחשב בתחרות עם בני אדם. כשטינסלי וויתר על תוארו במחאה, יצרו האגודות קטגוריה חדשה, אליפות העולם אדם נגד מחשב, והתחרות המשיכה. טינסלי ניצח ארבעה ניצחונות מול שניים של צ'ינוק, ו-33 משחקים הסתיימו בתיקו.

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

בשנת 1995 צ'ינוק הגנה על תואר האדם-מכונה שלה כנגד דון לפרטי בתחרות בת 32 משחקים. התוצאה הסופית הייתה 1-0 לטובת צ'ינוק ו-31 משחקי תיקו. לאחר התחרות, ג'ונתן שפר החליט לא לתת לצ'ינוק להתחרות עוד, ובמקום זאת לנסות לפתור את המשחק דמקה (כלומר לחשב באופן מלא מהו הצעד הטוב ביותר בכל מצב). באותו הזמן היא הייתה בעלת מד כושר 2814.

אופן הוכחת הפתרון

צ'ינוק משחקת גרסת דמקה הקרויה דמקה אנגלית או דמקה אמריקאית. בגרסה זו הלוח הוא של 8 על 8 משבצות, ומשחקים ב-24 אבנים. לגרסה זו של המשחק כ-10²⁰ מצבי לוח אפשריים.

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

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

אבני דרך

• 1997 - ג'ונתן שפר כותב ספר אודות צ'ינוק: קפיצה אחת קדימה: קריאת תגר על עליונות בני האדם בדמקה (One Jump Ahead: Challenging Human Supremacy in Checkers) מהדורה מעודכנת פורסמה בנובמבר 2008.
• 24 במאי 2003 - צ'ינוק משלימה מאגר של כל מצבי הלוח בעלי 10 אבנים, 5 אבנים בכל צד, כשכל מצב כזה פתור, כלומר האסטרגיה הטובה ביותר ידועה עבורו.
• 2 באוגוסט 2004 - צוות הצ'ינוק מכריז שמהלך הפתיחה המכונה הרופא הלבן (White Doctor, 10-14 22-18 12-16) נפתר, והוכח שהוא מוביל לתיקו לכל הפחות.
• 18 בינואר 2006 - צוות הצ'ינוק מכריז שמהלך הפתיחה 09–13 21-17 05-09 נפתר, והוכח שהוא מוביל לתיקו לכל הפחות.
• 18 באפריל 2006 - צוות הצ'ינוק מכריז שמהלך הפתיחה 09–13 22-17 13-22 נפתר, והוכח שהוא מוביל לתיקו לכל הפחות.
• 10 במרץ 2007 - ג'ונתן שפר מודיע (בכנס ACM SIGCSE 2007) שהפתרון המלא לדמקה צפוי בעוד 3–5 חודשים.
• 19 ביולי 2007 - כתב העת Science מפרסם את מאמר צוותו של שפר "דמקה נפתרה" (Checkers Is Solved). במאמר מוצגת הוכחה ששחקן המשחק נגד צ'ינוק יוכל להשיג לכל היותר תיקו.

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

• אתר האינטרנט הרשמי של צ'ינוק