tic-tac-toe.js

var Node = function (config, _isTerminal) {
  this.config      = config;
  this._isTerminal = _isTerminal;
};

Node.prototype.isTerminal = function () {
  this.evaluate();
  return this._isTerminal;
};

Node.prototype.draw = function () {
  var str = '';
  
  str = this.config.map(function (col) {
    col = col.map(function (cell) {
      return cell === null ? ' ' : (cell === 1 ? 'X' : 'O') ;
    }).join(' | ');
    
    return col;
  }).join("\n----------\n");
  
  return "\n" + str + "\n";
};

Node.prototype.expandChildren = function (player) {
  if (this.isTerminal()) {
    return [];
  }
  
  var nodes = [],
      newConfig, newNode;
  
  var rows = this.config,
      numNulls = 0;
  
  var cloneCol = function (col) {
    return col.slice(0);
  };
  
  var i, j, col;
  
  // Check for open spaces in grid
  for (i = 0; i < rows.length; i++) {
    col = rows[i];
    
    for (j = 0; j < col.length; j++) {
      if (col[j] === null) {
        numNulls++;
      }
    }
  }
  
  // Create variations
  for (i = 0; i < rows.length; i++) {
    col = rows[i];
    
    for (j = 0; j < col.length; j++) {
      if (col[j] === null) {
        // Can make move
        newConfig = rows.map(cloneCol); // Clone
        newConfig[i][j] = player;
        
        newNode = new Node(newConfig, (numNulls - 1) <= 0);
        nodes.push(newNode);
      }
    }
  }
  
  return nodes;
};

Node.prototype.evaluate = function () {
  var rows = this.config,
      val = 0,
      self = this;
  
  var rowCnts = [],
      colCnts = [];
  
  var diagCnt = [
    { 'null': 0, '1': 0, '2': 0 },
    { 'null': 0, '1': 0, '2': 0 }
  ];
  
  var i, j, k, col, cell;
  
  for (i = 0; i < rows.length; i++) {
    col = rows[i];
    
    colCnts[i] = { 'null': 0, '1': 0, '2': 0 };
    
    for (j = 0; j < col.length; j++) {
      cell = col[j];
      
      colCnts[i][cell]++;
      
      if (typeof rowCnts[j] === 'undefined') {
        rowCnts[j] = { 'null': 0, '1': 0, '2': 0};
      }
      
      rowCnts[j][cell]++;
      
      if (i === j) {
        diagCnt[0][cell]++;
      }
      
      if (j === (rows.length - i - 1)) {
        diagCnt[1][cell]++;
      }
    }
  }
  
  [rowCnts, colCnts, diagCnt].forEach(function (counter) {
    counter.forEach(function (item) {
      var counterVal = 0;
      
      if (item['1'] > item['2']) {
        if (item['2'] > 0) {
          // This is worth nuthin'
          counterVal = 0;
        } else if (item['null'] === 0) {
          // Winning condition for max
          counterVal = 1000;
          self._isTerminal = true;
        } else if (item['1'] > item['null']) {
          // We are getting there
          counterVal = 100;
        } else if (item['null'] > 0) {
          // This is something
          counterVal = 1;
        }
      } else if (item['2'] > item['1']) {
        if (item['1'] > 0) {
          // This is worth nuthin'
          counterVal = 0;
        } else if (item['null'] === 0) {
          // Winning condition for min
          counterVal = -1000;
          self._isTerminal = true;
        } else if (item['2'] > item['null']) {
          // We are getting there
          counterVal = -100;
        } else if (item['null'] > 0) {
          // This is something
          counterVal = -1;
        }
      }
      
      if (Math.abs(counterVal) > Math.abs(val)) {
        val = counterVal;
      }
    });
  });
  
  return val;
};

var minimax = function (node, depth, maxPlayer, alpha, beta) {
  var bestNode;
  
  if (depth === 0 || node.isTerminal()) {
    return [node, node.evaluate()];
  }
  
  if (maxPlayer) {
    node.expandChildren(1).some(function (_node) {
      var val = minimax(_node, depth - 1, false, alpha, beta);
      
      if (val[1] > alpha) {
        alpha = val[1];
        bestNode  = _node;
      }
      
      if (alpha >= beta) {
        return true;
      }
    });
    
    return [bestNode, alpha]
  } else {
    node.expandChildren(2).some(function (_node) {
      var val = minimax(_node, depth - 1, true, alpha, beta);
      
      if (val[1] < beta) {
        beta = val[1];
        bestNode  = _node;
      }
      
      if (alpha >= beta) {
        return true;
      }
    });
    
    return [bestNode, beta];
  }
};

var originNode = new Node([[null, null, null], [null, null, null], [null, null, null]], false);

var testCorrectness = function () {
  var node;
  
  node = new Node([[1, null, 2], [null, 2, null], [null, null, 1]], false);
  
  console.log(node.draw());
  console.log(node.evaluate(), 'expected: -100');
  
  node = new Node([[1, null, 2], [null, 2, null], [1, null, 1]]);
  
  console.log(node.draw());
  console.log(node.evaluate(), 'expected: 100');
  
  node = new Node([[null, 1, null], [null, 1, null], [null, 1, null]], true);
  
  console.log(node.draw());
  console.log(node.evaluate(), 'expected: 1000');
};

/* -------------
 * REACT UI
 * ------------- */

var GameCell = React.createClass({
  handleClick: function (e) {
    this.props.onMove(this.props.index);
  },
  
  render: function () {
    var player;
    
    if (this.props.data === null && !this.props.gameover) {
      player = <button onClick={this.handleClick}>Move</button>;
    } else if (this.props.data === 1) {
      player = 'X';
    } else if (this.props.data === 2) {
      player = 'O';
    } else {
      player = '';
    }
    
    return (<td>{player}</td>);
  }
});

var GameRow = React.createClass({
  handleMove: function (j) {
    this.props.onMove(this.props.index, j);
  },
  
  render: function () {
    var cells, handleMove = this.handleMove, gameover = this.props.gameover;
    
    cells = this.props.data.map(function (result, j) {
      return <GameCell key={j} index={j} data={result} onMove={handleMove} gameover={gameover} />;
    });
    
    return (<tr>{cells}</tr>);
  }
});

var GameUI = React.createClass({
  getInitialState: function () {
    return { config: originNode.config, value: 0, gameover: false };
  },
  
  handleMove: function (i, j) {
    console.log('Move at ' + i + ', ' + j);
  
    var userMoveConfig = this.state.config.map(function (col) { return col.slice(0); });
    userMoveConfig[i][j] = 2;
    
    this.setState({ config: userMoveConfig });
    
    var userMoveNode = new Node(userMoveConfig, false),
      nextMove   = minimax(userMoveNode, 5, true, -Infinity, +Infinity);
    
    this.setState({ config: nextMove[0].config, value: nextMove[1], gameover: nextMove[0].isTerminal() });
  },
  
  handleReset: function () {
    this.setState(this.getInitialState());
  },
  
  render: function () {
    var rows, handleMove = this.handleMove, _gameover = this.state.gameover, gameover;
    
    rows = this.state.config.map(function (result, i) {
      return <GameRow key={i} index={i} data={result} onMove={handleMove} gameover={_gameover} />;
    });
    
    if (_gameover) {
      gameover = 'Game over!';
    }
    
    return (<div><table>{rows}</table><p>You are O. Value: {this.state.value}. {gameover}</p><button onClick={this.handleReset}>Reset</button></div>);
  }
});

React.render(
  <GameUI />,
  document.getElementById('game')
);