【Unity】第二回 オセロAI開発 〜minimax法を用いたAIの作成〜【ゲームAI】

Unity
マイケル
マイケル
みなさんこんにちは!
マイケルです!
エレキベア
エレキベア
クマ〜〜〜
マイケル
マイケル
今日も前回に引き続きオセロAI作成を進めていきます!
エレキベア
エレキベア
前回はオセロゲームの基盤まで作ったクマね
マイケル
マイケル
今回からはいよいよAIを作成していくよ!
オセロの有名なアルゴリズムであるminimax法を活用したAIを作成してみます!
エレキベア
エレキベア
何か難しそうクマ〜〜
マイケル
マイケル
これがまたシンプルなアルゴリズムなんだけど、割と強いAIになるんだ!
この後、下記のminimax法に基づいた4つのアルゴリズムについて解説して、実際にいくつか実装してみるよ!

  • minimax法
  • negamax法
  • alpha-beta法
  • nega-alpha法

エレキベア
エレキベア
何がなんだか分からないクマ・・・
お手柔らかに頼むクマ〜〜
スポンサーリンク

参考書籍

マイケル
マイケル
AIを作成するにあたり、下記書籍を参考にさせていただきました!
こちらのゲームAIの章にminimax法、alpha-beta法について簡単に載っています!

ゲームプログラミングC++

エレキベア
エレキベア
この本はすごくお世話になっているクマね
マイケル
マイケル
それからオセロAI世界一位の方が書いたこちらのnoteも参考にさせていただきました!
すごく分かりやすくて勉強になったので、こちらも是非みてみてください!!

オセロAIの教科書

エレキベア
エレキベア
世界第一位・・・すごいクマ・・・・
マイケル
マイケル
それから個人的には下記書籍も気になっています・・・
古い本ですが、AIのアルゴリズムについても載っているようですね

リバーシのアルゴリズム C++&Java対応

エレキベア
エレキベア
これも読んでみたいクマね

評価値の計算方法について

マイケル
マイケル
AIのアルゴリズム説明に入る前に、良い悪いの基準をどのように判定するか?といったところを考えましょう!
こちらはいろいろな方法がありますが、一番シンプルな「マスごとに評価値を設定して計算する」方法を使うことにしました!
01 evalute↑マスごとに評価値を設定する
マイケル
マイケル
自分の石が置いてある評価値合計 – 相手の意思が置いてある評価値合計
で評価値を計算します。
エレキベア
エレキベア
シンプルで分かりやすいクマね
マイケル
マイケル
実装は下記の通り!
        /// <summary>
        /// ストーン状態に対する評価値
        /// </summary>
        private static readonly int[,] EvaluateStoneStatesScore= new[,] {
            {  30, -12,   0,  -1,  -1,   0, -12,  30},
            { -12, -15,  -3,  -3,  -3,  -3, -15, -12},
            {   0,  -3,   0,  -1,  -1,   0,  -3,   0},
            {  -1,  -3,  -1,  -1,  -1,  -1,  -3,  -1},
            {  -1,  -3,  -1,  -1,  -1,  -1,  -3,  -1},
            {   0,  -3,   0,  -1,  -1,   0,  -3,   0},
            { -12, -15,  -3,  -3,  -3,  -3, -15, -12},
            {  30, -12,   0,  -1,  -1,   0, -12,  30},
        };

        /// <summary>
        /// ストーン状態に対する評価値の計算
        /// </summary>
        /// <param name="stoneStates">ストーン状態配列</param>
        /// <param name="putStoneState">置くストーン状態</param>
        /// <returns>ストーン状態に対する評価値</returns>
        public static int EvaluateStoneStates(StoneState[,] stoneStates, StoneState putStoneState)
        {
            // 白と黒のストーン位置からそれぞれスコアを求める
            var whiteScore = 0;
            var blackScore = 0;
            for (var x = 0; x < stoneStates.GetLength(0); x++)
            {
                for (var z = 0; z < stoneStates.GetLength(1); z++)
                {
                    var score = EvaluateStoneStatesScore[x, z];
                    if (stoneStates[x, z] == StoneState.White)
                    {
                        whiteScore += score;
                    }
                    else if (stoneStates[x, z] == StoneState.Black)
                    {
                        blackScore += score;
                    }
                }
            }
            // 自分の色のスコア - 相手の色のスコア
            if (putStoneState == StoneState.White)
            {
                return whiteScore - blackScore;
            }
            return blackScore - whiteScore;
        }
↑評価値の計算
マイケル
マイケル
実際に設定する評価値に関しては、下記で紹介されているものをそのまま使わせてもらっています!

オセロ(リバーシ)の作り方(アルゴリズム) ~石の位置による評価~

オセロAIの教科書 3 【基礎】 1手読みAIを作る

エレキベア
エレキベア
公開してくれててありがたいクマ
チューニングまでしてたらキリがないクマね

minimax法とnegamax法

マイケル
マイケル
評価値の計算が分かったところで、
AIのアルゴリズムについて考えてみましょう!

minimax法

マイケル
マイケル
まずは基本となるminimax法について!
1手先を読む場合
マイケル
マイケル
簡単な例として、1手先を読む場合を考えてみましょう!
これは単純に評価値が大きい手を選ぶで問題なさそうですね!
02 minimax 01↑1手先を読む場合
エレキベア
エレキベア
こんなの余裕クマ
なめてるのかクマ
2手先以上を読む場合
マイケル
マイケル
それでは2手先の場合はどうでしょうか?
2手先の評価値が下記の場合は、どの手を選べばいいでしょう・・・?
02 minimax 02↑2手先の場合はどうするか
エレキベア
エレキベア
これも簡単クマ
一番大きい「3」を選べばいいクマ
マイケル
マイケル
そう思ってしまいますが、2手先は相手が打つターンです!
そう都合よくこちらに都合のいい手を打ってくるでしょうか?
エレキベア
エレキベア
た、確かにクマ・・・
マイケル
マイケル
そのため、相手は自分に対して一番不利な手を打ってくると仮定して、
最小の評価値として計算します。
今回の場合は-1となる手を選んだ方がマシ、といった結果になります!
02 minimax 03↑相手の番は最小の手を選ぶと仮定
エレキベア
エレキベア
相手の時は最小の手(min)、自分の時は最大の手(max)・・・!
まさかこれが・・・!
マイケル
マイケル
そう、これがminimax法と呼ばれている由来なんだ!!
エレキベア
エレキベア
や、やられたクマ〜〜〜
マイケル
マイケル
これを指定の深さまで探索して選ぶ手を決定していきます!
一番いいのは事前に全ての結果を計算しておくことですが、オセロだと到底無理なのでゲーム実行中に計算することになります!
02 minimax 04↑これがminimax法である

negamax法

マイケル
マイケル
そして次はnegamax法について!
Minimax法を実装しようとすると、手番によって計算方法を変えないといけないため実装が複雑になってしまいます。
結果はそのままに、毎回-1をかけて最大値のみ判定するようにしたのがnegamax法です!
03 negamax 01↑-をかけることで最大値のみ判定するようにする
エレキベア
エレキベア
-(nega)をかけて最大値(max)を見るということクマね
マイケル
マイケル
一つ注意点として、minimax法では局面の評価値で計算していましたが、
negamax法ではその手番の評価値で計算しないといけない点には注意しましょう!
エレキベア
エレキベア
自分が黒なら、相手の評価値は白で計算するクマね

negamax法の実装

マイケル
マイケル
negamax法を実装したのが下記になります!
評価値計算含めたアルゴリズム関連の処理はStoneCalculator.csにまとめてあるのでご参照ください!

GitHub – unity-reversi-game-scripts – AIAlgorithm.cs

        /// <summary>
        /// NegaMaxアルゴリズムによるストーンの探索
        /// </summary>
        /// <param name="stoneStates">ストーン状態配列</param>
        /// <param name="putStoneState">置くストーン状態</param>
        /// <param name="depth">探索する深さ</param>
        /// <returns>探索したストーン</returns>
        public static StoneIndex SearchNegaMaxStone(StoneState[,] stoneStates, StoneState putStoneState, int depth)
        {
            // 探索したストーン
            StoneIndex resultStoneIndex = null;

            // 置くことが可能なストーンを全て調べる
            var maxScore = int.MinValue;
            var canPutStonesIndex = StoneCalculator.GetAllCanPutStonesIndex(stoneStates, putStoneState);
            foreach (var putStoneIndex in canPutStonesIndex)
            {
                // 次の階層の状態を調べる
                var putStoneStates = StoneCalculator.GetPutStoneState(stoneStates, putStoneState, putStoneIndex.X, putStoneIndex.Z);
                var score = -1 * GetNegaMaxScore(putStoneStates, GetReverseStoneState(putStoneState), depth - 1);

                // 最大スコアの場合、スコアと該当インデックスを保持
                if (maxScore < score)
                {
                    maxScore = score;
                    resultStoneIndex = putStoneIndex;
                }
            }
            return resultStoneIndex;
        }

        /// <summary>
        /// NegaMaxアルゴリズムによるスコアの計算
        /// </summary>
        /// <param name="stoneStates">ストーン状態の配列</param>
        /// <param name="putStoneState">置くストーン状態</param>
        /// <param name="depth">探索する深さ</param>
        /// <param name="isPrevPassed">上の階層でパスしたか?</param>
        /// <returns>指定階層の最大スコア</returns>
        private static int GetNegaMaxScore(StoneState[,] stoneStates, StoneState putStoneState, int depth, bool isPrevPassed = false)
        {
            // 葉ノードで評価関数を実行
            if (depth == 0) return EvaluateStoneStates(stoneStates, putStoneState);

            // 置くことが可能なストーンを全て調べる
            var maxScore = int.MinValue;
            var canPutStonesIndex = StoneCalculator.GetAllCanPutStonesIndex(stoneStates, putStoneState);
            foreach (var putStoneIndex in canPutStonesIndex)
            {
                // 次の階層の状態を調べる
                var putStoneStates = StoneCalculator.GetPutStoneState(stoneStates, putStoneState, putStoneIndex.X, putStoneIndex.Z);
                maxScore = Math.Max(maxScore, -1 * GetNegaMaxScore(putStoneStates, GetReverseStoneState(putStoneState), depth - 1));
            }

            // 見つからなかった場合
            if (maxScore == int.MinValue)
            {
                // 2回連続パスの場合、評価関数を実行
                if (isPrevPassed) return EvaluateStoneStates(stoneStates, putStoneState);
                // ストーン状態はそのままで、次の階層の状態を調べる
                return -1 * GetNegaMaxScore(stoneStates, GetReverseStoneState(putStoneState), depth - 1, true);
            }
            return maxScore;
        }
↑negamax法の実装
エレキベア
エレキベア
説明を聞いた後に見ると分かるクマね
マイケル
マイケル
ちなみに何回か勝負してみたのですが、
自分はほぼ歯が立ちませんでした・・・。
01 negamax↑マイケル VS negamaxAI
エレキベア
エレキベア
(四隅取られてるクマ・・・)

alpha-beta法とnega-alpha法

マイケル
マイケル
次はalpha-beta法についての解説です!
こちらはminimax法から無駄な計算を省いて発展させたアルゴリズムです!
エレキベア
エレキベア
アルファベータ・・・

alpha-beta法

マイケル
マイケル
minimax法には無駄な計算処理が多数含まれていることに気付いたでしょうか?
例えば下記のように最初に計算した手の評価値が2だった場合、他の手はそれ以下の評価値になると分かった時点でそれ以上計算する必要はありません
04 alphabeta 01↑最初に調べた評価値が2だった場合
エレキベア
エレキベア
確かに全て調べる必要はなさそうクマね
マイケル
マイケル
そのため、下記のように最大値以下になると分かった時点で計算を止めてしまいます。
今回の場合、3階層目の中で最大値(alpha)が2以下となった時点で枝刈りを行なっています。
04 alphabeta 02↑評価値が2未満の場合には見る必要が無くなる
エレキベア
エレキベア
見る必要がないと切り落とすことを枝刈りというクマね
マイケル
マイケル
同様に4階層を調べる場合には、最小値(beta)を-1として、それより大きい場合に枝刈りを行えばOKです!
マイケル
マイケル
このように調べる範囲の最大値(alpha)、最小値(beta)を決めて枝刈りを行う手法をalpha-beta法といいます!
エレキベア
エレキベア
なんてスタイリッシュな手法クマ・・・!

nega-alpha法

マイケル
マイケル
nega-alpha法は、alpha-beta法の考えをnegamax法に適用させたものです!
基本的に同じですが、比較するalphaを毎回反転させる必要があることには注意が必要です!
05 negaalpha 01↑negamax法に適用した場合も基本的には同じ
マイケル
マイケル
また、枝刈りを行う手法はノードを調べる順番によって計算量が変わる点にも注意が必要です。
例えば、最初に評価値が高いノードが出れば計算量は少なくすみますが、評価値が低かった場合には枝刈りの量も少なくなってしまいます。
エレキベア
エレキベア
その辺はどうにもならないのクマか
マイケル
マイケル
この対処としては、評価値が高そうな順番に調べるよう工夫する手法が取られるみたいです。
この記事ではそこまで紹介しないので、気になる方はnegascout法等のキーワードで調べてみてください!
エレキベア
エレキベア
どこまで早く出来るかは勝負の世界クマね

nega-alpha法の実装

マイケル
マイケル
nega-alpha法の実装は下記のようになります!
negamax法に少し手を加えた形ですね

        /// <summary>
        /// NegaAlphaアルゴリズムによるストーンの探索
        /// </summary>
        /// <param name="stoneStates">ストーン状態の配列</param>
        /// <param name="putStoneState">置くストーン状態</param>
        /// <param name="depth">探索する深さ</param>
        /// <returns>探索したストーン</returns>
        public static StoneIndex SearchNegaAlphaStone(StoneState[,] stoneStates, StoneState putStoneState, int depth)
        {
            // 探索したストーン
            StoneIndex resultStoneIndex = null;

            // 置くことが可能なストーンを全て調べる
            var alpha = int.MinValue + 1; // MinValueを反転するとintの範囲を超えてしまうため、+1する
            var beta = int.MaxValue;
            var canPutStonesIndex = StoneCalculator.GetAllCanPutStonesIndex(stoneStates, putStoneState);
            foreach (var putStoneIndex in canPutStonesIndex)
            {
                // 次の階層の状態を調べる
                var putStoneStates = StoneCalculator.GetPutStoneState(stoneStates, putStoneState, putStoneIndex.X, putStoneIndex.Z);
                var score = -1 * GetNegaAlphaScore(putStoneStates, GetReverseStoneState(putStoneState), depth - 1, -beta, -alpha);

                // 最大スコアの場合、スコアと該当インデックスを保持
                if (alpha < score)
                {
                    alpha = score;
                    resultStoneIndex = putStoneIndex;
                }
            }
            return resultStoneIndex;
        }

        /// <summary>
        /// NegaAlphaアルゴリズムによるスコアの計算
        /// </summary>
        /// <param name="stoneStates">ストーン状態の配列</param>
        /// <param name="putStoneState">置くストーン状態</param>
        /// <param name="depth">探索する深さ</param>
        /// <param name="alpha">探索範囲の下限</param>
        /// <param name="beta">探索範囲の上限</param>
        /// <param name="isPrevPassed">上の階層でパスしたか?</param>
        /// <returns>指定階層の最大スコア</returns>
        private static int GetNegaAlphaScore(StoneState[,] stoneStates, StoneState putStoneState, int depth, int alpha, int beta, bool isPrevPassed = false)
        {
            // 葉ノードで評価関数を実行
            if (depth == 0) return EvaluateStoneStates(stoneStates, putStoneState);

            // 置くことが可能なストーンを全て調べる
            var maxScore = int.MinValue;
            var canPutStonesIndex = StoneCalculator.GetAllCanPutStonesIndex(stoneStates, putStoneState);
            foreach (var putStoneIndex in canPutStonesIndex)
            {
                // 次の階層の状態を調べる
                var putStoneStates = StoneCalculator.GetPutStoneState(stoneStates, putStoneState, putStoneIndex.X, putStoneIndex.Z);
                var score = -1 * GetNegaAlphaScore(putStoneStates, GetReverseStoneState(putStoneState), depth - 1, -beta, -alpha);

                // NegaMax値が探索範囲の上限より上の場合は枝狩り
                if (score >= beta) return score;

                // alpha値、maxScoreを更新
                alpha = Math.Max(alpha, score);
                maxScore = Math.Max(maxScore, score);
            }

            // 見つからなかった場合
            if (maxScore == int.MinValue)
            {
                // 2回連続パスの場合、評価関数を実行
                if (isPrevPassed) return EvaluateStoneStates(stoneStates, putStoneState);
                // ストーン状態はそのままで、次の階層の状態を調べる
                return -1 * GetNegaAlphaScore(stoneStates, GetReverseStoneState(putStoneState), depth - 1, -beta, -alpha, true);
            }
            return maxScore;
        }
↑nega-alpha法の実装
マイケル
マイケル
気になる速度ですが、negamax法だと3階層程度が限界だったのですが、
nega-alpha法だと6階層程度まで計算することができました!
エレキベア
エレキベア
元の実装も悪そうクマね
マイケル
マイケル
その辺りはご了承ください・・・

同じ評価値だった場合の対処

マイケル
マイケル
最後に、negamax法、nega-alpha法どちらも同じ順序で調べているため、
同じ評価値の場合には毎回同じ結果
になってしまいます。。
これだとゲーム開始後にも毎回同じ手になったり等、機会じみた感じがしますね
マイケル
マイケル
そのため、下記のように同じ評価値だった場合にはランダムで入れ替えるロジックを入れてあげると少しはランダム性が出るようになると思います。

        /// <summary>
        /// NegaAlphaアルゴリズムによるストーンの探索
        /// </summary>
        /// <param name="stoneStates">ストーン状態の配列</param>
        /// <param name="putStoneState">置くストーン状態</param>
        /// <param name="depth">探索する深さ</param>
        /// <param name="isRandom">スコアが同じだった場合にランダムにするか?</param>
        /// <returns>探索したストーン</returns>
        public static StoneIndex SearchNegaAlphaStone(StoneState[,] stoneStates, StoneState putStoneState, int depth, bool isRandom = false)
        {
            // 探索したストーン
            StoneIndex resultStoneIndex = null;

            // 置くことが可能なストーンを全て調べる
            var alpha = int.MinValue + 1; // MinValueを反転するとintの範囲を超えてしまうため、+1する
            var beta = int.MaxValue;
            var canPutStonesIndex = StoneCalculator.GetAllCanPutStonesIndex(stoneStates, putStoneState);
            foreach (var putStoneIndex in canPutStonesIndex)
            {
                // 次の階層の状態を調べる
                var putStoneStates = StoneCalculator.GetPutStoneState(stoneStates, putStoneState, putStoneIndex.X, putStoneIndex.Z);
                var score = -1 * GetNegaAlphaScore(putStoneStates, GetReverseStoneState(putStoneState), depth - 1, -beta, -alpha);

                // 最大スコアの場合、スコアと該当インデックスを保持
                if (alpha < score)
                {
                    alpha = score;
                    resultStoneIndex = putStoneIndex;
                }
                else if (isRandom && alpha == score && UnityEngine.Random.Range(0, 2) == 0)
                {
                    // スコアが同じだったら1/2の確率で入れ替える
                    alpha = score;
                    resultStoneIndex = putStoneIndex;
                }
            }
            return resultStoneIndex;
        }
↑評価値が同じだった場合の対処
エレキベア
エレキベア
機械らしさはなるべく取り除きたいクマね

nega-alphaAI VS ランダムAI

マイケル
マイケル
AI作成は以上になります!
最後におまけとしてnega-alpha法を使ったAI
前回作ったランダムに石を置くAIを闘わせてみます!
02 nega vs random↑nega-alphaAI VS ランダムAI
エレキベア
エレキベア
見てておもしろいクマね
マイケル
マイケル
気になる結果は・・・?!
Ramen bottom
Ramen top
 ・・・数分後・・・
マイケル
マイケル
30戦中、nega-alphaAIが27勝
圧倒的に強かったです!!
エレキベア
エレキベア
3勝したランダムAIに敬服クマ・・・
マイケル
マイケル
ランダムAIは何も考えてないから逆に不安だったけど、
無事に勝てて一安心しました・・・
エレキベア
エレキベア
ここまでして弱かったら涙ものクマね

おわりに

マイケル
マイケル
というわけで今回はminimax法を用いたAIの作成でした!
どうだったかな?
エレキベア
エレキベア
シンプルなアルゴリズムで強いAIが作れて感動だったクマ〜〜〜
実装も一つ一つ見ていけばそんなに難しくなかったクマね
マイケル
マイケル
minimax法は古典的な方法だけど安定した強さが特徴だね!
次回はこれまた簡単に強いAIが作れると言われているモンテカルロ法を使ってみるよ!
お楽しみに〜〜〜〜!!
エレキベア
エレキベア
クマ〜〜〜〜〜

【Unity】第二回 オセロAI開発 〜minimax法を用いたAIの作成〜【ゲームAI】

次回の記事はこちら!

コメント