ישראלים המציאו אלגוריתם שחמט המחקה את האבולוציה

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

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

• עוד בידען: מתברר ששני חלקיקים אכן יכולים להתאבך זה עם זה
  

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

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

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

עוד בידען: הטיגריסים באסיה בסיכון גבוה

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

למה לי לבצע תהליך כזה במחשב?

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

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

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

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

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

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

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

עוד בידען: תאים מלאכותיים מצליחים לזוז

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

המחקר הבא: המשותף בין בני אדם ועכברים

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

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

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