daruma3940の日記

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

電王トーナメントにおける棋譜の公開なのじぇ!

f:id:daruma3940:20160520223745p:plain
電王トーナメントの棋譜をこうっかいするのじぇ!
f:id:daruma3940:20160520223530p:plain
こんなもの公開して誰得なの??

f:id:daruma3940:20160709192554j:plain
まあ僕が頑張った思い出の記録として公開したいんだよ~~
f:id:daruma3940:20160521003616p:plain
Squirrel君得みたいね..

www.dropbox.com


~~追記~~
f:id:daruma3940:20160521003616p:plain
調べてみたら電王トーナメントの公式サイトでも棋譜が公開されていたわよ。
ここでも棋譜を公開したって何の意味もないんじゃない?
f:id:daruma3940:20160520223745p:plain
そんなこともないのじぇ。
公式ではテスト対局の棋譜は公開していなかったけれどここではちゃ~んと公開しているのじぇ。
テスト対局の相手はponanzaなのじぇ。ponanzaファンは喉から手が出るほど欲しがるんじゃないかだじぇ?
f:id:daruma3940:20160521003616p:plain
それは確かにそうでしょうけれどponanzaの相手がSquirrelじゃあねぇ....
f:id:daruma3940:20160520223745p:plain
それは言っちゃ駄目なのじぇ。

電王トーナメントで得られた知見についてなのじぇ!

電王トーナメントで得られた知見についてそろそろまとめておこうじぇ!


~~事前準備日
ハクビシンさんからの情報

技巧は今回
tree strapとalpha goの技術を用いているのではないか

tree strap...深い探索を行ったすべての局面の末端ノードの値を近似する。

一日目にもう一度お話を伺ったところ、実際はtree strapは行っておらず、
alpha goの方法はポリシーネットワークを用いているらしい。
tree strapに関しては昨日のやねうらさんと技巧さんの会話の中でやねさんが難色を呈していた。

syogi serverを用いれば自己対局が上手くいくのではないか

ハクビシンさんのソフトでは評価関数をメモリから読みとるのが全体の計算時間の30%を占めているのでそこを高速化したいそう。
そこでハクビシンさんは上手く評価関数がキャッシュに乗るようにpaddingを入れている。
キャッシュはマシンごとに違うのでこの電王トーナメントのマシン用に事前準備の日にチューニングされていた。


1日目
やねうら王さん
詰みを見つけやすい評価関数であればcheckのextensionはいらない。
今後はどの特徴量を追加していくか

どの手を重点的に読むかにdeep learning?

ponanzaは持ち時間にNNを使っている?

ツツカナ
持ち駒だけで進行度を図っている。
実現確率探索はreducationだけそこで考えて、extensionは他の項目で考えている。
null moveの代わりにmulti cutを使っている。(selene も)
→その局面でテキトウな指し手を一手指してみてそれが何個beta値を超えるかどうかで枝切り。
null moveを超える指し手がこの中にあればmulti cutのほうが精度が良くなる?

カパック
教師データの精度を上げている。
反省した局面は教師データに入れていない?

ラプンツェル
Sibling conspiracy number searchを用いている。
他のゲームでは上手く行ったらしいが、
将棋では上手く行かなかったらしいので
静止探索は行ったらしい。

selene
ABC探索の考えを取り入れた枝切りを行っている。
→複雑な局面には行きたくないという考え方?

技巧とやねさん
技巧 futility marginを120+80*progressで強くなった??

razoring パラメーターがバラバラ。深いほうが大きくないとおかしい。これは本当に必要なのか?
技巧ではrazoring入れてELO+10ぐらい。
razoringは割りと安全な枝切り?(このあたり周りがうるさくてよく聞こえなかった)
外してもそんなに強さ変わらない

静止探索は軽くならないか?
飛車角成を省く?
歩のcaptureよりも価値のある成を入れる?
技巧 歩以外の成を枝切りでELO-13

終盤の歩のcaptureなんて要らない

成を探索しなければいけないような評価関数か?

大抵はfutilityによって枝をかられる。

seeは利きを持っていれば相手の効きがそこにあるかどうかで省略できる。
王手のseeはききのかずさえあれば省略できる?

王手延長
技巧 SEEが+でONE_PLY
SEEが-でHALF_PLY
王手延長は王手をかけた後の局面の指し手の少なさから考えて積極的に延長スべし

教師データ作成のときは枝切りなしのdepth3で作成したほうがいいか?
枝切りありのdepth6ぐらいが普通のdepth3ぐらい?

boot strapの論文はデータが胡散臭い
Tree strapよりもRoot strapのほうが信頼できる?
探索のパラメーター調整はsingler extensitonの関係で他のソフトとやったほうがいい。

マルチスレッドの場合はhistoryの値の入り方がぜんぜん違うのでぜんぜん違う進行になる!
激指の研究ではKPが一番進行度を表現できるらしい。

shogi686さん
PEXT bitboard 飛車の利きを一回で求められるがmargeしないといけない
rotetedはmargeしなくていいところは早いけれども、利きは一回では求められない。
shogi686さんは両方試してみてrotetedのほうが早かった模様。
PEXTテーブルが大きいのでキャッシュに載るか乗らないかでソフトによるところが大きい?
レイテンシがどうこう言われたけれどわからなかった
_blsr_u64()
一手詰め関数はtemplateを使って短くしている。
強くなるときというのは遅くなるもの。
null moveが上手く行かなかった指し手の保存

2日目飲み会
次元下げは値の波及が激しい。
教師データが変わったのがソフトの気風の変化に影響?
Alpha Goも人間の棋譜からのほうが強くなっているところもある!
→人間の棋譜とソフト起伏の違いは?

発想の漏れを見つけなければならない。

ponanzaはKPP KKPTを使っている。(KPPTではない)だからめちゃくちゃ速い。
やねさん KPPTでもいいのでは。KPPTでパラメーターチューニングしなければならず、細かい比較はできていない。
去年の電王トーナメントバージョンに9割勝つ。
直近3ヶ月でパラメーター調整のために600のブランチを作った。

Squirrelについて2!

f:id:daruma3940:20160520223745p:plain
そろそろ開発にもめどが立ってきたのじぇ。
ここらで今のSquirrelの特徴をまとめておくのじぇ。
今日は眠いので詳しくは明日なのじぇ。

Squirrel!!!!
f:id:daruma3940:20160709192554j:plain
基本となっているのはやねうら王ナノ!
探索部の基本設計はstockfish7!

独自性!
f:id:daruma3940:20160520223530p:plain
進行度を絶対PとKEの線形和で評価!
KEのEは王の周りの升に効きがある升が何マスあるかを調べる!
    王の周りに壁がなかった場合→王の周り8マスの計算
    王の周りに壁がありかつ王のいる場所が盤の4隅でなかった場合→盤内の5マス
    王が4隅にいた場合→その周りの3マスのみの計算だけではなく、王の2マス前と王のいる位置に桂馬をおいた場合に効きが発生する場所における相手の利き
進行度の学習はfloodgateでrating 2800以上のソフトの棋譜からadadelta!!
進行度によって王手を延長して探索するか、静止探索で王手も探索するかを決めている!
また指し手のorderingについてもorderingに用いられる点数が格納された局面との進行度の差によってorderingに用いられる点数を補正している!
f:id:daruma3940:20160521003616p:plain
定跡は多腕バンディット問題のucbを用いて作成!ucbそのままでは初手の方の定跡手が少なくなってしまい、数手で定跡が外されるということがあったが、ucbに初手からの手数の逆数に比例する項を加えたことで初手の方の定跡も豊富にした!

3手詰関数、1手詰関数は積んでいない!

評価関数はそのままでいくか、学習に挑戦した結果1手目から56玉を指すような読み筋になってしまった評価関数で出場するか悩み中..
評価関数の学習方法は棋譜の局面で3手探索をした評価値と今の局面での静的評価値をすり合わせるようにパラメーターを動かす方法で実装した!しかし実装方法は滅茶苦茶で、次元下げもしていなければ(KPPのPP対称性だけは考慮した)パラメーターを動かすのは傾きが負の方向にパラメーターを0.01動かすだけ!そりゃ、弱くなりますわ...

f:id:daruma3940:20160520223745p:plain
ざっとこんなもんなのじぇ。
前までは独自性を入れる度に強くなってるか弱くなってるか図ってたけど、焼肉オフ会に行ってからは自分のソフトの独自性がなさすぎることに焦りを感じてもう強さを図らずに独自性をバンバン入れていくことにしたのじぇ
f:id:daruma3940:20160520223745p:plain
ライブラリ勢じゃない人もsquirrelくんの独自性を認めてくれると嬉しいのじぇ

久しぶりなのじぇ

f:id:daruma3940:20160520223745p:plain
はふ~~お久しぶりなのじぇ!
f:id:daruma3940:20160521003616p:plain
ほんとにひさしぶりね..
f:id:daruma3940:20160520223745p:plain
最近記事を書いていなかってけれど
プログラムのバグを取れないので息抜きに記事でも書くのじぇ。
f:id:daruma3940:20160520223530p:plain
ゆゆっ?きょうはSquirrelくんがいないね?
f:id:daruma3940:20160520223745p:plain
Squirrelくんはいま将棋の勉強中なのじぇ~~
大局観(KPP,KKP)を磨くため(機械学習するため)にここ2日ぐらいずっと勉強に励んでもらっているのじぇ~~
f:id:daruma3940:20160520223530p:plain
ひぇ~~大変だよぉ(´・ω・`)
f:id:daruma3940:20160520223745p:plain
でも多分今の学習方法では上手く行かないと思うので学習方法を変えてもう一度やり直してもらうのじぇ!
f:id:daruma3940:20160521003616p:plain
更に大変ね...
ところでまりちゃ、いまはどんなプログラムを書いてるの?
f:id:daruma3940:20160520223745p:plain
いま書いているのはUCBを用いた定跡作成のためのコードなのじぇ!
UCBって言うのの解説はここを見てほしいのじぇ!
d.hatena.ne.jp
ここで紹介されている他椀バンディット問題というのを利用してponanzaは定跡を作っているらしいのでそれをパクらせていただいて、
SquirrelではUCBを用いて定跡を作ろうということなのじぇ!!!
f:id:daruma3940:20160521003616p:plain
なるほど...ポナンザがやっている方法なのならこの方法でSquirrelくんの定跡もいい定跡を指すようになってくれるかもしれないわね!
f:id:daruma3940:20160520223745p:plain
まりちゃが思いついたアルゴリズムとしてはこうなのじぇ。

まず
指し手とUCBとその指し手を指した後のノードの情報が格納された構造体へのポインタを格納するための構造体を作る。

struct ucbMove {
double ucb;
Move move=MOVE_NONE;
Move pondermove = MOVE_NONE;
NodeInfo* next=nullptr;//次のnodeinfoへのポインタ
};

またゲーム木のノードの情報を格納するための構造体を作る。
struct NodeInfo {
vector um;//ひとつの局面に対して最大でも3つまでの定跡手を用意する。
bool is_mattan = false;//これがtrueであれば末端ノードであるのでここから探索を再開する。
NodeInfo* previous=nullptr;//一つ前のnodeのnodeinfoへのポインタ(これがnullptrであるということはrootである)
int this_arm_tried = 0;//これは過去に渡っても更新しなければならない。
string sfen_;
int depth;
NodeInfo() { um.resize(3); }

初期局面から探索を始める。
探索が終われば、探索の結果、指し手の評価値が高かった上位3つの指してを取り出して、
その3つの指し手からucBmoveを作り、NodeInfoのvector umにする。

ここでNodeInfoのumをucbが大きい順にソートする。

um[0]で局面を一手進る。
ここは新しいノードであるので新しいNodeInfoの*previousを一手進める前のNodeinfoの番地情報にして
一手進める前のnodeinfo.um[0].nextを新しいnodeInfoの番地情報にするにする。
そしてもう一度探索をして3つの指してに対してucbを計算。
そして連結リストを遡って指し手のucbを更新していく。

umはucbが大きい順に並んでいるはずであるが、先程のucbの更新で順番が壊れているところがあるはずであるのでそのノードをrootから探していく。
そのノードを見つけたら、umをucbの大きい順に並べ替えてその指し手で局面を一手すすめ、NodeInfoをその局面に合わせる。
その後そのノードは末端ノードではないかもしれないので末端ノードまで移動する。
そして次はそこから同じことを繰り返す。

f:id:daruma3940:20160520223745p:plain
アルゴリズムとしてはこれでいいはずなのじぇ。
細かい実装が出来ないのじぇ~~難しいのじぇ~~

コンピューター将棋開発者オフ会in梅田に行ってきたのじぇ!

f:id:daruma3940:20160520223745p:plain
今日はコンピューター将棋開発者オフ会に行ってきたのじぇ

f:id:daruma3940:20160520223745p:plain
参加者はSquirrelの開発者であるまりちゃとLabyrinthus+#の開発者の香上さんとCGPの開発者のwainさんだったのじぇ
どんなひとなのかわからない人はここをみて確認すればいいのじぇ。
denou.jp
f:id:daruma3940:20160521003616p:plain
どうだったの焼き肉は?
f:id:daruma3940:20160520223745p:plain
いや~~もうお二方の賢さに圧倒されるだけの焼き肉だったのじぇ。
特にwainさんのコンピューターの根本に関わることに関する知識は半端なかったのじぇ
でも色々役に立つお話を聞くことが出来て大変良かったのじぇ!
f:id:daruma3940:20160520223745p:plain
leaと呼ばれる命令があってその命令を使えば*5,*9も普通の掛け算演算子を使うよりも早く計算できるらしいのじぇ!(11/7修正)


if()でCPUが過去の履歴から予測したのと逆の条件分岐に移るときに10clockぐらいロスになり、最近のプロセッサでは1clockで3命令ぐらい処理できるのでかなりのロスに成ってしまうらしいのじぇ!(11/7修正)

まりちゃの使っているパソコンのcpu:core2duoでの3秒探索は最新のcpuで言うところの0.5秒探索ぐらいらしいのじぇ!

そしてまりちゃのソフトがレッサー改より弱くなり、20キロnpsしか出ていないという話をするとStockFish7式の探索でcore2duoであれば250キロnpsは出るはずであるのでバグを探せと教えて頂いたのじぇ!


f:id:daruma3940:20160520223530p:plain
ゆゆっ!?すごい情報を手に入れたね!

f:id:daruma3940:20160520223745p:plain
そうなのじぇ!これからは頑張ってコードの無駄な部分を探してnpsを増やしていく改良をしていくのじぇ!
めざせ!250knps!!!

応援していただいているのじぇ!


f:id:daruma3940:20160709192554j:plain
いろんな方に応援していただいているよ~うれしいよ~~
f:id:daruma3940:20160520223745p:plain
ゆゆっ!ほんとなのじぇ!
応援していただいていうれしいのじぇ!
頑張って開発しますなのじぇ!

電王トーナメント出場が決まったのじぇ!!

f:id:daruma3940:20160520223745p:plain

電王トーナメント出場が決まったのじぇ!!

denou.jp

 

f:id:daruma3940:20160520223530p:plain

やったね!!

f:id:daruma3940:20160521003616p:plain

やったわね!

f:id:daruma3940:20160709192554j:plain

やったよ!!

 

f:id:daruma3940:20160520223745p:plain

最近なかなかモチベーションが上がらなかったけど

モチベーション回復したのじぇ!!

 

f:id:daruma3940:20160520223745p:plain

大会までもうひと踏ん張りなのじぇ!!