JavaScript でオセロを実装する(原始モンテカルロAI編)

発想の転換

そもそも盤面の価値を算出していたのは何故でしょうか? それは各手の強さを定量化して「今の局面で打てる最善手を選ぶ」基準にする為です。

しかし手の強さの定量化は必要なのでしょうか? ある手が別の手より強いということは、つまり前者の方が後者よりも勝率が高いということですよね。 逆に、 勝率さえ分かれば盤面の価値を算出する必要はない のです。 そして勝率は簡単かつ正確に算出することができます。 だって ある手を打った後に起き得るゲーム展開を全て列挙 するだけですからね。

勿論これは非現実的です。 なんせ4x4という最小限の盤面ですら全局面を読むとかなり待たされるのですから。 しかし全局面を読まなくてもある程度の数の局面を読めば大体の勝率は分かります。 読む局面の数を増やせばより正確な勝率が分かるので、それによってAIの腕前を調整することもできます。

という訳でこの考え方(=モンテカルロ法)でAIを作れば オセロに関するノウハウが無くても 強いAIになるのではないでしょうか?

実装

この考え方を実践するにあたって、まず(大体の)勝率を求める必要があります。 これは以下の手順で簡単に求められます:

1. ゲームが終わるまでランダムに手を打つ。
2. 勝敗がどうなったかをカウントする。
3. 1-2を十分な回数繰り返す。
4. 勝利数 / 試行回数 = 大体の勝率

後はこの勝率概算を各手について行って、最も勝率の高い手を選ぶAIを書くだけです。 実際には勝率を求めなくても勝利数が最大の手を選べば十分ですね。 具体的には以下のコードになります:

function tryPrimitiveMonteCarloSimulation(rootGameTree, maxTries) {
  var scores = rootGameTree.moves.map(function (m) {
    var s = 0;
    for (var i = 0; i < maxTries; i++)
      s += simulateRandomGame(m, rootGameTree.player);
    return s;
  });
  var maxScore = Math.max.apply(null, scores);
  return rootGameTree.moves[scores.indexOf(maxScore)];
}

function simulateRandomGame(move, player) {
  var gt = force(move.gameTreePromise);
  while (gt.moves.length !== 0)
    gt = force(gt.moves[random(gt.moves.length)].gameTreePromise);
  return judge(gt.board) * (player === BLACK ? 1 : -1);
}

function judge(board) {
  var n = {};
  n[BLACK] = 0;
  n[WHITE] = 0;
  n[EMPTY] = 0;
  for (var i = 0; i < board.length; i++)
    n[board[i]]++;

  if (n[BLACK] > n[WHITE])
    return 1;
  if (n[BLACK] < n[WHITE])
    return -1;
  return 0;
}

動かしてみる

それでは実際に動かしてみましょう。 取り敢えずモンテカルロAIの試行回数は100回/手として、 まずは今までに作った石数最優先AIと対戦させてみましょう:

おお......圧勝ですね。とてもランダムに手を選んでるとは思えません。 でも、逆に言うと石数最優先AIが弱過ぎるだけではないでしょうか?

では 「角を最優先」「辺も重視する」「角に隣接するマスは避ける」 という最低限のコツを考慮したAIと戦わせてみるとどうなるでしょう?

うーん。これだと今一ですね。

ならモンテカルロAIの試行回数を200回/手に増やして対戦させてみるとどうなるでしょう?

試行回数が増えた分、より正確な勝率が分かるようになったので、 試行回数100回の時よりもなかなか強そうな動きをしています。

モンテカルロAIはオセロのコツを何も知らない状態で着手しているのに、 多少コツを知ってるAIよりも上手く着手しているように見えます。 こいつ、実は凄いのでは......?

興味のある方は実際に対戦することもできます (Type PM-100とType PM-200が今回作った原始モンテカルロAIです)。

次回予告

モンテカルロAIが何だか過ごそうということが良く分かりました。 実装はお手軽ですし、試行回数を増やせばその分強くなるので難易度調節もお手軽そうです。 しかし、本気で強くしようとするとただただ試行回数を増やすだけでは効率が悪そうです。 もっと強くする為にはどうすれば良いのでしょうか。

と言う訳で次回は「モンテカルロ木探索編」です。