Minimax implementation

minimax.js

'use strict';
// testing out minimax algorithm on node first before adding it to client side

/*
 a recursize algorithm
 base cases are end states
 1 for a win, 0 for a draw and -1 for a loss

 recursive steps
 recurse down with the other person's turn  
*/

// =============================== HELPER FUNCTIONS ======================================

// find draw
function isDraw(board){
	// check that none of the squares is null
	for(var i=0; i<3; i++){
		for(var j=0; j<3; j++){
			// one of the spaces is empty
			if(board[i][j] == null){
				return false;	
			}	
		}	
	}
	return true;
}

function calculateWinner(squares) {
  // squares is now a 2D array
  // checks rows, colums and diagonals
  // return a list of list containing the winning line
  // ie [[0,0], [1,1], [2,2]]
  
  // row check
  for (let i = 0; i < 3; i++) {
    if (squares[i][0] && squares[i][0] === squares[i][1] && squares[i][0] === squares[i][2]) {
      return [[i, 0], [i, 1], [i, 2]];
    }
  }
  
  // col check
  for (let j = 0; j < 3; j++) {
    if (squares[0][j] && squares[0][j] === squares[1][j] && squares[0][j] === squares[2][j]) {
      return [[0, j], [1, j], [2, j]];
    }
  }
  
  // diag check
  if (squares[0][0] && squares[0][0] === squares[1][1] && squares[0][0] === squares[2][2]) {
      return [[0, 0], [1, 1], [2, 2]];
  }
  
  if (squares[2][0] && squares[2][0] === squares[1][1] && squares[2][0] === squares[0][2]) {
      return [[2, 0], [1, 1], [0, 2]];
  }
  
  return null;
}

function nextTurn(turn){
	return turn == 'X' ? 'O' : 'X';
}

function printBoard(board){
	for(var i=0; i<3; i++){
		console.log(board[i]);
	}
	console.log('\n');
}

// =============================== HELPER FUNCTIONS ======================================

/*
 this function needs to know who the AI is in order to make
 the proper decision

 takes the board and who's turn it is
 returns highest scoring move
*/

// hardcoded as a global
// ideally, the function has a way to access who the AI plays (X or O)
var AI_player = 'X';

function findBestMove(board, turn, depth){

	// base cases
  var winner = calculateWinner(board);
	if(winner){
		// check who's the winner, return accordingly
		var x = winner[0][0];
		var y = winner[0][1];	
		
		if(board[x][y] == AI_player){
			return 10-depth;	
		} 
		else{
			return depth-10;	
		}
	}

	// draw case
	if( isDraw(board) ){
		return 0;	
	}

	// store the moves
  var moves = [];
	depth += 1;

	// recursive step
	for(var i=0; i<3; i++){
		for(var j=0; j<3; j++){

			// if the value isn't null, add it in and recurse
			if(board[i][j] == null){
				board[i][j] = turn;

				// move will be an obj of the format {x, y, score}
				var move = {};
				var score = findBestMove(board, nextTurn(turn), depth);
				
				// score can be an object
				// if so, extract the score
				if( !(typeof score == "number") ){
					score = score.score;
				}

				// set the values
				move.x = i;
				move.y = j;
				move.score = score;

				moves.push(move);
				
				// backtrack
				board[i][j] = null;
			}	
		}	
	}

	// look at the board and current available moves
	console.log('the board that was passed in is =============');
	printBoard(board)
	console.log('the moves are', moves);
	console.log('\n');

	// find the idx with the max and min
	var min = 0;
	var max = 0;
	// go through the scores, find 	
	for(var k=1; k<moves.length; k++){
		if(moves[k].score > moves[max].score){
			max = k;	
		}			
		if(moves[k].score < moves[min].score){
			min = k;	
		}
	}
	
	// if it's the AI's turn return max, otherwise min
	var result = turn == AI_player ? moves[max] : moves[min];
	return result;
}


// create dummy boards, can change this around
// WARNING, an empty board will crash your browser

var board = [['O', null, 'X'], 
						 ['X', null, null], 
						 ['X', 'O', 'O']];

// var board = [['X', 'O', null], 
// 						 ['O', 'X', 'O'], 
// 						 [null, null, null]];

// find next move for 'X'
findBestMove(board, 'X', 0);