DEV Community: CarloMonroy

Simple tic-tac-toe AI using minimax

CarloMonroy — Thu, 02 Jun 2022 16:55:53 +0000

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.

FizzBuzz Challenge Usando list comprehension!

CarloMonroy — Mon, 30 May 2022 19:18:51 +0000

Si eres programador o estas aprendiendo a programar seguramente te has encontrado con el FizzBuzz Challenge o lo encontraras.
A continuación hablaremos acerca de este reto y lo implementaremos utilizando list comprehension de python!

Que es FizzBuzz Challenge
Se nos pide escribir un programa el cual nos imprima n cantidad de numeros.
Si el numero es multiplo de 3 imprimir Fizz
Si el numero es multiplo de 5 imprimir Buzz
Si el numero es multiplo de 3 y de 5 imprimir FuzzBuzz
Si el numero no es multiplo de ninguno imprimir el numero

Implementación regular FizzBuzz
Para entender como funciona nuestra list comprehension primero necesitamos entender como necesita funcionar nuestro programa.
La forma mas sencilla de implementarlo es con un for loop y con expresiones if

Primero necesitamos iterar por la cantidad de numeros
for i in range(1, 15):
En cada iteracion revisaremos nuestras condiciones utilizando nuestro operador modulus %
Podemos manejar este operador de forma booleana ya que cuando el resultado de el modulo es 0 nos regresa False.
Podemos invertir nuestro resultado booleano utilizando not y de esta forma cuando nuestro numero si sea divisible nos regresara True, Esta logica la podemos implementar dentro de nuestro for loop de la siguiente forma:

for i in range(1, 16):
    if not (i%3 and not i%5):
        print("FizzBuzz")
    elif not (i%3):
        print("Fizz")
    elif not (i%5):
        print("Buzz")
    else:
        print(i)

Nuestra respuesta en consola seria:

Felicidades, ya completaste el FizzBuzz Challenge.

FizzBuzz con List Comprehension
Para poder aplicar nuestro list comprehension debemos recordar que al utilizar el operador * se repite esa cantidad de veces.
De esta forma podemos utilizar x = "string"*(not i%5):
Cuando el Resultado de nuestra evaluación sea False nuestro string no se mostrara.
primero evaluaremos nuestras condiciones.
Ejemplo:
"Fizz"*(not i%3) Si i==2 entonces nuestra evaluacion seria False, Despues evaluamos con nuestro operador * y al ser falso ese "String" no se estaria concatenando.

de esta forma:

FizzBuzzList = ["Fizz"*(not i%3) + "Buzz"*(not i%5) or i ]

Hasta aqui tenemos la parte logica de nuestro list comprehension.
Por cada iteracion pasaremos nuestro string en el que si no se cumple nuestra condicion no se concatena y cuando no se cumple ninguna condicion se concatena el numero de nuestra iteracion.

Ahora solo nos falta agregar nuestro for loop for i in range(1, 16), en range() nuestro primer parametro es inclusivo y el segundo parametro es exclusivo.
De esta forma si necesitamos numeros de el 1 al 15 debemos ingresarle los parametros 1, 16

Nuestro List Comprehension final quedaria de la siguiente forma:

FizzBuzz = ["Fizz"*(not i%3) + "Buzz"*(not i%5) or i for i in range(1, 16)]

Espero les haya sigo de ayuda!
Happy Hacking!
Carlo Monroy