אבולוציה בשחור-לבן

מאת: אומיד דויד, משה קופל ונתן נתניהו

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

חיפוש והערכה

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

 איור: דנה גוטליב

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

כפי שאפשר להבין מן התיאור, הליך החיפוש קשור למרכיב החישובי של התוכנה, ואילו ההערכה מבטאת את הידע וההבנה בשחמט. אלגוריתמים יעילים לחיפוש מצבים בעץ הם נפוצים ביותר (תוכלו למצוא השוואה בין כמה אלגוריתמי חיפוש בספר Computers, Chess and Cognition, המופיע ברשימה לקריאה נוספת שבסוף המאמר), והקושי העיקרי הוא ליצור פונקצית הערכה טובה. מכיוון שפונקצית ההערכה משקפת למעשה את הידע והבנת המשחק של התוכנה, היא המרכיב המכריע ביותר.

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

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

אלגוריתמים גנטיים

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

כדי להחיל אלגוריתם גנטי על בעיה, יש אפוא לייצג אותה תחילה ככרומוזום. לדוגמה, אם הבעיה כוללת חמישה פרמטרים, ובכל פרמטר יש 10 דרגות איכות (למשל, המלך מאוים בין רמה של 1 לרמה של 10). אז הבעיה תיוצג על-ידי כרומוזום באורך 50 סיביות, 10 סיביות לכל פרמטר. הצעד הבא הוא יצירת אוכלוסייה של כרומוזומים מאותחלים אקראית (כלומר, הסיביות של כל כרומוזום נקבעות כ-0 או 1 באופן אקראי). בשלב זה, יש אוכלוסייה של "אורגניזמים" (כל כרומוזום מייצג אורגניזם אחד). אוכלוסייה זו עוברת אבולוציה במשך כמה דורות, באופן הבא: בכל דור, מיוחס לכל אורגניזם ערך המציין כמה הוא "מתאים" (fit). עם סיום דור, כל אורגניזם מזווג ביחס לערך ההתאמה שלו. במילים אחרות, האורגניזם המתאים ביותר יהיה בעל הסיכוי הגבוה ביותר לשרוד ולהעמיד צאצאים.

איור: דנה גוטליב 

 איור: דנה גוטליב

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

איך מחשבים את ערך ההתאמה?

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

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

- צרו רשימה של בעיות אקראיות (במקרה של שחמט – מצבים).

- לכל בעיה, תנו למנחה להעריך את הבעיה ושמרו את התוצאה.

- תנו לכל אורגניזם להעריך את כל הבעיות, וחשבו – על פני כל הבעיות – את ההפרש הממוצע בין הערך שנותן האורגניזם ובין הערך שנותן המנחה. ערך ההתאמה הוא בפרופורציה הפוכה להפרש בין הערכים.

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

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

החוקרים יצרו אוכלוסייה התחלתית של 1,000 אורגניזמים (שכל אחד מהם היה עותק של מאסטרו עם ערכי אתחול אקראיים), והעבירו אותה אבולוציה של 300 דורות. בכל דור, כל אורגניזם העריך 5,000 מצבים, וציוני ההערכה הושוו לאלה של המנחה, פלקון, לאותם מצבים. בתום כל דור, ניתן לאורגניזמים שציונם היה קרוב ביותר לזה של פלקון סיכוי גבוה יותר להזדווג. לאחר 300 דורות, היה הציון שנתן השורד הטוב ביותר קרוב מאוד לזה של פלקון. במילים אחרות, הגישה מסתייעת-המנחה הצליחה לחולל אבולוציה מתוכנה חסרת כל ידע בשחמט לתוכנה שציונה קרוב מאוד לזה של תוכנת שחמט מן המובילות בעולם. איור 4 מראה כמה מהר מצליח האורגניזם המתפתח לחקות את המנחה.

איור: דנה גוטליב 

כדי למדוד את חוזק משחקה של התוכנה מאסטרו לאחר שעברה אבולוציה, נערכו 1,800 משחקים. מאסטרו לאחר אבולוציה ניצחה את פלקון, המנחה שלה, ב-50% מהמשחקים, מה שמעיד על כך שההנדסה-לאחור של פלקון הצליחה עד כדי כך שהשתיים הפכו למעשה שוות בחוזקן. כמו כן, מאסטרו לאחר אבולוציה ניצחה ב-58% מהמשחקים כנגד קראפטי (Crafty), גרסת המשך של קריי בליץ (Cray Blitz) של רוברט הייאט (Hyatt), פעמיים אלופת העולם בשחמט-מחשב.

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

המאמר מופיע בגיליון יולי של המגזין "גליליאו "

לקריאה נוספת:

C. Darwin, On the Origin of Species by Means of Natural Selection, John Murray, 1859.

T.A. Marsland and J. Schaeffer, Computers, Chess, and Cognition, Springer-Verlag, 1990.

J.H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975.

D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.

O. David, M. Koppel, and N.S. Netanyahu, Genetic Algorithms for Mentor-Assisted Evaluation Function Optimization, (to appear) in Proceedings of the ACM Genetic and Evolutionary Computation Conference, Atlanta, GA, July 2008.