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

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

スポンサーサイト

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

αβ探索をもっと効率よくするには?

 前回に続いてαβのことについて語りたいと思います!!

 で、まぁいくら語っても探索が早くならないと意味がないので早くなる手法について語ります。単純に前回の知識から高速化するには・・・・って考えると

枝刈りが増えれば早くなるんじゃねーの?」

ってのが1つとして出てくると思います!

 
まさにその通り!!ある方法を使って枝刈りが多く増えるようにすればイイんです☆☆

でまぁ今回はその枝刈りが増える方法をダラ②説明していきます。

「それ何か考えたら難しそう。:゚(。ノω\。)゚・。 」

って思うかもしれないけど、実はメッチャ簡単!!説明は一行で終わってしまうかもしれないけど、ナゼそうなるかについて説明して結論を言いたいと思います。

 まず、前回の図28のゲーム木を見て、どういう時に枝刈りが起こっているかを発見してみてください。



わかりました??


答えとしては、「枝刈りの起きる親の親のノードで自分の評価より大きい値が既にある場合」

という感じでしょうか?日本語苦手なので間違ってたらゴメンなさい・・・。何にせよ枝刈りというのは「前回の探索より悪いのが出てきたのでこれ以上探索する必要ないや~」って考え方なのです。だから、どうすれば枝刈りを増やせるかというと・・・・

評価が高くなるノードから探索すると良いのです!!←コレが結論



「それが分かったら探索する意味ねーじゃん!!」


あぁ~予想通りの声が聞こえてくる 耳ホジホジ*-o-(= ・ェ・=)聞コエニャイモ~ン
まぁまさにその通りなのです。。。ゴメンなさい(ノ´・Д・)ノミ(m´_ _)m
上の結論は実は少し言葉が抜けてます!!

評価が高くなると思われるノードから探索すると良いのです!!←コレが本当の結論

 では、どうすれば評価が高くなると思われるノードからたんさくするのか?

 まず、オセロ等何でも良いのでゲームを想像してみましょう。一回悪い手(行動)をすると形勢は悪くなりますよね?また、逆に一度良い手を打つと形勢は良くなりますよね?このように何ても深く読まなくてもこの手は悪いこの手は良いのいうモノが浅い探索でわかる場合があります。

 とまぁ文字ばかりの説明で目がチカチカしてきますが、上で言ったように浅い探索を予めしておき、評価が良かったノードから探索すれば良いのです。


コレで分かりました??まぁ今回の擬似コードを書いておきます。

int alpha_beta(盤面, int lv, int al, int be)
{
int val;

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

if(lv > 4)浅い探索で手を並べ替える;

while(打てる手がある){
手を差して次の盤面を作る;
val = -alpha_beta(盤面, lv - 1, -be, -al);
盤面を1手戻す;
//枝狩り
if(val >= be)return al;
//最高値
if(al < val)al = val;
}
return al;
}


えっと絶対疑問の声が聞こえてくるので説明を付け加えておきます。なぜ『if(lv > 4)』の時だけ手を並べ替えるのか。

答えは単純で、という数字は任意でかまいませんが、あまりノードが深くなってくると探索するより浅い探索をして並べ替えるリスクが高くなってしまうんです!それに、もし浅い探索をする場合に自分自身であるalpha_beta関数を使用する場合、その先でまた浅い並べ替え、呼び出されたalpha_beta関数でまた呼び出され・・・・・で無限ループに陥ってしまいます(>ω<;)そういう理由です。


ってわけで、中途半端な気もしますが語りたいことは語ったので今日はこのへんで[*l _ l]ノシ


次回予告:オセロの評価値を作ってみよう!



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

スポンサーサイト

αβアルゴリズムによる探索超高速化

 就職活動も無事終わったし久しぶりに書くかって感じで(゚ー゚;Aアセアセ

前回(何ヶ月前やねん・・・)NegaMaxについての説明を長々としましたが、まぁ余り深く探索できないのでほとんどの場合はαβアルゴリズムを応用したアルゴリズムを使って探索をしています。(まぁ元をたどれば全てMinimaxの応用なんだけどな)

 まっ早速ダラ②いきましょう!!NegaMaxと違うところは『余計な探索をしない!!』というところだけで、他はNegaMaxのソース自体を丸々使ってほど同じ!!

 それでは、NegaMaxで必要ない探索とは何なのかゲーム木を使って説明したいと思います。


図28:今回のゲーム木


 上は前回同様NegaMaxを使って探索をした場合です。この探索でαβを使うと探索する必要のないノードがたくさんあります。図28の場合で探索する必要のないノードは下の図29で×が付いているノードです。


図29:今回のゲーム木


 えっとマズはこの必要のないノードを探索しないことを枝刈りと言います。コレはゲーム木の枝を切る(刈る)というところからきているハズですウン。 で、なぜ枝狩りが起きるかと言うと、結局はNegaMaxのアルゴリズムが理解できてて、数字を見てみれば想像できる人もいるかもしれません。

 例えば左の2のノードが枝狩りされているかと言うと、このノードの親の親に当たるノードの一回目の探索で2という評価が出てきています。そして各ノードでは子の最小値を反転させた値が評価となります。そして、その右のノードの一回目の探索で0という評価が出てきています。その時点で、このノードの評価値が0以上という値が決定します。ということで、親のノードではこのノードが最高値となる事がナイのでこれ以上の探索は無意味となり、この時点での探索打ち切りとなります。他のノードでも全く同じ考え方です。

 今回の例では少ししか枝狩りされませんでしたが、もっと深く探索する場合では探索の早い段階で枝狩りが起きることにより無駄なノードを早くから枝狩りすることができます。一般的にはαβのアルゴリズムにすることにより、同じ探索時間で深さを2倍にできるとまで言われています。この探索方法はAIの基本と呼べるモノなのでこれから先のアルゴリズムでの基本知識として頭に叩き入れておいていただきたいです。

 でまぁ、最後に今回のαβアルゴリズムの擬似コードを書いて終わりにしたいと思います。
int alpha_beta(盤面, int lv, int al, int be)
{
int val;

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

while(打てる手がある){
手を差して次の盤面を作る;
val = -alpha_beta(盤面, lv - 1, -be, -al);
盤面を1手戻す;
//枝狩り
if(val >= be)return al;
//最高値
if(al < val)al = val;
}
return al;
}


こんなところかねαβは!重要な所は赤色になってますので、あとは・・・ノシ


次回予告:不明です。。風の吹くまま・・・



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

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つのランキングに参加しています↓

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つのランキングに参加しています↓

ゲーム木と探索での評価値

 本日はゲームのAIの基礎、探索についての更新をしようと予定していましたが、それまでにゲーム木評価値について説明する必要がりました。。。

 まず、ほとんどの(?)ゲームはゲーム木という形でゲームの状態を表すことができます。○×ゲーム(3目並べ?)を使ってゲーム木というものを説明します。←図24参照



図24:○×ゲームのゲーム木


 かなり省略した形になりましたが、○×ゲームは上のようなゲーム木になることがわかるでしょうか?このゲーム木において両者が最善手を尽くした場合を探索するのがMinimax等に代表される探索です。しかし、ゲームの状態の数鼠算式に増えていき大変な数のゲームの状態が考えられるでしょう。単純計算すると○×ゲームの状態の数は

9×8×7×・・・×2×1 = 9! = 362880

という計算ができます。36万とか莫大な数ですよね・・・。まぁ実際は途中でゲームが終わったりするので何分の1かになるでしょうが、それでも多くの状態が考えられます。しかし、今のPCではこの○×ゲームを全て探索するのに1秒もかからないでしょう。よって、9手先(全てが埋まるか3目並ぶまで)まで全て読んでどちらも最善手を尽くした場合を考えることができるでしょう。

 しかし、リバーシや将棋となるとゲームの状態の数は天文学的数字になるでしょう!!このゲームを最後まで読んで最善手を出していては地球が終わっても計算が終わらないのでは・・・(汗 そこで、ある程度先、例えば4手先まで読んで評価値というものを計算して返してやります。評価値というのは普段ゲームしているときに感じると思いますが、ゲームの途中で有利、不利、互角など感じるように、コンピュータにもそれを評価値として計算させます。これにより、最後まで読まなくても評価の有利・不利により探索することができます。

 この○×ゲームに関しては自分が2つ並んでいて相手に妨害されていない場合は評価値が高いのではないでしょうか?逆に相手がその状態ならば低くなるはずです。途中で自分の勝ちが見つかれば非常に大きな数を評価値として返し、負けの場合は低い数を返せばいいのです。


 次回は実際にMinimaxの探索についてどのような手順で探索するかについて説明します。それ以降、Minimax以外の効率の良い探索方法も紹介していきます。


次回予告:Minimaxアルゴリズムを使って探索する



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

クリックしたら投票されるみたいなので、明るい一票をお願いします(m。_。)m
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。