Як створити бот для гри в хрестики-нулики

Опубліковано: 7 Вересня, 2023

Як створити бот для гри в хрестики-нулики ми докладно розповіли у цій статті. Такого бота практично неможливо перемогти. Водночас ми протестуємо алгоритм мінімакс на практиці.

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

Основне про теорію мінімакс:

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

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

Що ми плануємо зробити:

Розробити ігровий інтерфейс, який працюватиме у веббраузері. Цей інтерфейс буде включати ігрове поле, фігури й можливість їх розміщення.
Створити логіку самої гри, включаючи правила та визначення переможця.
Реалізувати поведінку бота, який гратиме проти нас.

Ми маємо порожню вебсторінку, яка буде використовуватися для гри. На цій сторінці ми розмістимо назву гри, кнопку для перезапуску та ігрове поле. Ігрове поле буде 3×3 таблицею, щоб легше було орієнтуватися в клітинках. Ми призначимо кожній клітинці унікальний ідентифікатор, щоб згодом можна було до них звертатися. Також, ми відразу додамо блок із повідомленням про перемогу чи поразку. Але спочатку цей блок буде прихований. Ми покажемо його лише наприкінці гри.

<!DOCTYPE html>
<html lang=”ru” >
<head>
<meta charset=”UTF-8″>
<title>Хрестики-нулики</title>
<link rel=”stylesheet” href=”style.css”>

</head>
<body>

<h1>Хрестики-нулики</h1>
<!– ігрове поле –>
<table>
<!– кожна клітинка – комірка таблиці –>
<tr>
<td class=”cell” id=”0″></td>
<td class=”cell” id=”1″></td>
<td class=”cell” id=”2″></td>
</tr>
<tr>
<td class=”cell” id=”3″></td>
<td class=”cell” id=”4″></td>
<td class=”cell” id=”5″></td>
</tr>
<tr>
<td class=”cell” id=”6″></td>
<td class=”cell” id=”7″></td>
<td class=”cell” id=”8″></td>
</tr>
</table>
<!– блок із повідомленням про кінець гри –>
<div class=”endgame”>
<div class=”text”></div>
</div>
<!– кнопка перезапуску –>
<button onClick=”startGame()”>Заново</button>
<!– підключаємо скрипт –>
<script src=”script.js”></script>
</body>
</html>

Додаємо стилі

Стилі зроблять зовнішнє оформлення привабливішим. Ми створимо файл стилів із назвою style.css і внесемо до нього наступний код. Зверніть увагу на коментарі, які допоможуть розібратися у незрозумілих моментах:

/* налаштування комірки */
td {
/* кордон */
border: 2px solid #333;
/* висота та ширина комірки */
height: 100px;
width: 100px;
/* вирівнювання по центру */
text-align: center;
vertical-align: middle;
/* налаштовуємо шрифт */
font-family: “Comic Sans MS”, cursive, sans-serif;
font-size: 70px;
/* змінюємо вигляд курсору над клітинками */
cursor: pointer;
}

/* налаштування всієї таблиці */
table {
/* загальний кордон нехай виглядає як один */
border-collapse: collapse;
/* включаємо абсолютне позиціонування */
position: absolute;
/* Розташовуємо таблицю на сторінці */
left: 50%;
margin-left: -155px;
top: 50px;
}

/* прибираємо межі зовні таблиці, щоб розкреслити поле як для хрестиків-нуликів */
table tr:first-child td {
border-top: 0;
}

table tr:last-child td {
border-bottom: 0;
}

table tr td:first-child {
border-left: 0;
}

table tr td:last-child {
border-right: 0;
}

/* блок із повідомленням про кінець гри */
.endgame {
/* на старті не показуємо */
display: none;
/* Розміри та положення блоку */
width: 200px;
top: 120px;
position: absolute;
left: 50%;
/* колір фону */
background-color: rgba (205,133,63, 0.8);
/* налаштовуємо відступи */
margin-left: -100px;
padding-top: 50px;
padding-bottom: 50px;
text-align: center;
/* Радіус заокруглення */
border-radius: 5px;
/* колір та розмір шрифту */
color: white;
font-size: 2em;
}

Як створити бот: написання скрипту

Насамперед ми оголосимо змінні, які будуть нам потрібні у більшості функцій. Нам знадобляться змінні для представлення ігрового поля, символів “хрестик” та “нулик”, а також для всіх можливих виграшних комбінацій. Давайте детальніше розглянемо їх використання.

Якщо ми пронумеруємо усі клітини ігрового поля від 0 до 8, ми зможемо скласти список усіх можливих виграшних комбінацій. Наприклад, виграшні комбінації по горизонталі виглядатимуть так:

0 1 2

3 4 5

6 7 8

Аналогічно ми можемо визначити виграшні комбінації по вертикалі та діагоналі.

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

Для цього створимо файл script.js і розмістимо в ньому всю потрібну логіку:

// Змінна для ігрового поля
var origBoard;
// гравець ставить хрестики, комп’ютер – нулики
const huPlayer = ‘X’;
const aiPlayer = ‘O’;
// Виграшні комбінації
const winCombos = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8],
[0, 3, 6],
[1, 4, 7],
[2, 5, 8],
[0, 4, 8],
[6, 4, 2]
]

// отримуємо доступ до HTML-клітин на дошці
const cells = document.querySelectorAll(‘.cell’);
// запускаємо гру
startGame();

// запуск гри
function startGame() {
// приховуємо текст про те, що гра закінчилася
document.querySelector(“.endgame”).style.display = “none”;
// формуємо ігрове поле
origBoard = Array.from(Array(9).keys());
// перебираємо всі клітини, очищаємо їх, прибираємо колір фону і вішаємо оброблювач кліку на кожну клітинку
for (var i = 0; i < cells.length; i++) {
cells[i].innerText = ”;
cells[i].style.removeProperty(‘background-color’);
cells[i].addEventListener(‘click’, turnClick, false);
}
}

Як створити бот: додаємо обробку натискань на клітини

Логіка обробки натискань така: якщо в клітці вже знаходиться символ (хрестик або нулик), нічого не відбувається. Якщо ж клітина порожня (містить число), ми розміщуємо там символ “хрестик” і перевіряємо, чи це призвело до виграшу.

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

// обробляємо клік на клітинці
function turnClick(square) {
// якщо клітина вільна
if (typeof origBoard[square.target.id] == ‘number’) {
// ставимо там хрестик
turn(square.target.id, huPlayer)
// якщо після ходу гравець не виграв і немає нічиєї, комп’ютер знаходить найкраще місце для нулика і ставить його туди
if (!checkWin(origBoard, huPlayer) && !checkTie()) turn(bestSpot(), aiPlayer);
}
}

// обробка ходу
function turn(squareId, player) {
// Ставимо фігуру на обране місце
origBoard[squareId] = player;
// малюємо її на ігровому полі на сторінці
document.getElementById(squareId).innerText = player;
// перевіряємо, чи є перемога після ходу
let gameWon = checkWin(origBoard, player)
// якщо є – виводимо повідомлення про це
if (gameWon) gameOver(gameWon)
}
// комп’ютер знаходить найкраще поле для ходу
function bestSpot() {
// Отримуємо номер клітини для кращого ходу з мінімаксного алгоритму
return minimax(origBoard, aiPlayer).index;
}

// перевіряємо, чи хтось виграв після свого ходу
function checkWin(board, player) {
// проходимо ігровим полем і збираємо всі комбінації, проставлені учасником
let plays = board.reduce((a, e, i) =>
(e === player)? a.concat(i) : a, []);
// на старті вважаємо, що виграшної ситуації немає
let gameWon = null;
// перебираємо всі виграшні комбінації та порівнюємо їх із ситуацією на ігровому полі
for (let [index, win] of winCombos.entries()) {
// якщо одна з них збігається з тим, що на ігровому полі формуємо інформацію про переможця
if (win.every(elem => plays.indexOf(elem) > -1)) {
gameWon = {index: index, player: player};
break;
}
}
// Повертаємо інформацію про переможця
return gameWon;
}

// кінець гри
function gameOver(gameWon) {
// беремо виграшну комбірацію
for (let index of winCombos[gameWon.index]) {
// і розфарбовуємо їх у потрібні кольори
document.getElementById(index).style.backgroundColor =
gameWon.player == huPlayer? “blue”: “red”;
}
// Забираємо обробник натискання з усіх клітин
for (var i = 0; i < cells.length; i++) {
cells[i].removeEventListener(‘click’, turnClick, false);
}
// виводимо повідомлення про програш або перемогу гравця
declareWinner(gameWon.player == huPlayer ? “Ви виграли!”: “Ви програли.”);
}

// Висновок повідомлення про перемогу
function declareWinner(who) {
// робимо повідомлення видимим
document.querySelector(“.endgame”).style.display = “block”;
// Заповнюємо його потрібним текстом
document.querySelector(“.endgame .text”).innerText = who;
}

Застосовуємо метод мінімаксу

Ми вже розглядали цей алгоритм у попередній статті. Ось ключові кроки цього алгоритму:

Перший гравець розміщує хрестик у будь-якій із клітин поля. Спочатку доступно 9 клітин, одна з них вже зайнята, тому залишається 8 вільних клітин.
Ми послідовно уявляємо ходи другого гравця, розміщуючи нулики в 8 клітинках, що залишилися, і оцінюємо кожну ситуацію на наявність виграшу або програшу. Якщо неясно, яка ситуація краща, ми рекурсивно застосовуємо алгоритм мінімаксу з новими даними.
Цей процес продовжується до заповнення всіх клітин поля. При цьому виникає безліч варіантів та можливих ходів.
Для гілок, у яких ми перемагаємо, ми додаємо певну кількість балів до кожного ходу, а для тих, у яких ми програємо, забираємо таку ж кількість балів.
Після розрахунків кожна з 8 початкових клітин матиме свою оцінку ходу.
Потім ми вибираємо клітинку для наступного ходу, яка має найвищий сумарний бал, та розміщуємо туди нолик.

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

// функція, яка перевіряє, чи порожня обрана клітина на полі, чи ні
function emptySquares() {
return origBoard.filter(s => typeof s == ‘number’);
}
// Перевірка на нічию
function checkTie() {
// якщо порожніх клітин не залишилося
if (emptySquares().length == 0) {
// перебираємо всі клітини та розфарбовуємо їх зеленим
for (var i = 0; i < cells.length; i++) {
cells[i].style.backgroundColor = “green”;
// відключаємо обробники натискань
cells[i].removeEventListener(‘click’, turnClick, false);
}
// виводимо повідомлення про нічию
declareWinner(“Нічия у грі!”)
return true;
}
return false;
}

Як створити бот. Мінімакс на JavaScript

Як створити бот ми практично дізналися. На останньому етапі ми створюємо алгоритм мінімакс на JavaScript, де кожен рядок коду прокоментований для кращого розуміння того, що відбувається на кожному етапі роботи алгоритму.

// Алгоритм пошуку кращого ходу з мінімаксною стратегією
function minimax(newBoard, player) {
// Отримуємо всі клітини, доступні для ходів
var availSpots = emptySquares();

// якщо за поточного розташування перемагає гравець
if (checkWin(newBoard, huPlayer)) {
// віднімаємо від результату 10 балів
return {score: -10};
// якщо виграє комп’ютер
} else if (checkWin(newBoard, aiPlayer)) {
// Додаємо 10 балів
return {score: 10};
// якщо нічия, то не міняємо кількість балів
} else if (availSpots.length === 0) {
return {score: 0};
}

// тут зберігатимемо всі майбутні ходи для їх оцінки
var moves = [];
// перебираємо доступні клітини
for (var i = 0; i < availSpots.length; i++) {
// Змінна для наступного кроку
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);
}
// Змінна для кращого ходу
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];
}

Після оновлення сторінки ми можемо грати в гру, де комп’ютер завжди виграє або доводить гру до нічиєї.
Як створити бот ми вже дізналися, а якщо ви хочете створити власну гру запрошуємо вас на наші курси програмування. Наша IT школа GoMother пропонує комфортні умови для навчання онлайн або у нас в офісі на м. Академмістечко, м. Житомирська.