TreeStrapについて調べてみたのじぇ
https://chessprogramming.wikispaces.com/Meep
きっかけはここのページに
Algorithm Elo
Untrained 250 ± 63
TD-Leaf 1068 ± 36
RootStrap(αβ) 1362 ± 59
TreeStrap(mm) 1807 ± 32
TreeStrap(αβ) 2157 ± 31
と書かれていたので、「Tree StrapはRootStrapより強くなるのか!?そういえばtree strapやってるソフトなんて聞いたことないな!鉱脈を見つけてしまったかも!!!!」と思って詳しく知りたくなったからなのじぇ!
http://www0.cs.ucl.ac.uk/staff/d.silver/web/Applications_files/bootstrapping.pdf
論文を見つけたので読んでみたのじぇ
RootStrapはRootNodeの評価値を深い探索の結果の値に近づけるのに対してどうやらTreeStrapは探索木のノード全体を深い探索の値に近づける方法で、
αβ探索を用いる場合は探索木の多くのノードで正確な値を計算できないので代わりにそのノードにおけるalpha,beta値を利用して値を更新するということをするようだったのじぇ
ノードの評価値がαよりも小さければ評価値をαに近づけ、βよりも大きい場合は評価値をβに近づけるらしいのじぇ
確かにalpha,beta値は探索の結果出てくるものなので、正確な値がわからなければこれを用いるのはなるほどなと思ったのじぇ
しかし,探索した時の深さが8だったとするとrootnodeはdepth8の時の情報を利用できるが、ゲーム木の内部ではそれより浅いdepthにおける情報を利用するしかないのであまりよくないかとも思うのじぇ
まあこれはdepthがあまりに浅いと値を更新するのに使うのを制限するということをすれば大丈夫だと思ったし、探索に出てくる局面に対して値を更新できるので多くの局面を学習できるのでメリットがあるのではないかと思うのじぇ
しかし
論文の7ページ目の図を見ると図のnumber of training gamesが全然足りないことに気が付いたのじぇ。一万ゲームしかないのじぇ...
そしてもう少しiterationを増やせばrootstrapがtreestrapのELOを追い越しそうだったのじぇ
この辺で第四回電王トーナメントの時のことを思い出した。そういえばこのグラフ見たことがある....
そうだ...出村さんがやねさんと話していた時に出していた論文じゃん....そしてその時も「TreeStrapは胡散臭いよね~」「TreeStrapよくないかも」みたいな会話になっていた。
tree strapは鉱脈ではなかったようなのじぇ....
「探索に出てくる多くの局面に対して値を更新できるので多くの局面を学習できるメリット」についてもこのnodchipさんの一連のツイートを見ると
iは最大50億程度となります。開発者や学習条件によって最大1億~80億程度とばらつきがあります。特徴量因子は棋譜の生成条件や局面数によって異なりますが、過去に調べた結果こんな感じになりました。 pic.twitter.com/Q3FaxOquXf
— nodchip@tanuki- (@nodchip) 2017年5月26日
自己対戦ベース1…2駒の入れ替えあり・探索深さ3・評価値の絶対値の上限なし
— nodchip@tanuki- (@nodchip) 2017年5月26日
自己対戦ベース2…2駒の入れ替えなし・探索深さ3~4からランダムに選択・評価値の絶対値の上限2000
自己対戦ベース3…2駒の入れ替えあり・探索深さ3・評価値の絶対値の上限2000
RootStrapでも結構多くの特徴が出てくるのでゲーム木内部で浅い探索結果を利用してまで学習局面を増やす方法にメリットがなさそうということに気づいたのじぇ
そして何よりRoot Strapは教師データ生成と学習を別にできるので同じ教師データを用いて学習の条件調整が簡単にできるという大きなメリットがあるのじぇ
まあtree strapはお蔵入りになったが、この考え方はどこかで使えるかもしれない。
知識として引き出しの中にしまっておくことにしようじぇ?