reversi.js

function memoize(f) {
  return function () {
    if (!this._cache) {
      this._cache = Object.create(null);
    }
    var cache = this._cache;
    var k = arguments.length - 1;
    for (var i = 0; i < k; i++) {
      if (!(arguments[i] in cache)) {
        cache[arguments[i]] = Object.create(null);
      }
      cache = cache[arguments[i]];
    }
    if (!(arguments[k] in cache)) {
      cache[arguments[k]] = f.apply(this, arguments);
    }
    return cache[arguments[k]];
  };
}


function Reversi(state) {
  this._state = state || [
      0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 1, 2, 0, 0, 0,
      0, 0, 0, 2, 1, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0,
  ];
}

Reversi.prototype.get = function (i, j) {
  return this._state[i * 8 + j];
};

Reversi.prototype.map = function (callback) {
  var result = [];
  for (var i = 0; i < 8; i++) {
    var row = [];
    for (var j = 0; j < 8; j++) {
      row.push(callback(this._state[i * 8 + j], i, j));
    }
    result.push(row);
  }
  return result;
};

Reversi.prototype.reduce = function (callback, initialValue) {
  return this._state.reduce(function (oldValue, newValue, index) {
    return callback.call(this, oldValue, newValue, Math.floor(index / 8), index % 8);
  }, initialValue);
};

Reversi.opponent = function (player) {
  return 3 - player;
};

Reversi.prototype.getLines = function (player, i, j) {
  if (i < 0 || i > 7 || j < 0 || j > 7) {
    throw new Error();
  } else if (this._state[i * 8 + j] !== 0) {
    return [];
  } else {
    var index = i * 8 + j;
    var opponent = Reversi.opponent(player);
    return [-9, -8, -7, -1, 1, 7, 8, 9].some(function (offset) {
      var nextIndex = index;
      do {
        nextIndex += offset;
      } while (nextIndex >= 0 && nextIndex < 64 &&
          this._state[nextIndex] === opponent);
      if (nextIndex >= 0 && nextIndex < 64 &&
          this._state[nextIndex] === player) {
        return offset;
      } else {
        return null;
      }
    }).filter(function (line) {
      return !!line;
    });
  }
};

Reversi.prototype.canMove = function (player, i, j) {
  return this.getLines(player, i, j).length !== 0;
};

Reversi.prototype.getAvailableMoves = function (player) {
  return this.map(function (cell, i, j) {
    return this.canMove(player, i, j);
  });
};

Reversi.prototype.move = function (player, i, j) {
  var lines = this.getLines(player, i, j);
  if (lines.length) {
    var state = this._state.slice();
    var index = i * 8 + j;
    lines.forEach(function (offset) {
      while (state[index] !== player) {
        state[index] = player;
        index += offset;
      }
    });
    return new Reversi(state);
  } else {
    throw new Error();
  }
};

Reversi.prototype.score = function (player) {
  return this.reduce(function (score, cell, i, j) {
    if (cell === player) {
      score++;
    }
    return score;
  }, 0);
};

Reversi.prototype._stable = memoize(function (i, j) {
  return i < 0 || i > 7 || j < 0 || j > 7 ||
      (this._stable(i - 1, j) || this._stable(i + 1, j)) &&
      (this._stable(i, j - 1) || this._stable(i, j + 1));
});

Reversi.prototype.stability = function (player) {
  return this.reduce(function (count, cell, i, j) {
    if (cell === player && this._stable(i, j)) {
      count++;
    }
    return count;
  }, 0);
};


function Tree(state) {
  this._state = state;
  this._stability = state.stability();
  this._score = state.score();
}

Tree.prototype = Object.create(Reversi.prototype);

Tree.prototype.compare = function (other) {
  if (this._stability !== other._stability) {
    return this._stability - other._stability;
  } else {
    return this._score - other._score;
  }
};

Tree.prototype.simulateMove = memoize(function (player, i, j) {
  return new Tree(this._state.move(player, i, j));
});

Tree.prototype.getAllMoves = function (player, depth) {
  if (depth > 0) {
    return this._state.getAvailableMoves(player).forEach(function (move) {
      return this.simulateMove(player, move.i, move.j);
    });
  } else {
    // TODO
  }
};

Tree.prototype.getBestMove = function (player, depth) {
  if (depth > 0) {
    return this.getAllMoves(player, depth).sort(function (child1, child2) {
      return child2.compare(child1);
    })[0];
  } else {
    // TODO
  }
};