Як написати бота, якого буде неможливо обіграти в “хрестики-нулики”, або ознайомлення з правилом “мінімакс”


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

Цілком можливо, що після сотень партій в “хрестики-нулики” ви замислювалися: який же оптимальний алгоритм? Але якщо ви тут, то ви напевно ще і пробували написати реалізацію цієї гри. Ми підемо далі і напишемо бота, який буде неможливо обіграти в “хрестики-нулики”. Передбачивши ваше питання “чому?”, дамо відповідь: завдяки алгоритму “мінімакс”.

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

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

Спробуйте зіграти ось в таку гру.

Алгоритм ” мінімакс” найпростіше описати у вигляді рекурсивної функції, яка :

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

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

Щоб розібратися в тому, як влаштований мінімакс, давайте напишемо його реалізацію і змоделюємо його поведінку. Займемося цим в двох наступних розділах.

Реалізація мінімакса

Ми розглянемо ситуацію, коли гра добігає кінця (дивіться картинку нижче). Оскільки мінімакс проходить по усіх можливих станах гри (а їх сотні тисяч), має сенс розглядати ендшпіль – так нам доведеться відстежувати меншу кількість рекурсивних викликів функції (всього 9).

Нехай ШІ грає хрестиками, людина – нулями.

Щоб спростити роботу з полем, оголосимо його як масив з 9 елементів зі значеннями, рівними вмісту клітин. Заповнимо його хрестиками і нулями, як на картинці вище, і назвемо origBoard.

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

Потім оголосимо змінні aiPlayer і huPlayer і присвоїмо їм значення "X" і "O" відповідно.

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

/* початковий стан дошки O | | X
--------- X | | X --------- | O | O */var origBoard =["O", 1," X"," X", 4," X", 6," O"," O"];// человекvar huPlayer = " O";// ШІvar aiPlayer = " X";// повертає список індексів порожніх клітин доскиfunction emptyIndices (board){ return board.filter (s => s != "O" && s != "X");}// переможні комбінації з урахуванням индексов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; }}

Отже, давайте визначимо мінімакс-функцію з двома аргументами: newBoard (нове поле) і player (гравець). Потім знайдемо індекси вільних клітин на полі і передамо їх в змінну availSpots.

// основна минимакс-функцияfunction minimax (newBoard, player){ //доступні клітини var availSpots = emptyIndices (newBoard);

Крім того, нам треба відстежувати кінцеві стани і повертати відповідні значення. Якщо перемагає “нуль”, треба повернути - 10, якщо “хрестик” – +10. Якщо розмір масиву availSpots дорівнює нулю, значить, вільних клітин немає, гра закінчиться нічиїй, і треба повернути нуль.

// перевірка на термінальний стан (перемога / поразка / нічия)  //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}; }

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

Потім задамо індекс порожньої клітини, який зберігався у вигляді числа в origBoard, рівним властивості-індексу об’єкту move. Потім сходимо за поточного гравця на порожню клітину нового поля newBoard і викличемо функцію minimax від іншого гравця і поля, що вийшло newBoard. Після цього треба помістити властивість score об’єкту, поверненого функцією minimax, у властивість score об’єкту move.

Якщо мінімакс не знаходить кінцевий стан, він продовжує рекурсивне поглиблення в хід гри до тих пір, поки не досягне термінального стану. Після цього він передає окуляри цього “рівня” рекурсії на один рівень вище.

І нарешті, функція скидає зміни newBoard і поміщає об’єкт move у масив moves.

// масив для зберігання усіх об'єктів var moves =[]; // цикл по доступних клітинах 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]]; // вчинити хід за поточного гравця newBoard[availSpots[i]] = player; //отримати очки, зароблені після виклику мінімакса від супротивника поточного гравця if (player == aiPlayer){
var result = minimax (newBoard, huPlayer); move.score = result.score; } else{ var result = minimax (newBoard, aiPlayer); move.score = result.score; } // очистити клітину newBoard[availSpots[i]] = move.index; // покласти об'єкт в масив moves.push (move); }

Потім мінімаксу треба вибрати найкращий хід move з масиву moves. Йому потрібний move з найбільшим рахунком, якщо ходить ШІ, і з найменшим, якщо це хід людини. Таким чином, якщо значення player рівно aiPlayer, алгоритм ініціалізував змінну bestScore дуже маленьким числом і йде циклом по масиву moves: якщо хід move приносить більше очків score, чим bestScore, алгоритм запам’ятовує цей move. У разі ходів з однаковими очками алгоритм запам’ятовує перший з них.

У разі, коли player рівний huPlayer, все аналогічно – тільки тепер bestScore ініціалізувався великим числом, а мінімакс шукає хід move з найменшою кількістю очок.

У результаті мінімакс повертає об’єкт, що зберігається в bestMove.

// якщо це хід ШІ, пройти циклом по ходах і вибрати хід з найбільшою кількістю очок var bestMove; if (player === aiPlayer){ var bestScore = - 10000; for (var i = 0; i < moves.length; i++){ if (moves[i].score > bestScore){ bestScore = moves[i].score; bestMove = i; } } }else{// інакше пройти циклом по ходах і вибрати хід з найменшою кількістю очок var bestScore = 10000; for (var i = 0; i < moves.length; i++){ if (moves[i].score < bestScore){ bestScore = moves[i].score; bestMove = i; } } }// повернути вибраний хід (об'єкт) з масиву ходів return moves[bestMove];}

Ось і уся мінімакс-функція. Початковий код реалізації алгоритму ви можете знайти на GitHub і CodePen.

У наступному розділі ми змоделюємо роботу нашої програми, щоб зрозуміти, як вона працює.

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

Користуючись схемою нижче, розберемо покрокову модель алгоритму.

Примітка: На схемі великі числа означають порядковий номер виклику функції, а рівні – те, на скільки ходів вперед пройшов алгоритм.

  1. Алгоритму подаються origBoard і aiPlayer. Він складає список з трьох знайдених порожніх клітин, перевіряє кінцівку стану, і проходить циклом по усіх порожніх клітинах. Потім алгоритм міняє newBoard, поміщаючи aiPlayer у першу порожню клітину. Після цього він викликає сам себе від newBoard і huPlayer і чекає, поки другий виклик поверне значення.
  2. Поки перший виклик функції все ще працює, запускається другий, створюючи список з двох порожніх клітин, перевіряючи кінцівку стану і проходячи циклом по усіх порожніх клітинах. Потім другий виклик змінює newBoard, поміщаючи huPlayer у першу порожню клітину. Після цього він викликає сам себе від newBoard і aiPlayer і чекає, поки третій виклик поверне значення.
  3. Алгоритм складає список порожніх клітин і фіксує перемогу гравця після перевірки кінцівки стану. Тому він повертає об’єкт з полем рахунку, рівним (- 10).

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

  4. Алгоритм складає список порожніх клітин і фіксує перемогу гравця після перевірки кінцівки стану. Тому він повертає об’єкт з полем рахунку, рівним (- 10).

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

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

  5. У п’ятому виклику функції алгоритм складає список порожніх клітин і фіксує перемогу ШІ після перевірки кінцівки стану. Тому він повертає об’єкт з полем рахунку, рівним +10.

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

  6. Шостий виклик складає список з двох порожніх клітин, перевіряє кінцівку стану і йде циклом по усіх порожніх клітинах. Потім він змінює newBoard, поміщаючи huPlayer у першу порожню клітину. Потім він викликає сам себе від newBoard і aiPlayer і чекає, поки сьомий виклик поверне значення.
  7. Новий виклик складає список з однієї порожньої клітини, перевіряє кінцівку стану і змінює newBoard, поміщаючи aiPlayer у порожню клітину. Після цього він викликає сам себе від newBoard і huPlayer і чекає, поки цей виклик поверне значення.
  8. Восьмий виклик складає порожній список порожніх клітин і фіксує перемогу aiPlayer після перевірки кінцівки стану. Тому він повертає об’єкт з полем рахунку, рівним (+10), на рівень вище, сьомому виклику.

    Сьомий виклик отримав лише одне позитивне значення від нижніх рівнів. Оскільки це значення було отримане в хід aiPlayer, алгоритм повертає найбільше з отриманих значень. Тому він повертає позитивне значення (+10) на рівень вище, шостому виклику.

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

  9. Після цього алгоритм складає список порожніх клітин і фіксує перемогу aiPlayer після перевірки кінцівки стану. Тому він повертає об’єкт з полем рахунку, рівним (+10), на рівень вище.

    На цьому етапі шостий виклик повинен вибрати між рахунком (+10), який повернув сьомий виклик, і рахунком (- 10), який повернув дев’ятий виклик. Оскільки хід huPlayer приніс ці два результати, алгоритм вибирає найменший з них і повертає його на рівень вище у вигляді об’єкту з полями рахунку і індексу.

    Нарешті, усі три гілки першого виклику оцінюються (- 10, +10, – 10). Оскільки хід aiPlayer приніс ці три результати, алгоритм вибирає об’єкт, що містить найбільшу кількість очок (+10) і його індекс (4).

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

Кінець!

До цього моменту ви повинні були зрозуміти, як влаштований алгоритм мінімакс. Спробуйте написати його реалізацію самостійно або подивитеся приклад на GitHub чи CodePen і оптимізуйте його.

Якщо вас зацікавила тема ШІ в іграх, радимо почитати наші матеріали по цій темі:

  • Серія статей, присвячена написанню ШІ для хокею.
  • Як створити кращого бота для гри в стилі Dota – інтерв’ю з переможцем змагання Russian AI Cup.

Переклад статті “How to make your Tic Tac Toe game unbeatable by using the minimax algorithm”

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *