2017-12-02

SDT５を振り返って

なんか需要があるかもしれないと思ったので昔書いたのをおいておく（やっぱやめとこうかな...）

今大会（SDT5）を振り返って書くとすれば短くなる
全然強くならなかったし強くするモチベーションも湧いてこなかった。とりあえず６月にrootstrapがようやく成功してそこからほぼ何もしてこなかった。
いつも使っているi74770kを学習用に当ててしまうと、自分はオンボロPCで作業をしなければならなくなる。遅くてたまらん。あと夏場にマシンを動かすと暖房をつけてるのと同じようなものなので冷房をつけないとやってられず、暖房をつけながら冷房をつけている感じになり電気代が高くなって家族に申し訳ないという気持ちになる。それとスマホゲーム作成が面白くてそちらに注力してしまっていた。さすがに大会前はコード書く意欲が高まったのだがそれは全て研究のコードを書くほうに向かって行ってしまった。
やはり定跡が重要になってきてなんだかおもしろくないなという気持ちなんだけどこれは「スマホなんてくだらん！」と思う老害と同じなんだろうか。
今回もnozomiさんにはお世話になった。1日目の飲み会では色々なことを教わった。寝不足で飲んだので酔いが回りすぎて忘れてしまったことと周りがうるさかったので聞き取れなかったことが多々あったのだけれど覚えているだけでも重要なことを沢山教えてくださった。
とりあえず評価関数をmargeすると強くなるのはPRMLのバイアスバリアンス分解のところで出てきた話で過学習気味な評価パラメータを平均化すればバリアンスが下がるような感じじゃないのかと言ってみたら賛同してもらえたのでよかった。
正則化について話したときにbonanzamethodで次元下げをした評価関数では多くのパラメータに値が入っているのでL2、次元下げをしない評価関数では少しのパラメータにしか値がついていなくてそれらが大きな値をつけなければならない局面があるので弱めのL1を使うと強くなったのかという話をしたときに理由を聞かずに「まあ当たり前だよね」みたいなことを仰られていてすごいなぁと思った。評価関数の初期値についてもこだわられていてそこはあんまり着目していなかったので盲点だった。探索パラメータについて聞いてみたらLMRについての調整だけが本質的と仰られていて確かに僕もLMRについては結構重要だと思っていた（最近はそんなことを思っていたなんて忘れてしまっていたが）がそこまでバッサリ言い切るかと思った。
elmo絞りについて駒組というのはかなり先になって利益が出てくるものであるので、数手先の評価値に近づける方法であるrootstrapでそれをちゃんと評価することはできておらず勝敗を入れることでそれができるようになったのだと思うと理にかなうという話をしたら、負けた側のすべての指し手が悪かったわけではないだろうし逆転負けの場合でもすべての指し手対して咎めてしまうのはどうかとおっしゃっていたがどれが悪手だったのかそう簡単にはわからないしそれを調べるのにもかなりの時間がかかってしまうのでなかなか難しいだろうなという話をした。
やはりnozomiさんから学ぶことはたくさんある。
二日目の飲み会ではPonanzaの大渡さんが少しだけPonanzaの大まかなところを話してくれて興味深かった。まだほかのソフトがやっていないようなことが3つぐらい入っているらしいことと、将棋を指すコードがが一番のメインなところではなくて巨大な自己対局システムの中に将棋を差す機能がちょこっとあるというお話をしていた。そしてそれには億単位の価値があると。FishTestを拡張したようなものなのだろうか。
飲み会で山本さんがこらえきれなくて抑えながらも泣いてるのを見てやはりPonanzaは山本さんの青春そのものなんだなという気持ちになった。
あそこまで全てを犠牲にした努力は僕にはできないなという気持ちになった。やはり皆さんすごいなぁ...
あと大会が終わった後mEssiahさんがtwitterでつぶやいていた、西海枝さんが評価関数の特徴は実は2駒で十分でrootstrapが教師付き学習に近いものなのでアルゴリズムで天井を作っているのではないかとおっしゃっていたという内容もとても興味深い。
あまり注目はされていないがStockfish探索を積まず、独自の学習方法（方策勾配法）であそこまで強いソフトを作れるということは相当すごい。もし僕が将棋ソフトを本気で強くしようと思うなら進むべき道はSeleneさんの方のような気がする。
しかし2駒なぁ...静止探索を重くしたり、王手のかかっている局面は必ず延長して考えたり探索で誘導をしてやれば中盤終盤はそれでいけるかもしれなけど,序盤はそれじゃきつそうという感じがしないでもない
あとdlshogiの山岡さんにVNとPNを最新のAlphagoでは一つにまとめているがあれの利点はそこまで精度が落ちずに高速化できるからなのかと聞いてみたら、どうやら似た概念の物を一つのネットワークで出力すると逆に精度が上がるのだと教えてもらって目から鱗だった。
やはり関連することがらは分けて考えないほうがいいのか...昔杉田さんと実現確率探索について話したときに杉田さんが「複数のよく似た基準をもってしまうのはよくないと思う。評価値を利用するならそれでオーダリングし他の基準を用いないほうが良いのではないか」というお話をされていたのを思い出した。（関係ないかもしれない）
次の大会はどうしよう。このままダラダラと大会に出続けても仕方ないという気持ちが大きい。どうしようなぁ... とりあえずもう一台スペックのいいPCが欲しいがそうするとさらに電気代で迷惑をかけてしまうしなぁ...
短くなるはずが長くなってしまった。終わり。

2017-10-27

■

f:id:daruma3940:20160520223745p:plain
SDT5に向けて将棋盤アプリ作ったのじぇ
play.google.com
f:id:daruma3940:20160521003616p:plain
SDT5関係ある？？？

二日目暇な開発者さんにダウンロードしてもらってお金を稼ぐ算段なのじぇ

あんたねぇ...
f:id:daruma3940:20160520223745p:plain
どうぶつしょうぎも作ったのじぇ（公開はしてない　もうちょっと機能追加したい）
f:id:daruma3940:20171027232525p:plain
f:id:daruma3940:20160709192554j:plain
でメインである僕は強くなってるの？？？？

もうダメダメなのじぇ.....

機械学習で賢くなっているのはソフトだけじゃなくて開発者もソフトの学習結果からどのような学習方法を取るべきなのかというのを学習していくんだよなぁ(´･ω･｀)
WCSC27の時は大会2週間前には一番良い学習の条件を見つけてあとは本番の学習を回すだけだったのに今回はほんとにダメダメ
— だるま (@daruma3940) 2017年10月27日

僕の開発もがんばってくれよな～～たのむよ～～

2017-10-26

拡張ユークリッド互除法について

アルゴリズム

ユークリッド互除法について書くのじぇ
ユークリッドの互除法について書くといったけどユークリッドの互除法についてはさらっと流して
拡張ユークリッド互除法について書きたいのじぇ
蟻本の拡張ユークリッドについての記述がよくわからなかったので自分でわかるようにした備忘録なのじぇ

まりちゃがこういうこといいだすのは大体よくわかってないことについてなので鵜呑みにしないほうがいいわよ

まずはユークリッド互除法について
自然数a,bに対して最大公約数を求める方法をユークリッド互除法というのじぇ
自然数a,bの最大公約数と毎回書くのは面倒なのでgcd(a,b)と書くことにするのじぇ。
ここでaをbで割った商をp余りをqとすると
a=b*p+qと書けることは明らかなのじぇ
b,qの最大公約数をgcd(b,q)とすると
b=x*gcd(b,q),q=y*gcd(b,q)のようにかけるので
a=gcd(b,q)*(x*p+y)と変形できるののじぇ。
gcd(b,q)は明らかにbを割り切り、上の式からaも割り切るのでgcd(b,q)はgcd(a,b)も割り切ることができなければならないのじぇ

ここで逆に
q=a-b*qとすると先ほどと同様にgcd(a,b)はgcd(b,q)を割り切れなければならないのじぇ
つまり
gcd(a,b)=X*gcd(b,q)
gcd(b,q)=Y*gcd(a,b)
となり、最大公約数は少なくとも1(>0)より大きいはずなのでX=Y=1となり
gcd(a,b)=gcd(b,q)となるのじぇ

aをbで割った余りをqとしたのでC言語的にq=a%bと書くとするのじぇ.
上の処理を何回も繰り返すと第二引数はどんどん減っていき最終的にゼロとなるのじぇ
gcd(a,b)=gcd(b,a%b)=gcd(a%b,b%(a%b))=.......=gcd(x,0)
0とxの最小公倍数はxなのでこれでgcd(a,b)は求まるのじぇこれがユークリッドの互除法なのじぇ

コードにするとこんな感じ(from 蟻本)
aをbにbをa%bにどんどん変えていく感じ

int gcd(int a,int b){
    if(b==0){return a;}
    return gcd(b,a%b);
}

これを拡張した拡張ユークリッドの互除法を利用することで
ax+by=gcd(a,b)となる整数解x,yをを求めることができるのじぇ

ちなみに右辺がなんでgcd(a,b)じゃないといけないのかについてはここを見てほしいのじぇ
mathtrain.jp

ユークリッド互除法のaをbに、bをa%bにどんどん変えていってどんどん係数を簡単にしていってgcd(a,b)を求めるのに似た方法を用いて
ax+by=gcd(a,b)もどんどん簡単にしていくのじぇ

最大公約数を求める方法と似てるなーーと思いながら読み進めてほしいのじぇ

とりあえず一回簡単にしてみるのじぇ
bx'+(a%b)y'=gcd(a,b)

aがbになってbがa%bになってxがx'にyがy'になっているのじぇ
gcd(b,a%b)=gcd(a,b)なので右辺は変わらんのじぇ

さっきのと似てるなーーーー

そしてこれをどんどん繰り返していくのじぇ
そうするとyの係数bはどんどん減少していって最終的にゼロになるのじぇ

ax'+0y'=gcd(a,b)

gcd(a,b)を求めるときbがゼロになったらgcd(a,b)=aだったのを思い出してほしいのじぇ
ということはx'の値は1でないといけないのじぇ

a*1+0*y=gcd(a,b)

0がかかっているのでy'の値はなんでもいいのじぇ。
ここではy'=0ということにしておくのじぇ

さてここまでやってきたことはax+by=gcd(a,b)をどんどん簡単にしていくことだったのじぇ

(a,b,x,y)
↓
(b,a%b,x',y')
.
.
.
↓
(a,0,1,0)

ax+by=gcd(a,b)となる整数解x,yを求めるには今度はこの逆をたどって最初の式に戻らなければならないのじぇ

(a,b,x,y)
↓　　↑
(b,a%b,x',y')
.
.
.
↓　　↑
(a,0,1,0)

その方法をここで説明するのじぇ

ax+by=gcd(a,b)
を
bx'+(a%b)y'=gcd(a,b)
にした場合のもとに戻し方を考えるのじぇ。

a%bはプログラミングの整数の割り算の扱い的に
a%b=a-(a/b)*b
とかけるので
bx'+(a%b)y'=gcd(a,b)は
bx'+(a-(a/b)*b)y'=gcd(a,b)となって
aとbについてまとめると
ay'+b(x'-(a/b)*y')=gcd(a,b)
となるのじぇ。
これを
ax+by=gcd(a,b)
と比較すると
x=y'
y=x'-(a/b)*y'

となるのでこのようにしてx,yの値を順にもとに戻していくことで
ax+by=gcd(a,b)となるx,yを求めることができるのじぇ

コードにするとこんな感じ(from 蟻本)

int extgcd(int a,int b,int& x,int& y){
    int d=a;//b==0のときgcd=a
    if(b!=0){
        //ここでgcdが求まる（b=0になる）まで潜る
        //さかのぼりながらx yを更新してゆく
        d=extgcd(b,a%b,y,x);

        //y=x'-(a/b)y'
        //xは1つ前のy yは一つ前のx
        y-=(a/b)*x;
    }
    else{
        //gcdが求まるとき(b==0のとき)　x=1,y=0にする
        x=1;y=0;
    }
    return d;//gcdを返す
}

yの値をなんで0にしたのかについてはこれはほんとに何でもよくて他の値にすれば
他のax+by=gcd(a,b)を満たすx,yが求まるだけなのじぇ。
そもそもax+by=gcd(a,b)の解は一意ではないので...

ここからは完全に余談なのじぇ

さっき紹介したサイトを見ると
ax+by=gcd(a,b)の解き方は

この方程式の解を一つ求めてそれを(x0,y0)として

a(x1)+b(x2)=0
(x1:=x-x0 , y1:=y-y0 とした)

の形にすると
これは線形方程式なのでこの一般解はすぐに求まる。
そこからx=x1+x0,y=y1+y2の関係を用いて
x,yの一般式を求めることができると書いてあるのじぇ。
ここで(x0,y0)はさっき述べた拡張ユークリッド互除法で求めることができるのでこれで一般解を求めることができるのじぇ

これは非同次微分方程式を解くときと同じ考え方なのじぇ。

y''+ay'+y=f(x)
のを満たす解を一つ見つけてy_1とすると
(y-y_1)''+a(y-y_1)'+(y-y_1)=0　という形にできて
これは線形微分方程式なので簡単にとけて、その解をy_2とすると
y=y1+y2の関係から非同次微分方程式の一般解も求まるのじぇ

なるほど～～～～って感じなのじぇ

2017-10-22

SDT5個人的注目ソフト

きふわらべ

今年はどのような伝説を残してくれるのか期待ｗお話をするのが楽しみ。

messiah

個人的にすごく応援してます。

WCSC27でSquirrelにかなりヘイトを溜めているはずなのでガチで殺りに来てそう。怖い。

海底

私がかなり苦労したbitboardを軽く実装するつよい人学習部も軽く実装しててガクブル。競プロもつよい。2駒勢。怖い。

shogi686

コンピュータ将棋将棋についていろいろなことを教えてくださった師匠。競プロもめっちゃつよい。2駒勢。怖い。お話をするのが楽しみ。

2017-09-23

Unityのml-agents使ってみた

github.com
f:id:daruma3940:20160520223745p:plain

Unityのml-agents使ってみたので忘れる前に記録しておこうじぇ??

.......

......

...
f:id:daruma3940:20160520223745p:plain

もう忘れたwww

とりあえず記憶を呼び起こしながらでも今書いておかないとあとからまた思い出すのに手間取ってしまうのでがんばれ自分!!!

とりあえず上のリンクにあるwikiを見ながらやっていけば基本いける

Unityで作った環境（実行ファイルは　ml-agents\pythonに置くのが安全（exeファイルだけじゃなくてDataフォルダも一緒に置かないと動かないので注意な）
env_name
には
env_name = "TestBall2"
みたいな感じで実行ファイルから.exeを除いた名前を置いておく。ちょっとわかりにかった（ソースコード読んで理解した。）
この指定の仕方が嫌ならソースコードを改変すればよろし

学習するときはBrain（Script）のType of BrainをExternalにしておく。
Type of brainのtypeにはPlayer, Hulistic, External, Internalの4タイプがある。
PlayerはPlayer Actionを決めることで人間が動かすモード
Hulisticは手で書いたコードを動かすモード
Externalは学習するときのモード
Internalは学習させたモデルを使って動かすときのモード
InternalモードはTensorFlow＃　AssetをUnity Projectに入れて　PlayerSettingのScripting Define SymbolにENABLE_TENSORFLOWを追加して　Scripting Runtime VersionをExperimental(.Net4.6)にしないといけないはず

自分の作った環境で
学習させたりするのは大変そうに見えるかもしれないけどそんなに難しくないはず
AcademyとAgentとDecisionを作成した環境に合わせて弄ってやるだけでいい。
ML-AgentをgithubからダウンロードしてきたところについてるTemplateフォルダに雛形があるのでそれを弄れば基本出来るはず

CollectState()関数でStateにおける特徴をリストにして返す{{Brain(Script) InspectorのStateSizeはここの特徴の数を入力する}}
AgentStep(float[] act),AcademyStep()はFixedUpdate()で毎回呼ばれる処理を記述する
Agent.done=trueで今回の試行が終わったフラグを立てる
AgentReset(),AcademyReset()　はdone=trueになった後次の試行へ移るときに呼び出される
Agent.rewardは報酬
Decisionについてはよくわかってない

学習時にはml-agents\python内のppo.pyかPPO.ipynbを使えばいい
exeファイルのレスポンスがタイムアウトすることがよくあった。私の場合jupyter notebookを再起動したらタイムアウトしなくなったのでよくわからない。

wikiにはSplashImage(ゲームを開始したときに出てくるロゴ)の表示はOFFにしておけと書いているが、nonProUnityではオフにできないしONにしてても起動に時間がかかるようになるだけでちゃんと動くから大丈夫。

AndoridでInternalmodeを動かすことに成功したのでこれを利用したAndroidアプリも作れる

f:id:daruma3940:20160520223745p:plain
まあwikiに書いてないことで特記しておくことはこれぐらいかだじぇ...????

2017-09-05

行列　ベクトル　微分

物理

これであってるはずなのだけれど間違ってたら教えてほしいのじぇ。

$A = \left( \begin{array}{ccc} a_{11} & a_{21} \\ a_{12} & a_{22} \end{array} \right) \\ \vec{x }= \left( \begin{array}{c} x_1 \\ x_2 \end{array} \right) \\とすると\\ \vec{y}=A \vec{x}=\left( \begin{array}{c} a_{11} x_1+a_{21} x_2 \\ a_{12} x_1+a_{22} x_2 \end{array} \right) ≡ \left( \begin{array}{c} y_1 \\ y_2 \end{array} \right) \\となる\\ \\ここで\\ \frac{ \partial \vec{y} }{ \partial \vec{x} } = \left( \begin{array}{ccccc} \frac{ \partial {y}_{1} }{ \partial {x}_{1} } & \cdots & \frac{ \partial {y}_{j} }{ \partial {x}_{1} } & \cdots & \frac{ \partial {y}_{m} }{ \partial {x}_{1} }\\ \vdots & \ddots & & & \vdots \\ \frac{ \partial {y}_{1} }{ \partial {x}_{i} } & & \frac{ \partial {y}_{j} }{ \partial {x}_{i} } & & \frac{ \partial {y}_{m} }{ \partial {x}_{i} } \\ \vdots & & & \ddots & \vdots \\ \frac{ \partial {y}_{1} }{ \partial {x}_{n} } & \cdots & \frac{ \partial {y}_{j} }{ \partial {x}_{n} } & \cdots & \frac{ \partial {y}_{m} }{ \partial {x}_{n} }\end{array} \right) \\というベクトルに対するベクトル微分の定義$
http://www.r.dl.itc.u-tokyo.ac.jp/~nakagawa/SML1/math1.pdf

qiita.com

から
$\frac{ \partial \vec{y} }{ \partial \vec{x} } = \left( \begin{array}{ccc} \frac{ \partial {y}_{1} }{ \partial {x}_{1} } & \frac{ \partial {y}_{2} }{ \partial {x}_{1} } \\ \frac{ \partial {y}_{1} }{ \partial {x}_{2} } & \frac{ \partial {y}_{2} }{ \partial {x}_{2} } \end{array} \right) = \left( \begin{array}{ccc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right) = {}^t A \\ \\ \\$

$\\また\\ \vec{a}_{1}= \left( \begin{array}{ccc} a_{11} \\ a_{12} \end{array} \right) , \vec{a}_{2}= \left( \begin{array}{ccc} a_{21} \\ a_{22} \end{array} \right) \\とすると\\ A=\left( \begin{array}{ccc} \vec{a}_{1} & \vec{a}_{2} \end{array} \right) \\であるので\\ \frac{ \partial f( \vec{x}) }{ \partial \vec{x} } = \left( \begin{array}{ccc} \frac{ \partial f(\vec{x}) }{ \partial {x}_{1} } \\ \frac{ \partial f(\vec{x}) }{ \partial {x}_{2} } \end{array} \right) \\より\\ \frac{ \partial \vec{y} }{ \partial A } = \left( \begin{array}{ccc} \frac{ \partial \vec{y} }{ \partial \vec{a}_{1} } & \frac{ \partial \vec{y} }{ \partial \vec{a}_{2} } \end{array} \right) = \left( \begin{array}{ccc} \left( \begin{array}{ccc} \frac{ \partial {y}_{1} }{ \partial {a}_{11} } & \frac{ \partial {y}_{2} }{ \partial {a}_{11} } \\ \frac{ \partial {y}_{1} }{ \partial {a}_{12} } & \frac{ \partial {y}_{2} }{ \partial {a}_{12} } \end{array} \right) && \left( \begin{array}{ccc} \frac{ \partial {y}_{1} }{ \partial {a}_{21} } & \frac{ \partial {y}_{2} }{ \partial {a}_{21} } \\ \frac{ \partial {y}_{1} }{ \partial {a}_{22} } & \frac{ \partial {y}_{2} }{ \partial {a}_{22} } \end{array} \right) \end{array} \right) \\ = \left( \begin{array}{ccc} \left( \begin{array}{ccc} x_1& 0 \\ 0 & x_1 \end{array} \right) & \left( \begin{array}{ccc} x_2& 0 \\ 0 & x_2 \end{array} \right) \end{array} \right) \\ = \left( \begin{array}{ccc} x_1 I & x_2 I \end{array} \right) = \left( \begin{array}{ccc} x_1 & x_2 \end{array} \right) I = \left( \begin{array}{ccc} x_1 & x_2 \end{array} \right) = {}^t \vec{x}$

2017-08-25

電王トーナメント申し込み始まったみたいなのじぇ

f:id:daruma3940:20160520223745p:plain
電王トーナメントの申し込みが始まったみたいなのじぇ

denou.jp

f:id:daruma3940:20160521003616p:plain
他人事みたいに言うわね....
f:id:daruma3940:20160520223745p:plain
出ようかなぁどうしようかなぁ....

なんかほかにもいろいろやりたいことあるし,研究もあるし、以前みたいに熱中して開発する気は起らないし、
でも研究ややりたいことがいっぱいあるなんて言っても、どうせごろごろして無駄な時間を過ごしそうだし。出なかったら出なかったで後悔もしそうだし。
でも参加申し込みしたら大会のことで頭のメモリが常に何割か占拠されるし、
何日もウィンウィンうなるPCの前で寝るのもつらいし、
学習にi7 4770Kを占拠されて　開発はクッソ遅いi5でしないといけないのもつらいし....

もし出るとしてもまだWCSC27後からRootStrapを成功させたことによるR上昇100しかないし
おそらくトップ勢はR200ぐらい上げてくる気がするので今のままだと相対的に後ろに下がっていることになるし...

まあうちもR200ぐらい上げようと思えばKPPを取り入れてRootStrapで学習させればそれぐらいは行く気がする(簡単だとは言っていない)んだけれど
どこまで巨人の肩に乗り続けるんだよって感じもするし....
一応次の大会でやりたいことはあるけれど、モチベーションを保てるかどうか....
f:id:daruma3940:20160520223745p:plain
とりあえず申し込み期間はまだあるのでもう少しなやもうじぇ？？

daruma3940の日記

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