הידען - Hayadan

תכנות גנטי: כך אבולוציה במחשב מפתחת שחקן דמקה

אורן שעיה ·

Summary: נפגשתי עם עמית בן-בסט כדי לשאול אותו מה עושים שם באוניברסיטה

נפגשתי עם עמית בן-בסט כדי לשאול אותו מה עושים שם באוניברסיטה

נכון ל-2013, עמית בן-בסט (Amit Benbassat) הוא סטודנט לתואר שלישי במחלקה למדעי המחשב באוניברסיטת בן-גוריון שבנגב. הוא מבצע את עבודת הדוקטורט שלו בקבוצה של פרופ' משה זִיפֶּר (Moshe Sipper), וחוקר שימוש בתכנות גנטי (genetic programming) לפיתוח שחקנים במשחקי לוח. בזמנו הפנוי עמית כותב באתר ארגון הספקנים הישראלי, ומרצה פה ושם בנושאי מדע פופולרי.

עמית, אז מה אתם עושים שם?

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

כך עובד תכנות גנטי

איך עובד תכנות גנטי?

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

תוכל לתת דוגמא?

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

לוח דמקה מוכן למשחק
איור 1: למקרה שהגעתם מהחלל החיצון, לוח דמקה מוכן למשחק. האיור להמחשה בלבד! המקור: ויקיפדיה.

איך התוכנה מגדירה שחקן?

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

תוכל לתת דוגמא להבדלים באוכלוסיה?

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

התוכנות האלה בנויות במבנה נתונים שנקרא עץ GP, ומורכבות מאלמנטים שונים בצורה מודולרית (ראו איור 2). את האוכלוסיה ההתחלתית של לפחות מאה תוכנות או עצים אנחנו מפיקים באקראי באמצעות תוכנה שכתבנו למטרה זאת.

ביטוי אריתמטי המיוצג כעץ נתונים
איור 2: ביטוי אריתמטי המיוצג על ידי מבנה נתונים בצורת עץ. המקור: ויקיפדיה.

ברירה, מוטציה ורבייה

איך קובעים את זהות התוכנות הטובות ביותר?

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

למה אתה מתכוון? איך מיוצר הדור הבא?

ישנן שתי פעולות העוקבות אחרי תהליך הסלקציה ומטרתן לייצר שינוי באוכלוסיה. פעולה אחת נקראת מוטציה ובה נבחר באקראי תת-עץ מתוך העץ השלם המייצג את השחקן. אותו תת-עץ מוחלף בתת-עץ חדש. דוגמא למוטציה יכולה להיות החלפת תת-העץ x/11 מאיור 2, לתת-עץ שמבטא למשל x-5 (ראו איור 3). אנחנו בדרך כלל קובעים את הסיכוי למוטציה בעץ כך שבערך עשירית מהעצים יעברו מוטציה.

העץ מאיור 2 לפני ואחרי מוטציה
איור 3: העץ מאיור 2 לפני ואחרי מוטציה.

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

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

תרשים זרימה של תהליך התכנות הגנטי
איור 4: תרשים זרימה המתאר את תהליך התכנות הגנטי.

דמקה, מגבלות וגיזום

אז מה עם הדמקה?

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

נשמע נפלא, האם יש פה 'אבל' איפשהו?

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

אז מה עושים?

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

כיצד היית מסכם את היתרונות של השיטה?

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

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

זה הזמן לספר לכולם מה אתם עושים, אולי הפעם הם גם יבינו :-)

שאלות ותשובות

מהו תכנות גנטי?

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

איך קובעים אילו תוכנות יעברו לדור הבא?

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

איזה שינויים מתרחשים בין דור לדור?

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

מהי המגבלה העיקרית של השיטה בפיתוח שחקנים?

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

מה היתרון של הגיזום לפי עמית בן-בסט?

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

המאמר פורסם בבלוג של אורן שעיה "עד כדי קבוע"

עוד בנושא באתר הידען

שאלות ותשובות

מהו תכנות גנטי?

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

איך קובעים אילו תוכנות יעברו לדור הבא?

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

איזה שינויים מתרחשים בין דור לדור?

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

מהי המגבלה העיקרית של השיטה בפיתוח שחקנים?

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

מה היתרון של הגיזום לפי עמית בן-בסט?

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