これまでのあらすじ
新人の力量を測るための課題としてオセロの作成を指示したが、
指示した当人が作れないようでは話にならないので実際に作り始めた。
一先ず盤面が4×4で黒も白も人間が指す一人二役の寂しいオセロは実装できたのだが、
快適に遊ぶには大きな問題が潜んでいたのであった。
実は4×4で既に重い問題
実際に前回作成したオセロを実行すると、
ゲームが遊べるようになるまでに割りと待たされます。
それもそのはずで、あの実装は
ゲーム中で取り得る局面を予め全て列挙
していたからです。
しかも4×4という最小限の盤面のオセロですらゲーム中に出現し得る局面 = ゲーム木に含まれるノード数は 284,881個 あります(※回転すると同じになる盤面等は個別に数えて、同一盤面でも手番のプレイヤーが異なるなら別と数えて、パスした場合も1個と数えています)。
そりゃあ待たされるに決まってますし、無闇矢鱈にメモリも喰われます。
それに、全ての局面を列挙しても 実際にゲームを進めて行く中で出現する局面は極一部 です。
これは無駄……無駄過ぎる……!
ゲーム木を使うと非常に簡単に実装できたのに、
快適に遊べないようでは元も子もないです。
どうにかして簡潔な実装を保ったままパフォーマンスを向上できないものでしょうか。
遅延評価
そこで遅延評価です。
Haskell等と違ってJavaScriptの実行過程は遅延評価ではありませんが、
クロージャーが使えるので
遅延評価を手動で実現することは簡単にできます。
Schemeの delay / force
に倣って JavaScript で同様のものを実装しましょう:
function delay(expressionAsFunction) {
var result;
var isEvaluated = false;
return function () {
if (!isEvaluated) {
result = expressionAsFunction();
isEvaluated = true;
}
return result;
};
}
function force(promise) {
return promise();
}使い方としては以下の通りです:
var p = delay(function () {alert('hi'); return 42;});
force(p); //==> 42, alertが実行される。
force(p); //==> 42, alertは実行されない。
force(p); //==> 42, alertは実行されない。生憎Schemeと違ってマクロが無いので、
今まで単純に
... arbitraryExpression ...と書いていたところは軒並み
... delay(function () {return arbitraryExpression;}) ...と書くことになってクドくはなりますが、
遅延評価そのものはできているので良しとしましょう。
どの処理を遅延させるか
遅延評価が実現できるようになったものの、
どの処理を処理を遅延させるか
も問題です。
可能ならばあらゆる処理を遅延させたいところですが、
先述のように表記がクドくなるので考えものです。
今回のオセロで一番問題になるのはゲーム木の作成──より正確にはゲーム木のノードの作成──ですから、makeGameTree を使う箇所だけを遅延させることにしましょう。
具体的には completePassingMove と listAttackingMoves で列挙する手を選んだ場合の局面の算出を遅延させます
(やたらとコメントで括ってるところが変更箇所です):
function completePassingMove(attackingMoves, board, player, wasPassed) {
if (0 < attackingMoves.length)
return attackingMoves;
else if (!wasPassed)
return [{
isPassingMove: true,
// ****************************************************
gameTreePromise: delay(function () {
return makeGameTree(board, nextPlayer(player), true);
})
// ****************************************************
}];
else
return [];
}
function listAttackingMoves(board, player) {
var moves = [];
for (var x = 0; x < N; x++) {
for (var y = 0; y < N; y++) {
if (canAttack(board, x, y, player)) {
moves.push({
x: x,
y: y,
// ******************************************
gameTreePromise: (function (x, y) {
return delay(function () {
return makeGameTree(
makeAttackedBoard(board, x, y, player),
nextPlayer(player),
false
);
});
})(x, y)
// ******************************************
});
}
}
}
return moves;
}後は遅延されたゲーム木を参照するところで明示的に評価を force すればOKです。
function setUpUIToChooseMove(gameTree) {
$('#message').text('Choose your move.');
gameTree.moves.forEach(function (m, i) {
$('#console').append(
$('<input type="button" class="btn">')
.val(makeLabelForMove(m))
.click(function () {
// ******************************************
shiftToNewGameTree(force(m.gameTreePromise));
// ******************************************
})
);
});
}たったこれだけの変更ですが、
ゲーム全体の 実装は簡潔に保ったまま で
次の手を選んだ時に初めてその手の先の局面が評価される
形になり、動作速度を改善することが出来ました。
やりましたね。
遊んでみる
それでは実際にゲームをプレイしてみましょう!
前回作った遅延評価なしバージョンでのプレイの様子:
今回作った遅延評価ありバージョンでのプレイの様子:
新しくゲームを開始する時に注目してください。
カーソルが虹色のぐるぐるになってない = サクサク動いていることが分かります。
余談: JavaScriptで遅延評価する時にやりがちなミス
ところで、先程の listAttackingMoves ではdelay をさらに function で括っていました。
for (var x = 0; x < N; x++) {
for (var y = 0; y < N; y++) {
...
gameTreePromise: (function (x, y) {
return delay(function () {
return makeGameTree(
makeAttackedBoard(board, x, y, player),
nextPlayer(player),
false
);
});
})(x, y)
...
}
}このラップした function はループ変数の x と y を受け取るものの、
それをそのまま中身に渡すだけです。
これは一見すると無駄なようですが、実はこれが無いとまともに動きません。
仮に listAttackingMoves を以下のように書いたとしましょう:
for (var x = 0; x < N; x++) {
for (var y = 0; y < N; y++) {
...
gameTreePromise: delay(function () {
return makeGameTree(
makeAttackedBoard(board, x, y, player),
nextPlayer(player),
false
);
})
...
}
}問題は x と y の値です。
delayされた式はxとyという 変数を参照している のであってdelayされた時点でのxとyの変数の 値を参照しているのではない
なので後者の値が欲しければ明示的に新たな変数スコープを function で作る必要があります。
要はSchemeの let です。
余談: もっと遅延評価できるところはあるか
一応、 listAttackingMoves での手の列挙を遅延評価するという案はあったのですが、
そこを遅延評価するには前提としてLisp系のようなリスト構造を使ったコードにする必要があります。
ただ、それをやり始めると
- Lispライクなリスト処理ライブラリを一から書く羽目になって面倒臭い。
- 「現在の局面から取り得る手を列挙する」ことは「次の手の先を読む」ことと比較すれば格段に軽い(はず)。
ということが言えます。
今回のようにお手軽に実装しようという観点からすると、
苦労の割に見返りが少ないので止めました。
とはいえ、もっとカリカリにチューニングするなら手の列挙も遅延させた方が良いと思います。
特に次回以降で実装予定のAIを高速化していくと、例えば
「今の局面から選ぶべき手を順に検討しているけれど、全8手中3手を調べたところでもう残り5手は見る必要が無くなった」
ということは往々にしてありますし、
4×4の盤面と8×8の盤面では取り得る局面の数が全くもって桁違いなので、
手の列挙も遅延させる価値は出てくると思います。
次回予告
次回は仮AI実装編です。
＃人気の記事
＃タグ
