סיקור מקיף

הרובוט שפתר קוביה הונגרית בשתי שניות, הוא תוצר של 60 שנות מחקר בתחום הבינה המלאכותית

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

הרובוט  Cubestormer 3  פותר את הקוביה ההונגרית בשתי שניות. צילום: ARM
הרובוט Cubestormer 3 פותר את הקוביה ההונגרית בשתי שניות. צילום: ARM

לפני כחודשיים ביקשה חברת ARM, שהשבבים שלה עומדים בבסיס טלפונים סלולארים וטבלטים רבים להדגים את מהירות השבבים של סמסונג המבוססים על הטכנולוגיה שלה ואשר מניעים את שמונה הליבות של טלפוני גלקסי S4 (שהוחלף בינתיים ב-S5) באמצעות פתרון של הפאזל התלת ממדי המוכר לכולנו בשם "קוביה הונגרית" (Rubik's Cube).

המהנדס הראשי של ARM, דייויד גילדאי והשותף שלו מייק דובסון, מהנדס מערכות ביטחון ב-Securi-Plex. אחראים לרובוט Cubestormer 3 , שתוכנן לפתור את הקוביה בזמן מרשים של 3.253 שניות. השניים עבוד על הפרויקט בזמנם החופשי. הם היו גם אחראים על השיא הקודם 5.27 שניות שהשיג רובוט קודם – Cubestormer 2 בשנת 2011.
Cubestormer 3 מונע על ידי גרסת שמונת הליבות של מכשיר גלקסי S4, המכיל צמד מעבדי Cortex-A7 CPUs וארבעה מעבדי Cortex-A15. המכשיר התבונן בקוביה, חישב את הצעדים שנדרשים כדי לפתור אותה ושלח את ההוראות לארבע זרועות רובוטיות. ההתקן השתמש במעבדי ARM9 בשמונת לבני הלגו Mindstorm EV3, דבר שסייע לבקרה וסידר ברצף את הפעולות.

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

השיא העולמי לפותר קוביה הונגרית אנושי עומד על 5.5 שניות ומחזיק בו מאטס ואלק מהולנד. "אף כי הזמן קרוב יחסית לשיא של Cubestormer 2 משנת 2011, הוא רחוק משמעותית מהשיא החדש, ואם לא יהיה שינוי משמעותי באבולוציה האנושית, איך סיכוי שהוא יישבר בזמן הקרוב." אמר.
כמובן שלבני האדם נותרו אתגרים אחרים, למשל השיא בפתרון קוביה בגודל 7 על 7 עומד על 2 דקות ו-39 שניות.
"ידענו שלרובוט ה-CUBESTORMER 3יש את הפוטנציאל לשבור את שיא גינס העולמי ואת ההישג של הדור הקודם שלו, למרות שקיים סיכון מסוים בכך שהפעולות הפיזיות של הרובוט מהירות יותר ממה שהעין האנושית מסוגלת לקלוט", מציין גילדאי. "בסופו של דבר, השעות הרבות שהושקעו בפיתוח הרובוט והשיפור המתמיד ביכולותיו המוטוריות והטכנולוגיות השתלמו. האתגר המשמעותי שעומד לפתחנו כרגע הוא לנסות ולשפר את מהירות הרובוט אפילו יותר".

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

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

הקוביה ההונגרית הומצאה בסוף שנות השבעים והפכה לצעצוע פופולרי בשנות השמונים. עד 1982 היא כבר הפכה למוקד עניין לחוקרי אינטלגנציה מלאכותצית. בשנת 1997 הראה ריצ'ארד קורף כי המספר הנמוך ביותר של צעדים הנדרש לפתור קוביה הונגרית המסודרת בצורה אקראית הוא לפחות 20.
בשנת 2010 הראו מספר חוקרים כי ניתן לפתור כל סידור של הקוביה ההונגרית בלא יותר מ-20 צעדים. עבודת חישוב זו דרשה 35 שנות עיבוד של CPU . בכך הסתיימו להם 30 שנות מחקר בתחום התבונה המלאכותית שהוקדשו לחיפוש אחר מינימום ומקסימום הצעדים הנדרשים כדי לפתור קוביה הונגרית.

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

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

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

שיתוף ב print
שיתוף ב email
שיתוף ב whatsapp
שיתוף ב linkedin
שיתוף ב twitter
שיתוף ב facebook

10 תגובות

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

  2. אני חושב שזה לא הוגן להשוות בין רובוט בעל 4 ידיים לבן אדם בעל 2 ידיים מעניין איזו תוצאה היה משיג רובוט בעל 2 ידיים לעומת בן אדם …..

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

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

כתיבת תגובה

האימייל לא יוצג באתר.

לוגו אתר הידען
דילוג לתוכן