羊の人工知能研究 ~将棋AI開発の日々~

将棋、リバーシのAIプログラミングを中心にその開発過程及び記録を頑張って更新していきます。

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

NegaMaxアルゴリズムによる探索

 以前にMiniMaxアルゴリズムによる探索方法を紹介しましたが、本日はNegaMaxアルゴリズムによる探索を紹介します。

 うわ~また違う名前の探索アルゴリズムが出てきた~(*´□`)っと思う必要はあるません。基本はMinimaxですから!!違いとしては、Minimaxの場合は探索側と敵側を意識して、探索側の場合は評価値の最大値を、敵側の場合は最小値をとif文で処理を分けていました。

 しかし今回は、ある方法を使うことにより探索側と敵側の区別をする必要がなくなります。要するに、区別をしなくていいということは、if文を使う必要がないということです。前にも言いましたがif文等のジャンプ命令は大変時間のかかる処理で、今回のように探索毎に探索側と敵側を区別してるようでは、処理が遅くなるのは目に見えてます。

 まぁ解決する方法としては、相互再帰だっけ?を使うと、区別する必要がなくなると思うんですが、個人的に好きじゃありません。。。プログラムの感じとしては次のようなものです↓↓

int max(盤面, int lv)
{
int val, max = -∞;

if(lv == 0)return 評価値(盤面);

while(打てる手がある){
手を差して次の盤面を作る;
val = mini(盤面, lv - 1);
盤面を1手戻す;
if(max < val)max = val;
}
return max;
}

int mini(盤面, int lv)
{
int val, mini = ∞;

if(lv == 0)return 評価値(盤面);

while(打てる手がある){
手を差して次の盤面を作る;
val = max(盤面, lv - 1);
盤面を1手戻す;
if(mini > val)mini = val;
}
return mini;
}


Minimaxアルゴリズムのソースと比較してもらったら大体わかると思います。max関数が探索側で評価値は最大値をとるようにして、mini関数が敵側で評価値は最小値をとるようにする。max関数からはmini関数を呼び出しmini関数からはmax関数を呼び出す。←相互に呼び出されるので相互再帰と呼ばれる・・・多分(汗

 相互再帰を使ったMinimaxも悪くないとは思います!!好きじゃないだけ・・・まぁNegaMaxの方を紹介します。NegaMaxのある方法とは・・・返ってくる『返ってきた評価値を+-反転させ、評価値は常に最大値をとる』です。えっそれだけ?ってそれだけです。下の図27を見てください



図27:NegaMaxによる探索の様子


 このツリーは以前の図26と同じです。ここで注意が必要なのは、Minimaxの場合は末端の評価値を探索側から見たもので計算しなければならなかったのですが、今回は現在の手番(今回の場合だったら末端は敵側)から見た評価値を計算するので前回とは評価値が+-逆になっています。

 あとは探索していくだけです。評価値を反転させた中で最大値を求めて、さらに上のノードでも評価値を反転させて最大値を求めていくことで、前回と同じルートで同じ『3』という評価値が得られました。

 このことにより、探索側敵側ともに同じアルゴリズムが使えるので、プログラムが簡潔になるという点で優れていると思います。また、簡潔になるということは、探索速度の向上にもつながり強いAI完成にもつながります。

 最後に今回のNegaMaxのソースを紹介して終わりにします。

int nega_max(盤面, int lv)
{
int val, max = -∞;

if(lv == 0)return 評価値(盤面);

while(打てる手がある){
手を差して次の盤面を作る;
val = -nega_max(盤面, lv - 1);
盤面を1手戻す;
if(max < val)max = val;
}
return max;
}

ホンマ簡潔になったよな・・・


次回予告:αβアルゴリズムによる探索で超高速化



↓現在2つのランキングに参加しています↓

スポンサーサイト

コメントの投稿

URL
コメント
パスワード
秘密
管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://hitsujiai.blog48.fc2.com/tb.php/23-fb9664ec
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。