// Common.

var ROWS = 6;

var COLS = 7;

var EMPTY = 0;

var RED = 1;

var YELLOW = 2;

var DRAW = 3;

var oo = 123456789;

​

// Engine.

var DEPTH_LIMIT = ROWS * COLS;

var WIN_SCORE = 1001001;

var DRAW_SCORE = 0;

var THREAT_SCORE = 5;

var FORCING_BONUS = 50;

var TT_SIZE = 1 << 20;

var TT_MOVE_SCORE = 10000;

var NULL_MOVE = -1;

​

function getOpp(player) {

  return player ? (player === RED ? YELLOW : RED) : EMPTY;

}

​

function inside(r, c) {

  return r >= 0 && c >= 0 && r < ROWS && c < COLS;

}

​

var Engine = function() {

  this.EVAL_SCORES = this.computeEvalScores();

  this.WINNING = this.computeWinning();

  this.WINNING_GAPS = this.computeWinningGaps();

  this.ZOBRIST_TABLE = this.computeZobristTable();

  this.ZOBRIST_PLAYER_LOW = this.generateRandomInt32();

  this.ZOBRIST_PLAYER_HIGH = this.generateRandomInt32();

  this.tt = [];

  for (var i = 0; i < TT_SIZE; i++) {

    this.tt.push(new TTEntry(TTFlags.UNKNOWN, 0, 0, 0, 0, 0));

  }

};

​

Engine.prototype.computeEvalScores = function() {

  var i, j, u, v, h, k;

  var evalScores = new Array(64);

  for (i = 0; i < 64; i++) evalScores[i] = 0;

  var di = [1, 1, 1, 0];

  var dj = [-1, 0, 1, 1];

  for (i = 0; i < ROWS; i++)

    for (j = 0; j < COLS; j++)

      for (h = 0; h < 4; h++)

        if (inside(i + 3 * di[h], j + 3 * dj[h])) {

          for (k = 0; k < 4; k++) {

            u = i + k * di[h];

            v = j + k * dj[h];

            evalScores[u << 3 | v]++;

          }

        }

  for (i = 0; i < ROWS; i++)

    for (j = 0; j < COLS; j++) {

      v[i << 3 | j] -= 2 * Math.abs(2 * i - 5);

    }

  return evalScores;

};

​

Engine.prototype.computeWinningGaps = function() {

  var winningGaps = [];

  for (var i = 0; i < 7 << 16; i++) winningGaps.push(0);

  function computeGaps(len, b1, b2) {

    var gaps = [];

    for (var i = 0; i < len; i++)

      if (!(b1 >> i & 1) && !(b2 >> i & 1)) {

        var u = i - 1, v = i + 1;

        while (u >= 0 && (b1 >> u & 1)) u--;

        while (v < len && (b1 >> v & 1)) v++;

        if (v - 1 - u >= 4) {

          gaps.push(i);

        }

      }

    if (gaps.length === 0) return 255;

    if (gaps.length === 1) return 15 << 4 | gaps[0];

    return gaps[1] << 4 | gaps[0];

  }

  for (var len = 0; len < 7; len++)

    for (var b1 = 0; b1 < 1 << 8; b1++)

      for (var b2 = 0; b2 < 1 << 8; b2++) winningGaps[len << 16 | b1 << 8 | b2] = computeGaps(len + 1, b1, b2);

  return winningGaps;

};

​

Engine.prototype.isWinning = function(x) {

  var count = 0;

  for (var i = 0; i < 8; i++) {

    if (x >> i & 1) {

      count++;

      if (count >= 4) return true;

    } else {

      count = 0;

    }

  }

  return false;

};

​

Engine.prototype.computeWinning = function() {

  var winning = new Array(1 << 8);

  for (var i = 0; i < 1 << 8; i++) winning[i] = this.isWinning(i);

  return winning;

};

​

Engine.prototype.generateRandomInt32 = function() {

  return Math.floor(Math.random() * 4294967296);

};

​

Engine.prototype.computeZobristTable = function() {

  var zobristTable = new Array(256);

  for (var i = 0; i < 256; i++) {

    zobristTable[i] = this.generateRandomInt32();

  }

  return zobristTable;

};

​

Engine.prototype.init = function(board, turn) {

  var i, j;

  this.b = new Array(64);

  this.c = new Array(8);

  this.empty = ROWS * COLS;

  // Initializes board and turn.

  for (i = 0; i < 64; i++) this.b[i] = EMPTY;

  for (i = 0; i < 8; i++) this.c[i] = 0;  

  for (i = 0; i < ROWS; i++)

    for (j = 0; j < COLS; j++)

      if (board[i][j] !== EMPTY) {

        this.b[(ROWS - i - 1) << 3 | j] = board[i][j];

        this.c[j]++;

        this.empty--;

      }

  this.turn = turn;

  // Initializes evaluation scores.

  this.scores = [0, 0, 0];

  // Initializes winning bits.

  this.rowBits = new Array(32);

  this.colBits = new Array(32);

  this.diag1Bits = new Array(32);

  this.diag2Bits = new Array(32);

  for (i = 0; i < 32; i++) {

    this.rowBits[i] = 0;

    this.colBits[i] = 0;

    this.diag1Bits[i] = 0;

    this.diag2Bits[i] = 0;

  }

  // Initializes things releated to the transposition table.

  this.zobristLockLow = 0;

  this.zobristLockHigh = 0;

  for (i = 0; i < ROWS; i++)

    for (j = 0; j < COLS; j++)

      if (this.b[i << 3 | j] !== EMPTY) this.putBit(i, j, this.b[i << 3 | j]);

  this.moves = new Array(100);

  for (i = 0; i < this.moves.length; i++) this.moves[i] = 0;

  this.moveCount = 0;

};

​

Engine.prototype.evaluateLine = function(i, j) {

  var forcing = (this.empty - ROWS + i + 1) & 1;

  return (ROWS - i + this.c[j]) * THREAT_SCORE + (forcing ? FORCING_BONUS : 0);

};

​

Engine.prototype.evaluateRow = function(i, len, b1, b2) {

  var myGaps = this.WINNING_GAPS[(len - 1) << 16 | b1 << 8 | b2];

  var oppGaps = this.WINNING_GAPS[(len - 1) << 16 | b2 << 8 | b1];

  var s = 0;

  if ((myGaps & 15) < 15) s += this.evaluateLine(i, myGaps & 15);

  if ((myGaps >> 4) < 15) s += this.evaluateLine(i, myGaps >> 4);

  if ((oppGaps & 15) < 15) s -= this.evaluateLine(i, oppGaps & 15);

  if ((oppGaps >> 4) < 15) s -= this.evaluateLine(i, oppGaps >> 4);

  return s;

};

​

Engine.prototype.evaluateDiag1Line = function(i, j, p) {

  return this.evaluateLine(i + p, j + p);

};

​

Engine.prototype.evaluateDiag1 = function(d, b1, b2) {

  var len = d < 6 ? d + 1 : 12 - d;

  var i = d < 6 ? 0 : d - 6;

  var j = d < 6 ? 6 - d : 0;

  var myGaps = this.WINNING_GAPS[(len - 1) << 16 | b1 << 8 | b2];

  var oppGaps = this.WINNING_GAPS[(len - 1) << 16 | b2 << 8 | b1];

  var s = 0;

  if ((myGaps & 15) < 15) s += this.evaluateDiag1Line(i, j, myGaps & 15);

  if ((myGaps >> 4) < 15) s += this.evaluateDiag1Line(i, j, myGaps >> 4);

  if ((oppGaps & 15) < 15) s -= this.evaluateDiag1Line(i, j, oppGaps & 15);

  if ((oppGaps >> 4) < 15) s -= this.evaluateDiag1Line(i, j, oppGaps >> 4);

  return s;

};

​

Engine.prototype.evaluateDiag2Line = function(i, j, p) {

  return this.evaluateLine(i - p, j + p);

};

​

Engine.prototype.evaluateDiag2 = function(d, b1, b2) {

  var len = d < 6 ? d + 1 : 12 - d;

  var i = d < 6 ? d : 5;

  var j = d < 6 ? 0 : d - 5;

  var myGaps = this.WINNING_GAPS[(len - 1) << 16 | b1 << 8 | b2];

  var oppGaps = this.WINNING_GAPS[(len - 1) << 16 | b2 << 8 | b1];

  var s = 0;

  if ((myGaps & 15) < 15) s += this.evaluateDiag2Line(i, j, myGaps & 15);

  if ((myGaps >> 4) < 15) s += this.evaluateDiag2Line(i, j, myGaps >> 4);

  if ((oppGaps & 15) < 15) s -= this.evaluateDiag2Line(i, j, oppGaps & 15);

  if ((oppGaps >> 4) < 15) s -= this.evaluateDiag2Line(i, j, oppGaps >> 4);

  return s;

};

​

Engine.prototype.evaluate = function() {

  var i, j, d1, d2, b1, b2;

  var s = this.scores[this.turn] - this.scores[3 - this.turn];

  var myStart = this.turn === RED ? 0 : 16;

  var oppStart = 16 - myStart;

  // Rows

  for (i = 0; i < ROWS; i++) {

    b1 = this.rowBits[myStart | i];

    b2 = this.rowBits[oppStart | i];

    s += this.evaluateRow(i, COLS, b1, b2);

  }

  // Diag 1.

  for (d1 = 3; d1 < 9; d1++) {

    b1 = this.diag1Bits[myStart | d1];

    b2 = this.diag1Bits[oppStart | d1];

    s += this.evaluateDiag1(d1, b1, b2);

  }

  // Diag 2.

  for (d2 = 3; d2 < 9; d2++) {

    b1 = this.diag2Bits[myStart | d2];

    b2 = this.diag2Bits[oppStart | d2];

    s += this.evaluateDiag2(d2, b1, b2);

  }

  return s;

};

​

// Checks whether a move is a winning move after making it.

Engine.prototype.isWinningMove = function(j) {

  var i = this.c[j] - 1;

  // This is because the turn has already been changed after making move.

  var start = this.turn === RED ? 16 : 0;

  return this.WINNING[this.rowBits[start | i]] ||

    this.WINNING[this.colBits[start | j]] ||

    this.WINNING[this.diag1Bits[start | (i - j + COLS - 1)]] ||

    this.WINNING[this.diag2Bits[start | (i + j)]];

};

​

Engine.prototype.computeOrderedMoves = function(ttMove) {

  var i, j;

  var scores = [];

  var moves = [];

  for (j = 0; j < COLS; j++)

    if (this.c[j] < ROWS) {

      if (j === ttMove) {

        scores.push(TT_MOVE_SCORE);

      } else {

        scores.push(this.EVAL_SCORES[this.c[j] << 3 | j]);

      }

      moves.push(j);

    }

  for (i = 1; i < scores.length; i++) {

    for (j = i; j > 0 && scores[j] > scores[j - 1]; j--) {

      var tmp = scores[j];

      scores[j] = scores[j - 1];

      scores[j - 1] = tmp;

      tmp = moves[j];

      moves[j] = moves[j - 1];

      moves[j - 1] = tmp;

    }

  }

  return moves;

};

​

Engine.prototype.isOverTime = function() {

  return new Date().getTime() - this.startTime > this.timeLimit;

};

​

Engine.prototype.pvs = function(alpha, beta, depth, maxDepth) {

  if (this.isOverTime()) {

    return alpha;

  }

  var ttEntry = this.retrieveTTEntry(this.zobristLockLow, this.zobristLockHigh);

  if (ttEntry && ttEntry.height >= maxDepth - depth) {

    switch (ttEntry.flag) {

      case TTFlags.LOWER_BOUND:

        if (ttEntry.score > alpha) alpha = ttEntry.score;

        break;

      case TTFlags.UPPER_BOUND:

        if (ttEntry.score < beta) beta = ttEntry.score;

        break;

      case TTFlags.EXACT_SCORE:

        if (ttEntry.score < alpha) return alpha;

        if (ttEntry.score > beta) return beta;

        return ttEntry.score;

    }

    if (alpha >= beta) return beta;

  }  

  if (depth >= maxDepth) return this.evaluate();

  var score = 0;

  var foundPv = false;

  var bestLocalMove = -1;

  // Null move.

  if (this.empty >= 21 && (!ttEntry || ttEntry.flag !== TTFlags.EXACT_SCORE) && depth + 2 < maxDepth && this.isNullMoveOk()) {

    this.makeNullMove();

    var nmr = depth + 6 < maxDepth ? 3 : 2;

    score = -this.pvs(-beta, -alpha, depth + 1 + nmr, maxDepth);

    this.unMakeNullMove();

    if (score >= beta) return beta;

    if (score > alpha) alpha = score;

  }                  

  var orderedMoves = this.computeOrderedMoves(ttEntry ? ttEntry.move : -1);

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

    var j = orderedMoves[i];

    this.makeMove(j);

    if (this.isWinningMove(j)) {

      score = WIN_SCORE - depth;

    } else {

      if (foundPv) {

        score = -this.pvs(-alpha - 1, -alpha, depth + 1, maxDepth);

        if (alpha < score && score < beta) {

          score = -this.pvs(-beta, -alpha, depth + 1, maxDepth);

        }

      } else {

        score = -this.pvs(-beta, -alpha, depth + 1, maxDepth);

      }

    }

    this.unMakeMove(j);

    if (score >= beta) {

      alpha = beta;

      bestLocalMove = j;

      break;

    }

    if (score > alpha) {

      foundPv = true;

      alpha = score;

      if (depth === 0) {

        this.bestMove = j;

      }

      bestLocalMove = j;

    }

  }

  if (!orderedMoves.length) alpha = DRAW_SCORE + depth;

  var flag = TTFlags.EXACT_SCORE;

  if (alpha >= beta) {

    flag = TTFlags.LOWER_BOUND;

  } else if (!foundPv) {

    flag = TTFlags.UPPER_BOUND;

  }

  this.storeTTEntry(flag, this.zobristLockLow, this.zobristLockHigh, alpha, bestLocalMove, maxDepth - depth); 

  return alpha;

};

​

Engine.prototype.beforeSearch = function() {

  // Resets the transposition table.

  for (var i = 0; i < TT_SIZE; i++) this.tt[i].clear();

  this.startTime = new Date().getTime();

};

​

Engine.prototype.think = function(timeLimit) {

  this.timeLimit = timeLimit;

  this.beforeSearch();

  var lastBestMove = -1;

  var lastBestScore = - oo;

  var lastDepth = 0;

  for (var d = 1; d <= DEPTH_LIMIT; d++) {

    this.bestMove = -1;

    this.bestScore = this.pvs(-oo, +oo, 0, d);

    if (this.isOverTime()) break;

    if (this.bestMove !== -1) {

      lastBestMove = this.bestMove;

      lastBestScore = this.bestScore;

      lastDepth = d;

    }

  }

  return {

    bestMove: lastBestMove,

    bestScore: lastBestScore,

    depth: lastDepth

  };

};

​

Engine.prototype.putBit = function(i, j, turn) {

  var start = turn === RED ? 0 : 16;

  this.rowBits[start | i] ^= 1 << j;

  this.colBits[start | j] ^= 1 << i;

  this.diag1Bits[start | (i - j + COLS - 1)] ^= 1 << Math.min(i, j);

  this.diag2Bits[start | (i + j)] ^= 1 << Math.min(ROWS - 1 - i, j);

  // Transposition table.

  start = turn === RED ? 0 : 128;

  this.zobristLockLow ^= this.ZOBRIST_TABLE[start | (i << 3 | j) << 1];

  this.zobristLockHigh ^= this.ZOBRIST_TABLE[start | (i << 3 | j) << 1 | 1];

};

​

Engine.prototype.isNullMoveOk = function() {

  return this.moveCount < 2 || this.moves[this.moveCount - 1] !== NULL_MOVE || this.moves[this.moveCount - 2] !== NULL_MOVE;

};

​

Engine.prototype.switchTurn = function() {

  this.turn = getOpp(this.turn);

  this.zobristLockLow ^= this.ZOBRIST_PLAYER_LOW;

  this.zobristLockHigh ^= this.ZOBRIST_PLAYER_HIGH;

};

​

Engine.prototype.makeNullMove = function() {

  this.switchTurn();

  this.moves[this.moveCount++] = NULL_MOVE;

};

​

Engine.prototype.unMakeNullMove = function() {

  this.switchTurn();

  this.moveCount--;

};

​

Engine.prototype.makeMove = function(j) {

  var squareIndex = this.c[j] << 3 | j;

  this.b[squareIndex] = this.turn;

  this.scores[this.turn] += this.EVAL_SCORES[squareIndex];

  this.putBit(this.c[j], j, this.turn);

  this.c[j]++;

  this.switchTurn();

  this.moves[this.moveCount++] = j;

  this.empty--;

};

​

Engine.prototype.unMakeMove = function(j) {

  this.switchTurn();

  this.c[j]--;

  var squareIndex = this.c[j] << 3 | j;

  this.b[squareIndex] = EMPTY;

  this.scores[this.turn] -= this.EVAL_SCORES[squareIndex];

  this.putBit(this.c[j], j, this.turn);

  this.moveCount--;

  this.empty++;

};

​

Engine.prototype.unMakeLastMove = function() {

  this.unMakeMove(this.moves[this.moveCount - 1]);

};

​

Engine.prototype.retrieveTTEntry = function(hashLow, hashHigh) {

  var ttEntry = this.tt[hashLow & (TT_SIZE - 1)];

  if (ttEntry.flag !== TTFlags.UNKNOWN && ttEntry.lockLow === hashLow && ttEntry.lockHigh === hashHigh) {

    return ttEntry;

  }

  return null;

};

​

Engine.prototype.storeTTEntry = function(flag, lockLow, lockHigh, score, move, height) {

  var ttEntry = this.tt[lockLow & (TT_SIZE - 1)];

  if (ttEntry.flag === TTFlags.UNKNOWN || ttEntry.height >= height) {

    ttEntry.flag = flag;

    ttEntry.lockLow = lockLow;

    ttEntry.lockHigh = lockHigh;

    ttEntry.score = score;

    ttEntry.move = move;

    ttEntry.height = height;

  }

};

​

var TTFlags = {

  UNKNOWN: 0,

  LOWER_BOUND: 1,

  UPPER_BOUND: 2,

  EXACT_SCORE: 3

};

​

var TTEntry = function(flag, lockLow, lockHigh, score, move, height) {

  this.flag = flag;

  this.lockLow = lockLow;

  this.lockHigh = lockHigh;

  this.score = score;

  this.move = move;

  this.height = height;

};

​

TTEntry.prototype.clear = function() {

  this.flag = TTFlags.UNKNOWN;

  this.lockLow = 0;

  this.lockHigh = 0;

  this.score = 0;

  this.move = 0;

  this.height = 0;

};

​

var engine = new Engine();

​

self.addEventListener('message', function(e) {

  if (e.data) {

    var msgType = e.data.msgType;

    if (msgType === 'init') {

      engine.init(e.data.board, e.data.turn);

    } else if (msgType === 'makeMove') {

      engine.makeMove(e.data.move);

    } else if (msgType === 'unMakeMove') {

      engine.unMakeLastMove();

    } else if (msgType === 'think') {

      self.postMessage({

        msgType: 'think',

        result: engine.think(e.data.timeLimit)

      });

    }

  }

});

​