Как создать бот для игры в крестики-нолики мы подробно рассказали в этой статье. Такого бота будет практически невозможно победить. Заодно мы протестируем алгоритм минимакс на практике.
В прошлой статье мы рассмотрели алгоритм минимакс, который помогает находить оптимальную стратегию в неблагоприятных ситуациях.
Основное о теории минимакс:
Существуют игры, в которых победа одного игрока неминуемо означает поражение всех остальных.
Алгоритм минимакс находит наилучшее решение даже в худших условиях. Простыми словами, он стремится минимизировать потенциальные потери, даже если поражение неизбежно.
Этой стратегии может воспользоваться, как человек, так и компьютер.
Сегодня мы создадим бота, который будет рассчитывать оптимальную стратегию с помощью алгоритма минимакс и принимать наиболее разумное игровое решение.
Что мы планируем сделать:
Разработать игровой интерфейс, который будет работать в веб-браузере. Этот интерфейс будет включать в себя игровое поле, фигуры и возможность их размещения.
Создать логику самой игры, включая правила и определение победителя.
Реализовать поведение бота, который будет играть против нас.
Исходно у нас есть пустая веб-страница, которая будет использоваться для игры. На этой странице мы разместим название игры, кнопку для перезапуска и игровое поле. Игровое поле будет представлять собой 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 и разместим в нем всю необходимую логику:
Как создать бот: добавляем обработку нажатий на клетки
Логика обработки нажатий следующая: если в клетке уже находится символ (крестик или нолик), ничего не происходит. Если же клетка пуста (содержит число), мы размещаем там символ «крестик» и проверяем, привело ли это к выигрышу.
Для проверки наличия выигрыша или ничьей мы используем метод reduce, который принимает исходный массив и обрабатывает его согласно указанному правилу, формируя новое значение. В данном случае мы используем его для поиска всех комбинаций, в которых присутствуют символы одного из игроков. Затем мы сравниваем эти комбинации с предопределенными выигрышными комбинациями и, если они совпадают, выводим сообщение о победе и завершаем игру.
// обрабатываем клик на клетке
function turnClick(square) {
// если клетка свободна
if (typeof origBoard[square.target.id] == ‘number’) {
// ставим там крестик
turn(square.target.id, huPlayer)
// если после хода игрок не выиграл и нет ничьей, компьютер находит лучшее место для нолика и ставит его туда
if (!checkWin(origBoard, huPlayer) && !checkTie()) turn(bestSpot(), aiPlayer);
Мы уже рассматривали этот алгоритм в предыдущей статье. Вот ключевые шаги этого алгоритма:
Первый игрок размещает крестик в любой из клеток поля. Изначально доступно 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 предлагает комфортные условия для обучения онлайн или у нас в офисе на м. Академгородок, м. Житомирская.
IT-школа
