Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

JavaScript

Trying to get minimax to work correctly in tic-tac-toe

I am trying to implement the Minimax algorithm into my tic-tac-toe game. The problem that I am having is that the computer always chooses the first available space on the board instead of making the best move. If I output the array of scores to the console it looks like the final list I get is [5,5,5,5,5,5,5,5,5]. I know that I shouldn't get the same score for every possible move, that just does not make sense. Code is below:

// AI.js
var AI = (function(){
  "use strict";

  var currentMarker;
  var computerChoice;

  // function that chooses the best move for the computer using minimax
  // a copy of the current game board is created, which is passed to minimax
  // in this game, the computer is always 'x'
  var computerMove = function() {
    var aiboard = Board.getBoard();
    currentMarker = 'x';
    var depth = 0;
    minimax(aiboard,depth);
    $('li[data-square="' + computerChoice + '"]').addClass('box-filled-2').css('background-image','url("img/x.svg")');
  };

  // get all of the vacant squares on the current board
  var getAvailableMoves = function(aiboard) {
    var availableMovesList = [];
    for(var a = 0; a < aiboard.length; a++) {
      if (aiboard[a] === '') {
        availableMovesList.push(a);
      }
    }
    return availableMovesList;
  }

  // scoring system for minimax
  var score = function(depth,aiboard) {
    var aistatus = Board.checkAIBoard(aiboard);
    if (aistatus === 'winx') {
      return 10 - depth;
    } else if (aistatus === 'wino') {
      return depth - 10;
    } else {
      return 0;
    }
  }

  // makes a play (x or o) on the current minimax board (which also creates a new branch) and changes the marker
  var makeNewBranch = function(move,aiboard) {
    aiboard[move] = currentMarker;
    changePlayer();
    return aiboard;
  }

  // changes the marker between x (computer) and o (human)
  var changePlayer = function() {
    if (currentMarker === 'x') {
        currentMarker = 'o';
      } else {
        currentMarker = 'x';
      }
  }

  // clears the current move from the minimax board once the end of a branch is reached
  var clearMove = function(move,aiboard) {
    aiboard[move] = '';
    changePlayer();
    return aiboard;
  }

  // minimax algorithm
  var minimax = function(aiboard,depth) {
    //check to see if the board is a win or tie after each iteration
    if (Board.checkAIBoard(aiboard) !== 'game in progress') {
      return score(depth,aiboard);
    }
    depth += 1;
    var scores = [];
    var moves = [];
    var availableMoves = getAvailableMoves(aiboard);
    var move;
    var branch;
    // test each available square by creating a branch (and braches of) recursing as needed and
    // and pushing the resulting score from each branch into a scores array to evaluate later
    // the move that generated the score for each branch is pushed into a moves array (which
    // corrispods to the scores in the scores array
    // then clear the board after each move
    for (var m = 0; m < availableMoves.length; m++) {
      move = availableMoves[m];
      branch = makeNewBranch(move,aiboard);
      scores.push(minimax(branch,depth));
      moves.push(move);
      aiboard = clearMove(move,aiboard);
    }
    // at the end of the loop, if the current player is the computer (x), pick the highest score
    // from the scores array.  if the current player is the human (o), pick the lowest score from
    // the scores array.  The index position at the appropriate score is the move the computer should make.
    var highScore;
    var highScoreIndex;
    var lowScore;
    var lowScoreIndex;
    if (currentMarker === 'x') {
      highScore = Math.max.apply(Math,scores);
      highScoreIndex = scores.indexOf(highScore);
      computerChoice = moves[highScoreIndex];
      return scores[highScoreIndex];
    } else {
      lowScore = Math.max.apply(Math,scores);
      lowScoreIndex = scores.indexOf(lowScore);
      computerChoice = moves[lowScoreIndex];
      return scores[lowScoreIndex];
    }
  }
  // export the function computerMove for use in the game module
  return {
    computerMove: computerMove
  }
})();

// app.js
!function() {
  "use strict";
  // start the game
  Game.init();
}();

// board.js
var Board = (function Board() {
  "use strict";

  var gameboard = [];
  // all of the possible 'three in a row' combinations
  var winningRoutes = [
    [0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]
  ]

  // HTML code block for the board at game start
  var initialBoardHTML = '<div class="board" id="board">';
  initialBoardHTML += '<header>';
  initialBoardHTML += '<h1>Tic Tac Toe</h1>';
  initialBoardHTML += '<ul>';
  initialBoardHTML += '<li class="players" id="player1">';
  initialBoardHTML += '<svg xmlns="http://www.w3.org/2000/svg" width="42" height="42" viewBox="0 0 42 42" version="1.1"><g stroke="none" stroke-width="1" fill="none" fill-rule="evenodd"><g transform="translate(-200.000000, -60.000000)" fill="#000000"><g transform="translate(200.000000, 60.000000)"><path d="M21 36.6L21 36.6C29.6 36.6 36.6 29.6 36.6 21 36.6 12.4 29.6 5.4 21 5.4 12.4 5.4 5.4 12.4 5.4 21 5.4 29.6 12.4 36.6 21 36.6L21 36.6ZM21 42L21 42C9.4 42 0 32.6 0 21 0 9.4 9.4 0 21 0 32.6 0 42 9.4 42 21 42 32.6 32.6 42 21 42L21 42Z"/></g></g></g></svg>';
  initialBoardHTML += '<span class="player1"></span></li>';
  initialBoardHTML += '<li class="players" id="player2">';
  initialBoardHTML += '<svg xmlns="http://www.w3.org/2000/svg" width="42" height="43" viewBox="0 0 42 43" version="1.1"><g stroke="none" stroke-width="1" fill="none" fill-rule="evenodd"><g transform="translate(-718.000000, -60.000000)" fill="#000000"><g transform="translate(739.500000, 81.500000) rotate(-45.000000) translate(-739.500000, -81.500000) translate(712.000000, 54.000000)"><path d="M30 30.1L30 52.5C30 53.6 29.1 54.5 28 54.5L25.5 54.5C24.4 54.5 23.5 53.6 23.5 52.5L23.5 30.1 2 30.1C0.9 30.1 0 29.2 0 28.1L0 25.6C0 24.5 0.9 23.6 2 23.6L23.5 23.6 23.5 2.1C23.5 1 24.4 0.1 25.5 0.1L28 0.1C29.1 0.1 30 1 30 2.1L30 23.6 52.4 23.6C53.5 23.6 54.4 24.5 54.4 25.6L54.4 28.1C54.4 29.2 53.5 30.1 52.4 30.1L30 30.1Z"/></g></g></g></svg>';
  initialBoardHTML += '<span class="player2"></span></li>';
  initialBoardHTML += '</ul>';
  initialBoardHTML += '</header>';
  initialBoardHTML += '<ul class="boxes">';
  for(var s = 0; s < 9; s++) {
    initialBoardHTML += '<li class="box" data-square="' + s + '"></li>';
  }
  initialBoardHTML += '</ul>';
  initialBoardHTML += '</div>';

  // clear the game board at the start of a new game
  var init = function() {
    gameboard = [];
  }

  // export game board code block
  var getInitialBoard = function() {
    return initialBoardHTML;
  }

  // export current game board
  var getBoard = function() {
    return gameboard;
  }

  // parse the on-screen board for x and o and update the game board
  var boardContents = function() {
    $('.boxes li').each(function(){
      var index = parseInt($(this).attr('data-square'));
      if ($(this).hasClass('box-filled-1')) {
        gameboard[index] = 'o';
      } else if ($(this).hasClass('box-filled-2')) {
        gameboard[index] = 'x';
      } else {
        gameboard[index] = '';
      }
    });
  }

  // logic to check if a board (which could be either the game board and minimax board) has a win or tie
  var winningBoard = function (eitherboard) {
    var result = 'game in progress';
    for (var i = 0; i < winningRoutes.length; i++) {
      if (eitherboard[winningRoutes[i][0]] === 'x' && eitherboard[winningRoutes[i][1]] === 'x' && eitherboard[winningRoutes[i][2]] === 'x') {
        result = 'winx';
        break;
      } else if (eitherboard[winningRoutes[i][0]] === 'o' && eitherboard[winningRoutes[i][1]] === 'o' && eitherboard[winningRoutes[i][2]] === 'o') {
        result = 'wino';
        break;
      }   
    }
    if (eitherboard.indexOf('') === -1 && result !== 'winx' && result !== 'wino') {
        result = 'tie';
    }
    return result;
  }

  // update the game board and check for a win or tie after a move
  var status = function() {
    boardContents();
    var result = winningBoard(gameboard);
    return result;
  }

  // update the minimax board and check for a win or tie after a move
  var checkAIBoard = function(aiboard) {
    var airesult = winningBoard(aiboard);
    return airesult;
  }
  // export the following functions for use in the game module and ai module
  return {
    init: init,
    getInitialBoard: getInitialBoard,
    getBoard: getBoard,
    status: status,
    checkAIBoard: checkAIBoard
  }
})();

// game.js
var Game = (function GamePlay() {
  "use strict";

  // set players, clear board, and start new game
  var init = function(){
    Players.init();
    Board.init();
    start();
  };

  var repeat = false;  // did the user click 'new game' after the last game or is this the first game?
  var type;

  // HTML code block for the choose game type screen
  var gameTypeScreen = '<div class="screen screen-start" id="type">';
  gameTypeScreen += '<header>';
  gameTypeScreen += '<h1>Tic Tac Toe</h1>';
  gameTypeScreen += '<p class="intro">Please Choose Your Game Type:</p>'
  gameTypeScreen += '<a id="1player" href="#" class="button">1 Player Game<br><span class="subtitle">player vs. computer</span></a>'
  gameTypeScreen += '<a id="2player" href="#" class="button">2 Player Game<br><span class="subtitle">player vs. player</span></a>'
  gameTypeScreen += '</header>';
  gameTypeScreen += '</div>';

  // HTML code block for the enter your names screen
  var buildStartScreen = function() {
    var startScreen = '<div class="screen screen-start" id="start">';
    startScreen += '<header>';
    startScreen += '<h1>Tic Tac Toe</h1>';
    startScreen += '<p class="intro">Please Enter Your ';
    if (type === 1) {
      startScreen += 'Name:';
    } else if (type === 2) {
      startScreen += 'Names:';
    }
    startScreen += '</p>';
    startScreen += '<input type="text" name="player1" placeholder="Player 1" class="button">';
    if (type === 2) {
      startScreen += '<input type="text" name="player2" placeholder ="Player 2" class="button">';
    }
    startScreen += '<a id="startGame" href="#" class="button">Start Game</a>';
    startScreen += '</header>';
    startScreen += '</div>';
    return startScreen;
  };

  // renders code blocks on the screen
  var renderHTML = function(target,html) {
    $(target).html(html);
  };

  // highlights the current player's box on the screen
  var renderCurrentPlayer = function() {
    $('#player1,#player2').removeClass('active');
    var players = Players.getPlayers();
    if (players.current === players.player1) {
      $('#player1').addClass('active');
    } else {
      $('#player2').addClass('active');
    }
  };

  // makes a gray x or o appear in an unoccupied square when the current player hovers the mouse over it
  var hoverCurrent = function() {
    var players = Players.getPlayers();
    var hoverMarker;
    if (players.current === players.player1) {
      hoverMarker = "img/o.svg";
    } else if (players.current === players.player2) {
      hoverMarker = "img/x.svg";
    }
    $('.boxes li').unbind();
    $('.boxes li').hover(function() {
      if (!$(this).hasClass('box-filled-1') && !$(this).hasClass('box-filled-2')) {
        $(this).css('background-image','url(' + hoverMarker + ')');
      }
    }, function() {
      if (!$(this).hasClass('box-filled-1') && !$(this).hasClass('box-filled-2')) {
        $(this).css('background-image','none');
      }
    });
  };

  // HTML code block for the game over screen
  var gameEndScreen = function(result) {
    var players = Players.getPlayers();
    var gameOver;
    if (result === 'wino') {
    gameOver = '<div class="screen screen-win screen-win-one" id="finish">';
    } else if (result === 'winx') {
      gameOver = '<div class="screen screen-win screen-win-two" id="finish">';
    } else if (result === 'tie') {
      gameOver = '<div class="screen screen-win screen-win-tie" id="finish">';
    }
    gameOver += '<header>';
    gameOver += '<h1>Tic Tac Toe</h1>';
    if (result === 'winx' || result === 'wino') {
      gameOver += '<p class="message">Winner:<br>' + players.current.name + '</p>';
    } else {
      gameOver += '<p class="message">It\'s a Tie!</p>';
    }
    gameOver += '<a id="newGame" href="#" class="button">New game</a>';
    gameOver += '</header>';
    gameOver += '</div>';
    return gameOver;
  };

  // remove game over screen at game start if user just finished a game
  // render the game type screen and call button event function
  var start = function() {
    if (repeat) {
      $('#finish').detach();
    }
      renderHTML('body',gameTypeScreen);
      setGameTypeButtons();
  };

  // set event handlers for the game type buttons
   var setGameTypeButtons = function() {
    $('#1player').click(function(){
      type = 1;
      setGameType();
    });
    $('#2player').click(function(){
      type = 2;
      setGameType();
    });
  };

  // remove previous screen and render the enter your names screen
  var setGameType = function() {
    $("#type").detach();
    var startPage = buildStartScreen();
    renderHTML('body',startPage);
    getNames();
  };

  // get name(s) of player(s) with form validation
  // when names are entered and start button is clicked, current view is detached, initial board is rendered, and game begins
  var getNames = function() {
    $('#startGame').click(function(event) {
      $('input[name=player1],input[name=player2]').removeClass('inputError');
      $('.intro').removeClass('textError');
      if ($('input[name=player1]').val() === '' || ($('input[name=player2]').val() === '') && type === 2) {
        event.preventDefault();
        if ($('input[name=player1]').val() === '') {
          $('input[name=player1]').addClass('inputError');
        } 
        if ($('input[name=player2]').val() === '' && type === 2) {
          $('input[name=player2]').addClass('inputError');
        }
        $('.intro').addClass('textError');
      } else {
        var player1 = $('input[name=player1]').val();
        if (type === 2) {
          var player2 = $('input[name=player2]').val();
        } else var player2 = 'Computer';
        Players.setPlayerNames(player1,player2);
        $("#start").detach();
        renderHTML('body',Board.getInitialBoard);
        $('.player1').html(player1);
        $('.player2').html(player2);
        move();
      }
    });
  };

  // set up on-screen interactivity for the current player
  var move = function() {
    renderCurrentPlayer();
    hoverCurrent();
    setMarker();
  };

  // handles what happens when a player clicks on a square
  var setMarker = function() {
    var players = Players.getPlayers();
    var marker;
    if (players.current === players.player1) {
      marker = 'box-filled-1';
    } else if (players.current === players.player2) {
      marker = 'box-filled-2';
    }
    $('.boxes li').click(function(){
      if (!$(this).hasClass('box-filled-1') && !$(this).hasClass('box-filled-2')) {
        $(this).addClass(marker);
        afterMove();
      }
    });
  };

  // after a player clicks on a square, check for a win or tie then change players.  
  // if yes, remove current screen, render game over screen, and attach event handler to new game button.
  // if no, change players, then call functions for the next player's move (human or computer)
  var afterMove = function() {
    var result = Board.status();
    var players = Players.getPlayers(); 
    if (result === "winx" || result === "wino" || result === "tie") {
      $('#board').detach();
      renderHTML('body',gameEndScreen(result));
      $('#newGame').click(function() {
        repeat = true;
        init();
      });
    } else {
      Players.changePlayers();
      if(type === 1 && players.current.name === 'Computer') {
        AI.computerMove();
        afterMove();
      } else {
        move();
      }
    }
  };
  // export init function for use in app.js
  return {
    init: init
  };
})();

// players.js
var Players = (function Players() {

  var players = {
    player1: {
      name: "one",
      marker: "o"
    },
    player2: {
      name: "two",
      marker: "x"
    }
  }

  // set current player to player 1 at the start of the game
  var init = function() {
    players.current = players.player1;
  }

  // set player names upon input from the choose names screen
  var setPlayerNames = function(player1,player2) {
    players.player1.name = player1;
    players.player2.name = player2;
  };

  // change players between plays
  var changePlayers = function() {
    if (players.current === players.player1) {
      players.current = players.player2;
    } else {
      players.current = players.player1;
    }
  }

  // export players JSON
  var getPlayers = function() {
    return players;
  }
  // export the following functions for use in other modules
  return {
    init: init,
    setPlayerNames: setPlayerNames,
    getPlayers: getPlayers,
    changePlayers: changePlayers
  }
})();
Steven Parker
Steven Parker
230,970 Points

It looks like this is only part of the code.

There's probably an HTML component, some CSS, and perhaps even more JavaScript. If you post the whole thing it will facilitate observing the issue.

If this is in a workspace, use the snapshot function and provide the link to that.

I've updated the post with the code from all of the JavaScript files from this project. There's some HTML and CSS but it's really not relevant to the problem. The GitHub for it is https://github.com/DanielMcNeil/tic-tac-toe-v3 if you would like to see the whole thing.

I did refactor and add comments, as well as fix a faulty win/tie function. But I am still having the original problem, which is that the computer will not choose the best move. It won't even block.

1 Answer

Steven Parker
Steven Parker
230,970 Points

:point_right: Your "minimax" function is more of a "maximax" at the moment.

You wrote "There's some HTML and CSS but it's really not relevant to the problem." It may not be the cause of the problem, but the code needs to be present to be able to observe the problem. With all the pieces present I was able to try it out.

So it turns out the problem is in minimax where you have this line:

      lowScore = Math.max.apply(Math,scores);

It is not actually computing a low score, but a high score, just like the code above it. What you probably intended was this:

      lowScore = Math.min.apply(Math,scores);

With this change, the computer plays the "cautious" path, always going for a draw unless the opponent makes a mistake.

Yes it probably would have been more helpful to give you all of the code so that you could actually play the game. Sorry about that!

You were right. I can't believe I missed such an obvious mistake. I think that by trying to maximize the opponents score, instead of minimizing it, I ended up with a scenario where the computer thinks that it will always win no matter what square it picks. This would explain why all of the scores were positive (and all the same) no matter which square was chosen.

Thank you so much for your help!!!