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

スポンサーサイト

 初めまして.ちょっと突っ込みたかったので失礼します.
 まず,MinMax(NegaMax)も枝刈り出来ます.元の論文を読めば分かりますが,MinMaxの改良版としてαβ法が書かれています.そして,あまり改良されなかったとも書かれています.
 何でかと言えば,逐次探索になってしまうので結果を見ればこれ以降は不要と言うことが分かっても可能性がある限り実行するためではないかと思います.この点を改良しない限り無駄だろうと.
 もちろん,そこで並び替えも示唆されているわけですが,同じ深さの探索を行わなければ必ず正しくソートできないとされています.論理的に,等しいことが証明できないためです.
 これは,一般的に等しいことが証明できないと言う意味で,ある限定条件かでは等しいことが証明できる場合はこの手法を用いられるようです.

 個人的に,探索の高速化を考えるよりオセロならおける石の位置を探索するアルゴリズムを高速化した方が体感速度は確実に上がると思われます.
 もしくは,自分が打った手に対して相手が撃てる場所が多くなる手を先に探索するのも手だと思います.

 結論として,速度優先なら少しでも軽くすると言う意味で判定数が少ない枝刈りネガマックス法を試してみるのも一つの手ではないかと.(多分このワードで検索しても目的のものは出てこない)
http://algolist.manual.ru/games/alphabeta.php
 アルゴリズムの部分だけなら,何とか読めるので参考までに.

  • 2006年07月24日月
  • URL
  • れおぽるど #TmGpY.Bs
  • 編集

(/≧◇≦\)アチャー!!
突っ込みきたよ(;´Д`)

始めまして☆コメントありがとうございます。
まず、ソートの事ですが、「評価が高くなると思われる」と強調して書いているように、正しくなくてイイんです。ショボい探索でソートして、ある程度、良いノードから探索することにより、確実に評価の低いノードを後から探索することにより枝刈りしてしまおう!!っていう感じなので(´・ω・`;)

次に単純に高速化するならば、おっしゃられているような、
>石の位置を探索するアルゴリズムを高速化
を高速化するのが優先だと思います。
ってmobility tableを使った探索法っすか??コレならば以前に説明したんですけど・・・。まぁ俺の勘違いの可能性っていうか、今までの経験上そっちの方が多いから(┳◇┳)
しかし、やはり強くなくてはAIを作る意味がないと思うんです。←コレは基本ですね(汗 だから、単純に探索でより深く読めるように(アルゴリズムの)工夫をしてAIをより強くしようという考えで進めていっています。←自分勝手ですが・・ まぁそのうち探索アルゴリズムでの限界に達すると誰でも行き着く先が、基本を改良しての高速化でしょう!!(コレが何よりも効果かるんだけど・・)でも、やっぱり最初からオセロ等のAIを作ろうって人は最初は基本アルゴリズム激遅でも、探索アルゴリズムの工夫を重ねると思うんです。実際に自分が辿った道だからなんですけどね(´・ω・`;)
ちなみに、今回の擬似コードは枝刈りネガマックスのつもりで作ったんですけど・・・(>ω<;)僕の中ではネガマックスは基本として考えているので、αβアルゴリズムとして表現しているので、その点で誤解なされたのでしょうか?イヤ俺の勘違いか・・・?まぁ何か間違っているようであれば、ご指摘よろしくお願いします。

これかからも、コメントよろしくお願いします。

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

 「ある程度」の部分なんですよ,問題にしたいのは. ソートの処理によって短縮される処理とソートを天秤にかけたときちゃんと高速化の方に傾いてくれるのかが疑問なんです.むしろ,遅くなるんじゃないかと思ってしまうんです.
 
 一応確認しておきますが,探索って上からしてますよね?

 参考URLで私が指したいのはこの部分です.
integer procedure F1(position p, integer bound):
begin integer m,i,t,d;
ホ�裝褄頸��鉅��p1,...,pd, �蔔竟褊�p;
if d = 0 then F1 := f(p) else
begin m := -(infinity);
for i:= 1 step 1 until d do
begin
t := -F1(pi, -m);
if t > m then m := t;
if m >= bound then goto done;
end;
done: F1 := m;
end;
end.

で,私が想像しているαβ探索ってのはこれです.
integer procedure F2(position p, integer alpha, integer beta):
begin integer m,i,t,d;
ホ�裝褄頸��鉅��p1,...,pd, �蔔竟褊�p;
if d = 0 then F2 := f(p) else
begin m := alpha;
for i:= 1 step 1 until d do
begin t := -F2(pi, -beta, -m);
if t > m then m := t;
if m >= beta then goto done;
end;
done: F2 := m;
end;
end.

 と言うわけで,基本的な私の突っ込みは「αβ法じゃないヤン!」なので.ここを初めて見た人は気づけないのではないかと.

 しかし,これは何語で書かれているのだろう?

>石の位置を探索するアルゴリズム
 ちょっと言葉が足りませんでした.ようは,「打てる手がある」かを調べる部分です.こっちは,ぱっと思いつく方法は虱潰しにするしかないので,かなり足を引っ張るからです.

 あと,擬似コードできになったのはbeは一度も更新されませんが,beの存在意義がいまいち分かりません.
 それと,初期値を書かないと処理の流れは分かっても,動作まで分かりません.

 個人的にAIの強さは評価値にかかってくる(もちろん,深く探索することも大事ですが)次回を期待しています.

  • 2006年07月24日月
  • URL
  • れおぽるど #-
  • 編集

えっと・・・なんか難しくてついていけないんですが、まぁ探索は「上?」かな。どう想像されているか分かりませんが、深さ優先探索をしています。ソートの事については、根に近いところでは、明らかに効果があります。探索前に浅い探索を行ってソートを行っているものは、ほとんどのAI(僕の知っている限りのオセロAI全て)で実装されています。実際に僕もこの手法で探索時間を半分以下にすることができました。

>AIの強さは評価値にかかってくる
ソレはカナリ重要なことですよね☆というか常識だよね!!いくら深く読んでも評価値がクソだったら意味ないしな(>ω<;)まぁソレを次回語らせていただきます☆

あと、
>擬似コードできになったのはbeは一度も更新されませんが
と、ありますが再帰呼出でのalとbeに注目してもらったら分かりますが、逆転しています。見えましたか?ソレを分かっていただければbeの意味が見えてくると思います。

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

>beの意味
 これは,投稿してから思い出しました.
まぁ,どっちみちパラメータの説明がない気が・・・初めてここを見た人には何のことやらですよ.前回の記事でも触れられていませんし.どんな意味のあるパラメータかぐらいは説明した方がいいと思います.
 あと,与え方が重要なのですから初期値をどう設定するかも.


 私が引っかかったのは,「浅い探索」って言葉です.
 私が探索からイメージしたのは探索法と同じ過程で探索することナノで「遅くなりそう」と思ったわけです.もっと言えば,その方法では正しいネガマックス値は得られないので評価としてもやや怪しいのではないかと思ったわけです.
 私的には,前回の探索結果(αβ探索)をどっかに保持していてそれを元にすれば良いんじゃないかと考えていたので.こっちはキューを用いれば簡単に実装できるので.(deqを工夫すれば)
 でも,よくよく考えれば詳細について何も語られていないわけで勝手にこっちが妄想しただけですねw

  • 2006年07月24日月
  • URL
  • れおぽるど #-
  • 編集

あぁパラメータ説明はチョットないと痛いですね(;´Д`)
時間のあるときに修正および今後気をつけます☆ご指摘ありがとうございました(_ _(-ω-;(_ _(-ω-; ペコペコ
まぁ「浅い探索」については人それぞれで、別に浅い探索用に関数を作ってる人もいれば、自分自身の関数を利用している人もいます。浅いといっても、0手読みであったり、モノによってはもっと深く読んでいるモノもあるので人それぞれですが(´・ω・`;)

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

コメントの投稿

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

トラックバック

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