סנייק (Snake)

פרויקט זה מממש שני אלגוריתמי בינה מלאכותית (AI) לשחק במשחק הסנייק (נחש):

אלגוריתם	דוגמה	אורך ממוצע*	אחוז הצלחה*
חיפוש בגרף (Graph Search)		35.86	94%
למידת חיזוקים (Reinforcement Learning)		29.33	50%

* אורך ממוצע: האורך הממוצע של הנחש לפני שהמשחק מסתיים. המשחק מסתיים כאשר הנחש פוגע בעצמו או בקיר, או אוכל את כל המזון ומגיע לאורך המרבי. לוח המשחק הוא בגודל 6x6, ולכן האורך המרבי הוא 36. הממוצע מחושב על פני 1000 סיבובים.

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

התקנה

הפרויקט דורש Python מגרסה 3.10 ומעלה. ראשית, צרו סביבה וירטואלית:

python3 -m venv venv
source venv/bin/activate

התקינו את תלויות החובה (dependencies):

pip3 install -r requirements.txt

שחקו במשחק עם אלגוריתם חיפוש בגרף (הוסיפו -h כדי לראות את כל האפשרויות הנתמכות):

python3 main.py

אופציונלי: כדי לשחק במשחק עם למידת חיזוקים או כדי לאמן את מודל למידת החיזוקים, אנא התקינו את PyTorch בהתאם להעדפת ה-CPU/GPU שלכם. התוכנית תומכת גם ב-CPU וגם ב-GPU. הריצו את הפקודה להלן כדי לשחק במשחק עם למידת חיזוקים:

python3 main.py -m rl

מודל למידת החיזוקים המאומן מראש זמין כאן. הריצו את הפקודה להלן כדי לאמן מודל משלכם:

python3 rl_train.py

אלגוריתמים

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

חיפוש בגרף (Graph Search)

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

1. אם הנחש ארוך מספיק, האלגוריתם מחפש מסלול המילטוני (Hamiltonian path) מראש הנחש לזנבו. אם המסלול קיים, הנחש יכול לנוע בבטחה לאורך מעגל המילטוני כדי להגיע לאורך המרבי. אחרת, עוברים לשלב הבא.

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

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

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

האלגוריתם מיושם כאן.

מסלול המילטוני (Hamiltonian Path)

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

מציאת מסלול המילטוני היא בעיית NP-complete. עם זאת, עבור לוח קטן של 6x6, באמצעות נסיגה לאחור (backtracking) ויוריסטיקת וורנסדורף שמנחה את החיפוש, ניתן למצוא מסלול המילטוני בזמן סביר. האלגוריתם מחפש מסלול המילטוני רק כאשר הנחש ארוך מספיק כדי להגדיל את הסבירות למצוא כזה במהירות.

מסלול ארוך יותר (Longer path)

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

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

למידת חיזוקים (Reinforcement Learning)

למידת חיזוקים היא פרדיגמת למידת מכונה שבה סוכן (agent) לומד לקבל החלטות על ידי ביצוע פעולות בסביבה כדי למקסם תגמולים מצטברים. במשחק זה, הנחש הוא הסוכן, לוח המשחק הוא הסביבה, והפעולות הן המהלכים האפשריים. אלגוריתם הלמידה משתמש ברשת עצבית כדי לקרב את פונקציית הערך-פעולה, שמעריכה את התגמול המצטבר הצפוי עבור ביצוע פעולה מסוימת במצב נתון. הנחש לומד לשחק במשחק על ידי חקירת פעולות שונות וקבלת תגמולים על בסיס התוצאות (למשל, תגמול חיובי על אכילת מזון, תגמול שלילי על פגיעה בעצמו או בקיר). השימוש ברשתות עצביות בלמידת חיזוקים ידוע כלמידת חיזוקים עמוקה (deep reinforcement learning). להתכנסות ויציבות טובות יותר, תהליך האימון מיישם את טכניקת Double DQN.

יישום: מבנה רשת (Network Structure) | הסקה (Inference) | אימון (Training)

ייצוג המצב (State Representation)

מצבו הנוכחי של הנחש מיוצג כשני טנסורים (tensors) המחוברים יחד:

1. הטנסור הראשון הוא טנסור בגודל 6x6 עם 4 ערוצים (channels) שמוזן לשכבות קונבולוציה (convolutional layers). ארבעת הערוצים מקודדים את: 1) מיקום המזון, 2) גוף הנחש, 3) ראש הנחש, ו-4) מיקומי הסכנה (היכן שהמשחק מסתיים אם הנחש זז אליהם).

2. הטנסור השני הוא טנסור חד-ממדי (1D) הכולל את: 1) כיוון התנועה הנוכחי של הנחש, 2) הכיוון הנוכחי של המזון ביחס לראש הנחש, ו-3) מרחק מנהטן (Manhattan distance) בין ראש הנחש למזון.

הפלט משכבות הקונבולוציה והטנסור השני מחוברים ומוזנים למספר שכבות מחוברות-במלואן (fully connected layers) לקראת שכבת הפלט, המייצרת את ערכי ה-Q (Q-values) עבור כל פעולה אפשרית במצב הנוכחי.

מרחב הפעולות (Action Space)

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

תכנון התגמול (Reward Design)

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

1. אם הנחש פוגע בעצמו או בקיר, הוא מקבל תגמול שלילי גדול של -100.

2. אם הנחש אוכל חתיכת מזון אחת, הוא מקבל תגמול חיובי של +10.

3. אם הנחש מגיע לאורך המרבי, הוא מקבל תגמול חיובי גדול של +100.

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

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

רישיון

ראו את קובץ ה-LICENSE לזכויות ומגבלות הרישיון.