羊の人工知能研究 ~将棋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つのランキングに参加しています↓

スポンサーサイト

つ、遂にAIの基本完成

 つ、遂に将棋の基本AIが完成しましたヽ(●´ε`●)ノ 本日までに追加した機能としては、以下の2つです。

①王手を判定する
②合法手を生成する


 ①の王手を判定するについては、『王の座標に移動できる敵駒があるか?』という考えのもと、そのままコーディングした。王(玉)の座標についてはこの盤面の仕様で、盤面は駒のポインタ配列でできていて、それぞれの駒がどの座標にいるかという情報を持っているので、盤面を初期化するときにこの変数のポインタを保存してあるので、ポインタを参照することで座標は簡単に知ることができます。まぁ分かりにくいと思うので↓を参照。。。

//駒構造体
typedef struct KOMA{
char kind;//種類
char xy;//座標
bool nari;//成り状態
char owner;//所有者
}KOMA;

//盤面クラス
class BOARD{
private:
KOMA *table[121];//駒のポインタテーブル
KOMA koma[121];//上下左右に厚さ1の壁を設けている
char *ou_xy[2];//王の玉の駒構造体の座標へのポインタ



(省略)
};


言葉では説明が難しかったので簡単なソースを付けてみましたが言いたいことが分かってもらえたでしょうか?王は盤面から排除されることがないので、最初にこのようにポインタとしておくと、移動しても簡単に王の座標を知ることができるのです。これにより、この王の座標に移動できる相手の駒を探すことにより王手かどうかを判断することができます。


 次に②合法手を生成するについては、まず合法手とは、ルールに従って移動できる手及び置ける手です。また、王手がかかっている場合は王手を回避することのできる手が合法な手です。
 王手がかかっていない場合は、お得意関数ポインタ配列を使って『A座標の駒はB座標に移動できる』『K駒をB座標に置くことができる』というものを全てリストアップする関数が既に用意してあるので、そのリストを連結するだけです。
 王手がかかっている場合については、王手がかかっていない場合についてその中で『その手を打った次の手で相手に王が取られないか?』について判断し、王手がかかっていない場合が回避できた場合なのでそれをリストに追加していくだけです。

 この辺については、まだまだ改善する必要があると思うがこの2つの関数により、探索の中で合法手が存在しない場合は『詰み』と判断できるようになったので、

ようやく一応のAI完成

となった。




次回予告:詰め将棋の基礎
に入れたらイイな~頑張ります。。。



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

Minimaxアルゴリズムを使って探索する

 アンケートのご協力ありがとうございましたm(。_。;))m ペコペコ 数々のアンケートよりカナリ元気をもらい、ブックマークもされている方もあるようなので、忙しい中もますます『頑張って更新しないと』と思い本日の更新に至りました(´・ω・汗)ゞなお、アンケートは随時受け付けておりますので、ヨロシクお願いします(人>ω<`◎)


 ってわけで、途中になっていた探索最善手の探索方法について説明したいと思います。最善手とは普通に考えるとなかなか頭が痛く想像がつきにくいものですが、簡単に言うと『自分も相手も最善の手を打ったとき』という一言に尽きます。それをプログラムとして実現する方法として昔々に考えられた方法がMinimaxアルゴリズムなのです。Minimaxアルゴリズムの概要としては、上のノードから返ってきた評価値を探索側では最大値を、敵側では最小値をとることにより最善手が見つけられます。このときの探索側とは、探索をしようとしているプレイヤーのことです。わかりにくいと思いますので下の図25で説明したいと思います。



図25:探索前


 上の図25の木は深さ3のレベルで読んで、末端で評価値を求めたものです。この木において手番は毎回交代するものと考えて、最善のルートを見つけたいと思います。Minimaxにおける探索ルールは極めて簡単です。

①手番が探索側(Max側)ならば候補手の中で最も評価の高いものを選ぶ。
②手番が敵側(Min側)ならば候補手の中で最も評価の低いものを選ぶ。


 このルールに従って最善のルートを探索してみると以下のようになります。←図26参照



図26:探索後


 この結果から、探索側は右の方の手を選ぶと良い事がわかります。ここで、先ほどのルールがなぜ『自分も相手も最善の手を打ったとき』につながるかを説明します。

 ※まず、ここでの評価値は探索側から見た評価値が計算されていることに注意してください。

 ここで、ルール①『手番が探索側(Max側)ならば候補手の中で最も評価の高いものを選ぶ。』というのは簡単にわかると思います。評価値がズラーっと並べられてどれを選ぶ??となると、やはり一番高い(Max)評価値を選ぶでしょう。

 次に、ルール②『手番が敵側(Min側)ならば候補手の中で最も評価の低いものを選ぶ。』は、逆に考えると簡単です。評価値は探索側からみ見た評価で計算されていますので、一番小さいもの(Min)を選ぶと探索側にとって不利(敵側にとって有利)となります。

 これらのことにより、『自分も相手も最善の手を打ったとき』という考え方が出来上がっていることになります。

 最後にMinimaxアルゴリズムをC言語に似た擬似言語で紹介したいと思います。

int mini_max(盤面, int lv)
{
int val, max;

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

if(先手)max = -∞;
else max = ∞;

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

んま~頑張って理解してみてください(´・ω・汗)ゞわからないことがあれば、コメント又はメールでお願いします。。。。



次回予告:未定



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

アンケートにご協力お願いします

 最近就活が忙しく更新がかなり滞っていますがここらで、一つお越しいただいたお客様にアンケートをお願いしたいとおもい本日の更新に至りました。

アンケートはコチラからお願いします

 また、このアンケートは個人情報などの要求は一切なくこのブログの感想などチェックで5問の質問に答えていただくだけです。クオリティの高いブログを提供したいと思っていますので30秒ほどお時間をいただけると答えられると思いますのでご協力お願いいたします。。。



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

おかげさまで現在プログラミング部門のランキング2位を死守しておりますm(。_。;))m
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。