daruma3940の日記

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

備忘録

http://www2.computer-shogi.org/wcsc27/appeal/Apery/appeal_wcsc27.html
なんで強いソフト深い探索の評価値に今の局面の評価値を近づける学習方法使う時に静止探索の末端局面の特徴に対して更新しているのか?


静的な局面でないとあまり正確な局面評価ができない
つまり今の評価関数は静止探索をする前提である
今の評価関数では静止探索を表現できない?(手番があればある程度はできるような気がするのだけれど。しかしまあ最新の強いソフトがまだ静止探索をしてるってことはまあそういうことか。DNNほどの特徴があれば静止探索も表現できるだろうが静止探索するより遅いので論外)
静止探索を前提としているということはつまり今の評価関数には静止探索も含まれているということ?


Stockfish探索では静止探索はleaf nodeでしか呼び出されない。すべてのゲーム木内のノードで静止探索が呼び出されるわけではない。つまりleaf以外では完全な評価はできていないので前向き枝切りの精度が悪い?

この点ソースコードを見直してみると多くの前向き枝切りで静止探索をした点数を用いていたため大丈夫そう。
唯一使ってなかったのがfutility prunning。
これも静止探索した方がいいと思うがそれだとrazoringとかぶるよなとも思う。
この辺よくわからん

そして静止探索の末端局面の評価値を深い探索の値に近づけている都合上、ノードの評価値が深い探索の値に近づいているかといわれると直接的に近づいているわけではない
(しかし反復進化の考えによると一度はleaf nodeであったことがあるはずで静止探索の値がTTに格納されているはずなのでそこまで気にする必要はないのか?しかしnullwindowsearchとか枝切りとかが起こると読まれないし...)

RootStrapで静止探索をせずにRootの局面に対して値を更新する?
通常探索用の評価関数(手番付き)(rootにそのまま深い探索の値を近づける)と静止探索用の評価関数を用意する?(取り合いを読ませた後なら手番がなくても表現できるはず)(しかし取り合いがいつ終わるのかということはStandPatなどの影響で簡単にはわからない この辺がネック)

TreeStrapについて調べてみたのじぇ

f:id:daruma3940:20160520223745p:plain
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やってるソフトなんて聞いたことないな!鉱脈を見つけてしまったかも!!!!」と思って詳しく知りたくなったからなのじぇ!
f:id:daruma3940:20160520223745p:plain

http://www0.cs.ucl.ac.uk/staff/d.silver/web/Applications_files/bootstrapping.pdf
論文を見つけたので読んでみたのじぇ
f:id:daruma3940:20160520223745p:plain

RootStrapはRootNodeの評価値を深い探索の結果の値に近づけるのに対してどうやらTreeStrapは探索木のノード全体を深い探索の値に近づける方法で、
αβ探索を用いる場合は探索木の多くのノードで正確な値を計算できないので代わりにそのノードにおけるalpha,beta値を利用して値を更新するということをするようだったのじぇ
ノードの評価値がαよりも小さければ評価値をαに近づけ、βよりも大きい場合は評価値をβに近づけるらしいのじぇ
確かにalpha,beta値は探索の結果出てくるものなので、正確な値がわからなければこれを用いるのはなるほどなと思ったのじぇ
f:id:daruma3940:20160520223745p:plain
しかし,探索した時の深さが8だったとするとrootnodeはdepth8の時の情報を利用できるが、ゲーム木の内部ではそれより浅いdepthにおける情報を利用するしかないのであまりよくないかとも思うのじぇ
まあこれはdepthがあまりに浅いと値を更新するのに使うのを制限するということをすれば大丈夫だと思ったし、探索に出てくる局面に対して値を更新できるので多くの局面を学習できるのでメリットがあるのではないかと思うのじぇ
f:id:daruma3940:20160520223745p:plain
しかし
論文の7ページ目の図を見ると図のnumber of training gamesが全然足りないことに気が付いたのじぇ。一万ゲームしかないのじぇ...
そしてもう少しiterationを増やせばrootstrapがtreestrapのELOを追い越しそうだったのじぇ
f:id:daruma3940:20160520223745p:plain
この辺で第四回電王トーナメントの時のことを思い出した。そういえばこのグラフ見たことがある....
そうだ...出村さんがやねさんと話していた時に出していた論文じゃん....そしてその時も「TreeStrapは胡散臭いよね~」「TreeStrapよくないかも」みたいな会話になっていた。
tree strapは鉱脈ではなかったようなのじぇ....

f:id:daruma3940:20160520223745p:plain
「探索に出てくる多くの局面に対して値を更新できるので多くの局面を学習できるメリット」についてもこのnodchipさんの一連のツイートを見ると



RootStrapでも結構多くの特徴が出てくるのでゲーム木内部で浅い探索結果を利用してまで学習局面を増やす方法にメリットがなさそうということに気づいたのじぇ
f:id:daruma3940:20160520223745p:plain
そして何よりRoot Strapは教師データ生成と学習を別にできるので同じ教師データを用いて学習の条件調整が簡単にできるという大きなメリットがあるのじぇ
f:id:daruma3940:20160520223745p:plain
まあ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に格納するとキャッシュにのりやすいかといった高速化もしていたが、私にはそこまでできない。
局面の評価は一般的な3駒関係でなく2駒関係を用いることにした。これは2コマの方が3コマよりも強いと思ったからとかそういうわけではなくて単純に2駒のほうがサイズが小さくて取り扱いやすいこと、学習に時間があまりかからないことというLazyな理由からであった。学習にはbonanza methodを使うことにした。
符号の間違いが多くてちゃんと学習させるのにはかなり手間取った。
しかし学習させた自分のソフトが自力で穴熊に組んだ時はかなりうれしかった。
探索部はチェスの最強ソフトであるStockfishの探索部を将棋用に改良してそれを取り入れた。取り入れるだけであるがなんだかんだバグが出てきて取り除くのは大変だった
今回はどれぐらい強くなるか弱くなってしまってもしょうがないなと思ったがbonanza6に勝てるぐらいのソフトになった。正直感無量だった。あのbonanza6を超えることができるとは...
なんか書くの疲れてきたので大会は楽しかったでおわりにする

大会1日目の飲み会代払うの忘れてたのじぇ!

f:id:daruma3940:20160520223745p:plain

しまったのじぇ!!

大会一日目の飲み会代払うの忘れてたのじぇ!

f:id:daruma3940:20160520223745p:plain

あの日朝2時寝の4時起きで飲み会の途中でうとうとしてしまって、飲み会を途中で抜けたので翌日お金を渡すことになっていたのじぇ

 

f:id:daruma3940:20160520223745p:plain

Claireさんに冗談でここで黙ってれば払わなくて済むんじゃないww??

みたいなことを言ったけどまさかホントに払うの忘れてしまうとは....

f:id:daruma3940:20160520223745p:plain

非常に申し訳ないので次の大会の飲み会は余分に請求していただいて大丈夫です

f:id:daruma3940:20160520223745p:plain
きふわらべさんが飛び利きbitboardを作るのに苦労されているのを見て昔の自分を思い出したのじぇ。
occupied bitboard作るのもいい方法が思いつかなくて大変だったし、
飛び利きの邪魔ゴマのindexを取ってくるのも位置がずれてたりして修正するのが大変だったのじぇ...
懐かしんでいる場合ではないけれど懐かしいのじぇ...

f:id:daruma3940:20160520223745p:plain
ようやく5000万棋譜でR+25のバイナリができたのじぇ...
条件としては定跡を開始局面として教師データを作成し、値の更新時に探索はしない目的関数は交差エントロピー値の更新方法はadadeltaなのじぇ
この方法と同じ方法で教師データをもっと作って学習を回せばもっと強くなるはず!!!
イタチの最後っ屁ではあるものの強くなってほしいのじぇ!!!

中規模棋譜学習うまくいかんのじぇ...


f:id:daruma3940:20160520223745p:plain
う~~んう~~ん
中規模棋譜学習うまくいかんのじぇ...

一応損失はiteration回すたびに小さくなってるし
ゼロベクトルから始めた学習がゼロベクトルのものよりは強くなってるので
アルゴリズムがおかしいわけではないと思うのだけれど...

次元下げをすると多少勝率がましになるけど、それでも元のものよりはR100は低い...
f:id:daruma3940:20160520223745p:plain
う~~んう~~ん

ランダム開始局面データがマズすぎるのかもしれないので
開始局面は定跡から読み込ませることにするかなのじぇ....
でもこれが強くならない本質的な原因だとは思えないんだよなぁ...

評価値の符号は間違ってないはずだし...