4

As a personal exercise I'm trying to implement a minimax based tic-tac-toe game. I've been studying examples in a variety of languages I have found online. My implementation is at a point where it seems like its working but then the AI loses in certain edge cases. You can play my version here

If you select 3 corners and then the center you will win. Otherwise it seems to perform correctly. I can manually run my minmax() function with different game states and it seems to score incorrectly for the AI's first move. I'm worried that there is something fundamentally wrong with how i'm implementing the algorithm.

Here is my code:

// Board state 'object'
function State(old) {
  // Prior board states can be loaded in during minmax recursion
  if (typeof old !== 'undefined') {
    this.board = old.board.slice(0);
  } else {
  // Otherwise start with empty board
    this.board = ['E','E','E','E','E','E','E','E','E'];  
  }
  // Terminal game flag
  this.result = 'active';
  // Current player flag
  this.turn = "X";
  // Label to identify move that results in this state during recursion
  this.element = "";
  // Function to switch active player for minmax scoring
  this.advanceTurn = function() {
    this.turn = this.turn === "X" ? "O" : "X";
  }
  // Function to determine if game is complete
  this.isTerminal = function() {
    const lines = [
      [0, 1, 2],
      [3, 4, 5],
      [6, 7, 8],
      [0, 3, 6],
      [1, 4, 7],
      [2, 5, 8],
      [0, 4, 8],
      [2, 4, 6],
    ];
    for (let i = 0; i < lines.length; i++) {
      const [a, b, c] = lines[i];
      if (this.board[a] !== 'E' && this.board[a] === this.board[b] && this.board[a] === this.board[c]) {
        this.result = this.board[a];
        return true;
      } 
    } 
    if (this.moves().length < 1) {
        this.result = 'DRAW';
        return true;
    }
    return false;
  }
  // Function to find all possible moves
  this.moves = function() {
    arr = this.board.reduce(function(array,el,index){
      if (el === 'E') {
        array.push(index);
      }
      return array;
    },[]);
    return arr;
  }
}

// Recursive minmax function
function minmax(state) {
  // 1) If the state is terminal, return the score from O's perspective
  if (state.isTerminal() === true) {
    if (state.result === 'X') {
      return  -10; 
    } else if (state.result === 'O') {  
      return 10;
    } else {
      return 0;
    }
  } 

  // Generate list of possible new game states (moves) 
  newStatesSet = state.moves().map(function (el) {
    var newState = new State(state);
    newState.board[el] = state.turn.slice(0);
    newState.advanceTurn();
    newState.element = el;
    return newState;
  });  

  // Array to hold all child scores
  var newStateScores = [];

  // For each of these states, add the minmax score of 
  // that state to the scoreList
  newStatesSet.forEach(function(newState) {
    var newStateScore = minmax(newState);
    newStateScores.push(newStateScore);
  });
  stateScore = Math.min(...newStateScores);
  return stateScore;
}

function aiMove(state) {
  var possibleScores = [];
  var possibleMoves = [];
  var possibleStates = state.moves().map(function(el) {
    var newState = new State(state);
    possibleMoves.push(el);
    newState.board[el] = 'O';
    possibleScores.push(minmax(newState));
    return newState;
  });
  if (possibleMoves.length < 1) {
    return -1;
  }
  console.log(possibleStates);
  console.log(possibleScores);
  function indexOfMax(arr) {
    var max = arr.reduce(function(a,b) {
      return b > a ? b : a;   
    });
    return arr.indexOf(max);
  }
  return possibleMoves[indexOfMax(possibleScores)];
}  

var game = new State();
game.board = ['E','E','E',
              'O','E','E',
              'X','E','X']
game.turn = 'O';
//console.log(minmax(game));
console.log(aiMove(game));
1

2 Answers 2

2

MiniMini algorithm

I think there is a problem in your recursive minmax function here:

stateScore = Math.min(...newStateScores);

This always computes the minimum, so you are actually running an algorithm where in the recursion both X and O are cooperating to make X win!

(At your top level you do use max, but not within the recursion.)

You can fix this by choosing whether to max or min based on state.turn.

Sign up to request clarification or add additional context in comments.

1 Comment

Thanks for looking over the code! In the recursion, I am running Math.min on the set of scores of all the children of the current round on the function. I did this so that the AI would avoid states where it can lose. This was a simplified solution that after going through a bunch of cases on paper, i realize is wrong. I added a conditional to check the current turn and min or max depending on whose turn. it was still giving weird answers, but I noticed that I had a bug in the way I was assigning the current turn to new states generated from old states. I fixed that and now its working!
0

Perhaps this implementation in Typescript can help guide you. It uses Board and MiniMaxItem like:

interface Board {
    gameOver: boolean;
    score: number;
    playerX: boolean;
    val: GridEntry[];
}
interface  MinMaxItem {
    score: number;
    board: Board;
}

MiniMaxItem is the recursive element in which the state and its recursive score is saved. For implementation in JavaScript you have to change the methods of the BoardManager class by functions.

3 Comments

What does "...you have to change the methods of the BoardManager class by functions." mean?
I changed the code, check the repository again and you will understand
The link is now dead. Can you clarify how minimax can be implemented using these data structures?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.