モンテカルロ法を用いた四目並べAIを作ってみた
制作物
はじめに
C++で立体四目並べのプログラムを作成しました。
ただ交互にコマを置いていくだけだと、おもしろくない(そもそも戦う相手がいない)ので、敵を作ることにします。
なるべく強キャラにするため、モンテカルロ法というアルゴリズムを用いて実装してみました。
モンテカルロ法って？
ランダムな候補手で終局までゲームをシミュレーションし、その中でもっとも勝率の高いものを次の手として選択するアルゴリズムとなっています。
シミュレーション回数が少ないと得られる結果はデタラメとなってしまいますが、回数を増やすことでより統計的な分布を得ることができます。
このアルゴリズムを利用したコンピュータ囲碁が世界トップ棋士を倒したことが一時期話題になっていましたね。
実装
四目並べの盤面を 縦 6 x 横 7 としているため、置ける手数は 7 通りあります。
それぞれ 1~7 に対して順番にシミュレーションを行うことで最善の手を選ぶような実装にします。
実装する上で注意する点は
- 勝利判定
- 盤面の継承
- シミュレーション方法
の3点でした。
順に説明していきます。
勝利判定
愚直に縦横斜めに4つコマが並んでいるかをチェックします。
またすべてのコマが埋まっている場合引き分けとなります。
盤面の継承
シミュレーションをするために、ユーザーの代わりのAIと相手のターンにプレイするAIの2つで盤面を共有する必要があります。
そのため、それまでの盤面のコピーのオブジェクトを生成して、2つのAIそれぞれでコピーしたオブジェクトを参照するようにしました。
そうすることで本来の盤面に影響を及ぼさずにシミュレーションを行うことができます。
Board copyBoard = board; // これまでの盤面のコピー // それぞれ同じ盤面を参照する。 Cpu userCpu(1, copyBoard); Cpu ememyCpu(2, copyBoard);
シミュレーション方法
それぞれの手に対して、最も勝率が高いものを探します。
シミュレーションの流れは以下になります。
プレイヤーがコマを置く。
int score[7] を0初期化する。
一手目を決め打ちする。(1~7)
互いにランダムでコマを置きあい、勝利したら
score[一手目] += 1(scoreを増やす)指定されたシミュレーション回数分 3、4 を繰り返す。
もっともscoreが高い手を選択してコマを置く。
決着がつくまで 1 から繰り返す。
void Cpu::montecarlo(const Board &board, int depth) { if (depth >= g_maxDepth) return; // 指定した回数になるまでシミュレーションを行う playOut(board, depth); montecarlo(board, depth + 1); }
こんな感じで再帰的にシミュレーションしていました。
以上の3点に気をつけることで、つよつよの四目並べAIを作ることができました。
めでたしめでたし。
感想
今回の実装はいわゆる原始モンテカルロ法でそれぞれの手に対して複数回のシミュレーションを行うだけでした。そのため実装もかなりシンプルにできたと思います。
それぞれの手を成長させていくモンテカルロ木探索というアルゴリズムもあるので気が向いたら試してみたいです。
興味ある方はぜひ戦ってみてください〜。
