Tic Tac Toe game tree generator minimax

Question

I have coded a working Tic Tac Toe game tree generator. It doesn't only generate the game tree, it also applies minimax values to each node. The code works fine on a board that already has 2 or more played moves but slows down significantly for an empty board. I'm thinking of implementing alpha-beta pruning.

I am, however, having a hard time figuring out how I could modify my existing code to accommodate that. Can anyone point me in the right direction or suggest other improvements that may help with performance?

Notes: I am representing game states as a string in this format "0,0,0,1,0,0,-1,0,0" where 1 represents player X, -1 represent player O and 0 represents and empty square.

// Node constructor
var Node = function(state, parent, toPlay) {
  this.toPlay = toPlay;
  this.bestValue = null;
  this.state = state;
  this.parent = parent;
  this.child = [];
};

// Tree constructor
var Tree = function(state, toPlay) {
  this._head = new Node(state, null, toPlay);
};

// Possible winning combinations
var winStates = [
  [0, 1, 2],
  [3, 4, 5],
  [6, 7, 8],
  [0, 3, 6],
  [1, 4, 7],
  [2, 5, 8],
  [0, 4, 8],
  [6, 4, 2]
];

// Check if game has been won
var checkIfWon = function(gameState, mark) {
  // Convert gameState string to array
  gameState = gameState.split(",").map(function(c) {
    return parseInt(c, 10)
  });
  // Iterates thru the winning combos to see if one is active
  var winner = winStates.some(function(combination) {
    var winning = true;
    for (var y = 0; y < combination.length; y++) {
      if (gameState[combination[y]] !== mark) {
        winning = false;
      }
    }
    return winning;
  });
  return winner;
};

// Check if game is a draw
var checkIfDraw = function(gameState) {
  return possibleMoves(gameState).length === 0;
}

// Check possible moves
var possibleMoves = function(gameState) {
  // Convert gameState string to array
  gameState = gameState.split(",").map(function(c) {
    return parseInt(c, 10)
  });
  return gameState.reduce(function(p, c, i) {
    if (c === 0) {
      p.push(i);
    }
    return p;
  }, []);
}

// Populate game tree
var populateTree = function(currentNode, toPlay) {
  if (checkIfWon(currentNode.state, 1)) {
    currentNode.bestValue = 1;
    return;
  }
  if (checkIfWon(currentNode.state, -1)) {
    currentNode.bestValue = -1;
    return;
  }
  if (checkIfDraw(currentNode.state)) {
    currentNode.bestValue = 0;
    return;
  }
  // Generate possible next moves
  var possible = possibleMoves(currentNode.state);
  for (var i = currentNode.state - 1; i >= 0; i--) {
    possible.push(i);
  }

  while (possible.length) {
    // Selects the next move randomly
    var move = possible.splice(Math.floor(Math.random() * possible.length),
      1)[0];

    // Updates the new game state   
    var val = currentNode.state.split(",").map(function(c, i) {
      if (i === move) {
        return toPlay;
      }
      return parseInt(c, 10)
    }).join();

    // Create a new child Node  
    currentNode.child.push(new Node(val, currentNode, toPlay * -1));
    nodeCount++;
  }


  // Recursive call
  for (var j = 0; j < currentNode.child.length; j++) {
    populateTree(currentNode.child[j], toPlay * -1);

  }


  // Assign bestValue according to the value of child Nodes  
  if (currentNode.toPlay === 1) {
    currentNode.bestValue = currentNode.child.reduce(function(p, c) {
      return p > c.bestValue ? p : c.bestValue;
    }, -1);

  } else {
    currentNode.bestValue = currentNode.child.reduce(function(p, c) {
      return p < c.bestValue ? p : c.bestValue;
    }, 1);
  }



};

var nodeCount = 0;
tree = new Tree("0,0,0,1,0,0,-1,0,0", 1);
populateTree(tree._head, tree._head.toPlay);
//console.log(tree);
console.log(nodeCount);

Answer 1

Optimization ideas

Prevent wasteful data conversions

Don't convert from a string to an array. You could do better by simply storing your state as an array instead.

I suppose you chose to use a string since they are easily copied, but arrays are also easily copied with:

copy = old.slice(0);

You could do even better by keeping the state as a string; albeit with some modifications to the model. My only concern is the -1 since it's two characters. Using X, O, and - is a reasonable option, and it keeps the indices of the characters in the correct place.

"O-OXXX---" // a win for X

You'll also have some trouble with the high order functions since strings don't have them. Speaking of which...

High order functions come with a cost

While forEach, map, and some are awesome functions (and one of my favorite parts of JavaScript), they come with quite a bit of overhead compared to their for loop equivalents. The issue comes with the need to execute a callback function over and over as opposed to just running inline code.

Since your program is computation heavy, you probably want speed over elegance. Converting all the high order functions to for loops should help considerably.

Certain states are duplicates of others

You could use a JavaScript object to keep track of the past states, so you don't have to build redundant tree branches.

Something like:

stateMap = {};
// ...
state = makeMove(possibleMove);

if (stateMap[state] !== undefined) {
  // check state ...
  stateMap[state] = node;
  // recurse next possible moves ...
}
else {
  node.child = stateMap[state];
}

This way if a state ever comes up again, it will be defined in stateMap, and you can reuse the node. However, the parent pointers may become a bit muddled, so you might want to keep a list of parent nodes, or preform a deep copy on the child's branch.

Other optimization ideas

• Don't check every way to win each time. Each move only involves a subset of the possible ways.
• Certain states are merely rotations of others, but that might be hard to utilize.

---

Review

Modularize

Your code is global and scattered. You could store it in a function to make it more portable and scalable:

var ticTacToeTree = (function () {
    function Node(state, toPlay) {
        this.toPlay = toPlay;
        this.bestValue = null;
        this.state = state;
        this.parents = [];
        this.children = [];
    };

    var head = new Node("---------", 'X');

    // The rest of your code

    return {
        head: head
    };
})();

Reusable code

checkIfWon could be used to check both players:

function checkWinner(state) {
  for (var i = 0; i < winStates.length; i++) {
    if ("-" !==
         state[winStates[i][0]] ===
         state[winStates[i][1]] ===
         state[winStates[i][2]]) {
      return state[winStates[i][[0]];
    }
  }
  return "-"; // no one has won
}

Which prevents redundant calls:

function populateTree(currentNode, toPlay) {
  var winner = checkWinner(currentNode.state);

  if (winner === "-" && checkDraw(currentNode.state)) {
    return currentNode.bestValue = 0;
  }
  else if(winner === "X") {
    return currentNode.bestValue = 1;
  }
  else if(winner === "O") {
    return currentNode.bestValue = 1;
  }

  // ...
}

Don't worry about getting a random move; you end up computing them all anyways:

for (var i = 0; i < moves.length; i++) {
  move = moves[i];

  nextState = state.slice(0, move).concat(state.slice(move));

  if (stateMap[nextState] !== undefined) {
    var node = new Node(state, nextTurn(toPlay);
    node.parrents.push(currentNode);
    currentNode.children.push(node);
    populateTree(node, node.toPlay);
  }
  else {
    currentNode.children.push(stateMap[nextState]);
  }
}