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はお蔵入りになったが、この考え方はどこかで使えるかもしれない。
知識として引き出しの中にしまっておくことにしようじぇ？
第27回世界コンピューター将棋選手権に参加してきた。
第27回世界コンピューター将棋選手権に参加してきた。
今回はライブラリを使わずに参加しようということで前回の第4回電王トーナメントが終わった後動物将棋のエンジンを作り感覚を取り戻してから一から本将棋のプログラムを作り直した。
大会でshogi686さんからrotated bitboardはpext bitboardより高速に処理ができると教わったのでrotated bitboardを採用することにした。rotated bitboardの実装は結構大変でバグを取ったりするうちに丸一日経っていた。
bitboardには81bit必要で、飛び効きを処理するためにはこれに加えて+45,-45,90°回転(rotated)させたbitboardも必要なのだけれど,効きを遮る駒が盤の一番端っこにいる場合は一番端っこに駒がいないのと同じだけ盤上に効きを作ることができるので飛び効きの処理に必要なbitboardは81bitではなく縦横で7*9=63bit斜めで7*7=49bitあればいい。
これらは64bitに収まるので縦横斜めすべてを256bit型に格納してSIMD演算で一気に計算できると教わった。
shogi686は斜めのテーブルをどのbitに格納するとキャッシュにのりやすいかといった高速化もしていたが、私にはそこまでできない。
局面の評価は一般的な３駒関係でなく2駒関係を用いることにした。これは2コマの方が3コマよりも強いと思ったからとかそういうわけではなくて単純に2駒のほうがサイズが小さくて取り扱いやすいこと、学習に時間があまりかからないことというLazyな理由からであった。学習にはbonanza methodを使うことにした。
符号の間違いが多くてちゃんと学習させるのにはかなり手間取った。
しかし学習させた自分のソフトが自力で穴熊に組んだ時はかなりうれしかった。
探索部はチェスの最強ソフトであるStockfishの探索部を将棋用に改良してそれを取り入れた。取り入れるだけであるがなんだかんだバグが出てきて取り除くのは大変だった
今回はどれぐらい強くなるか弱くなってしまってもしょうがないなと思ったがbonanza6に勝てるぐらいのソフトになった。正直感無量だった。あのbonanza6を超えることができるとは...
なんか書くの疲れてきたので大会は楽しかったでおわりにする
大会1日目の飲み会代払うの忘れてたのじぇ！
しまったのじぇ！！
大会一日目の飲み会代払うの忘れてたのじぇ！
あの日朝2時寝の4時起きで飲み会の途中でうとうとしてしまって、飲み会を途中で抜けたので翌日お金を渡すことになっていたのじぇ
Claireさんに冗談でここで黙ってれば払わなくて済むんじゃないｗｗ？？
みたいなことを言ったけどまさかホントに払うの忘れてしまうとは....
非常に申し訳ないので次の大会の飲み会は余分に請求していただいて大丈夫です
■
きふわらべさんが飛び利きbitboardを作るのに苦労されているのを見て昔の自分を思い出したのじぇ。
occupied bitboard作るのもいい方法が思いつかなくて大変だったし、
飛び利きの邪魔ゴマのindexを取ってくるのも位置がずれてたりして修正するのが大変だったのじぇ...
懐かしんでいる場合ではないけれど懐かしいのじぇ...
Bonanza6たおしたのじぇ！
twitterで書くのははばかられる内容なのでここにかくのじぇ
どうしたのまりちゃ？
Squirrel君がついにBonaza6を倒したのじぇ！（1thread 1s）
おめでとうだよ！
いろいろな出来事が走馬灯のように思い出されるのじぇ...
開発をするためにクラスとポインタで挫折していたC++を勉強し直したあの頃...
池さんの「HTML版コンピュータ将棋のアルゴリズム」を読んで将棋プログラムの作り方を勉強したあの頃...
れさ改に勝てずに、もがき苦しんだあの頃..
Bonanza完全解析ブログで３駒関係について勉強したあの頃...
フラッドゲートで稲庭将棋に2回引き分けを繰り返してようやく勝ち星をつけレーティング表に乗ったあの頃...
徹夜でrotated bitboardを作成したあの頃...
学習の実装を失敗し続けて全然評価関数が強くならなかったあの頃...
なのはミニに勝ったあの頃...
bonanzaに追いついたあの頃...
そしてbonanzaに勝った今...
感無量だねっ...
