
マイケル
みなさんこんにちは!
マイケルです!
マイケルです!

エレキベア
クマ〜〜〜

マイケル
今日も前回に引き続きオセロAI作成を進めていきます!

エレキベア
前回はオセロゲームの基盤まで作ったクマね

マイケル
今回からはいよいよAIを作成していくよ!
オセロの有名なアルゴリズムであるminimax法を活用したAIを作成してみます!
オセロの有名なアルゴリズムであるminimax法を活用したAIを作成してみます!

エレキベア
何か難しそうクマ〜〜

マイケル
これがまたシンプルなアルゴリズムなんだけど、割と強いAIになるんだ!
この後、下記のminimax法に基づいた4つのアルゴリズムについて解説して、実際にいくつか実装してみるよ!
この後、下記のminimax法に基づいた4つのアルゴリズムについて解説して、実際にいくつか実装してみるよ!
- minimax法
- negamax法
- alpha-beta法
- nega-alpha法

エレキベア
何がなんだか分からないクマ・・・
お手柔らかに頼むクマ〜〜
お手柔らかに頼むクマ〜〜
参考書籍

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

エレキベア
この本はすごくお世話になっているクマね

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

エレキベア
世界第一位・・・すごいクマ・・・・

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

エレキベア
これも読んでみたいクマね
評価値の計算方法について

マイケル
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;
}
↑評価値の計算
マイケル
実際に設定する評価値に関しては、下記で紹介されているものをそのまま使わせてもらっています!
オセロ(リバーシ)の作り方(アルゴリズム) ~石の位置による評価~

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

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

マイケル
まずは基本となるminimax法について!
1手先を読む場合

マイケル
簡単な例として、1手先を読む場合を考えてみましょう!
これは単純に評価値が大きい手を選ぶで問題なさそうですね!
これは単純に評価値が大きい手を選ぶで問題なさそうですね!


エレキベア
こんなの余裕クマ
なめてるのかクマ
なめてるのかクマ
2手先以上を読む場合

マイケル
それでは2手先の場合はどうでしょうか?
2手先の評価値が下記の場合は、どの手を選べばいいでしょう・・・?
2手先の評価値が下記の場合は、どの手を選べばいいでしょう・・・?


エレキベア
これも簡単クマ
一番大きい「3」を選べばいいクマ
一番大きい「3」を選べばいいクマ

マイケル
そう思ってしまいますが、2手先は相手が打つターンです!
そう都合よくこちらに都合のいい手を打ってくるでしょうか?
そう都合よくこちらに都合のいい手を打ってくるでしょうか?

エレキベア
た、確かにクマ・・・

マイケル
そのため、相手は自分に対して一番不利な手を打ってくると仮定して、
最小の評価値として計算します。
今回の場合は-1となる手を選んだ方がマシ、といった結果になります!
最小の評価値として計算します。
今回の場合は-1となる手を選んだ方がマシ、といった結果になります!


エレキベア
相手の時は最小の手(min)、自分の時は最大の手(max)・・・!
まさかこれが・・・!
まさかこれが・・・!

マイケル
そう、これがminimax法と呼ばれている由来なんだ!!

エレキベア
や、やられたクマ〜〜〜

マイケル
これを指定の深さまで探索して選ぶ手を決定していきます!
一番いいのは事前に全ての結果を計算しておくことですが、オセロだと到底無理なのでゲーム実行中に計算することになります!
一番いいのは事前に全ての結果を計算しておくことですが、オセロだと到底無理なのでゲーム実行中に計算することになります!

negamax法

マイケル
そして次はnegamax法について!
Minimax法を実装しようとすると、手番によって計算方法を変えないといけないため実装が複雑になってしまいます。
結果はそのままに、毎回-1をかけて最大値のみ判定するようにしたのがnegamax法です!
Minimax法を実装しようとすると、手番によって計算方法を変えないといけないため実装が複雑になってしまいます。
結果はそのままに、毎回-1をかけて最大値のみ判定するようにしたのがnegamax法です!


エレキベア
-(nega)をかけて最大値(max)を見るということクマね

マイケル
一つ注意点として、minimax法では局面の評価値で計算していましたが、
negamax法ではその手番の評価値で計算しないといけない点には注意しましょう!
negamax法ではその手番の評価値で計算しないといけない点には注意しましょう!

エレキベア
自分が黒なら、相手の評価値は白で計算するクマね
negamax法の実装

マイケル
negamax法を実装したのが下記になります!
評価値計算含めたアルゴリズム関連の処理はStoneCalculator.csにまとめてあるのでご参照ください!
評価値計算含めたアルゴリズム関連の処理は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法の実装
エレキベア
説明を聞いた後に見ると分かるクマね

マイケル
ちなみに何回か勝負してみたのですが、
自分はほぼ歯が立ちませんでした・・・。
自分はほぼ歯が立ちませんでした・・・。


エレキベア
(四隅取られてるクマ・・・)
alpha-beta法とnega-alpha法

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

エレキベア
アルファベータ・・・
alpha-beta法

マイケル
minimax法には無駄な計算処理が多数含まれていることに気付いたでしょうか?
例えば下記のように最初に計算した手の評価値が2だった場合、他の手はそれ以下の評価値になると分かった時点でそれ以上計算する必要はありません。
例えば下記のように最初に計算した手の評価値が2だった場合、他の手はそれ以下の評価値になると分かった時点でそれ以上計算する必要はありません。


エレキベア
確かに全て調べる必要はなさそうクマね

マイケル
そのため、下記のように最大値以下になると分かった時点で計算を止めてしまいます。
今回の場合、3階層目の中で最大値(alpha)が2以下となった時点で枝刈りを行なっています。
今回の場合、3階層目の中で最大値(alpha)が2以下となった時点で枝刈りを行なっています。


エレキベア
見る必要がないと切り落とすことを枝刈りというクマね

マイケル
同様に4階層を調べる場合には、最小値(beta)を-1として、それより大きい場合に枝刈りを行えばOKです!

マイケル
このように調べる範囲の最大値(alpha)、最小値(beta)を決めて枝刈りを行う手法をalpha-beta法といいます!

エレキベア
なんてスタイリッシュな手法クマ・・・!
nega-alpha法

マイケル
nega-alpha法は、alpha-beta法の考えをnegamax法に適用させたものです!
基本的に同じですが、比較するalphaを毎回反転させる必要があることには注意が必要です!
基本的に同じですが、比較するalphaを毎回反転させる必要があることには注意が必要です!


マイケル
また、枝刈りを行う手法はノードを調べる順番によって計算量が変わる点にも注意が必要です。
例えば、最初に評価値が高いノードが出れば計算量は少なくすみますが、評価値が低かった場合には枝刈りの量も少なくなってしまいます。
例えば、最初に評価値が高いノードが出れば計算量は少なくすみますが、評価値が低かった場合には枝刈りの量も少なくなってしまいます。

エレキベア
その辺はどうにもならないのクマか

マイケル
この対処としては、評価値が高そうな順番に調べるよう工夫する手法が取られるみたいです。
この記事ではそこまで紹介しないので、気になる方はnegascout法等のキーワードで調べてみてください!
この記事ではそこまで紹介しないので、気になる方はnegascout法等のキーワードで調べてみてください!

エレキベア
どこまで早く出来るかは勝負の世界クマね
nega-alpha法の実装

マイケル
nega-alpha法の実装は下記のようになります!
negamax法に少し手を加えた形ですね
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階層程度まで計算することができました!
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-alpha法を使ったAIと
前回作ったランダムに石を置くAIを闘わせてみます!


エレキベア
見てておもしろいクマね

マイケル
気になる結果は・・・?!


・・・数分後・・・

マイケル
30戦中、nega-alphaAIが27勝!
圧倒的に強かったです!!
圧倒的に強かったです!!

エレキベア
3勝したランダムAIに敬服クマ・・・

マイケル
ランダムAIは何も考えてないから逆に不安だったけど、
無事に勝てて一安心しました・・・
無事に勝てて一安心しました・・・

エレキベア
ここまでして弱かったら涙ものクマね
おわりに

マイケル
というわけで今回はminimax法を用いたAIの作成でした!
どうだったかな?
どうだったかな?

エレキベア
シンプルなアルゴリズムで強いAIが作れて感動だったクマ〜〜〜
実装も一つ一つ見ていけばそんなに難しくなかったクマね
実装も一つ一つ見ていけばそんなに難しくなかったクマね

マイケル
minimax法は古典的な方法だけど安定した強さが特徴だね!
次回はこれまた簡単に強いAIが作れると言われているモンテカルロ法を使ってみるよ!
お楽しみに〜〜〜〜!!
次回はこれまた簡単に強いAIが作れると言われているモンテカルロ法を使ってみるよ!
お楽しみに〜〜〜〜!!

エレキベア
クマ〜〜〜〜〜
【Unity】第二回 オセロAI開発 〜minimax法を用いたAIの作成〜【ゲームAI】
次回の記事はこちら!
コメント