Adding a Versus Computer Mode to our Connect 4 Game
#Javascript
In this article we will build upon the Connect 4 like game that we created in an earlier article with vanilla javascript. We will add a versus computer mode, first by having the computer play in a random column, then by implementing a minimax algorithm.
Selecting The Game Mode
We will start where we left off in the A Connect 4 Like Game in Vanilla Javascript article.
If you have not read it yet, you should probably read it before this article.
At first, I did not intended to expand on this article but still I found it frustrating not to be able to play it alone versus the computer.
If you want to follow along you can find the code in this Github repository.
For this article, we will start in the "vs_computer_start" branch.
Before trying to generate the computer moves themselves, the first thing we want to do is create some kind of way for the user to choose between playing versus another human or versus the computer.
In the "index.html" file, we will add a new div with an id of "selectGameMode" that will contain two buttons, one for playing versus human, the other for playing versus the computer. The buttons' data-mode attribute will allow us to know which mode was selected.
src/index.html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Connect 4</title>
<link rel="stylesheet" href="css/app.css" />
</head>
<body>
<h1>Connect 4</h1>
<div id="selectGameMode">
<h2>Select Game Mode</h2>
<button data-mode="human">VS HUMAN</button>
<button data-mode="computer">VS COMPUTER</button>
</div>
<div id="board"></div>
<div id="message">player1 turn</div>
<script src="js/app.js"></script>
</body>
</html>
Then we will hide the divs with ids "board" and "message" with css. We will also add some basic styling for the buttons.
src/css/app.css
...
h2 {
text-align: center;
}
..
#board {
...
display: none;
}
...
#message {
...
display: none;
}
#selectGameMode {
margin-bottom: 60px;
}
button {
border-radius: 4px;
border: none;
padding: 8px 16px;
cursor: pointer;
margin: 8px;
}
Then in our app.js file, at the end of the "initBoard" function, which is responsible for creating the gameboard, we will show the board and message divs that were initially hidden.
src/js/app.js
const initBoard = (height, width) => {
const boardElt = document.querySelector('#board')
const messageElt = document.querySelector('#message')
const tableElt = document.createElement('table')
boardElt.appendChild(tableElt)
const board = Array.from({ length: height }, () => [])
for (let i = 0; i < height; i++) {
const rowElt = document.createElement('tr')
for (let j = 0; j < width; j++) {
const cellElt = document.createElement('td')
cellElt.className = 'empty'
cellElt.dataset.column = j
rowElt.appendChild(cellElt)
board[i][j] = cellElt
}
tableElt.appendChild(rowElt)
}
boardElt.style.display = 'block'
messageElt.style.display = 'block'
return board
}
We create a new "selectGameMode" function. It will now be our app entry point instead of the "game" function. It adds an event listener on the buttons, on click it calls the "game" function with an new "mode" argument which is equal to the dataset mode of the clicked button, i.e. either "human" or "computer".
src/js/app.js
const selectGameMode = () => {
document.querySelectorAll('#selectGameMode button').forEach((btn) =>
btn.addEventListener('click', function (e) {
game(e.target.dataset.mode)
document.querySelector('#selectGameMode').remove()
})
)
}
In the "game" function, we add a new variable "vsComputer " which is true when the user selects the versus computer mode. If this is true, after player1 (human) turn, we have to handle the computer move, we will leave it as a "TODO" for the next step.
src/js/app.js
const game = (mode) => {
const board = initBoard(BOARDHEIGHT, BOARDWIDTH)
const maxNumberOfTurns = BOARDHEIGHT * BOARDWIDTH
const messageElt = document.querySelector('#message')
let turnCounter = 0
let player = 'player1'
let gameOver = false
let blockedInput = false
let vsComputer = mode === 'computer'
document.querySelector('table').addEventListener('click', async function (e) {
if (
gameOver ||
undefined === e.target.dataset.column ||
blockedInput ||
(vsComputer && player === 'player2')
) {
return
}
const colNumber = parseInt(e.target.dataset.column, 10)
const rowNumber = getLowestEmptyRowNumber(board, colNumber)
if (rowNumber < 0) {
return // Column is full
}
blockedInput = true
turnCounter++
await drop(board, player, rowNumber, colNumber, 0)
if (isWinner(board, player, colNumber, rowNumber)) {
messageElt.textContent = `${player} has won!`
gameOver = true
return
}
if (turnCounter >= maxNumberOfTurns) {
messageElt.textContent = `It's a draw game!`
gameOver = true
return
}
player = player === 'player1' ? 'player2' : 'player1'
messageElt.textContent = `${player} turn`
// Computer turn
if (vsComputer && player === 'player2') {
// TODO
}
blockedInput = false
})
}
window.addEventListener('DOMContentLoaded', () => {
selectGameMode()
})
If you open "index.html" in your browser you should get something like this:
Generating a Random Computer Move
Right now if we select the "vs computer" mode, we are blocked after the first player turn. We must complete the part we left "TODO" in the "game" function.
We set the "columnNumber" variable (the column index in which the computer will drop a token) to the result of a new "generateComputerMove" function that we will create afterwards.
Once we know in which column the computer will play, the rest of the logic for the computer turn is similar to the human player turn, calcultate the lowest empty row of this column, drop the token in the corresponding cell, check if computer has won, check if the game has ended with a draw, switch the player turn and update the message accordingly.
src/js/app.js
const game = (mode) => {
const board = initBoard(BOARDHEIGHT, BOARDWIDTH)
const maxNumberOfTurns = BOARDHEIGHT * BOARDWIDTH
const messageElt = document.querySelector('#message')
let turnCounter = 0
let player = 'player1'
let gameOver = false
let blockedInput = false
let vsComputer = mode === 'computer'
document.querySelector('table').addEventListener('click', async function (e) {
if (
gameOver ||
undefined === e.target.dataset.column ||
blockedInput ||
(vsComputer && player === 'player2')
) {
return
}
const colNumber = parseInt(e.target.dataset.column, 10)
const rowNumber = getLowestEmptyRowNumber(board, colNumber)
if (rowNumber < 0) {
return // Column is full
}
blockedInput = true
turnCounter++
await drop(board, player, rowNumber, colNumber, 0)
if (isWinner(board, player, colNumber, rowNumber)) {
messageElt.textContent = `${player} has won!`
gameOver = true
return
}
if (turnCounter >= maxNumberOfTurns) {
messageElt.textContent = `It's a draw game!`
gameOver = true
return
}
player = player === 'player1' ? 'player2' : 'player1'
messageElt.textContent = `${player} turn`
// Computer turn
if (vsComputer && player === 'player2') {
const columnNumber = generateComputerMove(board)
const rowNumber = getLowestEmptyRowNumber(board, columnNumber)
turnCounter++
await drop(board, player, rowNumber, columnNumber, 0)
if (isWinner(board, player, columnNumber, rowNumber)) {
messageElt.textContent = `${player} has won!`
gameOver = true
return
}
if (turnCounter === maxNumberOfTurns) {
messageElt.textContent = `It's a draw game!`
gameOver = true
return
}
player = 'player1'
document.querySelector('#message').textContent = `${player} turn`
}
blockedInput = false
})
}
For this step, the "generateComputerMove" function will return us a random available (not full) column index.
src/js/app.js
const generateComputerMove = (board) => {
// Pick a random column number
const columnNumber = Math.floor(Math.random() * BOARDWIDTH)
if (board[0][columnNumber].className !== 'empty') {
return generateComputerMove(board)
}
return columnNumber
}
You can find the code for this version on the vs_computer_random branch.
Implementing a Minimax Algorithm
The random move for the computer is working but is not very interesting to play with. In this step we want to make our computer player a little "smarter" ðŸ§
We will try to implement a minimax algorithm. The minimax algorithm is a decision-making technique used in games where each player tries to win. It looks at all possible moves and picks the one that gives the player the highest minimum gain, assuming the opponent will make the most disadvantageous move.
If you want to learn more about this algorithm, please have a look a this wikipedia article on minimax.
We will use the pseudocode given in this article to help us build our own version.
function minimax(node, depth, maximizingPlayer) is
if depth = 0 or node is a terminal node then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max(value, minimax(child, depth − 1, FALSE))
return value
else (* minimizing player *)
value := +∞
for each child of node do
value := min(value, minimax(child, depth − 1, TRUE))
return value
We first need to create some kind of scoring method for a given state of our board.
The "scoreWindow" function takes in a group of four cells in a row, column, or diagonal, and calculates a score based on how many of the cells are occupied by the player and how many are empty. The score is higher if the player has more cells in the group, especially if they have four in a row. The score is lower if the opponent has three cells in a row and there is one empty cell, as this creates a potential winning position for the opponent.
The "scoreBoard" function takes in the entire game board and calculates a score for the player based on their position on the board. It does this by looking at each row, column, and diagonal on the board and calling scoreWindow to evaluate the score for each group of four cells. The function gives extra weight to cells in the center column of the board, as having control of this column can be advantageous.
src/js/app.js
const scoreWindow = (window, player) => {
let score = 0
let opponent = player === 'player2' ? 'player1' : 'player2'
const nbOfPlayerCells = window.filter((c) => c.className === player).length
const nbOfOpponentCells = window.filter(
(c) => c.className === opponent
).length
const nbOfEmptyCells = window.filter((c) => c.className === 'empty').length
if (nbOfPlayerCells === 4) {
score += 100
} else if (nbOfPlayerCells === 3 && nbOfEmptyCells === 1) {
score += 10
} else if (nbOfPlayerCells === 2 && nbOfEmptyCells === 2) {
score += 5
}
if (nbOfOpponentCells === 3 && nbOfEmptyCells === 1) {
score -= 80
}
return score
}
const scoreBoard = (board, player) => {
let score = 0
// CENTER COLUMN
let centerCount = 0
for (let rowNum = 0; rowNum < BOARDHEIGHT; rowNum++) {
if (board[rowNum][Math.floor(BOARDWIDTH / 2)].className === player) {
centerCount++
}
}
score += centerCount * 6
// HORIZONTAL
for (let rowNum = 0; rowNum < BOARDHEIGHT; rowNum++) {
const rowArray = board[rowNum]
for (let x = 0; x < BOARDWIDTH - 3; x++) {
const window = rowArray.slice(x, x + 4)
score += scoreWindow(window, player)
}
}
// VERTICAL
for (let colNum = 0; colNum < BOARDWIDTH; colNum++) {
const colArray = board.map((row) => row[colNum])
for (let y = 0; y < BOARDHEIGHT - 3; y++) {
const window = colArray.slice(y, y + 4)
score += scoreWindow(window, player)
}
}
for (let rowNum = 0; rowNum < BOARDHEIGHT - 3; rowNum++) {
//DESC DIAGONAL
for (let colNum = 0; colNum < BOARDWIDTH - 3; colNum++) {
const window = []
for (let i = 0; i < 4; i++) {
window.push(board[rowNum + i][colNum + i])
}
score += scoreWindow(window, player)
}
// ASC DIAGONAL
for (let colNum = 3; colNum < BOARDWIDTH; colNum++) {
const window = []
for (let i = 0; i < 4; i++) {
window.push(board[rowNum + i][colNum - i])
}
score += scoreWindow(window, player)
}
}
return score
}
We will also refactor our "isWinner" method. When we created it in the previous article it needed to know the coordinates of the cell where the player has just played. We want to be able to reuse it in other functions where we will not have that information, therefore we have to update it so that it only takes the board and the player as arguments.
src/js/app.js
const isWinner = (board, player) => {
// HORIZONTAL
for (let rowNum = 0; rowNum < BOARDHEIGHT; rowNum++) {
const rowArray = board[rowNum]
for (let x = 0; x < BOARDWIDTH - 3; x++) {
const window = rowArray.slice(x, x + 4)
if (window.filter((c) => c.className === player).length === 4) {
return true
}
}
}
// VERTICAL
for (let colNum = 0; colNum < BOARDWIDTH; colNum++) {
const colArray = board.map((row) => row[colNum])
for (let y = 0; y < BOARDHEIGHT - 3; y++) {
const window = colArray.slice(y, y + 4)
if (window.filter((c) => c.className === player).length === 4) {
return true
}
}
}
for (let rowNum = 0; rowNum < BOARDHEIGHT - 3; rowNum++) {
//DESC DIAGONAL
for (let colNum = 0; colNum < BOARDWIDTH - 3; colNum++) {
const window = []
for (let i = 0; i < 4; i++) {
window.push(board[rowNum + i][colNum + i])
}
if (window.filter((c) => c.className === player).length === 4) {
return true
}
}
// ASC DIAGONAL
for (let colNum = 3; colNum < BOARDWIDTH; colNum++) {
const window = []
for (let i = 0; i < 4; i++) {
window.push(board[rowNum + i][colNum - i])
}
if (window.filter((c) => c.className === player).length === 4) {
return true
}
}
}
return false
}
We will also create two new helper functions that will be useful in our "minimax" function.
The "getAllowedCols" function takes in the game board as input and returns an array of column numbers that still have empty cells in the bottom row of the board. These are the columns where a new token can be dropped.
The "isTerminalNode" function takes in the game board as input and checks if the current game state is a terminal node, meaning that the game is over and no more moves can be made. This happens if one of the players has won the game (we reuse "isWinner" here), or if there are no more allowed columns left to play in.
src/js/app.js
const getAllowedCols = (board) => {
return Array.from({ length: BOARDWIDTH }, (value, index) => index).filter(
(colNum) => board[0][colNum].className === 'empty'
)
}
const isTerminalNode = (board) => {
return (
isWinner(board, 'player1') ||
isWinner(board, 'player2') ||
getAllowedCols(board).length === 0
)
}
And finally we implement the "minimax" function. The first step is to get the list of allowed columns on the board by calling the "getAllowedCols" function. Then, the function checks if the current node is a terminal node by calling the "isTerminalNode" function. If the depth is 0 or if the node is a terminal node, the function returns a score for the node.
If the maximizing player is the current player, the function iterates through all the allowed columns and makes a copy of the board. The function then updates the copy of the board by placing a piece in the current column, and recursively calls the "minimax" function with the new board and a decreased depth. The "minimax" function returns the score for the best move, and the function updates the best score and best column number if the score is better than the current best score.
If the minimizing player is the current player, the function does the same as above, but it looks for the minimum score instead.
Finally, the function returns an object with the best score and best column number.
src/js/app.js
const minimax = (board, depth, maximizingPlayer) => {
const allowedCols = getAllowedCols(board)
const terminalNode = isTerminalNode(board)
if (depth === 0 || terminalNode) {
if (terminalNode) {
if (isWinner(board, 'player2')) {
return {
bestScore: Infinity,
bestColNum: null,
}
}
if (isWinner(board, 'player1')) {
return {
bestScore: -Infinity,
bestColNum: null,
}
}
return {
bestScore: 0,
bestColNum: null,
}
}
return {
bestScore: scoreBoard(board, 'player2'),
bestColNum: null,
}
}
if (maximizingPlayer) {
let bestScore = -Infinity
let bestColNum = allowedCols[Math.floor(Math.random() * allowedCols.length)]
for (let colNum of allowedCols) {
const boardCopy = board.map((row) =>
row.map((cell) => ({ className: cell.className }))
)
boardCopy[getLowestEmptyRowNumber(board, colNum)][colNum].className =
'player2'
const score = minimax(boardCopy, depth - 1, false).bestScore
if (score > bestScore) {
bestScore = score
bestColNum = colNum
}
}
return {
bestScore,
bestColNum,
}
}
let bestScore = Infinity
let bestColNum = allowedCols[Math.floor(Math.random() * allowedCols.length)]
for (let colNum of allowedCols) {
const boardCopy = board.map((row) =>
row.map((cell) => ({ className: cell.className }))
)
boardCopy[getLowestEmptyRowNumber(board, colNum)][colNum].className =
'player1'
const score = minimax(boardCopy, depth - 1, true).bestScore
if (score < bestScore) {
bestScore = score
bestColNum = colNum
}
}
return {
bestScore,
bestColNum,
}
}
Then we only need to modify our "generateComputerMove" function to use this new "minimax" function. Calling it with a depth of 3 or 4 is enough to make it a decent opponent, a greater depth might take too much calculation time.
src/js/app.js
const generateComputerMove = (board) => {
return minimax(board, 3, true).bestColNum
}
Of course it is still possible for the human player to win because in Connect 4 the first player can always win by playing the right moves.
You can find the code in the vs_computer_minimax branch.
And the online demo has been updated accordingly.
Last updated 7 months ago