Implement alpha-beta pruning in my game tree generator for Tic Tac Toe?

Implement alpha-beta pruning in my game tree generator for Tic Tac Toe?
0

#1

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 have looked at many different examples of implementations of alpha-beta pruning on S/O and Google but they all seem to be for searching an already existing tree. I would like to implement alpha-beta pruning in my code so that it doesn’t build the entire tree and skips (prunes) branches/nodes that don’t need to be expanded. How can I modify this code to implement alpha-beta pruning?

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);