יישום פותר 2048 בג'אווה

1. הקדמה

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

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

2. הגדרה ראשונית

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

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

2.1. לוח משחק

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

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

תא בכיתה ציבורית {final final int x; גמר פרטי פרטי; // בונה, גטרס ו- toString}

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

לוח מעמד ציבורי {לוח גמר פרטי int [] []; ציון אינטלי סופי פרטי; לוח ציבורי (גודל int) {this.board = new int [size] []; this.score = 0; עבור (int x = 0; x <size; ++ x) {this.board [x] = int int [size]; עבור (int y = 0; y <size; ++ y) {board [x] [y] = 0; }}} public int getSize () {board board.length; } public int getScore () {ציון החזרה; } ציבורי int getCell (תא תא) {לוח החזרה [cell.getX ()] [cell.getY ()]; } בוליאני ציבורי isEmpty (תא תא) {להחזיר getCell (תא) == 0; } רשימה ציבורית רמות ריקות () {תוצאת רשימה = ArrayList חדש (); עבור (int x = 0; x <לוח.אורך; ++ x) {עבור (int y = 0; y <לוח [x]. אורך; ++ y) {תא תא = תא חדש (x, y); אם (isEmpty (תא)) {result.add (תא); }}} להחזיר את התוצאה; }}

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

2.2. נגן מחשב והצבת אריחים

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

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

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

לוח פרטי (int [] [] לוח, ציון int) {this.score = ציון; this.board = int int [board.length] []; עבור (int x = 0; x <board.length; ++ x) {this.board [x] = Arrays.copyOf (board [x], board [x] .length); }}

זה פְּרָטִי כך שהוא יכול לשמש רק אי פעם בשיטות אחרות באותו מעמד. זה עוזר לקפסול הלוח שלנו.

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

public Board placeTile (תא תא, מספר int) {אם (! isEmpty (תא)) {לזרוק IllegalArgumentException חדש ("התא הזה אינו ריק"); } תוצאת לוח = לוח חדש (this.board, this.score); result.board [cell.getX ()] [cell.getY ()] = מספר; תוצאת החזרה; }

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

מחלקה ציבורית {גמר פרטי SecureRandom rng = SecureRandom חדש (); מועצה ציבורית makeMove (קלט לוח) {List emptyCells = input.emptyCells (); מספר כפול ToPlace = rng.nextDouble (); int indexToPlace = rng.nextInt (emptyCells.size ()); Cell cellToPlace = emptyCells.get (indexToPlace); להחזיר input.placeTile (cellToPlace, numberToPlace> = 0.9? 4: 2); }}

זה מקבל את הרשימה של כל תא ריק מהלוח, בוחר תא אקראי ואז מכניס אליו מספר. נחליט באופן אקראי להכניס "4" לתא 10% מהמקרים, ו- "2" ל 90% האחרים.

2.2. שחקן "אנושי" ואריחי העברה

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

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

enum ציבור העבר {למעלה, למטה, שמאלה, ימינה}

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

פירוש הדבר שאנו זקוקים לאמצעי הן להעברה והן לביטול הלוח:

פרטית int [] [] transpose (int [] [] קלט) {int [] [] תוצאה = int int [input.length] []; עבור (int x = 0; x <input.length; ++ x) {result [x] = int int [input [0] .length]; עבור (int y = 0; y <קלט [0]. אורך; ++ y) {תוצאה [x] [y] = קלט [y] [x]; }} להחזיר תוצאה; } int סטטי פרטי [] [] הפוך (int [] [] קלט) {int [] [] תוצאה = int int [input.length] []; עבור (int x = 0; x <input.length; ++ x) {result [x] = int int [input [0] .length]; עבור (int y = 0; y <input [0] .length; ++ y) {result [x] [y] = input [x] [input.length - y - 1]; }} להחזיר תוצאה; }

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

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

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

מהלך לוח ציבורי (העבר מהלך) {int newScore = 0; // שיבט את הלוח int [] [] tile = int int [this.board.length] []; עבור (int x = 0; x <this.board.length; ++ x) {tile [x] = Arrays.copyOf (this.board [x], this.board [x] .length); }

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

אם (move == Move.LEFT || move == Move.RIGHT) {tile = transpose (tile); } אם (move == Move.DOWN || move == Move.RIGHT) {tile = reverse (tile); }

אנו זקוקים למערך אריחים נוסף - הפעם זה שנבנה את התוצאה הסופית אליו - ולעקוב אחר הציון החדש שצבר עבור המהלך הזה:

int [] [] תוצאה = int int [tile.length] []; int newScore = 0;

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

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

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

זה משיג את השינוי שלנו אך עדיין לא מיזוג האריחים:

עבור (int x = 0; x <tile.length; ++ x) {LinkedList thisRow = חדש LinkedList (); עבור (int y = 0; y 0) {thisRow.add (אריחים [x] [y]); }}

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

זה מושג על ידי בניית אחר רשימה מקושרת מהאריחים מהאמור לעיל, אך הפעם מתמזגים תוך כדי תנועה:

LinkedList newRow = חדש LinkedList (); ואילו (thisRow.size ()> = 2) {int first = thisRow.pop (); int שנייה = thisRow.peek (); אם (שנייה == ראשונה) {int newNumber = ראשון * 2; newRow.add (newNumber); newScore + = newNumber; thisRow.pop (); } אחר {newRow.add (ראשון); }} newRow.addAll (thisRow);

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

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

 תוצאה [x] = int int [אריחים [0] .length]; עבור (int y = 0; y <tile [0] .length; ++ y) {if (newRow.isEmpty ()) {result [x] [y] = 0; } אחר {תוצאה [x] [y] = newRow.pop (); }}}

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

if (move == Move.DOWN || move == Move.RIGHT) {result = reverse (result); } אם (move == Move.LEFT || move == Move.RIGHT) {result = transpose (result); }

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

 להחזיר לוח חדש (תוצאה, this.score + newScore); }

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

מעמד ציבורי אנושי {SecureRandom פרטי rng = SecureRandom חדש (); מועצה ציבורית makeMove (קלט לוח) {Move move = Move.values ​​() [rng.nextInt (4)]; להחזיר קלט. להזיז (להזיז); }}

2.3. משחק את המשחק

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

ראשית, אנו זקוקים לדרך להדפיס את לוח המשחק.

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

ריק סטטי פרטי printBoard (לוח לוח) {StringBuilder topLines = StringBuilder חדש (); StringBuilder midLines = StringBuilder חדש (); עבור (int x = 0; x <board.getSize (); ++ x) "); topLines.append (" + "); midLines.append (" | "); עבור (int y = 0; y <board .getSize (); ++ y) {System.out.println (topLines); System.out.println (midLines); עבור (int x = 0; x <board.getSize (); ++ x) {תא תא = תא חדש (x, y); System.out.print ("|"); אם (board.isEmpty (תא)) {System.out.print ("");} אחר {פלט StringBuilder = StringBuilder חדש (מספר שלם .toString (board.getCell (cell))); while (output.length () <8) {output.append (""); if (output.length () <8) {output.insert (0, "" );}} System.out.print (פלט);}} System.out.println ("|"); System.out.println (midLines);} System.out.println (topLines); System.out.println ("ציון:" + board.getScore ());}

אנחנו כמעט מוכנים לצאת לדרך. אנחנו רק צריכים להגדיר את הדברים.

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

מועצת המנהלים = מועצה חדשה (4); מחשב מחשב = מחשב חדש (); אנושי אנושי = אנושי חדש (); עבור (int i = 0; i <2; ++ i) {board = computer.makeMove (board); }

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

printBoard (לוח); לעשות {System.out.println ("מהלך אנושי"); System.out.println ("==========="); לוח = human.makeMove (לוח); printBoard (לוח); System.out.println ("מהלך מחשב"); System.out.println ("=============="); לוח = computer.makeMove (לוח); printBoard (לוח); } בעוד (! board.emptyCells (). isEmpty ()); System.out.println ("ציון סופי:" + board.getScore ());

בשלב זה, אם היינו מריצים את התוכנית, היינו רואים משחק אקראי של 2048.

3. יישום נגן 2048

ברגע שיש לנו בסיס שממנו נשחק את המשחק, נוכל להתחיל ליישם את השחקן "האנושי" ולשחק משחק טוב יותר מאשר רק לבחור כיוון אקראי.

3.1. מדמה מהלכים

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

אנו משתמשים בכבדות ב- Java 8 Streams בכדי לסייע בבניית קוד זה, מסיבות שנראה בהמשך.

נתחיל בכתיבה מחדש של ה- makeMove () שיטה מתוך שלנו בן אנוש מעמד:

מועצה ציבורית makeMove (קלט לוח) {החזר Arrays.stream (Move.values ​​()) .map (קלט :: העבר) .max (Comparator.comparingInt (לוח -> createScore (לוח, 0))). ; }

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

שֶׁלָנוּ createScore () לאחר מכן מדמה כל מהלך אפשרי במחשב - כלומר הצבת "2" או "4" לכל תא ריק - ואז רואה מה יכול לקרות אחר כך:

פרטי int generateScore (לוח לוח, עומק int) {אם (עומק> = 3) {return calcinalFinalScore (לוח); } להחזיר board.emptyCells (). stream () .flatMap (cell -> Stream.of (Pair new (cell, 2), Pair new (cell, 4))) .mapToInt (move -> {Board newBoard = board. placeTile (move.getFirst (), move.getSecond ()); int boardScore = calculateScore (newBoard, עומק + 1); return (int) (boardScore * (move.getSecond () == 2? 0.9: 0.1)); }) .sum (); }

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

שֶׁלָנוּ חישוב ציון () השיטה היא אז המשך הסימולציה שלנו, תוך הפעלת צד המהלך האנושי של המשוואה.

זה דומה מאוד ל makeMove () השיטה לעיל, אך אנו מחזירים את הציון השוטף במקום הלוח בפועל:

int int privateScore (לוח לוח, עומק int) {return Arrays.stream (Move.values ​​()) .map (board :: move) .mapToInt (newBoard -> createScore (newBoard, עומק)) .max () .orElse ( 0); }

3.2. ציון לוחות סופיים

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

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

ככזה, עלינו ליצור רשימה של שורות ועמודות כדי להבקיע כנגד:

רשימה rowsToScore = ArrayList חדש (); עבור (int i = 0; i <board.getSize (); ++ i) {שורה שורה = ArrayList חדש (); רשימה col = ArrayList חדש (); עבור (int j = 0; j <board.getSize (); ++ j) {row.add (board.getCell (תא חדש (i, j))); col.add (board.getCell (תא חדש (j, i))); } rowsToScore.add (שורה); rowsToScore.add (col); }

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

להחזיר שורותToScore.stream () .mapToInt (שורה -> {int ציון = 0; ציון להחזיר;}) .sum ();

לבסוף, עלינו למעשה ליצור את הציונים שלנו. זה נכנס לממבה הנ"ל, וזה כמה גורמים שונים שכולם תורמים:

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

לפני שנוכל לחשב את הציונים, עלינו לבנות נתונים נוספים.

ראשית, אנו רוצים להסיר רשימה של המספרים עם תאים ריקים:

רשימה preMerged = row.stream () .filter (value -> value! = 0) .collect (Collectors.toList ());

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

int numMerges = 0; מונוטוניות int משמאל = 0; מונוטוניות int = 0; עבור (int i = 0; i שנייה) {monotonicityLeft + = first - second; } אחר {monotonicityRight + = second - first; }}

כעת אנו יכולים לחשב את הציון שלנו לשורה זו:

ציון int = 1000; ציון + = 250 * שורה.זרם (). פילטר (ערך -> ערך == 0) .ספירה (); ציון + = 750 * מספר מיזוגים; ציון - = 10 * row.stream (). mapToInt (value -> value) .sum (); ציון - = 50 * Math.min (מונוטוניות שמאלה, מונוטוניות צדק); ציון החזרה;

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

4. שיפורים באלגוריתם

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

4.1. עיבוד מקביל

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

שינוי זה בלבד מוריד אותנו לסביבות 20 שניות לכל מהלך.

4.2. גיזום ענפים שלא ניתנים להשמעה

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

לשם כך עלינו ליישם שיטה שווה על זו שלנו גלשן כדי שנוכל להשוות ביניהם:

@ עקוף בוליאני ציבורי שווה (Object o) {if (this == o) {return true; } אם (o == null || getClass ()! = o.getClass ()) {return false; } לוח לוח 1 = (לוח) o; החזר Arrays.deepEquals (לוח, לוח 1. לוח); }

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

החזר Arrays.stream (Move.values ​​()). parallel () .map (board :: move) .filter (עבר ->! move.equals (board)) ........

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

5. סיכום

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

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


$config[zx-auto] not found$config[zx-overlay] not found