נפגשתי עם עמית בן-בסט כדי לשאול אותו מה עושים שם באוניברסיטה
עמית הוא סטודנט לתואר שלישי במחלקה למדעי המחשב באוניברסיטת בן-גוריון שבנגב. הוא מבצע את עבודת הדוקטורט שלו בקבוצה של פרופ’ משה זִיפֶּר, וחוקר שימוש בתכנות גנטי לפיתוח שחקנים במשחקי לוח. בזמנו הפנוי עמית כותב באתר ארגון הספקנים הישראלי, ומרצה פה ושם בנושאי מדע פופולרי.
עמית, אז מה אתם עושים שם?
קבוצת המחקר שלנו עוסקת במגוון נושאים הקשורים לאלגוריתמים אבולוציוניים שהוא תחום במדעי המחשב ששייך לבינה מלאכותית. הכוונה באלגוריתמים אבולוציוניים היא יצירת סימולציה מופשטת של תהליך אבולוציה בברירה טבעית במחשב כדי לייצר פתרונות טובים יותר לבעיות. אני עובד בתת-תחום שנקרא תכנות גנטי.
איך עובד תכנות גנטי?
הצעד הראשון הוא לייצר אוכלוסיה התחלתית של תוכנות שפותרות בעיה מסוימת, למשל איך לשחק טוב משחק לוח. האסטרטגיה שלנו היא בדרך כלל לשפר בתהליך אבולוציה רק חלק של התוכנה שנמצא בתוך מעטפת שאינה משתנה. החלק שעובר את תהליך האבולוציה הוא מה שמבדיל בין הפרטים באוכלוסיה.
תוכל לתת דוגמא?
כן, קח למשל את משחק הדמקה. חלק התוכנה שאנחנו משפרים באבולוציה הוא זה שמזהה את מצב הלוח ומחזיר מספר. ‘מצב הלוח’ מתאר מצב חוקי יחיד של המשחק, ובדמקה יוגדר על ידי מספר, סוג ומיקום הכלים על הלוח, ומי הבא בתור לשחק. תוכנת המעטפת תהיה אלגוריתם חיפוש כלשהוא.
איך התוכנה מגדירה שחקן?
על ידי הגדרת אסטרטגיית המשחק שלו. אותו שחקן יכול להשתמש בתוכנה כדי לבדוק את המצב בו הוא נמצא כרגע, ולהשוות אותו בדמיונו הממוחשב למצבים הנובעים מכל המהלכים החוקיים האפשריים. אותו שחקן יכול כעת לבחור את המצב שקיבל את הציון הטוב ביותר. אם נרצה שחקן טוב יותר, נוכל לדרוש ממנו לבצע בדיקות גם עבור מספר מהלכים קדימה. המחיר הוא זמן ריצה, והוא גדל באופן מעריכי.
תוכל לתת דוגמא להבדלים באוכלוסיה?
כן, למשל תוכנה אחת באוכלוסיה יכולה לנקד מצב לוח על ידי ההפרש בין מספר הכלים של שני השחקנים. אם ההפרש גדל לטובתי, אני מרוצה כי כנראה אכלתי כלי של היריב. תוכנה אחרת באוכלוסיה יכולה לנקד מצב לוח על פי אותו עיקרון אך להוסיף סייג שמלך שווה יותר בספירה.
התוכנות האלה בנויות במבנה נתונים שנקרא עץ GP, ומורכבות מאלמנטים שונים בצורה מודולרית (ראו איור 2). את האוכלוסיה ההתחלתית של לפחות מאה תוכנות או עצים אנחנו מפיקים באקראי באמצעות תוכנה שכתבנו למטרה זאת.
איך קובעים את זהות התוכנות הטובות ביותר?
כפי שקלישאת הכדורגל אומרת, הטבלה לא משקרת. כדי לקבוע מי הן התוכנות המוצלחות (בעגה ה-fitness) אנחנו מקיימים טורניר בין הפרטים באוכלוסיה. התוכנות מקבלות נקודה עבור כל ניצחון, וחצי נקודה על תוצאת תיקו. ככל שתוכנה נמצאת במקום גבוה יותר בטבלה, כך סיכוייה להיבחר לדור הבא גבוהים יותר. לדוגמא, אם יש לנו אוכלוסיה של מאה פרטים, אנחנו נבחר מאה פרטים שירכיבו את הדור הבא. כל תוכנה יכולה להיבחר יותר מפעם אחת, ולכן התוכנות במיקום גבוה בטבלה יבחרו מספר רב של פעמים על חשבון תוכנות במיקום נמוך. ממאה התוכנות שנבחרו בסוף התהליך ניצור את הדור הבא.
למה אתה מתכוון? איך מיוצר הדור הבא?
ישנן שתי פעולות העוקבות אחרי תהליך הסלקציה ומטרתן לייצר שינוי באוכלוסיה. פעולה אחת נקראת מוטציה ובה נבחר באקראי תת-עץ מתוך העץ השלם המייצג את השחקן. אותו תת-עץ מוחלף בתת-עץ חדש. דוגמא למוטציה יכולה להיות החלפת תת-העץ x/11 מאיור 2, לתת-עץ שמבטא למשל x-5 (ראו איור 3). אנחנו בדרך כלל קובעים את הסיכוי למוטציה בעץ כך שבערך עשירית מהעצים יעברו מוטציה.
הפעולה השניה נקראת קרוס-אובר (crossover) והיא מדמה רבייה מינית. אנחנו בוחרים שני עצים, ובתוך כל עץ בוחרים באקראי תת עץ. כעת אנחנו מבצעים אחת משתי האפשריות הבאות: מחליפים בין שני תתי-העצים, או מחליפים את תת-העץ בעץ שהצליח פחות טוב בטורניר בתת-העץ מהעץ שהצליח יותר.
אחרי שלבי המוטציה והקרוס-אובר, מתקבלת אוכלוסיה המורכבת ממאה פרטים חדשים שנקראים דור 1 (האוכלוסיה ההתחלתית נקראת דור 0). לקבלת דור 2 נחזור על התהליך: ליגה, סלקציה ורבייה (מוטציה וקרוס-אובר), וכך הלאה עד למספר דורות שנקבע מראש (ראו איור 4). את רמת השחקנים נקבע אובייקטיבית על ידי משחק נגד שחקן חיצוני שאנחנו כתבנו ללא אלגוריתם תכנות גנטי. סוף התהליך הוא חיפוש השחקן הטוב ביותר בכל הדורות.
אז מה עם הדמקה?
אחד הדברים הראשונים שעשיתי בעזרת תכנות גנטי היה לכתוב שחקן למשחק דמקה הפוכה, וזאת מבלי להיות מומחה גדול במשחק. נתתי לאבולוציה לעשות את העבודה במקומי. בהמשך הראיתי שניתן להשתמש בתהליך גם לדמקה רגילה ומשחקים נוספים. התכנות הגנטי אפשר לי לכתוב שחקנים מוצלחים למשחקים שונים ללא צורך בהשקעת מאמץ רב נוסף על זה שכבר השקעתי.
נשמע נפלא, האם יש פה ‘אבל’ איפשהו?
תראה, יש להבין שאנחנו מאוד מוגבלים במספר המהלכים קדימה שאנחנו מאפשרים לשחקנים לחשב. עבור מספר גדול של מהלכים לא נוכל לסיים את הטורנירים של תהליך הסלקציה בזמן סביר מכיוון שזמן הריצה גדל, כאמור, באופן מעריכי. ניתן גם להראות שאם ייצרנו שחקן בתהליך אבולוציה שבו היתה בדיקה של מספר מסוים של מהלכים קדימה, לא נוכל לשפר משמעותית את איכותו בצורה פשוטה על ידי הגדלת מספר הצעדים קדימה שהוא בודק. כלומר המוצר הסופי אופטימלי לתנאים בהם הוא נוצר.
אז מה עושים?
מנסים להתחכם. נניח שבמצב לוח מסוים כל מהלך קדימה מוביל לעשר אפשריות פעולה. במידה ונבדוק רק חמש מהן עבור כל מהלך, נוכל להרשות לעצמנו לבדוק יותר מהלכים קדימה. כדי לבחור את חמש האפשריות הטובות מבין העשר נוכל להשתמש בשחקן שרואה רק מהלך אחד קדימה. תהליך זה נקרא בעגה המקצועית pruning, כלומר גיזום. במהלך המחקר הצלחנו להראות שבעקבות הגיזום אנחנו מרוויחים פעמיים. ראשית, השחקנים האלה טובים יותר, ושנית ניתן לשפר אותם ישירות על ידי הקטנת הגיזום, למשל בדוגמא כאן לבחור שבע אפשריות מתוך עשר במקום חמש, ללא תהליך אבולוציה נוסף.
כיצד היית מסכם את היתרונות של השיטה?
התכנות הגנטי מאפשר ללמוד ולהשתפר במשחק, מבלי בעצם לדעת עליו דבר מלבד למהלכים הבסיסיים. השיטה היא גנרית ומותאמת בקלות לבעיות שונות, והיא יכולה להצליח גם בפתרון בעיות שבהן ההיגיון האנושי אינו מהווה יתרון.
——————————————————————
אני אשמח להפגש ולשוחח עם כל תלמיד מחקר (אולי אתם?) שמוכן להשתתף ולספר לי קצת על מה הוא עושה (והכול במחיר של שיחה לא יותר מידי ארוכה). תוכלו ליצור איתי קשר דרך טופס יצירת קשר.
זה הזמן לספר לכולם מה אתם עושים, אולי הפעם הם גם יבינו 🙂
אני אשמח להפגש ולשוחח עם כל תלמיד מחקר (אולי אתם?) שמוכן להשתתף ולספר לי קצת על מה הוא עושה (והכול במחיר של שיחה לא יותר מידי ארוכה). תוכלו ליצור איתי קשר דרך טופס יצירת קשר.
זה הזמן לספר לכולם מה אתם עושים, אולי הפעם הם גם יבינו
המאמר פורסם בבלוג של אורן שעיה “עד כדי קבוע“
