【Unity】第三回 オセロAI開発 〜モンテカルロ法を用いたAIの作成〜【ゲームAI】

Unity
マイケル
マイケル
みなさんこんにちは!
マイケルです!
エレキベア
エレキベア
こんにちクマ〜〜〜
マイケル
マイケル
今日は引き続き オセロAIの作成 を進めていこうと思います!
エレキベア
エレキベア
確か前回はminimax法を使ってAIを作成したクマね

↑前回までの記事

マイケル
マイケル
今回は簡単に実装できて割と強いと言われている、
モンテカルロ法を使ってAIを実装してみるよ!
エレキベア
エレキベア
モンテカルロ・・・
難しそうクマ〜〜〜
マイケル
マイケル
やってることは単純だからすぐに理解できると思うよ!
早速やってみよう!!
スポンサーリンク

参考書籍

マイケル
マイケル
実装するにあたり、下記書籍をチラ見させていただきました!
リバーシにモンテカルロ法を活用しているサンプルが載っていて大変参考になりました!

Pythonで作って学べる ゲームのアルゴリズム入門

エレキベア
エレキベア
Pythonで作るゲームシリーズは分かりやすいクマね

モンテカルロ法とは

マイケル
マイケル
それでは本題に入っていきましょう!
モンテカルロ法は下記のような手法になります!
モンテカルロ法とは
  • 乱数を用いた試行を繰り返すことによって近似値を求める方法。
エレキベア
エレキベア
乱数を用いた試行・・・
ピンとこないクマね〜〜
マイケル
マイケル
実例で見た方が分かりやすいから、
一つ見てみよう!

モンテカルロ法を用いて円周率を求める

マイケル
マイケル
モンテカルロ法の有名な活用法として、
「ランダムに点を打ちまくって円周率を求める方法」があります!
01 monte pi↑ランダムに点を打って円周率を求める
エレキベア
エレキベア
ランダムに打つだけでそんなことが可能なのクマ・・・?
マイケル
マイケル
円の中に入った点の数と全体の点の数の比率 から簡単に求めることができるんだ!
まず点の数は面積比に比例しているはずだから、下記のような式で表すことができるね。

$$  \frac{inCount}{totalCount} = \frac{\pi r^2}{4r^2} $$

エレキベア
エレキベア
全体を四角(2r*2r)として面積比を求めているわけクマね
マイケル
マイケル
その通り!
そしてこの式を変形すると下記のようになります。

$$  \pi=\frac{inCount}{totalCount}\times4 $$

マイケル
マイケル
つまり円の中に入った点の数/全体の点の数に4をかける
ことで円周率を求めることができるんだ!
エレキベア
エレキベア
そういうことクマか!
マイケル
マイケル
半径を1とした円の中に入ったかどうかは、下記式で求めることができるよ!
ここまでくれば実装できそうだね!

$$ x^2 + y^2 <= 1 $$

エレキベア
エレキベア
これならイメージが湧いてきたクマ〜〜〜
マイケル
マイケル
以上を踏まえて実装したコード、シミュレータは下記になります!
回数を多くするほど近似値(円周率)に近づくので是非試してみてください!

See the Pen
20220620_montecarlo
by masarito617 (@masarito617)
on CodePen.


↑モンテカルロ法で円周率を求めるシミュレータ(※最大数は100000回)

エレキベア
エレキベア
たったこれだけのコードで書けてしまうクマね
解したクマ〜〜〜〜〜

オセロAIの実装

マイケル
マイケル
モンテカルロ法の概要が分かったところで、オセロAIを作ってみよう!
どのように活かせばいいか分かるかな?
エレキベア
エレキベア
あまり思い浮かばないクマね〜〜
ひたすら打ちまくるクマ?
マイケル
マイケル
おぉ!だいぶ近いね!!
打てる手から「ゲーム終了までランダムに打つ」のを数回試行して各手の勝率を求める
ことで決める方法があるよ!!

ScreenShot 2022 06 25 11 16 24↑各手の勝率から選ぶ(100回試行した例)

エレキベア
エレキベア
なるほどクマ〜〜〜!!
それなら試行回数をそれなりに設ければ有利な手が分かりそうクマ
マイケル
マイケル
この考えで実装してみよう!!
今回実装したコードはGitHubにも上げているのでご参照ください!

GitHub – unity-reversi-game-scripts v0.2.0

GitHub – モンテカルロ法の実装

エレキベア
エレキベア
やってやるクマ〜〜
置いた手から勝利した回数を調べる
マイケル
マイケル
まずは 置いた手から指定回数ゲームを行い勝った数を返す 関数から!
ゲーム終了までランダムな手を打った結果から算出 するようにしています。
        /// <summary>
        /// 指定回数ゲームを行い、勝利した回数を返却する
        /// </summary>
        /// <param name="stoneStates">ストーン状態配列</param>
        /// <param name="checkStoneState">置くストーン状態</param>
        /// <param name="checkStoneIndex">置く位置</param>
        /// <param name="playCount">ゲームをプレイする回数</param>
        /// <returns>勝利した回数</returns>
        private static int GetPlayGameWinCount(StoneState[,] stoneStates, StoneState checkStoneState, StoneIndex checkStoneIndex, int playCount)
        {
            // 別スレッドでも動作するようSystemの乱数を使用
            var random = new Random();

            // 勝利した回数をカウントする
            var winCount = 0;
            for (var i = 0; i < playCount; i++)
            {
                // 勝敗が決まるまでゲームを行う
                var activeStoneState = checkStoneState;
                var activeStoneStates = StoneCalculator.GetPutStoneState(stoneStates, activeStoneState, checkStoneIndex.X, checkStoneIndex.Z);
                while (true)
                {
                    // 手番を交代して置くことが可能なストーン状態を取得
                    activeStoneState = GetReverseStoneState(activeStoneState);
                    var canPutStonesIndex = StoneCalculator.GetAllCanPutStonesIndex(activeStoneStates, activeStoneState);
                    if (canPutStonesIndex == null || canPutStonesIndex.Count == 0)
                    {
                        // 置けなくなったらゲーム終了
                        break;
                    }
                    // ランダムで置く
                    var randomIndex = random.Next(0, canPutStonesIndex.Count);
                    var selectStoneIndex = canPutStonesIndex[randomIndex];
                    activeStoneStates = StoneCalculator.GetPutStoneState(activeStoneStates, activeStoneState, selectStoneIndex.X, selectStoneIndex.Z);
                }

                // 勝利判定を行う
                if (StoneCalculator.GetWinStoneState(activeStoneStates) == checkStoneState)
                {
                    winCount++;
                }
            }
            return winCount;
        }
↑指定回数バトルして勝利回数をカウントする
エレキベア
エレキベア
ゲーム終了まで適当に打ちまくればいいわけクマね
勝利した回数から手を選ぶ
マイケル
マイケル
あとはこの関数を使って、
最も勝利回数が多い手を選択すれば実装は完了です!
        /// <summary>
        /// モンテカルロ法によるストーンの探索
        /// </summary>
        /// <param name="stoneStates">ストーン状態配列</param>
        /// <param name="putStoneState">置くストーン状態</param>
        /// <param name="playCount">プレイする回数</param>
        /// <returns>探索したストーン</returns>
        public static StoneIndex SearchMonteCarloStone(StoneState[,] stoneStates, StoneState putStoneState, int playCount)
        {
            // 探索したストーン
            StoneIndex resultStoneIndex = null;

            // 置くことが可能なストーン
            var maxWinCount = -1; // 勝った数
            var canPutStoneIndex = StoneCalculator.GetAllCanPutStonesIndex(stoneStates, putStoneState);
            foreach (var putStoneIndex in canPutStoneIndex)
            {
                // 置いた場合に勝った数を求める
                var winCount = GetPlayGameWinCount(stoneStates, putStoneState, putStoneIndex, playCount);
                if (maxWinCount < winCount)
                {
                    maxWinCount = winCount;
                    resultStoneIndex = putStoneIndex;
                }
            }
            return resultStoneIndex;
        }
↑置ける手からゲーム終了までプレイして最も勝率が高い手を選ぶ
エレキベア
エレキベア
何て手軽なんだクマ・・・!!
処理が重いため注意
マイケル
マイケル
実装はこのようにとても簡単ですが、打つ回数がそれなりに必要なため処理が重くなりがちです・・・。
そのため非同期で別スレッドの処理として切り離しておいた方がよさそうです。
        /// <summary>
        /// 選択するストーンを考える
        /// </summary>
        private async void StartThinkAsync()
        {
            // 考える時間
            await UniTask.Delay(200);

            // ストーンを探索
            SelectStoneIndex = await SearchStoneTask();
        }

        /// <summary>
        /// ストーン探索処理
        /// </summary>
        /// <returns></returns>
        private async UniTask<StoneIndex> SearchStoneTask()
        {
            await UniTask.SwitchToThreadPool(); // 時間がかかるため別スレッドで実行
            var result = AIAlgorithm.SearchMonteCarloStone(StoneStates, MyStoneState, 100);
            await UniTask.SwitchToMainThread();
            return result;
        }
↑モンテカルロ法は重いので別スレッドにした方がよい
エレキベア
エレキベア
UniTaskも別スレッドに切り替える処理が用意されているクマね
マイケル
マイケル
以上で実装は完了です!!

他のAIと対戦させる

マイケル
マイケル
それでは早速強さを見ていきましょう!
前回作ったminimax法を使ったAI、ランダムに置くAIと対戦させてみます。
02 vs monte↑minimaxAIとモンテカルロAIのバトル風景
エレキベア
エレキベア
これは結果が楽しみクマ〜〜〜〜
マイケル
マイケル
ゲーム終了まで計算しているため、
序盤の判断が遅く、終盤の判断が早い のも面白いですね
マイケル
マイケル
それでは対戦した結果は・・・
こちら!!

[対戦結果]
VS ランダムAI -> 30勝0敗
VS minimaxAI -> 15勝15敗

マイケル
マイケル
ランダムに置くAIには圧勝しましたが、
minimax法を用いたAIとは互角 といった結果が出ました!
エレキベア
エレキベア
適当に置きまくるだけで
minimax法と同等の力を得れるとは・・・
マイケル
マイケル
モンテカルロ法、恐るべし・・・

minimax法とミックスさせたら強くなる?

マイケル
マイケル
どうすれば更に強くなるのか・・・?
そう考えた結果、序盤はminimax法で進めて終盤にモンテカルロ法を使用することでそれぞれのメリットが活かせるのでは?
といった案を思い付きました!
エレキベア
エレキベア
確かに序盤はゲーム終了までが長いクマから
確率の精度も甘くなっていそうクマね
マイケル
マイケル
うん、それに序盤は計算時間がかかってしまうという欠点も解消できそうだ!
マイケル
マイケル
というわけで最後に、
下記のようなAIを作って対戦させてみます!
        /// <summary>
        /// ストーン探索処理
        /// </summary>
        private async UniTask<StoneIndex> SearchStoneTask()
        {
            // 時間がかかるため別スレッドで実行
            await UniTask.SwitchToThreadPool();

            // 序盤はMiniMax、終盤はモンテカルロ法で探索する
            var gameRate = StoneCalculator.GetGameRate(StoneStates);
            var result = gameRate <= 0.8f
                ? AIAlgorithm.SearchNegaAlphaStone(StoneStates, MyStoneState, 3, true)
                : AIAlgorithm.SearchMonteCarloStone(StoneStates, MyStoneState, 100);

            await UniTask.SwitchToMainThread();
            return result;
        }
↑終盤からモンテカルロ法を使用するAI
エレキベア
エレキベア
ゲームの進捗状況から使用するアルゴリズムを選択するわけクマね
マイケル
マイケル
その通り!
このアルゴリズムを切り替えるタイミングを変えながら勝率がどう変わるか見てみよう!
マイケル
マイケル
このAIとminimax法を使ったAIを対戦させてみた結果がこちら!

[対戦結果]
※minimax:モンテカルロ
2 : 8 -> 12勝18敗
5 : 5 -> 18勝12敗
8 : 2 -> 21勝9敗
エレキベア
エレキベア
これは・・・
想定通りクマ!!
マイケル
マイケル
やはり基本はminimax法で進めて、終盤にモンテカルロ法で確実にしとめる方法が最も強いことが分かりました!
逆にモンテカルロ法に切り替えるタイミングが早すぎると弱くなってしまう傾向にあるようです。
エレキベア
エレキベア
現時点で最強のAIが完成したクマね
マイケル
マイケル
測定回数が少ないから断定はできないけれど、
こうやって数字に現れると面白いね!!

おわりに

マイケル
マイケル
というわけで、今回はモンテカルロ法を用いたAIの作成でした!
どうだったかな??
エレキベア
エレキベア
考えはシンプルなのにそれなりに強いAIが作れて感動したクマ〜〜〜
マイケル
マイケル
確率で決めるから、処理の過程や中身のロジックについて気にしなくていい
のも汎用性が高くていいよね!
要は専門知識が無くても作れてしまうわけだ!
エレキベア
エレキベア
これは今後作るゲームへの活用も期待できそうクマ
マイケル
マイケル
手軽に使えるから今後も積極的に使ってみよう!!
マイケル
マイケル
それでは今日はこの辺で!!
次回はML-Agentsを使ったAI作成に挑戦していく予定です!
お楽しみに〜〜!!
エレキベア
エレキベア
ついに機械学習に手を出すクマね
楽しみクマ〜〜〜〜

【Unity】第三回 オセロAI開発 〜モンテカルロ法を用いたAIの作成〜【ゲームAI】〜完〜

次回の記事はこちら!

コメント