Вчера мы разобрали алгоритм минимакса, который позволяет находить лучшую стратегию в плохих условиях. Вот короткая версия:
- Есть игры, в которых выигрыш одного сразу приводит к проигрышу всех остальных.
- Есть стратегия минимакса — она находит наилучшее решение в наихудших условиях. Проще говоря, она старается сделать так, что даже в случае проигрыша он был максимально небольшим.
- Благодаря этой стратегии вы можете выигрывать в подобных играх. Или не вы, а тот, кто будет этой стратегией пользоваться, — например компьютер.
Сегодня мы напишем бота, который будет считать минимаксную стратегию и принимать самое рациональное игровое решение.
Что делаем
Проект будет состоять из трёх частей:
- Игровой интерфейс, который работает в браузере, — игровое поле, фигуры, их постановка.
- Логика самой игры — правила и проверка выигрыша.
- Поведение бота, который будет играть против нас.
Исходная пустая страница
Для игры нам достаточно обычной веб-страницы. Мы разместим на ней название игры, кнопку перезапуска и игровое поле. Игровое поле — таблица 3 на 3, чтобы было проще ориентироваться в клетках. Клеткам сразу дадим id с номером, чтобы потом к ним обращаться. Ещё сразу добавим блок с сообщением о выигрыше или проигрыше, но мы его сначала скроем, а покажем только в самом конце.
<!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. Мы прокомментировали каждую строку, чтобы вы могли разобраться, что происходит на каждом этапе его работы.
// алгоритм поиска лучшего хода с минимаксной стратегией
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];
}Обновляем страницу и играем в игру, в которой компьютер всегда или побеждает, или сводит игру вничью:
Поиграть в крестики-нолики на странице проекта
<!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>/* настройки ячейки */
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;
}// переменная для игрового поля
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);
}
}
// обрабатываем клик на клетке
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 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;
}
// функция, которая проверяеят, пустая ли выбранная клетка на поле или нет
function emptySquares() {
return origBoard.filter(s => typeof s == 'number');
}
// компьютер находит лучшее поле для хода
function bestSpot() {
// получаем номер клетки для лучшего хода из минимаксного алгоритма
return minimax(origBoard, aiPlayer).index;
}
// проверка на ничью
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;
}
// алгоритм поиска лучшего хода с минимаксной стратегией
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];
}Интересно такое? Приходите во фронтенд
В этой профессии хорошо платят, а в «Практикуме» — хорошо обучают: на практике, с тренажерами и помощью наставников. Старт бесплатно.
Начать бесплатно
