כיצד להפוך את משחק ה- Tic Tac Toe ללא תחרות באמצעות אלגוריתם מינימקס

תִכנוּת

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

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

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

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

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

  1. להחזיר ערך אם נמצא מצב מסוף (+10, 0, -10)
  2. לעבור על נקודות זמינות על הלוח
  3. התקשר לפונקציית המינימקס בכל נקודה זמינה (רקורסיה)
  4. להעריך החזרת ערכים משיחות פונקציה
  5. ולהחזיר את התמורה הטובה ביותר

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

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

מינימום מקס בקוד

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

לדמות הבאה, נניח שה- AI הוא X והשחקן האנושי הוא O.

כדי לעבוד עם לוח ה- Ti Tac Toe קל יותר, עליך להגדיר אותו כמערך עם 9 פריטים. לכל פריט יהיה האינדקס שלו כערך. זה יהיה שימושי בהמשך. מכיוון שהלוח הנ"ל כבר מאוכלס בכמה מהלכי X ו- Y, בואו נגדיר את הלוח עם המהלכים של X ו- Y שכבר נמצאים בו ( origBoard ).

var origBoard = ["O",1,"X","X",4,"X",6,"O","O"];

ואז להכריז aiPlayer ו huPlayer משתנים ולהגדיר אותם "X" ו- "O" בהתאמה .

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

/* the original board O | | X --------- X | | X --------- | O | O */ var origBoard = [“O”,1 ,”X”,”X”,4 ,”X”, 6 ,”O”,”O”]; // human var huPlayer = “O”; // ai var aiPlayer = “X”; // returns list of the indexes of empty spots on the board function emptyIndexies(board){ return board.filter(s => s != "O" && s != "X"); } // winning combinations using the board indexies function winning(board, player){ if ( (board[0] == player && board[1] == player && board[2] == player) || (board[3] == player && board[4] == player && board[5] == player) || (board[6] == player && board[7] == player && board[8] == player) || (board[0] == player && board[3] == player && board[6] == player) || (board[1] == player && board[4] == player && board[7] == player) || (board[2] == player && board[5] == player && board[8] == player) || (board[0] == player && board[4] == player && board[8] == player) || (board[2] == player && board[4] == player && board[6] == player) ) { return true; } else { return false; } }

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

// the main minimax function function minimax(newBoard, player){ //available spots var availSpots = emptyIndexies(newBoard);

כמו כן, עליכם לבדוק אם קיימים מצבי מסוף ולהחזיר ערך בהתאם. אם O מנצח אתה צריך לחזור -10, אם X מנצח אתה צריך להחזיר +10. בנוסף, אם אורכו של מערך ה- Spotpots הזמין הוא אפס, זה אומר שאין יותר מקום לשחק, המשחק הביא לשוויון, וכדאי להחזיר אפס.

 // checks for the terminal states such as win, lose, and tie //and returning a value accordingly if (winning(newBoard, huPlayer)){ return {score:-10}; } else if (winning(newBoard, aiPlayer)){ return {score:10}; } else if (availSpots.length === 0){ return {score:0}; }

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

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

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

לבסוף, Minimax מאפס את newBoard למה שהיה קודם ודוחף את אובייקט המעבר למערך המהלכים .

// an array to collect all the objects var moves = []; // loop through available spots for (var i = 0; i < availSpots.length; i++){ //create an object for each and store the index of that spot var move = {}; move.index = newBoard[availSpots[i]]; // set the empty spot to the current player newBoard[availSpots[i]] = player; /*collect the score resulted from calling minimax on the opponent of the current player*/ if (player == aiPlayer){ var result = minimax(newBoard, huPlayer); move.score = result.score; } else{ var result = minimax(newBoard, aiPlayer); move.score = result.score; } // reset the spot to empty newBoard[availSpots[i]] = move.index; // push the object to the array moves.push(move); }

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

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

בסוף, Minimax מחזיר את האובייקט המאוחסן ב- bestMove .

// if it is the computer's turn loop over the moves and choose the move with the highest score var bestMove; if(player === aiPlayer){ var bestScore = -10000; for(var i = 0; i  bestScore){ bestScore = moves[i].score; bestMove = i; } } }else{ // else loop over the moves and choose the move with the lowest score var bestScore = 10000; for(var i = 0; i < moves.length; i++){ if(moves[i].score < bestScore){ bestScore = moves[i].score; bestMove = i; } } } // return the chosen move (object) from the moves array return moves[bestMove]; }
זהו זה עבור פונקציית המינימקס. :) אתה יכול למצוא את האלגוריתם שלמעלה ב- github ו- codepen. שחק עם לוחות שונים ובדוק את התוצאות במסוף.

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

מינימקס בפעולה

בעזרת האיור הבא, בוא נעקוב אחר שיחות הפונקציה של האלגוריתם ( FC ) אחת אחת.

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

1. origBoard ו- aiPlayer מוזנים לאלגוריתם. האלגוריתם מכין רשימה של שלושת הנקודות הריקות שהוא מוצא, בודק מצבי מסוף ומעביר דרך כל נקודה ריקה החל מהראשון. לאחר מכן, זה משנה את הלוח החדש על ידי הצבת ה- aiPlayer במקום הריק הראשון.לאחר מכן,הוא מכנה את עצמו עם newBoard ו- huPlayer ומחכה שה- FC יחזיר ערך.

2. בזמן שה- FC הראשון עדיין פועל, השני מתחיל בעריכת רשימה של שני הנקודות הריקות שהוא מוצא, בדיקת מצבי מסוף, ולולאות דרך הנקודה הריקה החל מהראשון. לאחר מכן, זה משנה את הלוח החדש על ידי הצבת huPlayer במקום הריק הראשון.לאחר מכןהוא מכנה את עצמו עם newBoard ו- aiPlayer ומחכה שה- FC יחזיר ערך.

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

מכיוון שה- FC השני רשם שני נקודות ריקות, Minimax משנה את ה- Board החדש על ידי הצבת huPlayer במקום הריק השני. לאחר מכן, הוא מכנה את עצמו עם הלוח החדש ו- aiPlayer .

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

ב- FC השני, האלגוריתם אוסף את הערכים שמגיעים מרמות נמוכות יותר (3rd ו- 4th FC). מכיוון שהתור של huPlayer הביא לשני הערכים, האלגוריתם בוחר את הנמוך מבין שני הערכים. מכיוון ששני הערכים דומים, הוא בוחר את הראשון ומחזיר אותו ל- FC הראשון. בשלב זה ה- FC הראשון העריך את הציון של העברת aiPlayer במקום הריק הראשון. לאחר מכן, הוא משנה את ה- Board החדש על ידי הצבת aiPlayer במקום הריק השני. לאחר מכן, הוא מכנה את עצמו עם ה- NewBoard ו- huPlayer .

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

לאחר מכן, ה- FC הראשון עובר על ידי שינוי ה- Board החדש והצבת ה- aiPlayer במקום הריק השלישי. לאחר מכן, הוא מכנה את עצמו עם הלוח החדש ו- huPlayer .

6. ה- FC השישי מתחיל בעריכת רשימה של שני נקודות ריקות שהוא מוצא, בדיקת מצבי מסוף ומדליק בין שני הנקודות הריקות החל מהראשון. לאחר מכן, זה משנה את הלוח החדש על ידי הצבת huPlayer במקום הריק הראשון.לאחר מכן,it calls itself with newBoard and the aiPlayer and waits for the FC to return a score.

7. Now the algorithm is two level deep into the recursion. It makes a list of the one empty spot it finds, checks for terminal states, and changes the newBoard by placing the aiPlayer in the empty spot.After that,it calls itself with newBoard and the huPlayer and waits for the FC to return a score so it can evaluate it.

8. On the 8th FC,האלגוריתם מכין רשימה ריקה של נקודות ריקות, ומוצא ניצחון עבור ה- aiPlayer לאחר בדיקת מצבי הטרמינל. לכן, הוא מחזיר אובייקט עם מאפיין ניקוד וערך של +10 ברמה אחת למעלה (7th FC).

ה- FC השביעי קיבל רק ערך חיובי אחד מרמות נמוכות יותר (FC 8). מכיוון שתורו של aiPlayer הביא לערך זה, האלגוריתם צריך להחזיר את הערך הגבוה ביותר שקיבל מרמות נמוכות יותר. לכן הוא מחזיר את הערך החיובי היחיד שלו (+10) ברמה אחת למעלה (6th FC). מכיוון שה- FC השישי רשם שני נקודות ריקות, Minimax משנה newBoard על ידי הצבת huPlayer במקום הריק השני. ואז, קורא לעצמו עם הלוח החדש ו- aiPlayer .

9. Next, the algorithm makes a list of the empty spots, and finds a win for the aiPlayer after checking for terminal states. Therefore, it returns an object with score properties and value of +10.

בשלב זה, ה- FC 6 צריך לבחור בין הציון (+10) שנשלח מה- FC השביעי (שהוחזר במקור מה- 8 FC) לבין הציון (-10) שהוחזר מה- FC ה- 9. מכיוון שהתור של huPlayer הביא לשני הערכים שהוחזרו, האלגוריתם מוצא את הציון המינימלי (-10) ומחזיר אותו כלפי מעלה כאובייקט המכיל מאפייני ניקוד ואינדקס. לבסוף, כל שלושת הסניפים של ה- FC הראשון הוערכו (-10, +10, -10). אך מכיוון שתורו של aiPlayer הביא לערכים אלה, האלגוריתם מחזיר אובייקט המכיל את הציון הגבוה ביותר (+10) ואת האינדקס שלו (4).

בתרחיש לעיל, Minimax מסיקה כי העברת ה- X לאמצע הלוח מביאה לתוצאה הטובה ביותר. :)

הסוף!

By now you should be able to understand the logic behind the Minimax algorithm. Using this logic try to implement a Minimax algorithm yourself or find the above sample ongithub or codepen and optimize it.

Thanks for reading! If you liked this story, don't forget to share it on social media.

Special thanks to Tuba Yilmaz, Rick McGavin, and Javid Askerovfor reviewing this article.