JavaScript でオセロを実装する(AI vs AI編)


2013年 09月 19日

これまでのあらすじ

オセロを実装し始めて早幾年。
ようやくまともなAIを作る基礎ができたので、
ここからは「より強いAI」をどう作っていくかを考える段階になりました。
しかし、これには色々と問題があります:

  • 「AIの強さ」を定量化できないと
    「ぼくのかんがえたさいきょうのAI」がどれぐらい強いのかさっぱり分からない。
  • かといって人間が判定するにしても
    「これは雑魚だなー」
    「これは手強かったかも」
    程度の大雑把な分類しかできない。
  • そもそもこれまでにテストプレイとして何十回もオセロをやってきたので、
    もう手動でオセロをプレイするのは面倒臭い。

AI同士を対戦させる

最初にAIを実装した時からずっと「黒は人間が打つ」「白はAIが打つ」と固定されていました。

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か)」の対応表
playerTypeTable
を用意しましょう:

var playerTypeTable = {};

HTML側にはプレイヤーの種類を選ぶフォームを用意するとしましょう:

<label>
  Black:
  <select id="black-player-type">
    <option value="human" selected>Human</option>
    <option value="ai">AI</option>
  </select>
</label>
<label>
  White:
  <select id="white-player-type">
    <option value="human">Human</option>
    <option value="ai" selected>AI</option>
  </select>
</label>

ゲーム開始時に playerTypeTable の内容を適宜更新して:

playerTypeTable[BLACK] = $('#black-player-type').val();
playerTypeTable[WHITE] = $('#white-player-type').val();
shiftToNewGameTree(makeGameTree(makeInitialGameBoard(), BLACK, false));

次の手をどう選ぶかは playerTypeTable に応じて決めれば良いだけです。

function shiftToNewGameTree(gameTree) {
  drawGameBoard(gameTree.board, gameTree.player, gameTree.moves);
  resetUI();
  if (gameTree.moves.length == 0) {
    showWinner(gameTree.board);
    setUpUIToReset();
  } else {
    var playerType = playerTypeTable[gameTree.player];  // *
    if (gameTree.player == 'human')                     // *
      setUpUIToChooseMove(gameTree);                    // *
    else                                                // *
      chooseMoveByAI(gameTree);                         // *
  }
}

これで黒と白の両方をAIが担当するよう選択してゲームを開始すれば全自動でオセロが進む様を眺められます。やりましたね。

AI vs AI

外部から新たなAIを追加する

しかし……これだけでは全く面白くありません。
何故ならAIは「プレイヤー間の石の個数の差」が基準のものだけで、
他にAIは実装していないからです。
かといってここから新たにAIを実装していくのも面倒臭い話ですし、
何より一人で作っていては発想が固定されてよろしくありません。
ここはやはり
他の人にAIを作ってもらって自分の作ったAIと対戦させる
ようにしたいものです。
また、気軽に対戦させられるようにするには、
Gist 等にAIの実装をアップロードして、
それを動的に読み込んで対戦できるようにすれば良いですね。

まずはAIを新たに追加するUIを用意しましょう。
AIの実装が入ったJavaScriptへのURLを入力するフォームと、
「追加」を実行するボタンがあれば十分でしょう:

<input id="new-ai-url" type="text" value="">
<button id="add-new-ai-button" class="btn" type="button">Add new AI</button>

フォームは簡単ですが、肝心の「追加」処理はちょっと厄介です。
ここは

  • AIを登録するには othello.registerAI(ai) を呼ぶ。
  • 引数 ai はオブジェクトで、 findTheBestMove プロパティがあり、
    その値は「ゲーム木を受け取り次の手を返す」関数である。

としましょう。
同じAIを何度も追加されても困りますから、
追加済みのAIについては何度も登録しないようチェックも必要ですね。

$('#add-new-ai-button').click(function () {addNewAI();});

var aiTable = {};

var lastAIType;

othello.registerAI = function (ai) {
  aiTable[lastAIType] = ai;
};

function addNewAI() {
  var aiUrl = $('#new-ai-url').val();
  var originalLabel = $('#add-new-ai-button').text();
  if (aiTable[aiUrl] == null) {
    lastAIType = aiUrl;
    $('#add-new-ai-button').text('Loading...').prop('disabled', true);
    $.getScript(aiUrl, function () {
      $('#black-player-type, #white-player-type').append(
        '<option value="' + aiUrl + '">' + aiUrl + '</option>'
      );
      $('#white-player-type').val(aiUrl);
      $('#add-new-ai-button').text(originalLabel).removeProp('disabled');
    });
  } else {
    $('#add-new-ai-button').text('Already loaded').prop('disabled', true);
    setTimeout(
      function () {
        $('#add-new-ai-button').text(originalLabel).removeProp('disabled');
      },
      1000
    );
  }
}

後はAIの種類 aiTable に応じて処理を変えましょう:

function shiftToNewGameTree(gameTree) {
  ...
    var playerType = playerTypeTable[gameTree.player];
    if (playerType == 'human') {
      setUpUIToChooseMove(gameTree);
    } else {
      var ai = aiTable[playerType];  // *
      chooseMoveByAI(gameTree, ai);  // *
    }
  ...
}

function chooseMoveByAI(gameTree, ai) {
  ...
      shiftToNewGameTree(
        force(ai.findTheBestMove(gameTree).gameTreePromise)  // *
      );
  ...
}

また、ちゃんとしたAIを実装するには必要なAPIが足りていないので、
これも othello オブジェクト経由で公開することにしましょう:

othello.force = force;
othello.delay = delay;
othello.EMPTY = EMPTY;
othello.WHITE = WHITE;
othello.BLACK = BLACK;
othello.nextPlayer = nextPlayer;

これだけあればAIを外部ファイルで書くことはできるはずです。
例えばランダムに次の手を選ぶAIなら以下のように実装できます:

othello.registerAI({
  findTheBestMove: function (gameTree) {
    return gameTree.moves[Math.floor(Math.random() * gameTree.moves.length)];
  }
});

他にも、次の手のうち相対的な石の数が最も多い手を選ぶAIは以下のように実装できます:

(function () {
  var O = othello;

  function sum(ns) {
    return ns.reduce(function (t, n) {return t + n;});
  }

  function scoreBoard(board, player) {
    var opponent = O.nextPlayer(player);
    return sum($.map(board, function (v) {return v == player;})) -
           sum($.map(board, function (v) {return v == opponent;}));
  }

  O.registerAI({
    findTheBestMove: function (gameTree) {
      var scores =
        gameTree.moves.map(function (m) {
          return scoreBoard(O.force(m.gameTreePromise).board, gameTree.player);
        });
      var maxScore = Math.max.apply(null, scores);
      return gameTree.moves[scores.indexOf(maxScore)]
    }
  });
})();

では試しに前回作成したAIと今回作成したランダムに次の手を選ぶAIを対戦させてみましょう:

外部AIを読み込んで対戦する図

おお……ちゃんと動いてます。
これで「ぼくのかんがえたさいきょうのAI」同士を持ち寄って対戦することができるようになりました。やったー。

実際に遊んでみたい!

http://kana.github.io/othello-js/ で遊べるのでどうぞご自由に。