読者です 読者をやめる 読者になる 読者になる

daruma3940の日記

理解や文章に間違い等あればどんなことでもご指摘お願いします

探索の手法についてなのじぇ

f:id:daruma3940:20160520223745p:plain

探索の手法について解説していくのじぇ
f:id:daruma3940:20160520223745p:plain   
探索は時間が豊富にあるならすべての差し手に関して探索をし、どの差し手が一番いいのかを決定してやるのが一番正確な方法なのじぇ

しかし普通に考えてそんなに莫大な時間を探索に割くことはできないのじぇ

そこでこんな手なんかは探索しなくてもいいよね!って手は探索を打ち切ってしまって探索のスピードを向上させる手法がApery等の将棋ソフトには組み込まれているのじぇ
f:id:daruma3940:20160520223745p:plain
またこんな手なんかは探索しなくていいよねって思って探索を打ち切った手でも
もうちょっと探索をしてみるとそこにはとってもいい手が隠れているかもしれないのじぇ
探索の打ち切りとは早くなる代わりにその危険と隣り合わせなのじぇ
その危険を減少させる手法も探索の手法には含まれているのじぇ

ここではApery-twig-std3(通称 大樹の枝)の探索部の探索の手法について簡単に概略だけを抑えておくのじぇ
f:id:daruma3940:20160520223745p:plain
間違ってるかもしれないのでここの内容はまあ話半分に見ておくのじぇ。

その手法を行う詳しい条件などを見たければ前の記事を見てほしいのじぇ。 ちなみにbeta値というのは探索の評価値が超えてしまってはいけない値で上界とよばれるものなのじぇ。

f:id:daruma3940:20160520223745p:plain

ここで方法ごとに番号が振られているけど番号はaperyの番号の振り方に合わせているのじぇ。

3 mate distance prunning

探索の上界の方が自分が現在詰まされてしまっている評価値以下
または探索の下界が相手を現在積ませている評価値以上であれば
このような評価値の値はありえないのでここで枝切りしてしまう

6 razoring

razorとはカミソリ
芝刈り機で下に生えてる芝を刈り取っていくイメージ
beta値をmargin分だけ小さくした新しいbeta値でnullwindow幅searchをおこない
それでも新しいbeta値を超えられない場合はこいつは見込みがない局面であるのでこの局面の探索を中止する。

margin:       512+16*depth  

7 static null move prunning

現在の評価値がbeta値+marginよりも大きくなってしまっている(つまりbeta値を大きく超えてしまっている)場合
これ以上探索を深くしてもbeta値を下回ることはないと考えられるのでここで枝切りをしてしまってもよい。

margin:    112*log((depth)^2/2)/log(2)+1.001-8*movecount+45  

8 null move prunning

現在の探索の結果beta値を超えてしまっている値が返ってきた
しかしもしかするとここに良い手が隠れてしまっているかもしれない
そこでこの手番をパスするという悪い手を指してしまったとしてもまだbeta値を超えてしまっているならば
たぶんここには良い手が隠れていないだろうということで探索を中止してしまうしてしまう

9 probcut

非常に良い手が現局面で存在するとして
その差し手で浅い探索を行ってみて、その探索で帰ってきた評価値が
beta値を200点も上回るような値であればbeta値をはるかに超えていて
探索を深くしてもbeta以下にはならないと考えられるので
ここで枝切りできる

12 singuler extension

王手や駒の取り合いの局面または
局面の差し手の中でいい手が一つしかないような場合は
探索を深さを拡張して深くまで読みようにする

13 futility pruning

futilityとは無益という意味
考えても無益な差し手を飛ばしてしまうイメージ

これには現在探索中の指し手が何番目の指し手を考慮する方法と現在の評価値を考慮する方法の2種類ある

13 A movecount based pruning

その局面における差し手は一番可能性があると思われる差し手から渡される
ということは最後の最後の方に渡される差し手で相手の駒に当たらない指し手は可能性に乏しい指し手であると考えられる
このような手は読むのを飛ばしてしまう(?本当にそうか?)

↓この値以上の指し手の番目であれば読むのを飛ばしてしまう

FutilityMoveCounts[d] = static_cast<int>(3.001 + 0.3 * pow(static_cast<double>(d), 1.8));  

TODO:↑この値はかなり論理的に決められているので裏にはなにか理論があるのかもしれない...

13B score based pruning

現在の差し手の評価値にmarginを足した値がbeta値を下回る
つまりbeta値よりもかなり小さい指し手が現れればそのような手を考えるのはパスする。
(betaを下回ればその指し手を飛ばす?? それはおかしいような...
でもあんまりbeta値よりも小さくても駄目というのもわかるような...)

15 lazy move reducation

その局面における差し手は一番可能性があると思われる差し手から渡される
後の方の差し手はあんまりよい指し手である可能性が高くないのでこの指し手で浅いnullmove探索をしてみて
その結果が良くない値であればnullwindowsearchにする。