IT-школа
How to create a tic-tac-toe bot
How to create a tic-tac-toe bot, we described in detail in this article. Such a bot will be almost impossible to defeat. At the same time, we will test the minimax algorithm in practice.
In the last article, we considered the minimax algorithm, which helps to find the optimal strategy in unfavorable situations.
Basic about minimax theory:
- There are games in which the victory of one player inevitably means the defeat of all the others.
- The minimax algorithm finds the best solution even under the worst conditions. In simple terms, he seeks to minimize potential losses, even if defeat is inevitable.
- Both humans and computers can use this strategy.
Today we will create a bot that will calculate the optimal strategy using the minimax algorithm and make the most reasonable game decision.
What we plan to do:
- Develop a game interface that will work in a web browser. This interface will include the playing field, pieces, and the ability to place them.
- Create the logic of the game itself, including the rules and determining the winner.
- Implement the behavior of the bot that will play against us.
Initially, we have an empty web page that will be used for the game. On this page, we will place the name of the game, the button to restart, and the playing field. The playing field will be a 3×3 table to make it easier to navigate in the cells. We will assign a unique ID to each cell so that we can refer to them later. Also, we will immediately add a block with a message about victory or defeat. But initially, this block will be hidden. We will show it only at the very end of the game.
<!DOCTYPE html>
<html lang=”en”>
<head>
<metacharset=”UTF-8″>
<title>Tic Tac Toe</title>
<link rel=”stylesheet” href=”style.css”>
</head>
<body>
<h1>Tic Tac Toe</h1>
<!– playing field –>
<table>
<!– each cell is a table cell –>
<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>
<!– block with a message about the end of the game –>
<div class=”endgame”>
<div class=”text”></div>
</div>
<!– restart button –>
<button onClick=”startGame()”>Restart</button>
<!– include script –>
<script src=”script.js”></script>
</body>
</html>
Adding Styles
Styles will make the appearance more attractive. We will create a style file called style.css and add the following code to it. Pay attention to the comments that will help you understand incomprehensible points:
/* cell settings */
td {
/* border */
border: 2px solid #333;
/* cell height and width */
height: 100px;
width: 100px
/* center alignment */
text-align: center;
vertical-align: middle;
/* set the font */
font-family: “Comic Sans MS”, cursive, sans-serif;
font-size: 70px
/* change the appearance of the cursor over the cell */
cursor: pointer;
}
/* whole table settings */
table {
/* let the common border look like one */
border-collapse: collapse;
/* enable absolute positioning */
position: absolute;
/* place the table on the page */
left: 50%
margin-left: -155px;
top: 50px;
}
/* remove the borders outside the table to draw the field as for tic-tac-toe */
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;
}
/* block with a message about the end of the game */
.endgame {
/* do not show at start */
display: none;
/* block size and position */
width: 200px
top: 120px;
position: absolute;
left: 50%
/* background color */
background-color: rgba(205,133,63, 0.8);
/* adjust padding */
margin-left: -100px;
padding-top: 50px;
padding-bottom: 50px
text-align: center;
/* rounding radius */
border-radius: 5px
/* font color and size */
color:white;
font-size: 2em
}
How to create a tic-tac-toe bot: scripting
First of all, we will declare the variables that we will need in most of the functions. We’ll need variables to represent the playing field, the X’s and O’s, and all possible winning combinations. Let’s take a closer look at their use.
If we number all the cells of the playing field from 0 to 8, we can make a list of all possible winning combinations. For example, winning combinations horizontally would look like this:
0 1 2
3 4 5
6 7 8
Similarly, we can determine winning combinations vertically and diagonally.
Once we’ve finished setting up the game, we’ll immediately call the function to start the game, which is also associated with the restart button. Inside the launch function, we’ll hide the end-of-game message, clear the playing field, and add an event handler for each cell.
To do this, we will create a script.js file and place all the necessary logged:
// variable for the playing field
var origBoard;
// player puts crosses, computer – zeros
const huPlayer = ‘X’;
const aiPlayer = ‘O’;
// winning combinations
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]
]
// get access to the HTML cells on the board
const cells = document.querySelectorAll(‘.cell’);
// start the game
startGame();
// start the game
function startGame() {
// hide the text about the fact that the game is over
document.querySelector(“.endgame”).style.display = “none”;
// form the playing field
origBoard = Array.from(Array(9).keys());
// iterate through all the cells, clear them, remove the background color and hang a click handler on each
for (var i = 0; i < cells.length; i++) {
cells[i].innerText = ”;
cells[i].style.removeProperty(‘background-color’);
cells[i].addEventListener(‘click’, turnClick, false);
}
}
How to create a tic-tac-toe bot: Add cell click handling
The logic for processing clicks is as follows: if there is already a symbol (cross or zero) in the cell, nothing happens. If the cell is empty (contains a number), we place a “cross” symbol there and check if this led to a win.
To check for a win or a tie, we use the reduce method, which takes the original array and processes it according to the specified rule, forming a new value. In this case, we use it to find all combinations that contain the symbols of one of the players. We then compare these combinations with the predefined winning combinations and if they match, print a win message and end the game.
// handle the click on the cell
function turnClick(square) {
// if cell is free
if (typeof origBoard[square.target.id] == ‘number’) {
// put a cross there
turn(square.target.id, huPlayer)
// if after the move the player has not won and there is no draw, the computer finds the best place for the zero and puts it there
if (!checkWin(origBoard, huPlayer) && !checkTie()) turn(bestSpot(), aiPlayer);
}
}
// move processing
function turn(squareId, player) {
// put the figure in the selected place
origBoard[squareId] = player;
// draw it on the playing field on the page
document.getElementById(squareId).innerText = player;
// check if there is a win after the move
let gameWon = checkWin(origBoard, player)
// if there is – display a message about it
if (gameWon) gameOver(gameWon)
}
// the computer finds the best field to move
bestSpot() {
// get the cell number for the best move from the minimax algorithm
return minimax(origBoard, aiPlayer).index;
}
// check if someone won after their turn
function checkWin(board, player) {
// go through the board and collect all the combinations put down by the participant
let plays = board.reduce((a, e, i) =>
(e === player) ? a.concat(i) : a, []);
// at the start, we consider that there is no winning situation
let gameWon = null;
// iterate over all winning combinations and compare them with the situation on the board
for (let [index, win] of winCombos.entries()) {
// if one of them matches the one on the board, we generate information about the winner
if (win.every(elem => plays.indexOf(elem) > -1)) {
gameWon = {index: index, player: player};
break;
}
}
// return information about the winner
return gameWon;
}
// end of the game
function gameOver(gameWon) {
// take the winning combo
for (let index of winCombos[gameWon.index]) {
// and color it in the desired colors
document.getElementById(index).style.backgroundColor =
gameWon.player == huPlayer ? “blue” : “red”;
}
// remove the click handler from all cells
for (var i = 0; i < cells.length; i++) {
cells[i].removeEventListener(‘click’, turnClick, false);
}
// display a message about the loss or victory of the player
declareWinner(gameWon.player == huPlayer ? “You win!” : “You lose.”);
}
// output a victory message
function declareWinner(who) {
// make the message visible
document.querySelector(“.endgame”).style.display = “block”;
// fill it with the desired text
document.querySelector(“.endgame .text”).innerText = who;
}
Applying the minimax method
We have already considered this algorithm in the previous article. Here are the key steps of this algorithm:
- The first player places a cross in any of the cells of the field. Initially, 9 cells are available, and one of them is already occupied, so 8 free cells remain.
- We sequentially imagine the moves of the second player, placing zeros in the remaining 8 cells, and evaluate each situation for a win or loss. If it is not clear which situation is better, we recursively apply the minimax algorithm with new data.
- This process continues until all cells of the field are filled. In this case, there are many options and possible moves.
- For branches in which we win, we add a certain number of points to each move, and for those in which we lose, we subtract the same number of points.
- After calculations, each of the 8 initial cells will have its move score.
- Then we select the cell for the next move, which has the highest total score, and place a zero there.
In this article “How to create a tic-tac-toe bot” we will apply the acquired knowledge about minimax in practice. To implement this strategy, you need to know which cells are freely available and determine whether a draw has occurred in the current situation. The availability of cells is determined by the presence of a number in them, and a draw – the absence of free cells in the absence of a winner.
// function that checks if the selected cell on the field is empty or not
function emptySquares() {
return origBoard.filter(s => typeof s == ‘number’);
}
// check for a draw
function checkTie() {
// if there are no empty cells left
if (emptySquares().length == 0) {
// loop through all the cells and color them green
for (var i = 0; i < cells.length; i++) {
cells[i].style.backgroundColor = “green”;
// disable click handlers
cells[i].removeEventListener(‘click’, turnClick, false);
}
// display a message about a draw
declareWinner(“Draw!”)
return true;
}
return false;
}
How to create a tic-tac-toe bot. Minimax in JavaScript
We practically learned how to create a bot. At the last stage, we create a minimax algorithm in JavaScript, where each line of code is commented on for a better understanding of what happens at each stage of the algorithm.
// algorithm for finding the best move with a minimax strategy
function minimax(newBoard, player) {
// get all cells available for moves
var availSpots = emptySquares();
// if player wins at the current location
if (checkWin(newBoard, huPlayer)) {
// subtract 10 points from the result
return {score: -10};
// if the computer wins
} else if (checkWin(newBoard, aiPlayer)) {
// add 10 points
return {score: 10};
// if it’s a draw, then don’t change points
} else if (availableSpots.length === 0) {
return {score: 0};
}
// here we will store all future moves for their evaluation
var moves = [];
// loop through the available cells
for (var i = 0; i < availSpots.length; i++) {
// variable for the next step
var move = {};
// take a step into the next empty cell and get a new position on the board
move.index = newBoard[availSpots[i]];
// fill this cell with the symbol of the one whose move we are counting
newBoard[availSpots[i]] = player;
// if we count the move for the computer
if (player == aiPlayer) {
// recursively call the minimax function for the new position and indicate that the next move is made by a person
var result = minimax(newBoard, huPlayer);
move.score = result.score;
// the same, but if we count the person’s move
} else {
var result = minimax(newBoard, aiPlayer);
move.score = result.score;
}
// remember the result
newBoard[availSpots[i]] = move.index;
// add a move to the list of moves
moves.push(move);
}
// variable for best move
varbestMove;
// if we count the computer’s move
if(player === aiPlayer) {
// take the lowest possible value
var bestScore = -10000;
// iterate through all the moves that we got
for(var i = 0; i < moves.length; i++) {
// if the points of the current turn are greater than the best value
if (moves[i].score > bestScore) {
// remember this as the best value
bestScore = moves[i].score;
// remember the move number
bestMove = i;
}
}
// we do the same with the move if we are simulating the move of a person
} else {
var bestScore = 10000;
for(var i = 0; i < moves.length; i++) {
if (moves[i].score < bestScore) {
bestScore = moves[i].score;
bestMove = i;
}
}
}
// return the best move
return moves[bestMove];
}
After refreshing the page, we can play a game where the computer always wins or draws the game.
We have already learned how to create a bot, and if you want to create your own game, we invite you to our programming courses. Our IT school GoMother offers comfortable conditions for learning online or in our office at Akademgorodok metro station, Zhitomirskaya metro station.
