JavaScript でオセロを実装する(仮AI作成編)

2013年 07月 16日

これまでのあらすじ

新人の力量を測るための課題としてオセロの作成を指示したが、
指示した当人が作れないようでは話にならないので実際に作り始めた。
盤面が4×4で黒も白も人間が指す一人二役の寂しいオセロは実装でき、
遅延評価を導入して性能の改善と実装の簡潔さの両立を図った。

しかし一人二役はいくらなんでも虚しい。
なので
AI
を実装して一人でも遊べるようにしようと思うのであった。

AIは何をすべきか

ところで……これまでAIなんて実装したことはありません。
一体どうやって実装したものでしょうか。
今一度、オセロについて考え直してみましょう。

うーん……あー、そうか。AIと言っても

盤面から今後の展開を予測して今の局面で指せる 最善手を選び 、
選んだ手を指す

というだけですね。
しかもゲーム木をベースに実装してあるので指せる手は既に提示されている状態です。

ただ、「どの手が最も良いか」を判断するのは難しい問題です。
逆に言えば、形勢判断を後回しにして、
「取り敢えず適当な手を指す」
だけなら簡単に出来そうですね。
と言う訳で、まずは

取り得る手のうち最も上の行に石が置ける手を選ぶ。
同一行に指せる手が複数あるなら最も左の列に石が置ける手を選ぶ。

というAIにしてみましょう。

ゲーム進行処理の修正

最初にオセロを実装した時に「次の局面に切り換える」処理 shiftToNewGameTree(gameTree) を書きました:

function shiftToNewGameTree(gameTree) {
  drawGameBoard(gameTree.board, gameTree.player, gameTree.moves);
  resetUI();
  if (gameTree.moves.length == 0) {
    showWinner(gameTree.board);
    setUpUIToReset();
  } else {
    setUpUIToChooseMove(gameTree);
  }
}

ここは手番によって人間が指すかAIが指すかを切り換えるようにしましょう。
取り敢えず黒を人間が、白をAIが指すとします。

プログラムからすれば人間がどういう手を指すのかは分からないので、
人間のターンでは
「どの手を指すか人間が選ぶ……ためのUIを用意する」
処理
setUpUIToChooseMove(gameTree)
を呼ぶ形になっています。

一方、AIはどういう手を選ぶのか分かっていますから、
「現在の局面から最も良い手を判断する」 findTheBestMoveByAI と
「選んだ手が示す局面に切り換える」 shiftToNewGameTree に処理を分けましょう。
また、これを総合した「AIが手を指す」 chooseMoveByAI も用意しましょう。

shiftToNewGameTree については以下のように変更しましょう
(やたらとコメントで強調しているところが変更箇所です):

function shiftToNewGameTree(gameTree) {
  drawGameBoard(gameTree.board, gameTree.player, gameTree.moves);
  resetUI();
  if (gameTree.moves.length == 0) {
    showWinner(gameTree.board);
    setUpUIToReset();
  } else {
    // ****************************************
    if (gameTree.player == BLACK)
      setUpUIToChooseMove(gameTree);
    else
      chooseMoveByAI(gameTree);
    // ****************************************
  }
}

「AIが手を指す」処理の実装

次は chooseMoveByAI ですが、
findTheBestMoveByAI があると仮定すれば実装は簡単です。

function chooseMoveByAI(gameTree) {
  $('#message').text('Now thinking...');
  shiftToNewGameTree(
    force(findTheBestMoveByAI(gameTree).gameTreePromise)
  );
}

「最も良い手を選ぶ」関数の実装

さて問題は findTheBestMoveByAI です。
まともな形勢判断をコードに落とし込むのは難しいですが、
今回は単に現在指せる手の中からテキトーな基準で選ぶだけなので簡単です。

しかし……指せる手を先述の基準で選ぶ処理を書くのは何だか面倒です。
ここはちょっとズルをしましょう。

最初にオセロを実装した時に書いた
「攻撃できる手を列挙する」関数 listAttackingMoves ですが、

function listAttackingMoves(board, player, nest) {
  var moves = [];

  for (var x = 0; x < N; x++) {
    for (var y = 0; y < N; y++) {
      var vulnerableCells = listVulnerableCells(board, x, y, player);
      if (canAttack(vulnerableCells)) {
        moves.push(...);
      }
    }
  }

  return moves;
}

となっていました。
x と y の走査順序を

for (var y = 0; y < N; y++) {
  for (var x = 0; x < N; x++) {
    ...

に変えれば……なんということでしょう!
これで

取り得る手のうち上の行にあるものが先に列挙される。
同一行に指せる手が複数あるなら左の列にあるものが先に列挙される。

ので、結果として
listAttackingMoves が列挙した最初の手が仮AIの指すべき手になります。
ということは findTheBestMoveByAI の実装は1行で済みます。

function findTheBestMoveByAI(gameTree) {
  return gameTree.moves[0];
}

はじめての対AI戦

それではさっそくAIと対戦してみましょう!

……?!
「俺が手を指したから次は相手の手番だと思っていたら俺の手番になっていた」
だと……!?

それもそのはず。
AIが手を指す処理は何の障害物もないので超高速です。
人間が手を指しても間断なく一瞬でAIが手を指し終えるために、
AIがどこに指したのかすら認識に困る状態になっています。

さすがにこれはプレイ感覚が悪いので、
多少はAIも「考えている」ように見えるよう、
手を指す前に多少の待ち時間を入れることにしましょう。

function chooseMoveByAI(gameTree) {
  $('#message').text('Now thinking...');
  setTimeout(
    function () {
      shiftToNewGameTree(
        force(findTheBestMoveByAI(gameTree).gameTreePromise)
      );
    },
    500
  );
}

気を取り直してAIと対戦し直してみましょう。