daruma3940の日記

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

Probcutについてなのじぇ2

f:id:daruma3940:20160520223745p:plain
https://chessprogramming.wikispaces.com/ProbCut#cite_note-8
の翻訳なのじぇ。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ProbCutは探索手法の一つである。
ProbCutとその進化形であるMalti-Probcutはオセロや将棋で効果的であると証明されている。
(将棋はKazutomo Shibahara, Nobuo Inui, Yoshiyuki Kotani (2002). Effect of ProbCut in Shogi - by changing parameters according to position category. 7th Game Programming Workshop)
チェスソフトCraftyを用いた幾つかレポートの結果にもかかわらず,すでにNullmove,LMRを実装しているチェスソフトではあまり成功していないように思われたが、 Gary Linscottの実装によるStockfishによって初めてそうではないことを証明した。
http://www.talkchess.com/forum/viewtopic.php?p=518426


The idea

浅い探索の結果である評価値はより深い探索の評価値の荒っぽい見積もりであるとするアイディアにProbcutは基づいている。

浅い探索の結果である評価値をv'
深い探索の結果である評価値をv
とすると

これらの関係性は線形モデルを用いてモデル化される。

v=a*v'+b+e


ここでeは正規分布の標準誤差で平均値0標準偏差がσ、分散がσ**2である。
もし評価関数がきちんとしたものであれば、勾配aは1.0であり、定数項bはほぼ0で、分散も非常に小さくなる。

v>β
であればbeta-cutしてもよいので
(a*v'+b+e)>β

よって
(a*v'+b-β)/σ>-e/σ
ここでa=1とした。

  • e/σは通常、平均が0の正規分布で、分散が1である。

分布関数をΦとすると、
この条件は(v'+b-β)/σがp以上である確率と同値であると言える。
よって(v'+b-β)/σ>Φ^-1(p)となる。
(Φ^-1(p)はΦ(p)の逆関数であると思われる)
{なんでΦの逆関数を使う?よくわからん}
(誰かここおしえてください)

よって
beta-cutの条件式は
v'>{Φ^-1(p)*σ+β-b/a}
となる。



ProbCut

σ以前にa,bは線形回帰によって見積もられる。これらは局面の段階によって異なる可能性がある。
探索深さやしきい値は経験的に決められるに違いない。


Multi–ProbCut
これはProb cutを以下の方法で強化したものである。

異なるパラメーターとしきい値を用いることを許す
探索深さのペアを一つ以上使う
内部反復深化を浅い探索に使う


ProbeCut or MPC in Chess

2003年の議論

これまで以下の2つの理由でProbeCut or MPCの成功例の報告はなかった
1 nullmoveも同じようなアイディアに基づいている。
2 チェスの探索はオセロの探索に比べて間違いが多い。このことは浅い探索と深い探索の結果に大きな逸脱をもたらし、そしてそれはprobcutが怒るのを難しくする。


Robert Allgeuerのテストの結果
ProbCutが有効に働く相手がいればその逆の相手もいる。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

f:id:daruma3940:20160520223745p:plain
......
f:id:daruma3940:20160521003616p:plain
.......
f:id:daruma3940:20160709192554j:plain
........よくわかんないね...

f:id:daruma3940:20160520223745p:plain
ちょっと理論のところはよくわからないのじぇ
標準誤差やら標準分散やら標準分布やら似た言葉がいっぱいあって頭がこんがらがりそうだったのじぇ。
確率統計は授業で習ったけれどもう忘れてしまったのじぇ。

正規分布に従った誤差と言うのはよく出てくるやつなので理解できるのじぇ。
しかし分布関数の逆関数みたいなのを使うpが出てきたところらへんからわからないのじぇ。
f:id:daruma3940:20160520223745p:plain
と言うかprobcutあんまりいいこと書いてないのじぇ
nullmoveで十分なのかだじぇ???

f:id:daruma3940:20160520223745p:plain
まあForum Postsのところにあるチェスのフォーラムも見ながら
勉強していこうじぇ(^ω^)