האדם נגד המכונה

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

תיקו טוב מניצחון?

הישג ידוע אף יותר של ג'וניור הוא התיקו שהשיגה בקרב נגד אלוף העולם האנושי גארי קספארוב בשנת 2003. למרות שקספארוב כבר הפסיד לתוכנת שחמט אחרת – "כחול עמוק" של חברת IBM – בשנת 1997, מוסכם בקהילת השחמט כי הישגה של ג'וניור מרשים הרבה יותר.

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

מגבלות הכוח

בהשוואה לתוכנות השחמט של היום, "כחול עמוק" נחשבת למהירה מאוד אך לא חכמה במיוחד. בזמן הקרב ב-1997, יכלה התוכנה לבדוק 200,000,000 עמדות שחמט שונות בכל שנייה. מהירות מסחררת זו הושגה על ידי מהנדסי IBM דרך בניית חומרה מיוחדת עבור משחקי שחמט, והפעלת מספר רב של מעבדים חישוביים. לעומתה, פעלה ג'וניור ב- 2003 על מחשב שולחני רגיל, שהותקנו בו ארבעה מעבדים, ובדקה "רק" 3,000,000 עמדות בשנייה.

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

עד ארבעה מסעים קדימה

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

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

לפסול מסעים טפשיים

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

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

המרחק לעתיד

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

בשנת 2000 הראה פרופ' ארנסט היינץ (Heinz) כי ההשערה של קמבל אינה נכונה – מה שכבר היה אפשר לנחש מתוך כישלונה של ההשערה לנבא את תוצאות המשחקים נגד קספארוב. הוא הריץ מספר רב של קרבות שבהם שיחקה בכל צד אחת מהתוכנות המובילות בעולם השחמט – "פריץ". 

היתרון למרחיק הראות

בכל משחק הוא אִפשר לצד אחד לראות X מהלכים קדימה ולצד היריב לראות 1+X מהלכים קדימה. כצפוי, לשחקן "מרחיק הראות" יש סיכוי רב יותר לנצח. עם זאת, התועלת השולית הלכה ופחתה: כאשר X נמוך, צפייה של מהלך אחד יותר קדימה מעלה בהרבה את סיכויי הזכייה.

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

ניתוח תלת-ממדי

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

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

תיאום בין שלושה צירים

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

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

שחור או לבן

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