Game AI (בינה מלאכותית במשחקים)

שני מובנים שונים ל"בינה מלאכותית" במשחק

המילה "בינה מלאכותית" מופיעה בהקשר של משחקים בשני מובנים שונים, וחשוב להפריד ביניהם. לפי הערך "⁦Artificial intelligence in video games⁩" בוויקיפדיה, "בינה מלאכותית אקדמית, שמטרתה לפתח היגיון או למידה אוטונומיים, נבדלת מבינה מלאכותית במשחקים" (⁦academic AI—aimed at developing autonomous reasoning or learning—is distinct from game AI⁩), שמטרתה "התנהגות מרתקת, אמינה ויעילה בשביל השחקנים", ולפי אותו ערך היא מורכבת לרוב מ"חצי תריסר כללי אגודל, או היוריסטיקות, שמספיקים בדיוק כדי לתת חוויית משחק טובה" (⁦a half-dozen rules of thumb, or heuristics, that are just enough to give a good gameplay experience⁩). זה ה-⁦Game AI⁩ שהקטגוריה הזאת מתייחסת אליו ברוב ערכיה: הרוחות של ⁦Pac-Man⁩, הדמויות ב-⁦Left 4 Dead⁩, היריב במשחק מירוץ. למובן השני קוראים כאן "מחשב שמשחק נגד אדם או לומד לשחק" — למשל ⁦Deep Blue⁩, שניצח את אלוף העולם בשחמט, ו-⁦AlphaGo⁩, שלמד לשחק גו. אלה מערכות שהמטרה שלהן היא לנצח במשחק, ולפעמים יש בהן למידת-מכונה אמיתית. שני המובנים חולקים את המילה "בינה מלאכותית", אבל לא את השיטה ולא את המטרה.

מכונת מצבים סופית: אבן הבניין הבסיסית

אחת הטכניקות הפשוטות והנפוצות ביותר ל-⁦Game AI⁩ היא מכונת מצבים סופית (⁦finite-state machine⁩, ⁦FSM⁩). לפי ויקיפדיה, FSM "ממדלת דמות לא-שחקן (⁦NPC⁩) כמצב אחד בכל רגע נתון, כמו תקיפה או סיור" (⁦models an NPC as one state at a time, such as attacking or patrolling⁩). שומר במשחק התגנבות, למשל, יכול להיות במצב "סיור", ולעבור למצב "חקירה" כששומע רעש, ולמצב "תקיפה" כשהוא רואה את השחקן. כל מעבר בין מצבים נקבע מראש בידי המתכנת: אם קורה X, עבור למצב Y. השיטה קלה לבנייה ולהבנה, אבל לפי אותו מקור, "FSM כאלה קלות לבנייה אבל מתקשות להתרחב כשמספר ההתנהגויות גדל" (⁦these FSMs are simple to build but become difficult to extend as the number of behaviors grow⁩): כל התנהגות חדשה שמתכנת מוסיף מוסיפה עוד מעברים שצריך להגדיר בין המצבים הקיימים.

עץ התנהגות: כש-FSM לא מספיקה

כדי להתמודד עם המגבלה הזאת פותחו עצי ההתנהגות (⁦behavior tree⁩), ששייכים גם לרובוטיקה ומוסברים כאן בערך נפרד. ההבדל המרכזי מ-FSM: אבן הבניין של עץ ההתנהגות היא משימה (⁦task⁩), לא מצב, והמשימות מסודרות בעץ היררכי שבוחר בכל רגע מה לנסות קודם. לפי ויקיפדיה, עצי התנהגות "שימשו בהרחבה במשחקי וידאו מוכרים" (⁦have been extensively used in high-profile video games⁩) כמו ⁦Halo⁩, ⁦BioShock⁩ ו-⁦Spore⁩, והערך מפנה להרצאה מ-2005 על ה-AI של ⁦Halo 2⁩, המשחק של ⁦Bungie⁩ מ-2004. במקום לכתוב מראש כל מעבר אפשרי בין "סיור" ל"תקיפה", המתכנת מגדיר רשימת משימות מדורגת לפי עדיפות, והעץ בודק אותן שוב ושוב לפי סדר החשיבות, ומפעיל את הראשונה שאפשר לבצע כרגע — כך קל יותר להוסיף התנהגות חדשה בלי לשכתב את כל הקודמות.

למצוא דרך במפה: ניווט וחיפוש מסלולים

בעיה אחרת שכל דמות שזזה במשחק צריכה לפתור היא ניווט: איך להגיע מנקודה א' לנקודה ב' בלי להיתקע בקיר. אחד האלגוריתמים הנפוצים ביותר לכך, ⁦A*⁩ (נקרא "⁦A-star⁩"), פורסם לראשונה ב-1968 בידי פיטר הארט, נילס נילסון וברטרם רפאל ממכון המחקר של סטנפורד (⁦Stanford Research Institute⁩, כיום ⁦SRI International⁩), במסגרת פרויקט ⁦Shakey⁩ — ניסיון לבנות רובוט נייד שמתכנן את הפעולות שלו בעצמו. לפי ויקיפדיה, "⁦A*⁩ משמש לעיתים קרובות לבעיית חיפוש-המסלול הנפוצה באפליקציות כמו משחקי מחשב" (⁦A* is often used for the common pathfinding problem in applications such as video games⁩). משחקים מסחריים רבים מחלקים את המפה לרשת של משבצות, ו-⁦A*⁩ מחשב ביעילות את המסלול הקצר ביותר ביניהן, בלי לבדוק כל מסלול אפשרי — כך דמות יכולה "לדעת" לעקוף שולחן, בלי שמתכנת כתב לה את העקיפה הספציפית הזאת מראש.

ארבע האישיויות של הרוחות ב-Pac-Man

⁦Pac-Man⁩, שחברת ⁦Namco⁩ היפנית הוציאה ב-1980, הוא דוגמה מוקדמת ומוכרת במיוחד ל-⁦Game AI⁩. לפי ויקיפדיה, לכל אחת מארבע הרוחות יש "בינה מלאכותית, או 'אישיות', ייחודית משלה" (⁦unique artificial intelligence (A.I.), or "personality"⁩). לפי ניתוח מפורט של קוד המשחק (⁦The Pac-Man Dossier⁩, ⁦Jamey Pittman⁩), לכל רוח יש כלל-מיקוד קבוע: ⁦Blinky⁩ האדומה שואפת ישר למשבצת שבה ⁦Pac-Man⁩ נמצא כרגע. ⁦Pinky⁩ הוורודה שואפת לנקודה ארבע משבצות קדימה בכיוון התנועה שלו, ולכן "מארבת" לו. ⁦Inky⁩ התכולה מחשבת נקודה שתי משבצות קדימה מ-⁦Pac-Man⁩, ואז מכפילה את אורך הקו בין ⁦Blinky⁩ לנקודה הזאת — כלל שהופך אותה לקשה לחיזוי. ו-⁦Clyde⁩ הכתומה נוהגת כמו ⁦Blinky⁩ כשהיא רחוקה מ-⁦Pac-Man⁩ יותר משמונה משבצות, אבל פונה לפינה שלה כשהיא קרובה אליו יותר מזה. הרוחות גם מתחלפות במחזוריות קבועה בין מצב "מרדף" (⁦chase⁩), שבו כל אחת פועלת לפי כלל-המיקוד שלה, לבין מצב "פיזור" (⁦scatter⁩), שבו כל אחת נסוגה לפינה שלה במבוך. אין כאן שום למידה: ארבעה כללי חשבון קבועים הם שגורמים לרוחות להיראות כאילו יש להן אופי.

AI שמנהל את כל המשחק: ה-Director של Left 4 Dead

לא כל ⁦Game AI⁩ שולט בדמות בודדת. ⁦Left 4 Dead⁩ (2008), שפיתח הסטודיו ⁦Turtle Rock Studios⁩ (שנקרא אז ⁦Valve South⁩) ופרסמה ⁦Valve⁩, הציג מערכת בשם "⁦Director⁩" שמנהלת את כל המשחק: לפי ויקיפדיה, זו "מערכת דינמית לדרמה, לקצב ולרמת הקושי של המשחק" (⁦a dynamic system for game dramatics, pacing and difficulty⁩), בלי נקודות-הופעה קבועות — במקום זה היא מחליטה כמה אויבים ופריטים להציב, ואיפה, לפי מצבו, מיקומו ומיומנותו של כל שחקן בזמן אמת, כדי לשמור על מתח גבוה ולהפוך כל משחק לחוויה שונה. היא גם משתמשת באפקטים חזותיים, במוזיקה דינמית ובדיאלוג של הדמויות כרמזים רגשיים. ⁦Gabe Newell⁩ מ-⁦Valve⁩ תיאר את זה כך, בטור שכתב למגזין ⁦Edge⁩: "⁦This is what makes procedural narrative more of a story-telling device than, say, a simple difficulty mechanism.⁩" ("זה מה שגורם לנרטיב הפרוצדורלי להיות יותר כלי לסיפור סיפורים, ולא רק מנגנון קושי פשוט"). זו רמה אחרת של ⁦Game AI⁩: לא דמות שמחליטה בשביל עצמה, אלא מנצח-תזמורת שמעצב את החוויה של כל המשחק.