Minimax for Tic-Tac-Toe

Question

I have written AI for Tic-Tac-Toe using Negamax in JavaScript. The Negamax object is translated from an implementation written in Python. The code runs on a Node.js server and the player interacts with it via web socket. The code works and the game is unbeatable meaning it always wins if it can and if it can't, will force a tie.

I am looking for advice on how to optimize this implementation of MiniMax. I am also fairly new to Node.js and am wondering if this will run in a non-blocking way (assuming an instance of the object for each connected user.

Minimax Object:

var MiniMax = function(){
  //init values and options
  this.bestMove = 0;
  this.MAX_DEPTH = 6;
}

MiniMax.prototype = {
  //function called from game, bestmove will return the computer move
  buildTree: function(board, player, cb){
    this.bestMove = 0;
    var alpha = this.buildTree_r(board, player, 0);
    cb(this.bestMove);
  },
  //recursive function to build minimax tree and rate the value of the board
  buildTree_r: function(board, currPlayer, depth){
    if(depth > this.MAX_DEPTH){
      return 0;
    }
    //Set the otherplayer for the next game state and to check for loss
    var otherPlayer;
    if(currPlayer == board.X){
      otherPlayer = board.O;
    } else {
      otherPlayer = board.X;
    }
    //check for a winner in the boardstate, if currPlayer we win, else we lose in this tree
    var winner = board.getWinner();
    if(winner == currPlayer){
      return 1;
    } else if(winner == otherPlayer){
      return -1;
    }
    //check for a full board and therefore cats game in this true
    if(board.isFull()){
      return 0;
    }
    //this is where we begin to rank moves, get an array of moves, set alpha low, instantiate parallel
    //subAlpha list  to movelist to remember move ranks
    var moveList = board.getMoves();
    var alpha = -1;
    var saList = [];
    for(var i=0; i<moveList.length; i++){

      var boardCopy = board.copy(); //Copy current gamestate
      boardCopy.move(currPlayer, moveList[i]); //Make a move for in the gamestate for each possible move
      //console.log(boardCopy.gamestate);

      var subalpha = -this.buildTree_r(boardCopy, otherPlayer, depth + 1); //pass new gamestate into recursion
      if(alpha < subalpha){ //if move is better than alpha, increase alpha
        alpha = subalpha;
      }
      if(depth == 0){ //only if we are looking at REAL gamestate do we push an alpha to the list
        saList.push(subalpha);
      }
    }
    if(depth == 0){
      var posMoves = [];
      for(var n=0; n<saList.length; n++){
        if(saList[n] == alpha){
          posMoves.push(moveList[n]);
        }
      }
      this.bestMove = this.rand(posMoves); //in future pick random..
    }
    return alpha;
  },
  rand: function(list){
    var item = list[Math.floor(Math.random() * list.length)];
    return item;
  }
}

Board Object:

var Board = function(){
  this.empty = 0;
  this.X = 1;
  this.O = 2;
  this.wins = [
    [0,1,2],
    [3,4,5],
    [6,7,8],
    [0,3,6],
    [1,4,7],
    [2,5,8],
    [0,4,8],
    [2,4,6]
    ];
  this.gamestate = [0,0,0,0,0,0,0,0,0];
}

Board.prototype = {
  copy: function(){
    var b = new Board();
    for(var i=0; i<9; i++){
      b.gamestate[i] = this.gamestate[i];
    }
    return b;
  },
  move: function(player, pos){
    this.gamestate[pos] = player;
  },
  getMoves: function(){
    var moves = [];
    for(var i=0; i<9; i++){
      if(this.gamestate[i] == this.empty){
        moves.push(i);
      }
    }
    return moves;
  },
  isFull: function(){
    for(var i=0; i<9; i++){
      if(this.gamestate[i] == this.empty){
        return false;
      }
    }
    return true;
  },
  getWinner: function(){
    for(var i=0; i<this.wins.length; i++){
      var a, b ,c;
      a = this.gamestate[this.wins[i][0]];
      b = this.gamestate[this.wins[i][1]];
      c = this.gamestate[this.wins[i][2]];

      if(a == b && a == c && a != this.empty){
        return a;
      }
    }
    return this.empty;
  }
}

Answer 1

This would be a good place to use a ternary comparison operator:

var otherPlayer;
if(currPlayer == board.X){
  otherPlayer = board.O;
} else {
  otherPlayer = board.X;
}

Then it would become a single line:

var otherPlayer = currPlayer == board.X ? board.O : board.X;

You could do this in a few other places as well.

---

for(var i=0; i<moveList.length; i++){

You use spaces around your operators for the most part, you should be consistent with this.

---

var b = new Board();

In the Minimax object code, you use good variables names. Not so much in the Board object code.

Otherwise, this looks good to me, very clean, neat, and well documented.