# Minimax for Tic-Tac-Toe

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

• If you're new to Node.js and Javascript, a great tool to use is gulp or grunt. Something that will run JSHint for you. JSHint is a linter tool that finds common errors, like your unused 'alpha' variable on line 11. Also if the Game Tree Size is small enough, you might be able to use some memorization and save the results in a LRU cache. Jul 2, 2015 at 4:10

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.