ゲーム開発
Unity
UnrealEngine
C++
Blender
Houdini
ゲーム数学
ゲームAI
グラフィックス
サウンド
アニメーション
GBDK
制作日記
IT関連
ツール開発
フロントエンド関連
サーバサイド関連
WordPress関連
ソフトウェア設計
おすすめ技術書
音楽
DTM
楽器・機材
ピアノ
ラーメン日記
四コマ漫画
その他
おすすめアイテム
おもしろコラム
  • ゲーム開発
    • Unity
    • UnrealEngine
    • C++
    • Blender
    • Houdini
    • ゲーム数学
    • ゲームAI
    • グラフィックス
    • サウンド
    • アニメーション
    • GBDK
    • 制作日記
  • IT関連
    • ツール開発
    • フロントエンド関連
    • サーバサイド関連
    • WordPress関連
    • ソフトウェア設計
    • おすすめ技術書
  • 音楽
    • DTM
    • 楽器・機材
    • ピアノ
  • ラーメン日記
    • 四コマ漫画
      • その他
        • おすすめアイテム
        • おもしろコラム
      1. ホーム
      2. 20220612_01

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

      UnityゲームAIゲームAIminimax法
      2022-06-12

      マイケル
      マイケル
      みなさんこんにちは!
      マイケルです!
      エレキベア
      エレキベア
      クマ〜〜〜
      マイケル
      マイケル
      今日も前回に引き続きオセロ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のアルゴリズム説明に入る前に、良い悪いの基準をどのように判定するか?といったところを考えましょう!
      こちらはいろいろな方法がありますが、一番シンプルな「マスごとに評価値を設定して計算する」方法を使うことにしました!
      ↑マスごとに評価値を設定する
      マイケル
      マイケル
      自分の石が置いてある評価値合計 – 相手の意思が置いてある評価値合計
      で評価値を計算します。
      エレキベア
      エレキベア
      シンプルで分かりやすいクマね
      マイケル
      マイケル
      実装は下記の通り!
              /// <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手先を読む場合を考えてみましょう!
      これは単純に評価値が大きい手を選ぶで問題なさそうですね!
      ↑1手先を読む場合
      エレキベア
      エレキベア
      こんなの余裕クマ
      なめてるのかクマ
      2手先以上を読む場合
      マイケル
      マイケル
      それでは2手先の場合はどうでしょうか?
      2手先の評価値が下記の場合は、どの手を選べばいいでしょう・・・?
      ↑2手先の場合はどうするか
      エレキベア
      エレキベア
      これも簡単クマ
      一番大きい「3」を選べばいいクマ
      マイケル
      マイケル
      そう思ってしまいますが、2手先は相手が打つターンです!
      そう都合よくこちらに都合のいい手を打ってくるでしょうか?
      エレキベア
      エレキベア
      た、確かにクマ・・・
      マイケル
      マイケル
      そのため、相手は自分に対して一番不利な手を打ってくると仮定して、
      最小の評価値として計算します。
      今回の場合は-1となる手を選んだ方がマシ、といった結果になります!
      ↑相手の番は最小の手を選ぶと仮定
      エレキベア
      エレキベア
      相手の時は最小の手(min)、自分の時は最大の手(max)・・・!
      まさかこれが・・・!
      マイケル
      マイケル
      そう、これがminimax法と呼ばれている由来なんだ!!
      エレキベア
      エレキベア
      や、やられたクマ〜〜〜
      マイケル
      マイケル
      これを指定の深さまで探索して選ぶ手を決定していきます!
      一番いいのは事前に全ての結果を計算しておくことですが、オセロだと到底無理なのでゲーム実行中に計算することになります!
      ↑これがminimax法である

      negamax法

      マイケル
      マイケル
      そして次はnegamax法について!
      Minimax法を実装しようとすると、手番によって計算方法を変えないといけないため実装が複雑になってしまいます。
      結果はそのままに、毎回-1をかけて最大値のみ判定するようにしたのがnegamax法です!
      ↑-をかけることで最大値のみ判定するようにする
      エレキベア
      エレキベア
      -(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法の実装
      エレキベア
      エレキベア
      説明を聞いた後に見ると分かるクマね
      マイケル
      マイケル
      ちなみに何回か勝負してみたのですが、
      自分はほぼ歯が立ちませんでした・・・。
      ↑マイケル VS negamaxAI
      エレキベア
      エレキベア
      (四隅取られてるクマ・・・)

      alpha-beta法とnega-alpha法

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

      alpha-beta法

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

      nega-alpha法

      マイケル
      マイケル
      nega-alpha法は、alpha-beta法の考えをnegamax法に適用させたものです!
      基本的に同じですが、比較するalphaを毎回反転させる必要があることには注意が必要です!
      ↑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を闘わせてみます!
      ↑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】

      次回の記事はこちら!

      UnityゲームAIゲームAIminimax法
      2022-06-12

      関連記事
      【Unity】Timeline × Excelでスライドショーを効率よく制作する
      2024-10-31
      【Unity】Boidsアルゴリズムを用いて魚の群集シミュレーションを実装する
      2024-05-28
      【Unity】GoでのランキングAPI実装とVPSへのデプロイ方法についてまとめる【Go言語】
      2024-04-14
      【Unity】第二回 Wwiseを使用したサウンド制御 〜インタラクティブミュージック編〜
      2024-03-30
      【Unity】第一回 Wwiseを使用したサウンド制御 〜基本動作編〜
      2024-03-30
      【Unity】第二回 CRI ADXを使用したサウンド制御 〜インタラクティブミュージック編〜
      2024-03-28
      【Unity】第一回 CRI ADXを使用したサウンド制御 〜基本動作、周波数解析編〜
      2024-03-28
      【Unity】サウンドミドルウェアに依存しない設計を考える【CRI ADX・Wwise】
      2024-03-27