Делаем бота для крестиков-ноликов, который почти невозможно обыграть — Журнал «Код» программирование без снобизма

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

Есть игры, в которых выигрыш одного сразу приводит к проигрышу всех остальных.
Есть стратегия минимакса — она находит наилучшее решение в наихудших условиях. Проще говоря, она старается сделать так, что даже в случае проигрыша он был максимально небольшим.
Благодаря этой стратегии вы можете выигрывать в подобных играх. Или не вы, а тот, кто будет этой стратегией пользоваться, — например компьютер.

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

Что делаем

Проект будет состоять из трёх частей:

Игровой интерфейс, который работает в браузере, — игровое поле, фигуры, их постановка.
Логика самой игры — правила и проверка выигрыша.
Поведение бота, который будет играть против нас.

Исходная пустая страница

Для игры нам достаточно обычной веб-страницы. Мы разместим на ней название игры, кнопку перезапуска и игровое поле. Игровое поле — таблица 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];
}

Текст:

Михаил Полянин

Код:

Мэтью Беннет

Редактор:

Максим Ильяхов

Художник:

Алексей Сухов

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев