Skip to content

Instantly share code, notes, and snippets.

@71104
Created March 14, 2016 18:40
Show Gist options
  • Save 71104/912888dbeb23e21b42c9 to your computer and use it in GitHub Desktop.
Save 71104/912888dbeb23e21b42c9 to your computer and use it in GitHub Desktop.
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
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment