"מחשבים משחקים שחמט בצורה יצירתית יותר מבני אדם". הצהרה פרובוקטיבית זו היתה עשויה להישמע תלושה לחלוטין מהמציאות, אך לא כאשר היא נאמרת על ידי שי בושינסקי. שי בושינסקי, מרצה לבינה מלאכותית באוניברסיטאות חיפה ותל אביב, הוא חבר בצוות הפיתוח של תוכנת השחמט "ג'וניור". תוכנת ג'וניור זכתה ביולי השנה באליפות העולם לשחמט ממוחשב, כפי שגם עשתה בשנים 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, הגיעה רק למקום השלישי תוכנה של הוועדה לאנרגיה אטומית בהולנד, שהשתמשה ברשת של שרתי חישוב מהירים).
שי בושינסקי מגדיר את האתגר של משחק שחמט כתיאום בין שלושה צירים: ציר הזמן, ציר המרחב, וציר הכוח. בהפשטה מסוימת, ניתן לומר כי הכוח הוא ספירת הכלים שעל הלוח וחוזקם היחסי (כאשר המלכה היא החזקה ביותר והרגלי הוא החלש ביותר); והמרחב הוא מספר משבצות הלוח הנשלטות על ידי כל צד. לכן, למחשב קל לראות היכן הוא נמצא בציר המרחב וציר הכוח.
ציר הזמן, לעומת זאת, היה תמיד בעיה קשה עבור מחשבים. כדי לדעת את איכות העמדה בציר הזמן, צריך לפרש את העמדה ולזהות אצל איזה צד נמצאת היוזמה. המושג השחמטאי "טמפו" קשור לניתוח ציר זה. זיהוי היוזמה הוא קשה לביצוע, וגם אינו "מדע מדויק": שחמטאים מהשורה הראשונה עשויים לתת לאותה עמדה פירושים שונים לחלוטין. למשל, פירוש אחד עשוי לראות את יתרון משמעותי ללבן, בכך שהוא ערוך לניצול הזדמנויות ולהתקפה חזקה; בפירוש אחר, שני הצדדים עדיין עוסקים בביצור עמדתם ובתמרונים, ואין יתרון יוזמה מובהק לאף צד; ובמשחקים המעניינים ביותר, יתכן כי דווקא השחור יוכל להפתיע מתוך עמדה זו כך שבמהלך הבא היוזמה תעבור לצידו.
עד לעשור האחרון, תוכנות שחמט היו חזקות במיוחד בניתוח ציר המרחב וציר הכוח. כתוצאה מכך, הן התאפיינו ב"חמדנות": ניצול הזדמנויות לשיפור באחד מצירים אלה, למשל על ידי הכאת כלים של היריב. תוכנה כזו עשויה לנצל הזנחה-לכאורה של היריב כדי להכות כלים באגף המלכה, בעוד היריב מציב את כליו באגף המלך לקראת התקפה בלתי ניתנת לעצירה. גם היכולת לצפות מספר מסעים מרשים לתוך העתיד לא תעזור אם בניית ההתקפה מתרחשת לאורך מסעים רבים. במקרה כזה, אומרים כי האיום התבטא מעבר ל"אופק החישוב" - ביטוי ציורי למספר הצעדים שהתוכנה "רואה" קדימה.
מהפך היצירתיות
תוכנות כמו ג'וניור הפכו את הקערה על פיה. הן מסוגלות לוותר בציר המרחב או ציר הכוח כדי לבנות לעצמן יוזמה חזקה, והשחקן האנושי המתמודד מולן עשוי למצוא את עצמו כחמדן יותר, וכמרחיק-ראות פחות, מאשר התוכנה שמולו. זהו הרקע לאמירתו של בושינסקי כי המחשב הפך להיות יותר יצירתי.
הפרש הוא הכלי היצירתי ביותר במשחק השחמט, כי תנועתו אינה ליניארית
אלוסטרציה: ASAP photos
הוא מביא תימוכין להצהרה זו גם ממקורות נוספים. לדוגמה, כאשר ניתח רב האמן אלון גרינפלד את המשחקים של קספארוב נגד ג'וניור, הוא זיהה חלק מהאסטרטגיה של קספארוב: לגרום לניטרול או הכאת הפרשים של ג'וניור. לדעת בושינסקי, זה אינו מקרה: "הפרש הוא הכלי היצירתי ביותר במשחק השחמט, כי תנועתו אינה ליניארית". ואכן, במשחק היחיד שבו ניצחה ג'וניור הכריע את הכף פרש של ג'וניור שנמצא בפינת הלוח (משבצת א' 1). כוחו של פרש הנמצא בפינה הוא מינימלי - הוא שולט על שתי משבצות בלבד, כלומר הוא כמעט מנוטרל ברוב המקרים. כאן הצליחה תוכנת ג'וניור למצוא את היוצא מכלל זה, ובכך להפתיע את קספארוב. קספארוב עצמו העיר על אחד המשחקים של ג'וניור נגד תוכנת "פריץ" כי התמרון שביצעה ג'וניור היה כל כך יפה ויצירתי עד כי הדרך היחידה שבה אדם עשוי להמציא תמרון כזה אינה במשחק: תמרון כזה מתאים למחברי בעיות שחמט, שראשית ממציאים רעיון ואז בונים עמדה שבה רעיון זה יכול לפעול.
כתוצאה מהיכולת של תוכנות שחמט מודרניות לזהות אפילו יתרון עמדתי זעיר ולנצל אותו לחתירה עקבית לניצחון, סיגלו לעצמם בני אדם המשחקים נגד מחשב גישה זהירה ביותר. בעשותם כן, לפי בושינסקי, הם מדכאים את היצירתיות וההרפתקנות שלהם עצמם, מה שנותן למחשב יתרון דווקא בתחום המצאת הרעיונות - תחום שבהשוואות אחרות נהוג לראותו כמפלטו האחרון של האדם.
מקורות שונים ליצירתיות
לאלה מאיתנו שאינם שחמטאים, פרטי המשחק, האסטרטגיות והטקטיקות הם פחות מעניינים מאשר השאלה איך אפשר לתכנת מחשב להגיע ליצירתיות. "לא המצאנו פטנט חדש בתחום החשיבה," אומר בושינסקי. "המחשב יודע איפה להעמיק, יודע מה הוא רואה, ויודע ללמוד. השילוב של יכולות אלה נותן אפקטיביות וגמישות". המילים "יודע מה הוא רואה" מתייחסות לניתוח העמדה, המוביל להחלטה אם כדאי להעמיק יותר בניתוח המשכים אפשריים למשחק מנקודה זו.
יוצרי ג'וניור משקיעים במיוחד ביכולת ניתוח העמדה, על ידי הכללת ממצאים תיאורטיים בתחום השחמט ועל ידי שימוש נרחב בלמידה. יכולת למידה זו היא יתרון קריטי עבור התוכנה: היא סורקת משחקים רבים ככל האפשר כדי למצות מתוכם רעיונות ולשפר את יכולת הניתוח שלה. לדוגמה, נניח כי עמדה במשחק הנסרק הוערכה על ידי התוכנה כמביאה ליתרון ללבן, אך המשחק מתפתח בשליטתו של השחור. אם לא זוהתה טעות ברורה של הלבן, תנסה התוכנה להסיק כיצד יש לשנות את ניתוח העמדה כדי להראות את ההזדמנות שזיהה השחקן השחור.
מחקרים רבים בוצעו על הדרך שבה שחמטאים בכירים אנושיים חושבים במהלך המשחק. המחקרים תומכים בהשערה כי הם אינם חושבים במונחים של כלים בודדים, אלא על ידי הכללה לתבניות המוכרות להם. היה מי שהעריך כי שחמטאים עשויים להכיר כמה עשרות אלפי תבניות, ומנסים להתאים כל עמדה לאחת מתבניות אלה. קשה מאוד להגדיר בצורה פורמלית את הדרך שבה מצב כלשהו במשחק ממופה לתבנית אחת או יותר, ובסופו של דבר נשענים הסברים כאלה על תכונה אנושית ייחודית: אינטואיציה. אין ספק כי שחקנים אנושיים משתמשים באינטואיציה לא פחות מאשר בניתוחים שהם יכולים להסביר, אך איננו מבינים מהי בעצם אינטואיציה זו (במילים אחרות, זהו מושג אינטואיטיבי...).
היכולת לפעול ברמת התבניות היא יתרון גדול לאדם: תבנית עשויה לקפל בתוכה מאות מיליונים של מצבים שונים, ובכך לקצר מאוד את תהליכי החשיבה תוך פגיעה מעטה מאוד ביכולתם. למרות זאת, זהו גם חיסרון, כאשר האדם נכשל בזיהוי ובניתוח מצבים החורגים מהמאגר המוכר לו. שחקנים אנושיים יודעים זאת היטב, ומנסים להוביל את המשחק לסיטואציות הנוחות יותר להם ופחות ליריביהם. מבט מעניין על ההבדל בין שיטות המשחק של אדם ושל מחשב, ועל האלמנטים הפסיכולוגיים בשיקולי האדם, אפשר למצוא במאמר הנגיש גם ללא-שחמטאים, שנכתב על ידי אלון גרינפלד (קישור במסגרת). מאמר זה גם מראה את המידה הרבה שבה השפיעו תוכנות השחמט על צורת האימונים והמחקר התיאורטי של אמני שחמט אנושיים.
ניסיונות לכתוב תוכנות שחמט המשתמשות בתבניות בצורה כמו-אנושית נעשו מפעם לפעם. דוגמה מוקדמת לכך היא תוכנת Pioneer שפותחה על ידי צוות בראשות מיכאיל בוטביניק (שהיה אלוף העולם רוב השנים בין 1948 ל- 1963). לבוטביניק היתה יכולת מיוחדת לתאר את תהליכי המחשבה שלו עצמו, וקידוד תיאורים אלה לתוך תוכנת מחשב הביא להצלחות מוקדמות מרשימות. למרות זאת, תוכנות כאלו לא הגיעו מעולם לצמרת עולם השחמט הממוחשב. אמיר באן, שותף לצוות ג'וניור, טוען כי שחמטאים מהשורה הראשונה לא יוכלו לפתח תוכנות שחמט טובות, בדיוק מפני שהאינטואיציה שלהם טובה כל כך. הסיבה לכך היא טבעה החמקמק של האינטואיציה, שאינו ניתן (לפחות כיום) להעתקה בתוכנת מחשב. שחמטאים חלשים יותר עשויים לכתוב תוכנה טובה יותר, כי הם נשענים על החוזק היחסי של המחשב במקום על ניסיון לחקות חשיבה אנושית. בכל מקרה, ההימנעות מההסתמכות על תבניות מאפשרת למחשבים לגלות אותם תמרונים מפתיעים, כמו במקרה המוזכר לעיל שאותו שיבח קספארוב.
קישורים
♠מאמר של ארנסט היינץ על התועלת השולית הפוחתת של חיפוש עמוק
♠אלון גרינפלד כותב על שיטות המשחק של אדם ושל מכונה