שימוש בבינה מלאכותית כדי לפתור את משחק 2048 (קוד JAVA)

• אפריל 7, 2014
• וסיליס ווריניוטיס
• . 6 תגובות

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

במאמר זה אדון בקצרה בגישתי לבניית פותר הבינה המלאכותית של משחק 2048, אתאר את ההיוריסטיות בהן השתמשתי ואתן את הקוד המלא אשר כתוב ב- JAVA. הקוד פתוח באמצעות רישיון GPL v3 ותוכל להוריד אותו מ GitHub.

פיתוח משחק 2048 ב- JAVA

המשחק המקורי כתוב ב- JavaScript, אז הייתי צריך לכתוב אותו מחדש ב- JAVA מאפס. הרעיון המרכזי של המשחק הוא שיש לך רשת 4 × 4 עם ערכים שלמים, כולם כוחות של 2. תאים בעלי ערך אפס נחשבים ריקים. בכל נקודה במהלך המשחק אתה יכול להזיז את הערכים לכיוון 4 כיוונים למעלה, למטה, ימינה או שמאלה. כאשר אתה מבצע מהלך כל ערכי הרשת נעים לכיוון זה והם נעצרים כאשר הם מגיעים לגבולות הרשת או כאשר הם מגיעים לתא אחר בעל ערך שאינו אפס. אם לתא הקודם יש אותו ערך, שני התאים מוזגו לתא אחד עם ערך כפול. בסוף כל מהלך נוסף ערך אקראי בלוח באחד התאים הריקים והערך שלו הוא 2 עם הסתברות 0.9 או 4 עם הסתברות 0.1. המשחק מסתיים כאשר השחקן מצליח ליצור תא בעל ערך 2048 (win) או כשאין מהלכים אחרים לבצע (להפסיד).

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

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

1. מחלקת לוח

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

2. ActionStatus וכיוון Enum

ה- ActionStatus והכיוון הם שני אינומים חיוניים המאחסנים את התוצאה של מהלך וכיוונו בהתאם.

3. Class ConsoleGame

ConsoleGame הוא המחלקה העיקרית המאפשרת לנו לשחק את המשחק ולבדוק את הדיוק של ה- AI Solver.

4. Class AIsolver

ה- AIsolver הוא המחלקה העיקרית של מודול הבינה המלאכותית אשר אחראי על הערכת המהלך הבא הטוב ביותר בהינתן לוח מסוים.

טכניקות בינה מלאכותית: גיזום מינימקס לעומת אלפא-בטא

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

אלגוריתם מינימקס

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

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

[תוכן מוטבע]

למטה תוכלו לראות פסאודוקוד של האלגוריתם של מינימקס:

פונקציה minimax (צומת, עומק, maximizing Player)
    if עומק = 0 or הצומת הוא צומת מסוף
        לַחֲזוֹר הערך ההיוריסטי של הצומת
    if maximizingPlayer bestValue: = -∞
        לכל אחד ילד של צומת ערך: = מינימום (ילד, עומק - 1, FALSE)) bestValue: = max (bestValue, val);
        לַחֲזוֹר בעל הערך הטוב ביותר
    אחר
        הטוב ביותר ערך: = + ∞
        לכל אחד ילד של צומת val: = מינימום (ילד, עומק - 1, TRUE)) bestValue: = min (bestValue, val);
        לַחֲזוֹר בעל הערך הטוב ביותר
(* קריאה ראשונית למקסום הנגן *)
מינימקס (מקור, עומק, נכון)

גיזום אלפא-בטא

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

[תוכן מוטבע]

להלן תוכלו לראות את הפסאודוקוד של האלגוריתם הגיזום Alpha-beta:

פונקציה אלפביתית (צומת, עומק, α, β, maximizing Player)
    if עומק = 0 or הצומת הוא צומת מסוף
        לַחֲזוֹר הערך ההיוריסטי של הצומת
    if מקסימום שחקן
        לכל אחד ילד של הצומת α: = מקסימום (α, אלפבית (ילד, עומק - 1, α, β, FALSE))
            if β ≤ α
                לשבור (* ß מנותק *)
        לַחֲזוֹר α
    אחר
        לכל אחד ילד של צומת β: = דקה (β, אלפבית (ילד, עומק - 1, α, β, TRUE))
            if β ≤ α
                לשבור (* α מנותק *)
        לַחֲזוֹר β
(* שיחה ראשונית *)
אלפביתית (מקור, עומק, -∞, + ∞, TRUE)

כיצד AI משמש לפתרון המשחק 2048?

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

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

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

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

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

פיתוח פונקציית ניקוד היוריסטית

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

private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
     int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
     return Math.max(score, Math.min(actualScore, 1));
}

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

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

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

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

עוד על ציון האשכולות

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

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

ציון האשכולות כולל את התכונות הבאות:

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

דיוק האלגוריתם

כצפוי הדיוק (aka אחוז המשחקים שזכו) באלגוריתם תלוי מאוד בעומק החיפוש בו אנו משתמשים. ככל שעומק החיפוש גבוה יותר, כך רמת הדיוק גבוהה יותר ונדרש זמן רב יותר לרוץ. בבדיקות שלי, חיפוש עם עומק 3 נמשך פחות מ -0.05 שניות אך נותן סיכוי של 20% לנצח, עומק של 5 נמשך כשעה אחת אך נותן סיכוי של 1% לנצח ולבסוף עומק של 40 נמשך 7-27 שניות ו נותן כ 28-70% סיכוי לזכות.

הרחבות עתידיות

לאלו מכם שמעוניינים בשיפור הקוד הנה כמה דברים שתוכלו לבדוק בהם:

1. שפר את המהירות: שיפור מהירות האלגוריתם יאפשר לכם להשתמש בעומק גדול יותר וכך לקבל דיוק טוב יותר.
2. צור גרפיקה: יש סיבה טובה לכך שהיישום של גבריאלה סירולי התפרסם כל כך. זה יפה למראה! לא טרחתי לפתח ממשק משתמש GUI אלא אני מדפיס את התוצאות על הקונסולה מה שמקשה על המשחק לעקוב אחר המשחק. יצירת ממשק משתמש נחמד הוא חובה.
3. כוונן היוריסטיקות: כפי שציינתי קודם, מספר משתמשים הציעו להיוריסטיקות שונות. ניתן להתנסות בדרך של חישוב הניקוד, המשקולות ותכונות הלוח שנלקחים בחשבון. הגישה שלי למדידת ציון האשכול אמורה לשלב הצעות אחרות כמו מונוטוניות וחלקות, אך עדיין יש מקום לשיפור.
4. כוונון העומק: אפשר גם לנסות לכוונן / להתאים את עומק החיפוש בהתאם למצב המשחק. אתה יכול גם להשתמש ב- העמקה איטרטיבית העמקה ראשונה אלגוריתם שידוע כמשפר את אלגוריתם הגיזום של אלפא-בטא.

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