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

以前、オセロの対戦AIの作成しましたが、そこでは実装を簡略化する為に盤面の価値を

• 盤面の価値 = 自分の石の数 – 相手の石の数

という単純な方法で決めていました。
でも、これには問題があります。

• 同じ石でも配置場所によって価値は異なるはずです(例: 角は最強)。それが考慮されていません。
• ゲーム終盤になってくると石の数が重要になってきます。でも序盤から石の数を重視するのは方向性としておかしいです。

という訳で、

• 序盤から中盤では石の配置場所を重視する
• 終盤では石の数を重視する

形で盤面の価値を算出すれば、結構良さそうなAIになりそうです。

しかし、今度は

• 「序盤」「中盤」「終盤」をどのように区別するのか?
• 石の配置場所の強弱はどう決めるのか?
• 同じ配置場所でも周囲の状況次第で強弱が異なるのでは?

という問題が出てきます。これは作るのが面倒臭そうです。

どうにかしてお手軽かつそこそこ強そうなAIを作れないものでしょうか?

発想の転換

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

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

勿論これは非現実的です。
なんせ4×4という最小限の盤面ですら全局面を読むとかなり待たされるのですから。
しかし全局面を読まなくてもある程度の数の局面を読めば大体の勝率は分かります。
読む局面の数を増やせばより正確な勝率が分かるので、それによって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が何だか凄そうということが良く分かりました。
実装はお手軽ですし、試行回数を増やせばその分強くなるので難易度調節もお手軽そうです。
しかし、本気で強くしようとするとただただ試行回数を増やすだけでは効率が悪そうです。
もっと強くする為にはどうすれば良いのでしょうか。

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