Як зробити вашу гру Tic Tac Toe неперевершеною, використовуючи алгоритм мінімаксу

Я боровся годинами, прокручуючи підручники, переглядаючи відео та б’ючись головою про стіл, намагаючись створити неперевершену гру в Tic Tac Toe із надійним штучним інтелектом. Отже, якщо ви проходите подібну подорож, я хотів би познайомити вас з алгоритмом Minimax.

Як і професійний шахіст, цей алгоритм бачить кілька кроків вперед і ставить себе на місце свого суперника. Він продовжує грати вперед, поки не досягне термінального розташування дошки ( стан терміналу ), що призведе до нічого , виграшу або програшу. Опинившись у кінцевому стані, ШІ призначає довільний позитивний бал (+10) за перемогу, негативний бал (-10) за програш або нейтральний бал (0) за нічию.

Одночасно алгоритм оцінює ходи, що призводять до термінального стану, на основі ходу гравців. Він обирає хід з максимальним балом, коли настає черга ШІ, і вибирає хід з мінімальним балом, коли настає черга гравця. Використовуючи цю стратегію, Мінімакс уникає програвати людському гравцеві.

Спробуйте самі в наступній грі, бажано за допомогою браузера Chrom.

Алгоритм Minimax найкраще визначити як рекурсивну функцію, яка виконує такі дії:

  1. повернути значення, якщо знайдено стан терміналу (+10, 0, -10)
  2. перегляньте доступні місця на дошці
  3. викликати функцію мінімакс на кожному доступному місці (рекурсія)
  4. оцінити повернення значень із викликів функцій
  5. і повернути найкраще значення

Якщо ви не знайомі з концепцією рекурсії, рекомендую переглянути це відео з Гарвардського CS50.

Щоб повністю зрозуміти процес роздумів Minimax, давайте впровадимо його в код і побачимо в дії в наступних двох розділах.

Мінімакс у коді

У цьому підручнику ви будете працювати над майже завершеним станом гри, який показано на малюнку 2 нижче. Оскільки minimax оцінює кожен стан гри (сотні тисяч), стан близького кінця дозволяє легше відстежувати рекурсивні виклики minimax (9).

Для наступного малюнка припустимо, що ШІ дорівнює X, а людський гравець - О.

Щоб легше працювати з дошкою Ti Tac Toe, слід визначити її як масив з 9 елементами. Кожен елемент матиме свій індекс як значення. Це стане в нагоді пізніше. Оскільки наведена вище дошка вже заповнена деякими ходами X та Y, давайте визначимо дошку з X та Y ходами, які вже є в ній ( origBoard ).

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

Потім оголосіть змінні aiPlayer та huPlayer і встановіть для них значення “X” та “O” відповідно .

Окрім того, вам потрібна функція, яка шукає виграшні комбінації і повертає true, якщо знаходить, і функція, яка перераховує індекси доступних місць на дошці.

/* 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. Крім того, якщо довжина масиву availableSpots дорівнює нулю, це означає, що більше немає місця для гри, у грі з’явився рівний результат, і ви повинні повернути нуль.

 // 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, для властивості index об’єкта переміщення . Пізніше встановіть для порожнього місця на дошці поточного гравця і викличте функцію мінімаксу разом з іншим програвачем та нещодавно зміненою дошкою . Далі слід зберегти об’єкт, отриманий у результаті виклику функції 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); }

Потім алгоритм мінімаксу повинен оцінити найкращий хід в масиві ходів . Він повинен вибрати хід з найвищим балом, коли грає ШІ, і хід з найнижчим балом, коли грає людина. Отже, якщо гравець є aiPlayer , він встановлює змінну, яка називається bestScore, на дуже низьке число і перебирає масив ходів , якщо хід має більший бал, ніж bestScore , алгоритм зберігає цей рух . Якщо є ходи з подібною оцінкою, буде збережено лише перший.

Той самий процес оцінки відбувається, коли гравець є huPlayer , але цього разу для BestScore буде встановлено велике число, і Minimax шукає ходу з найнижчим балом для зберігання.

В кінці 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 подаються в алгоритм. Алгоритм складає список трьох порожніх місць, які він знаходить, перевіряє стан терміналів і переглядає кожне порожнє місце, починаючи з першого. Потім він змінює newBoard , розміщуючи aiPlayer на першому порожньому місці.Після того,він викликає себе за допомогою newBoard і huPlayer і чекає, поки FC поверне значення.

2. While the first FC is still running, the second one starts by making a list of the two empty spots it finds, checks for terminal states, and loops through the empty spot starting from the first one. Then, it changes the newBoard by placing the huPlayer in the first empty spot.After thatit calls itself with newBoard and the aiPlayer and waits for the FC to return a value.

3. Finally the algorithm makes a list of the empty spots, and finds a win for the human player after checking for terminal states. Therefore, it returns an object with a score property and value of -10.

Оскільки другий FC перерахував два порожні місця, Minimax змінює нову дошку , розміщуючи huPlayer у другому порожньому місці. Потім він викликає себе з новою платою та aiPlayer .

4. Алгоритм складає список порожніх місць і знаходить виграш для гравця людини після перевірки стану терміналу. Тому він повертає об'єкт із властивістю оцінки та значенням -10.

На другому FC алгоритм збирає значення, що надходять з нижчих рівнів (3-го та 4-го FC). Оскільки поворот huPlayer привів до двох значень, алгоритм вибирає найнижче з двох значень. Оскільки обидва значення схожі, він вибирає перше і повертає його до першого FC. На цьому етапі перший ФК оцінив рахунок переміщення aiPlayer у першому порожньому місці. Далі він змінює newBoard , розміщуючи aiPlayer у другому порожньому місці. Потім він викликає себе за допомогою newBoard та huPlayer .

5. На п’ятому FC, алгоритм складає список порожніх місць і знаходить виграш для людського гравця після перевірки стану терміналу. Тому він повертає об'єкт із властивістю оцінки та значенням +10.

Після цього перший FC рухається далі, змінюючи нову дошку та розміщуючи aiPlayer на третьому порожньому місці. Потім він викликає себе з новою дошкою та huPlayer .

6. 6-й ФК починається зі складання списку двох порожніх місць, які він знаходить, перевіряє стан кінцевих станцій і перебирає два пусті місця, починаючи з першого. Потім він змінює newBoard , розміщуючи 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 на один рівень вище (7-й FC).

7-й ФК отримав лише одне позитивне значення з нижчих рівнів (8-й ФК). Оскільки поворот aiPlayer привів до цього значення, алгоритму потрібно повернути найвище значення, яке він отримав з нижчих рівнів. Тому він повертає своє єдине позитивне значення (+10) на один рівень вище (6-й ФК). Оскільки 6-й 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.

На даний момент 6 FC повинен вибрати між рахунком (+10), який був надісланий з 7-го FC (повернутий спочатку з 8 FC) та рахунком (-10), повернутим з 9-го FC. Оскільки поворот huPlayer привів до цих двох повернутих значень, алгоритм знаходить мінімальний бал (-10) і повертає його вгору як об’єкт, що містить властивості оцінки та індексу. Нарешті, були оцінені всі три гілки першого ФК (-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.