Got a working game but need hints to implement a clever AI

Got a working game but need hints to implement a clever AI
0.0 0

#1

Hi everbody!

I’m happy that I’ve got a working Tic Tac Toe game without looking at other code :wink: Buuuuut the problem is that I got a really stupid AI. It’s just a random number picker (0…8)… So I’m sure you’ll win in 99% of your games againt it. That game seems to be okay when I look at the projects objectives (no sentence about a clever AI) but I really wan’t to do it better.

So, does anybody can give me some hints on how to implement the Minimax algo on the base of my code? I understand what the algorithm does and how works in theory (I hope so) but I really got no idea how to do this with my codebase.

Any hints for me? Would be great!

The game: https://fngr2911.github.io/tictactoe/
The repo: https://github.com/FNGR2911/tictactoe

And here my JS code:

$(document).ready(function() {
  // global variables
  var startBoard    = [0,1,2,3,4,5,6,7,8];
  var currBoard     = [];
  var userBoard     = [];
  var aiBoard       = [];
  var currPlayer    = undefined;
  var beginner      = true;
  var boardCell     = $('.cell');
  var startButton   = $('#start');
  var result        = $('#result');

  var userSign      = 'O';
  var aiSign        = 'X';

  // need to store winning combinations in an variable (array or object)
  var winningCombos = [
    [0,1,2], [3,4,5], [6,7,8], // horizontal
    [0,3,6], [1,4,7], [2,5,8], // vertical
    [2,4,6], [0,4,8]           // diagonal
  ];

  // toggle active Class on user choice
  $('label').on('click', function() {
    $('label').removeClass('active');
    $(this).addClass('active');
  })

  // user clicks on start beginner game
  startButton.on('click', function() {
    $('.board').addClass('active');
    startButton.prop('disabled', true);
    currPlayer = 'X';

    if ($('#X').prop('checked')) {
      userSign = 'X';
      aiSign   = 'O';
    }

    if (aiSign == 'X') {
      moveAI();
    }
  });

  // if currPlayer is the user and he clicks on cell
  boardCell.on('click', function() {
    if (currPlayer === userSign) {
      var cellIndex = $(this).attr('data-index');  // get data-index of clicked cell
      if (cellIndex != 'X' && cellIndex != 'O') {  // check if cell is not clicked before
        cellIndex = Number(cellIndex);             // convert to Number before push
        userBoard.push(cellIndex);                 // push to user userBoard
        currBoard.push(cellIndex);                 // check to currBoard
        $(this).attr('data-index', currPlayer);    // set data-index to currPlayer
        $(this).text(userSign);                    // fill text on field
      }
      checkBoard(userBoard);
    }
  });

  // function that checks if there is a winning combination on players board
  function winCheck(board) {
    for (var i = 0; i < winningCombos.length; i++) { // looop through arrays...
      var count = 0;
      for (var j = 0; j < board.length; j++) {
        if (winningCombos[i].toString().indexOf(board[j]) != -1) { count++ }
        if (count == 3) {
          return true; // if count is 3, there is a winning combiniation and the function returns true
        }
      }
    }
  }

  // function that checks for a win or draw (full board)
  function checkBoard(board) {
    var board = board.sort(function(a, b){return a-b}); // sort the board

    if (winCheck(board)) { // check if board got a winning combination and returns true
      // if true, return currPlayer as winner and quit game
      if (currPlayer == userSign) {
        result.html('<h1>You won :)</h1><p>In 5 seconds you can start a new game.</p>').fadeIn('fast');
      } else {
        result.html('<h1>Oh, computer won :(</h1><p>In 5 seconds you can start a new game.</p>').fadeIn('fast');
      }
      window.setTimeout(setGameBack, 5000);
    } else if (currBoard.length == 9) { // if not, check if currBoard is full without a winner
      // if true, return a draw and set game back
      result.html('<h1>Draw!</h1><p>In 5 seconds you can start a new game.</p>').fadeIn('fast');
      window.setTimeout(setGameBack, 5000);
    } else { // if nothing is true, check the currPlayer and set it to the other player
      if (currPlayer == userSign) {
        currPlayer = aiSign;
        moveAI();
      } else {
        currPlayer = userSign;
      }
    }
  }

  // random number generator for beginner AI
  function ranNumber(min, max) {
    var minNum = min;
    var maxNum = max;
    var num = Math.floor(Math.random() * (max - min + 1)) + min;
    var found  = false;
    for (var i = 0; i < currBoard.length; i++) {
      if (num === currBoard[i]) { found = true }
    }
    if (found === true) {
      return ranNumber(minNum, maxNum);
    }
    return num;
  }

  // function that makes the step / move for AI
  function moveAI() {
    if (beginner) { // if AI is beginner make a random move
      var number = ranNumber(0,8); // generate random number
      var cellNum = number + 1;
      aiBoard.push(number);
      currBoard.push(number);
      $('.cell:nth-child(' + cellNum + ')').attr('data-index', currPlayer);
      $('.cell:nth-child(' + cellNum + ')').text(aiSign);
      checkBoard(aiBoard); // go to the checkboard function
    } else { // if AI is on expert check best move an make one
      // implement MINIMAX algorythm

      checkBoard(aiBoard); // go to the checkboard function
    }
  }

  // if game is finished (win, draw) set all back to the starting values
  function setGameBack() {
    $('.board').removeClass('active');
    result.fadeOut('fast');
    startButton.prop('disabled', false);
    currPlayer = undefined;
    aiBoard = [];
    userBoard = [];
    currBoard = [];
    boardCell.text('');
    for (var i = 0; i < startBoard.length; i++) { // loop to set back the data indexes on the fields
      var childNum = i+1;
      $('.cell:nth-child(' + childNum + ')').attr('data-index', startBoard[i]);
    }
  }
});

Any help would be great!


#2

There are very elaborate algorithms for m,n,k games (m rows, n columns and you need k stones in a row to win). Tic-TacToe is such a simple game, though, that you don’t really need them to have a perfect computer player. Just think about how you would play optimally and write a program that does just that.
I would start with determining all possible moves the computer can make. For each possible move, I would then work through certain conditions and decide which is the most important:

  1. Can I win now? I should do that asap!
  2. Can my opponent win now? I should prevent that!
  3. Can I place a piece in such a way that I have more than one way to complete three in a row next turn? (I’m not sure if that is even possible in tic-tac-toe because if you can do that you might as well just win:
    o..
    .xo
    .xx)
  4. Can my opponent do that? I should not let them.
  5. Is the center not occupied? Now it is mine!.
  6. Otherwise, put a piece in an empty row (horiz/vert/diagonal), the row with no enemy pieces, at the position where you can ‘touch’ the most rows at once etc…

This list may not be complete, but I assume it would result in an okay player that may not be great at winning, but hardly if ever loose. You have to analyze the state of board to make any decisions, of course. There are eight ways to put three in a row, which you’d have to check each turn and know what pieces are missing to complete any of them.


#3

Its a bit more complicated than that. Here is a good set of rules:

Is there a way to never lose at Tic-Tac-Toe?


#4

thank you @lincore & @rickstewart! I worked through all of your tipps and tried to build my own AI. And I think it’s not that stupid anymore :slight_smile: would be happy if you test it: https://fngr2911.github.io/tictactoe/


#5

Hey @FNGR2911 functionally it works well, but even on advanced I beat it every time I tried.

Just to put this challenge in perspective, it took me 3 weeks to complete this, and because I did not use the Minimax algorithm most of that time was working through all the possible edge case. On the plus side not using Minimax makes my code more performant.

If you would like, have a peek at the AI code - here…


#6

You could also look at this code:

This is what I based my code on. It uses a heuristic method, instead of minimax.