Skip to content

Instantly share code, notes, and snippets.

@jwgeller

jwgeller/_tic-tac-toe-minimax.markdown

Created March 27, 2019 22:08
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jwgeller/753cc2797a49f6819155911255d658f8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jwgeller/753cc2797a49f6819155911255d658f8 to your computer and use it in GitHub Desktop.
Download ZIP
_Tic Tac Toe Minimax
Raw
_tic-tac-toe-minimax.markdown
Raw
index.html
<button onclick="resetGame()">Reset Game</button>
<span id="turn_display"></span>
<hr>
<table id="board">
<tr>
<td data-row="0" data-col="0"></td>
<td data-row="0" data-col="1"></td>
<td data-row="0" data-col="2"></td>
</tr>
<tr>
<td data-row="1" data-col="0"></td>
<td data-row="1" data-col="1"></td>
<td data-row="1" data-col="2"></td>
</tr>
<tr>
<td data-row="2" data-col="0"></td>
<td data-row="2" data-col="1"></td>
<td data-row="2" data-col="2"></td>
</tr>
</table>
Raw
script.js
let defaultGameMatrix = [
['', '', ''],
['', '', ''],
['', '', '']
];
const DIM = 3;
let gameMatrix = null;
let player = 'x';
let computer = 'o';
let win = 'win';
let lose = 'lose';
let draw = 'draw';
let currentTurn = null;
let turnDisplay = document.getElementById('turn_display');
Array.prototype.clone = function() {
let outputMatrix = [];
for (let i = 0; i < DIM; ++i) {
let newRow = this[i].slice(0);
outputMatrix.push(newRow);
}
return outputMatrix;
}
resetGame();
let cells = document.getElementsByTagName('td');
for (let i = 0; i < cells.length; ++i) {
cells[i].addEventListener('click', function(e) {
let pos = {
row: e.target.getAttribute('data-row'),
col: e.target.getAttribute('data-col')
}
if (canMakeMove(player, pos)) {
gameMatrix[pos.row][pos.col] = player;
e.target.innerHTML = player;
// determine if player won
let winning = countWinningMoves(gameMatrix, player);
if (typeof(winning) == 'boolean' && winning) {
changeTurn(win);
} else {
changeTurn(computer);
}
}
}, false);
}
// determine best move for computer, which minimizes player
function computerMove() {
let min = 999; // will be less than this
let minCell = null;
let computerWin = false;
loop1: for (let i = 0; i < DIM; ++i) {
loop2: for (let j = 0; j < DIM; ++j) {
if ('' == gameMatrix[i][j]) {
let testMatrix = gameMatrix.clone();
// find moves to win!
let winning = countWinningMoves(testMatrix, player, true);
if (winning instanceof Object) {
minCell = winning;
computerWin = true;
break loop1;
}
testMatrix[i][j] = computer;
let blocking = countWinningMoves(testMatrix, computer, true);
if (blocking instanceof Object) {
minCell = blocking;
break loop1;
}
let playerCount = countWinningMoves(testMatrix, player);
let computerCount = countWinningMoves(testMatrix, computer);
if (playerCount - computerCount < min) {
min = playerCount - computerCount;
minCell = {
row: i,
col: j
};
}
}
}
}
if (null !== minCell) {
drawComputerMove(minCell);
if (computerWin) {
changeTurn(lose);
} else {
changeTurn(player);
}
}
}
function countWinningMoves(testMatrix, testTurn, findBlockers) {
// for a set of 3 to pass, need at least one to match testTurn, and none to match otherTurn
let otherTurn = 'x' == testTurn ? 'o' : 'x';
let winningCount = 0;
// test verticals (3)
for (let i = 0; i < DIM; ++i) {
let testColumn = [
testMatrix[0][i],
testMatrix[1][i],
testMatrix[2][i]
];
let testFound = 0;
let otherFound = 0;
let possibleBlock = null;
for (let j = 0; j < DIM; ++j) {
switch (testColumn[j]) {
case otherTurn:
++otherFound;
break;
case testTurn:
++testFound;
break;
case '':
possibleBlock = {
row: j,
col: i
};
break;
}
}
if (testFound > 2) {
return true;
}
if (otherFound > 1 && null !== possibleBlock && findBlockers) {
return possibleBlock; // block player!
}
if (testFound > 0 && otherFound < 1) {
++winningCount;
}
}
// test horizontals (3)
for (let i = 0; i < DIM; ++i) {
let testRow = testMatrix[i].slice(0);
let testFound = 0;
let otherFound = 0;
let possibleBlock = null;
for (let j = 0; j < DIM; ++j) {
switch (testRow[j]) {
case otherTurn:
++otherFound;
break;
case testTurn:
++testFound;
break;
case '':
possibleBlock = {
row: i,
col: j
};
break;
}
}
if (testFound > 2) {
return true;
}
if (otherFound > 1 && null !== possibleBlock && findBlockers) {
return possibleBlock; // block player!
}
if (testFound > 0 && otherFound < 1) {
++winningCount;
}
}
// test diagonals (2)
let testDiagonalOne = [
testMatrix[0][0],
testMatrix[1][1],
testMatrix[2][2]
];
let testFound = 0;
let otherFound = 0;
let possibleBlock = null;
for (let i = 0; i < DIM; ++i) {
switch (testDiagonalOne[i]) {
case otherTurn:
++otherFound;
break;
case testTurn:
++testFound;
break;
case '':
possibleBlock = {
row: i,
col: i
};
break;
}
}
if (testFound > 2) {
return true;
}
if (otherFound > 1 && null !== possibleBlock && findBlockers) {
return possibleBlock; // block player!
}
if (testFound > 0 && otherFound < 1) {
++winningCount;
}
let testDiagonalTwo = [
testMatrix[2][0],
testMatrix[1][1],
testMatrix[0][2]
];
testFound = 0;
otherFound = 0;
possibleBlock = null;
for (let i = 0; i < DIM; ++i) {
switch (testDiagonalTwo[i]) {
case otherTurn:
++otherFound;
break;
case testTurn:
++testFound;
break;
case '':
possibleBlock = {
row: 2 - i,
col: i
};
break;
}
}
if (testFound > 2) {
return true;
}
if (otherFound > 1 && null !== possibleBlock && findBlockers) {
return possibleBlock; // block player!
}
if (testFound > 0 && otherFound < 1) {
++winningCount;
}
return winningCount;
}
function resetGame() {
let cells = document.getElementsByTagName('td');
for (let i = 0; i < cells.length; ++i) {
cells[i].innerHTML = '';
}
gameMatrix = defaultGameMatrix.clone();
changeTurn(player);
}
function changeTurn(mode) {
switch (mode) {
case player:
currentTurn = player;
turnDisplay.innerHTML = "Your turn!";
break;
case computer:
currentTurn = computer;
turnDisplay.innerHTML = "";
if (canMakeMove(computer)) {
computerMove();
} else {
changeTurn(draw);
}
break;
case win:
case lose:
case draw:
turnDisplay.innerHTML = 'You ' + mode + '!';
break;
}
}
function canMakeMove(mode, pos = {}) {
if (mode != currentTurn) {
return false;
}
if (pos.length > 0) {
return '' == gameMatrix[pos.row][pos.col];
}
// look for any empty position
loop1: for (let i = 0; i < DIM; ++i) {
loop2: for (let j = 0; j < DIM; ++j) {
if ('' == gameMatrix[i][j]) {
return true;
}
}
}
return false;
}
// find cell and draw computerChar!
function drawComputerMove(pos) {
let cells = document.getElementsByTagName('td');
for (let i = 0; i < cells.length; ++i) {
let posCheck = {
row: cells[i].getAttribute('data-row'),
col: cells[i].getAttribute('data-col')
};
if (pos.row == posCheck.row && pos.col == posCheck.col) {
gameMatrix[pos.row][pos.col] = computer;
cells[i].innerHTML = computer;
return;
}
}
}
Raw
style.css
td {
border: 1px solid black;
height: 50px;
width: 50px;
font-family: sans-serif;
font-size: 30px;
text-align: center;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment