Question About Minimax Algorithm and Code Execution

Question About Minimax Algorithm and Code Execution
0.0 0

#1

Hello FCC,

I am working on my Tic Tac Toe game an I would like to implement minimax for my opponent’s turn. I think I understand in a general sense how the algorithm and tree structure works but I’ve been reading lots of different code implementations and one thing in particular has me confused — order of how the code is executed and how are results are stored.

Here is what I have so far:

runMinimax: function(board, player){
    if (gameState.checkForVictory(board).icon === managePlayers.computerPlayer.icon){
      //computer won
      return 1;
    } else if (gameState.checkForVictory(board).icon === managePlayers.playerOne.icon){
      //human won
      return -1
    } else if (board.indexOf(null) === -1){
      //draw
      return 0;
    } else {
      //carry on with the algorithm
      let nextPlayer = player === 'x' ? 'o' : 'x';
      let moves = [];
      let scores = [];
      let nextBoard = board.slice(); ///copy board to avoid changing actual game state;
      let availableMoves = this.getAvailableMoves(nextBoard); //array of open spaces on the board
  
      for (let i = 0; i < availableMoves.length; i++){
        nextBoard[availableMoves[i]] = player; //set the first available move to the icon of player (x or o depending on # of recursive calls?? aka 'depth')
        scores.push(this.runMinimax(nextBoard, nextPlayer)); //next player is the opposite icon then was passed in;
        moves.push(availableMoves[i]); //push the index into moves array
      }
      if (managePlayers.getCurrentPlayer() === managePlayers.computerPlayer){ //if comps turn comp is maximizing get highest
        //find the biggest score in scores array
        //make the move that corresponds with that score
      } else { //if human turn, human is minimizing, get lowest
        //find the smallest score in scores array
        //make the move that corresponds with that score
      }
    }

So basically, I first check if the board passed in is a winning board (computer wins), a losing board(human wins) or a draw. If none are true I continue with the algorithm. The nextPlayer is set to switch back and forth when the recursive calls start. A moves array and scores array are also created. This seem to be the containers that hold the values that will be used to make decisions, but I don’t understand how this works because are they not reset to a blank array after every recursive call?

Next we enter the for loop. I change the state of the board by adding a player move to the first open space on the board. I We push into the scores array the result of a recursive call to runMinimax(). If this is the second move of the game (human went first, then we added a move in the line above) are there 7 more recursive calls before anything is returned / the for loop increments by one? But if something is returned the for loop wont even be executed… Also, are the scores and moves arrays not reset to [] after every recursive call? isnt this a problem? If anyone could help me out picturing what the scores and moves arrays are doing / look like it would be really helpful.

After the for loop and recursion has taken place there is another if statement which determines who the current player of the game is. If it is the computer – since the computer is my maximizing player I will select the move corresponding to the max value. If it is the human, I will select the minimum score and then make the move associated with it. But again i dont really understand how these arrays work or what they look like.

This post has gotten a lot more longwinded than I intended but if anyone could shed some light on how this code executing (recursion nested inside for loop) and how the moves/scores arrays work it would be really helpful. I find myself more confused every time i step through it line by line.

Thanks in advance!


#2

To answer your first question as directly as I can, what should be passed into runMinimax is the ‘board state’ (all moves so far). What the newly initialized moves array represents is the next board state (ie. the state after the next move is chosen).

The new board state is passed back into the function (recursively) and that process is repeated until a winner is detected. Each run of the function tests a board that is one move closer to victory.

The design of the function should test every possible combination of board states and pass back relative “scores” using the return values.

One final return value is included at the end of the function with the move whos series of moves (via recursive calls) produced the best “score”.

Sorry if my explination is unclear. Recursive functions, and this one in particular, are not easy to explain via forum.Someone shared a JS Fiddle with a tic-tac-toe / minmax solution in Javascript here if you get stuck for too long.

For what it’s worth, using this method in tic-tac-toe is overkill. It’s sort-of a proof of concept for a technique that would be necessary for more complicated games. I think I was able to put together an AI that always wins without recursion and with a little logic (prefer to move in the center, prefer to move to corners, take winning moves first, etc.). Minmax is more elegant for sure :slight_smile:


#3

Thanks for the input @cjsheets – really appreciate it.

As a small update i did manage to implement minimax by heavily referencing some code written by @geligelu and applying it to my game (thanks!)

I still have a lot of questions RE: HOW the code executes. But hopefully with more study and reviewing my code daily I will be able to get a REALLY solid grasp on everything.


#4

@Swoodend - hey thanks for the tag and the mention. Glad that my code could be useful. I thought the comments in the code went a long way to explaining how minimax works.

If you still need some pointers, list some explicit questions and we’ll see what we can do.

Can you share your final code so I can see how I was ‘heavily referenced’? :wink:


#5

I made this image to help you (and others) understand the code execution. Recursive functions can be difficult to understand.


#6

Hi @geligelu,

First off, thank you for taking the time to go through your code so thoroughly. You can find my code below. I think functionally the only difference between my code and yours is that I check for a draw when the function begins execution whereas you handled it later.

I’m going to take some time to go over the image that you posted and try my best to understand the execution of the code. Again thank you so much for doing this. I’m sure I will have some specific questions later :slight_smile:

const Ai = {
  takeTurn : function(){
    //call miniMax, pass in the max player and min player. miniMax will call runMM()
    this.miniMax(ManagePlayers.computerPlayer.icon, ManagePlayers.playerOne.icon); //max player is o (computer), min player is x (human)
    //increment turns by 1
    GameState.incrementTurns();
    //check for victory
    if (GameState.checkForVictory(GameState.currentState, ManagePlayers.computerPlayer.icon)){
      ControlUi.displayWin(ManagePlayers.computerPlayer); 
    }
  },
  
  miniMax : function(maxPlayer, minPlayer){
    let nextMove = null;
    
    function runMM(board, player, depth){
      if(GameState.checkForVictory(board) === maxPlayer) { 
        return 10 - depth;
      } else if (GameState.checkForVictory(board) === minPlayer){ 
        return depth - 10;
      } else if (GameState.checkForDraw(board)){
        return 0;
      }
      
      //next player is set to switch between x and o through subsequent recursive calls
      let nextPlayer = player === 'x' ? 'o' : 'x';
      let moves = [];
      let scores = [];
      
      for (let i = 0; i < board.length; i++){
        let boardCopy = board.slice();
        if (boardCopy[i] === null){
          boardCopy[i] = nextPlayer;
          moves.push(i);
          scores.push(runMM(boardCopy, nextPlayer, depth + 1))
        }
      }
      
      if (depth === 0){
        nextMove = moves[scores.indexOf(Math.max.apply(null, scores))];
      } else {
        if (nextPlayer === maxPlayer){
          return Math.max.apply(Math, scores);
        } else {
          return Math.min.apply(Math, scores);
        }
      }
    }// run mm
    runMM(GameState.currentState, minPlayer, 0); //actually call the function that determines the next move
    GameState.move(nextMove, ManagePlayers.computerPlayer); //update the game state
    ControlUi.displayMove(nextMove, ManagePlayers.computerPlayer);  //display the move on the board
  }
}

#7

I particularly agree with @cjsheets comments. However it is a nice challenge to implement the more complex solution.

EDIT: I deleted my explanation for the recursion because it was still wrong and cumbersome. I will try to see if I can find a better way to explain it and post it here or somewhere in the forum.