As I'm learning more about recursive algorithms I found out about minimax.
If you want to learn more about minimax I higly reccommend Sebastian Lague video
In tic-tac-toe the rules are the following:
There is a 3x3 board and 2 players
Each square can be in 3 different states:
'X' for player 1, 'O' for player 2 or it can be blank
To win you need to align 3 of the same symbol in a horizontal line, vertical line or diagonal line. This means that we have 3 options per square and we have 9 squares.
3⁹ = 19,683 possible board states.
This means that we can use minimax to teach our computer how to play
We can determine the best move by trying out all the moves and figuring out whats the best option.
First we need to create our webpage.
I created a really basic website just to show the board.
You can take a look at the finished code in my Github
We will be using JavaScrip to add a eventlistener to all of our squares and to fill that square when we click on it.
I don't want to write 9 eventlisteners so I will be adding them with a for loop.
const posList = [
document.querySelector(".pos-1"),
document.querySelector(".pos-2"),
document.querySelector(".pos-3"),
document.querySelector(".pos-4"),
document.querySelector(".pos-5"),
document.querySelector(".pos-6"),
document.querySelector(".pos-7"),
document.querySelector(".pos-8"),
document.querySelector(".pos-9"),
];
for (let i = 0; i < posList.length; i++) {
posList[i].addEventListener("click", function () {
insertLetter(user, i);
botMove();
});
}
We are calling the botMove() function every time the user makes a move just to avoid using an extra loop, we are working with the event loop only.
Now that we have all the event listeners ready we now need to create or minimax algorithm
To do this we need to create a few helper functions.
Such as insertLetter botMove checkwin and checkwinmark
function is_free(position) {
if (board[position] == " ") {
return true;
} else {
return false;
}
}
function check_draw() {
for (let i = 0; i < board.length; i++) {
if (board[i] == " ") {
return false;
}
}
return true;
}
function check_win() {
if (board[0] == board[1] && board[0] == board[2] && board[0] != " ") {
return true;
} else if (board[3] == board[4] && board[3] == board[5] && board[3] != " ") {
return true;
} else if (board[6] == board[7] && board[6] == board[8] && board[6] != " ") {
return true;
} else if (board[0] == board[3] && board[0] == board[6] && board[0] != " ") {
return true;
} else if (board[1] == board[4] && board[1] == board[7] && board[1] != " ") {
return true;
} else if (board[2] == board[5] && board[2] == board[8] && board[2] != " ") {
return true;
} else if (board[0] == board[4] && board[0] == board[8] && board[0] != " ") {
return true;
} else if (board[6] == board[4] && board[6] == board[2] && board[6] != " ") {
return true;
} else {
return false;
}
}
function check_win_mark(mark) {
if (board[0] == board[1] && board[0] == board[2] && board[0] == mark) {
return true;
} else if (board[3] == board[4] && board[3] == board[5] && board[3] == mark) {
return true;
} else if (board[6] == board[7] && board[6] == board[8] && board[6] == mark) {
return true;
} else if (board[0] == board[3] && board[0] == board[6] && board[0] == mark) {
return true;
} else if (board[1] == board[4] && board[1] == board[7] && board[1] == mark) {
return true;
} else if (board[2] == board[5] && board[2] == board[8] && board[2]) {
return true;
} else if (board[0] == board[4] && board[0] == board[8] && board[0] == mark) {
return true;
} else if (board[6] == board[4] && board[6] == board[2] && board[6] == mark) {
return true;
} else {
return false;
}
}
function showWin() {
resultModal.style.display = "block";
resultText.innerHTML = "You Won";
initialText.style.display = "none";
}
function showLost() {
resultModal.style.display = "block";
resultText.innerHTML = "You Lost";
initialText.style.display = "none";
}
function showDraw() {
resultModal.style.display = "block";
resultText.innerHTML = "Draw";
initialText.style.display = "none";
}
function insertLetter(letter, position) {
if (is_free(position)) {
board[position] = letter;
posList[position].innerHTML = letter;
if (check_draw()) {
console.log("Draw");
showDraw();
}
if (check_win()) {
if (letter == "X") {
showLost();
console.log("BOT WINS");
} else {
console.log("User wins");
}
}
return;
} else {
console.log("That space is not avaialble");
return;
}
}
function botMove() {
var best_score = -800;
var best_move = 0;
for (let i = 0; i < board.length; i++) {
if (board[i] == " ") {
board[i] = bot;
var score = minimax(board, 0, false);
board[i] = " ";
if (score > best_score) {
best_score = score;
best_move = i;
}
}
}
console.log(score);
console.log(best_move);
console.log(board);
insertLetter(bot, best_move); // Here we insert the final move
return;
}
Now we need to dive into the minimax algorithm
Our minimax algorithm will iterate trough every possible combination of moves in our board and will choose the best move available.
We do this assigning a -800 when the move results in loss and 800 when the move results in win.
In order for us to iterate trough all posible positions we also need to add inteligence to the user moves.
We are doing this using an extra
var board = [" ", " ", " ", " ", " ", " ", " ", " ", " "];
This board is only being used to represent the board in a way that is easier to access its elements.
Usually with minimax we need to define the depth of the search, however there is not a lot of states that our board can be on. So we can get away not using any depth.
function minimax(board, depth, is_maximizing) {
if (check_win_mark(bot)) {
return 1;
} else if (check_win_mark(user)) {
return -1;
} else if (check_draw()) {
return 0;
}
if (is_maximizing) {
var best_score = -800;
for (let i = 0; i < board.length; i++) {
if (board[i] == " ") {
board[i] = bot;
var score = minimax(board, 0, false);
board[i] = " ";
if (score > best_score) {
best_score = score;
}
}
}
return best_score;
} else {
best_score = 800;
for (let i = 0; i < board.length; i++) {
if (board[i] == " ") {
board[i] = user;
score = minimax(board, 0, true);
board[i] = " ";
if (score < best_score) {
best_score = score;
}
}
}
return best_score;
}
}
You can take a look a the live version here!
Happy Hacking!
Carlo Monroy.
Top comments (0)