streamalism.org

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

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

נדון גם ביתרונות השימוש באלגוריתם ונראה כיצד ניתן לשפר אותו.

2. מבוא

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

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

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

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

עובדה מעניינת - בשנת 1997, מחשב השחמט של יבמ Deep Blue (שנבנה עם Minimax) ניצח את גארי קספרוב (אלוף העולם בשחמט).

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

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

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

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

שקול את עץ המשחק הבא:

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

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

1. בנה את עץ המשחק השלם
2. הערך ציונים עלים באמצעות פונקציית ההערכה
3. ציוני גיבוי מעלים לשורש, בהתחשב בסוג השחקן:
   • עבור שחקן מקסימום, בחר את הילד עם הציון המקסימלי
   • לשחקן דקות, בחר את הילד עם הציון המינימלי
4. בצומת הבסיס, בחר את הצומת עם הערך המקסימלי ובצע את המהלך המתאים

4. יישום

עכשיו, בואו נבצע משחק.

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

כדי להגדיר את כללי המשחק, אנו ניישם GameOfBones מעמד:

class GameOfBones {List static getPossibleStates (int noOfBonesInHeap) {return IntStream.rangeClosed (1, 3) .boxed () .map (i -> noOfBonesInHeap - i). filter (newHeapCount -> newHeapCount> = 0) .collect (Collectors. למנות()); }}

יתר על כן, אנו זקוקים גם ליישום עבור צוֹמֶת ו עֵץ גם שיעורים:

צמת מעמד ציבורי {int noOfBones; isMaxPlayer בוליאני; ציון int; רשימת ילדים; // סטרים וגטררים} עץ מחלקה ציבורית {שורש הצומת; // סטרים וגטררים}

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

מחלקה ציבורית MiniMax {עץ עץ; בטל ציבורי בטל (int noOfBones) {עץ = עץ חדש (); שורש הצומת = צומת חדש (noOfBones, נכון); tree.setRoot (שורש); buildTree (שורש); } בטל פרטי constructTree (צומת parentNode) {List listofPossibleHeaps = GameOfBones.getPossibleStates (parentNode.getNoOfBones ()); isChildMaxPlayer בוליאני =! parentNode.isMaxPlayer (); listofPossibleHeaps.forEach (n -> {Node newNode = new Node (n, isChildMaxPlayer); parentNode.addChild (newNode); if (newNode.getNoOfBones ()> 0) {constructTree (newNode);}}); }}

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

• +1, אם מקסימום זוכה
• -1, אם מינימייזר מנצח

ה checkWin יחזיר אמת אם השחקן הראשון (במקרה שלנו - מקסימום) יזכה:

checkWin () בוליאני ציבורי ציבורי = tree.getRoot (); checkWin (שורש); להחזיר root.getScore () == 1; } check ריק חלל פרטי (צומת צומת) {רשימת ילדים = node.getChildren (); isMaxPlayer בוליאני = node.isMaxPlayer (); children.forEach (child -> {if (child.getNoOfBones () == 0) {child.setScore (isMaxPlayer? 1: -1);} else {checkWin (child);}}); צומת bestChild = findBestChild (isMaxPlayer, ילדים); node.setScore (bestChild.getScore ()); }

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

צומת פרטית findBestChild (בוליאני isMaxPlayer, רשימת ילדים) {Comparator byScoreComparator = Comparator.comparing (צומת :: getScore); להחזיר את הילדים.זרם () .max (isMaxPlayer? byScoreComparator: byScoreComparator.reversed ()) .orElseThrow (NoSuchElementException :: new); }

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

@Test הציבור בטל givenMiniMax_whenCheckWin_thenComputeOptimal () {miniMax.constructTree (6); תוצאה בוליאנית = miniMax.checkWin (); assertTrue (תוצאה); miniMax.constructTree (8); תוצאה = miniMax.checkWin (); assertFalse (תוצאה); }

5. שיפור

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

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

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

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

6. מסקנה

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

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

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