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

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

מ-PSPACE ל-RE-Complete: קפיצה אדירה במורכבות

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

עם זאת, עבודה שנערכה לאחרונה על ידי צוות סטודנטים — Hayashi Ani, Holden Hall, Ricardo Ruiz, ו-Naveen Venkat — ניפצה את ההנחה הזו. באמצעות שימוש בעורכי שלבים וב-Super Mario Maker, החוקרים בנו שלבים ספציפיים שהם RE-Complete. המשמעות היא שהמשחק נכנס לתחום של בעיות בלתי ניתנות להכרעה (undecidable problems). בתרחישים ספציפיים אלו, בלתי אפשרי מבחינה מתמטית לכתוב תוכנית מחשב שתמיד תוכל לחזות במדויק האם מריו יוכל להגיע בהצלחה לתורן או לטירה.

הקשר לבעיית העצירה (Halting Problem)

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

צוות המחקר מ-MIT יישם את הלוגיקה הזו על ממלכת הפטריות (Mushroom Kingdom) באמצעות טכניקה הנקראת רדוקציה (reduction). על ידי פירוק שלב בסופר מריו לרכיבים מקומיים המכונים "גאדג'טים" (gadgets), החוקרים הצליחו לסמלץ לוגיקה חישובית מורכבת בתוך מכניקת המשחק. הגאדג'טים הללו פועלים כשערים לוגיות; כאשר הם מסודרים בתבניות ספציפיות של צינורות, פלטפורמות ואויבים כמו Goombas או Spinies, הם יכולים לשקף את ההתנהגות של מכונת טיורינג. כתוצאה מכך, קביעה האם מריו מגיע לסוף השלב הופכת לזהה פונקציונלית לקביעה האם תוכנית מורכבת תעצור אי פעם.

מדוע זה חשוב לעתיד הבינה המלאכותית והמחשוב

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

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

נקודות מפתח

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