עץ מונטה קרלו חפש משחק טיק-טאק-בו בג'אווה

1. סקירה כללית

במאמר זה, אנו הולכים לחקור את אלגוריתם חיפוש עץ של מונטה קרלו (MCTS) ויישומיו.

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

2. מבוא

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

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

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

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

והערת צד מהירה - היא חוללה מהפכה בעולם המחשב Go. מאז מרץ 2016 זה הפך לנושא מחקר מקובל כאשר AlphaGo של גוגל (שנבנה עם MCTS ורשת עצבית) גברה על לי סדול (אלופת העולם ב- Go).

3. אלגוריתם חיפוש עץ מונטה קרלו

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

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

האלגוריתם מורכב מארבעה שלבים; בואו נחקור את כולם בפירוט.

3.1. בְּחִירָה

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

הרעיון הוא להמשיך ולבחור צמתים לילד אופטימליים עד שנגיע לצומת העלים של העץ. דרך טובה לבחור צומת ילד כזה היא להשתמש בנוסחה UCT (Bound Confidence Bound מוחל על עצים):

באיזה

  • wאני = מספר הזכיות לאחר אנימהלך -th
  • נאני = מספר הדמיות לאחר ה אנימהלך -th
  • ג = פרמטר חקירה (שווה תיאורטית ל- √2)
  • t = המספר הכולל של סימולציות לצומת האב

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

3.2. הַרחָבָה

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

3.3. סימולציה

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

3.4. תפיסה אחורית

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

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

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

4. ריצה יבשה

כאן, צמתים מכילים נתונים סטטיסטיים בתור סך כל הביקורים / ציון הזכייה.

5. יישום

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

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

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

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

צמת מעמד ציבורי {State state; הורה צומת; רשימת childArray; // סטרים וגטררים} עץ מחלקה ציבורית {שורש הצומת; }

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

מעמד ציבור ציבורי {מועצת המנהלים; נגן int לא; int visitCount; כפול winScore; // העתק קונסטרוקטור, גטרים וקובעים ציבוריים רשימה getAllPossibleStates () {// בונה רשימה של כל המצבים האפשריים מהמצב הנוכחי} public void randomPlay () {/ * קבל רשימה של כל המיקומים האפשריים על הלוח והשחק אקראי מהלך \ לזוז \ לעבור */ } }

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

מחלקה ציבורית MonteCarloTreeSearch {גמר סטטי int WIN_SCORE = 10; רמת int; יריב int; לוח ציבורי findNextMove (לוח לוח, int playerNo) {// מגדירים זמן סיום שישמש כיריב תנאי מסתיים = 3 - playerNo; עץ עץ = עץ חדש (); צומת rootNode = tree.getRoot (); rootNode.getState (). setBoard (לוח); rootNode.getState (). setPlayerNo (יריב); בעוד (System.currentTimeMillis () 0) {nodeToExplore = promisingNode.getRandomChildNode (); } int playoutResult = simulateRandomPlayout (nodeToExplore); backPropogation (nodeToExplore, playoutResult); } צומת winnerNode = rootNode.getChildWithMaxScore (); tree.setRoot (winnerNode); להחזיר winnerNode.getState (). getBoard (); }}

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

עכשיו, בואו נשתמש בשיטות לכל השלבים.

נתחיל משלב הבחירה הדורש יישום UCT גם כן:

צומת פרטית selectPromisingNode (Node rootNode) {Node node = rootNode; בעוד (node.getChildArray (). גודל ()! = 0) {node = UCT.findBestNodeWithUCT (node); } הצומת החזרה; }
מחלקה ציבורית UCT {uctValue כפול ציבורי סטטי (int totalVisit, כפול nodeWinScore, int nodeVisit) {אם (nodeVisit == 0) {return Integer.MAX_VALUE; } return ((double) nodeWinScore / (double) nodeVisit) + 1.41 * Math.sqrt (Math.log (totalVisit) / (double) nodeVisit); } צומת סטטי ציבורי findBestNodeWithUCT (צומת צומת) {int parentVisit = node.getState (). getVisitCount (); להחזיר Collections.max (node.getChildArray (), Comparator.comparing (c -> uctValue (parentVisit, c.getState (). getWinScore (), c.getState (). getVisitCount ()))); }}

שלב זה ממליץ על צומת עלים שיש להרחיב אותו בשלב הרחבה:

חלל פרטי expandNode (צומת צומת) {List possibleStates = node.getState (). getAllPossibleStates (); possibleStates.forEach (state -> {Node newNode = new Node (state); newNode.setParent (node); newNode.getState (). setPlayerNo (node.getState (). getOpponent ()); node.getChildArray (). add (newNode);}); }

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

חלל פרטי backPropogation (Node nodeToExplore, int playerNo) {Node tempNode = nodeToExplore; בעוד (tempNode! = null) {tempNode.getState (). incrementVisit (); אם (tempNode.getState (). getPlayerNo () == playerNo) {tempNode.getState (). addScore (WIN_SCORE); } tempNode = tempNode.getParent (); }} int intimate privateRandomPlayout (צומת צומת) {צומת tempNode = צומת חדש (צומת); מצב tempState = tempNode.getState (); int boardStatus = tempState.getBoard (). checkStatus (); אם (boardStatus == יריב) {tempNode.getParent (). getState (). setWinScore (Integer.MIN_VALUE); לוח החזרה סטטוס; } בעוד (boardStatus == Board.IN_PROGRESS) {tempState.togglePlayer (); tempState.randomPlay (); boardStatus = tempState.getBoard (). checkStatus (); } לוח החזרה סטטוס; }

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

לוח מעמד ציבורי {int [] [] boardValues; גמר סטטי ציבורי int DEFAULT_BOARD_SIZE = 3; גמר סטטי ציבורי int IN_PROGRESS = -1; גמר סטטי ציבורי אינטנסיבי DRAW = 0; סופי סטטי ציבורי int P1 = 1; סופי סטטי ציבורי int P2 = 2; // גטרים וקובעים ציבוריים מבטלים performMove (נגן int, עמדה p) {this.totalMoves ++; boardValues ​​[p.getX ()] [p.getY ()] = נגן; } public int checkStatus () {/ * הערך אם המשחק זכה והשיג מנצח. אם זה צייר החזר 0 אחר החזר -1 * /} רשימה ציבורית getEmptyPositions () {int size = this.boardValues.length; רשימת emptyPositions = ArrayList חדש (); עבור (int i = 0; i <size; i ++) {for (int j = 0; j <size; j ++) {if (boardValues ​​[i] [j] == 0) emptyPositions.add (מיקום חדש (i, י)); }} להחזיר ריק מיקומים; }}

הרגע יישמנו AI שלא ניתן לנצח בטיק-טאק-טו. בוא נכתוב מקרה יחידה המדגים כי AI מול AI תמיד יביא לתיקו:

@ מבחן הריק פומבי givenEmptyBoard_whenSimulateInterAIPlay_thenGameDraw () {Board board = Board חדש (); נגן int = Board.P1; int totalMoves = לוח.DEFAULT_BOARD_SIZE * לוח.DEFAULT_BOARD_SIZE; עבור (int i = 0; i <totalMoves; i ++) {board = mcts.findNextMove (לוח, נגן); אם (board.checkStatus ()! = -1) {הפסקה; } שחקן = 3 - שחקן; } int winStatus = board.checkStatus (); assertEquals (winStatus, Board.DRAW); }

6. יתרונות

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

7. חסרון

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

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

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

8. סיכום

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

כמו תמיד, ניתן למצוא את הקוד השלם לאלגוריתם ב- GitHub.


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