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

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

スポンサーサイト

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

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

 就職活動も無事終わったし久しぶりに書くかって感じで(゚ー゚;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つのランキングに参加しています↓

スポンサーサイト

お久しぶりですっ!

まずは就職活動終了&再開おめでとうございます。
αβって普通の解説を読むと難しそうですけど、図と擬似コードがあると分かりやすいですよね。
次回ですけど、詰め将棋関連でAND-OR木の探索、その次でdf-pnってのはどうでしょう?
いえ、単に自分が読みたいだけなんですけど (汗

お久しぶりっす

ひえ~~
まだ将棋の方は全然進めてないので・・・
もうチョット勉強してから少しずつ書いていきたいと思います(;´Д`)
でも、読みたいと言っていただける方が一人でもおられるとヤル気が出るものですね~☆☆

  • 2006年07月19日水
  • URL
  • 羊 #AN1TInro
  • 編集

承認待ちコメント

このコメントは管理者の承認待ちです

  • 2015年07月07日火
  • #
  • 編集

コメントの投稿

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

トラックバック

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