2017-07-19

レート測定エンジン ELQを使って君も棋力解析をしよう！

藤井四段と羽生三冠のどちらが強いか、流行の人工知能に聞いてみました - qhapaq’s diaryで用いたレート解析機をやっとの思いでリリースいたしましたので、此処に報告いたします。ソフト自体はかなり前にできていたのですが、皆様の利用に耐える形になるのに凄く時間がかかりました......

DLはこちらから（ソースコード付き）

Release レート測定器ELQ · qhapaq-49/qhapaq-bin · GitHub

レート測定器ELQの使い方

０．ELQの動作環境

ELQはC#で開発されています。windows上での動作を確認していますが、他OSでの動作は確認しておりません。

１．将棋guiを用いた棋譜解析

まず最初に、ELQのkif_exampleのように、解析したいプレイヤー（プロ棋士、ソフト、etc）の棋譜を先手、後手別に分別して保存してください。ELQには棋譜コメントから先手後手を判別する機能はついていません。

分別が終わったら、解析したい棋譜を将棋guiの"連続解析"を用いて解析します。手元のバージョンでは対局タブから棋譜解析から連続解析が出来ました。指定したフォルダにkif、csaファイルといった将棋guiに対応した棋譜ファイルを置くことで、連続で解析を行うことができます。解析にはそこそこ時間がかかります。ラノベを読むなどしてお待ちください。

kif_example/fujiis/fujiis_sente/ 内のkifファイルのように、kifファイル内に指し手とソフトの評価値が用意されたら準備OKです。

２．ELQを用いて仮想エージェントを創る

kifファイルが保存されたフォルダを指定して、「指し手データ作成」ボタンを押してください。保存するcsvファイルの名前を聞かれるので、適当な名前を付けてあげましょう。

注：ELQは指定したフォルダ内のkifファイル"のみ"を"全て"読み込む仕様になっています。将棋guiの解析の保存形式がkif以外だったり、元の棋譜ファイルがkifファイルだったりすると不具合の原因となりますのでご注意ください。

注２：将棋guiは日本語でログが保存される関係で、テキストエンコーディングの愛称が問題になってきます。ELQはshift_jis対応ですが、他のエンコーディングへの対応は明示的にはしていません。将棋guiのデフォルト設定で問題なく動いていることは確認していますが、ご注意ください。

３．仮想エージェント同士で対局させる

step2で作ったエージェントをレート測定のタブ上で戦わせることが可能です。細かい動作原理はソースコードを参照していただけると幸いですが、雑に言えば「各プレイヤーについて、局面の良さに毎の指し手の統計データを取り、それにしたがって局面の評価値を動かすエージェントを作り、その勝率を測定」することでレートを測っています。

藤井四段と羽生三冠のどちらが強いか、流行の人工知能に聞いてみましたで用いたレート測定用のパラメタは評価値カーネル200、ノイズ20です。これは羽生三冠ととある棋士（双方とも対局数が多く年単位でレートがあまり動いていない）のレート差を際限するように調整した結果です。

４．棋風を解析する

step2で作ったcsvファイルをelq_templateに入れることで、棋風の解析が出来ます。一例として、藤井聡太四段のデータを可視化してみましょう。

f:id:qhapaq:20170719231154p:plain

横軸は局面の評価値、縦軸は悪手を指す確率（厳密にはソフトが評価する手を指す前と後での勝率の差分の変化量の平均）です。値が大きいほど悪い手を指す傾向が強いです。青が藤井四段、赤が対局相手です。

こうして見比べると、藤井四段と対局相手とでは200-1000点程度の自身が有利な局面での手の質に大きな差があることが解ります。藤井四段の２９連勝には逆転勝ちの棋譜も少なくないですが、改めて数値化すると、藤井四段は自分が有利なときはミスをせず、相手が有利なときにミスを誘うような手を指すのがとても上手であると言えます。加えて、相手のミスを誘う勝負手はソフト的にはベストな手ではないことが多いにも拘わらず、藤井四段の不利な局面での悪手率は対局相手と比べてもあまり高くないのは驚愕です。

藤井四段旋風に乗っかって藤井四段の棋譜ばかり解析していたので、他の棋士のデータがあまりないのは心苦しいですが、本ソフトを使って皆様も棋風解析を楽しんでくれれば幸いです。本研究ではやりませんでしたが、戦型別の棋風測定なども有意義であると思います。

おまけ、本ソフトの名前の由来

本ソフトの正式名称は「やねうら王の学習がまだ終わらないから作ったelmo-qhapaq理論型レート測定器」略して「山田エルク」です。

どういうわけか某大作ノベルの人気キャラの名前にとても良く似ていますが、１億％偶然です。やる気が出たからコードを書きました。レート測定部分の変数添字が逆だったなどのバグを発見した際はダビデ像を添えてご報告いただければ幸いです。

2017-07-17

REsolve MUtationエンジンの使い方

ゼロから始める評価関数分解のやり方紹介です。

githubのドキュメントがあまりに貧弱すぎたので、幾つかの具体例を以って使い方をもう少し細かく解説したいと思います。

注：この関数がパクリじゃないか的な議論をするためにREMUを使うことは推奨しません。また、私自身がそういった用途での解析に協力することもありません。KPPTという同じ評価軸を使ってる以上、強い関数がある程度似るは仕方がないことですし、ちょっと数理を理解してる人ならバレないように関数をコピペすることは容易だからです。

本体：

Release 評価関数分解機 REsouve MUtationエンジン · qhapaq-49/qhapaq-bin · GitHub

sseバージョンも作りました

https://t.co/6I2Sypa5nC

１．評価関数フォルダと実行ファイルを揃える

YaneuraOuが置かれているフォルダと同じフォルダに評価関数を並べます。このとき、evalフォルダにダミーのKPPT評価関数を置くようにしてください。これをやらないと、コマンド実行直後に「open evaluation file failed」というコメントが出て計算に失敗します。

f:id:qhapaq:20170717001919p:plain

こんな感じ（binディレクトリの上半分しか写ってませんが、下にはYaneuraOu-by-gcc-remu.exeが居ます）

２．evalresolveコマンドを実行する

例えば

test evalresolve elmo_ep8_55 elmo epoch8

と打ち込んでみましょう。elmo_ep8_55はelmoとリゼロepoch8を5:5で混ぜた関数です。このコマンドはelmo_ep8_55をelmoとepoch8で分解するという意味です。

３．解析結果を読み解く

出力結果一例（evalフォルダにはwcsc27のqhapaqの評価関数が入ってます）

test evalresolve elmo_ep8_55 elmo epoch8
info string Eval Check Sum = 702fb2ee5672156 , Eval File = Qhapaq(WCSC27)
REsolve MUtation engine target = elmo_ep8_55, reference = elmo,epoch8,
prodmatrix
7.60975e+13,1.06684e+13,
1.06684e+13,2.91226e+13,
converge in 5 loop
result : elmo_ep8_55 = 0.49981 x elmo + 0.499613 x epoch8 + 0.00111753(diff ratio)

解析結果は最後の行です。

elmo_ep8_55 = 0.49981 x elmo + 0.499613 x epoch8 + 0.00111753(diff ratio) とは

「elmo_ep8_55の評価関数はelmoを0.49981倍したものと、epoch8を0.499613倍したものに、0.00111753 x 未知の関数（雑に言えば、学習によって生じた差分）を加えたもの」という意味です。

未知の関数の大きさ（KPPTのパラメタの２乗和）は解析元の評価関数（例の場合は、elmo_ep8_55の２乗和）に等しいです。今回はelmoとepoch8を混ぜただけの関数なのでdiff ratioは極めて小さい値になっています。やねうら王を使った単純な合成を施した関数であれば、個数や割合が未知であっても大体分解できます。分解元の評価関数に漏れがなければ、diff ratioが極めて小さい値になるかと思います。

評価関数の合成し過ぎで迷子になった時にお使いいただければ幸いです。

４．学習の効果を可視化する

wcsc27のqhapaqを分解してみます

test evalresolve qheval-wcsc27 elmo epoch8

qheval-wcsc27 = 0.865984 x elmo + 0.0192829 x epoch8 + 0.311523(diff ratio)

qhapaqとelmoの内積は割と大きいです。どちらも浮かむ瀬を元にしているからでしょう。

これにelmo絞りを加えるとこうなります（この関数は公開してないです）。

test evalresolve 0621-yz elmo epoch8

0621-yz = 0.860074 x elmo + 0.0660107 x epoch8 + 0.403802(diff ratio)

ちょっとepoch8の要素が増えるのと同時に、何らかの差分が加わっているように見えます。

リファレンスにqhapaqを加えて再分解

test evalresolve 0621-yz elmo epoch8 qheval-wcsc27

result : 0621-yz = 0.0249868 x elmo + 0.0474157 x epoch8 + 0.964326 x qheval-wcsc27 + 0.282281(diff ratio)

どうやらqhapaqに何らかのdiffが加わった形とするほうがより正確なようです（qhapaqの成分があんまり減ってなくて驚いた）。この関数のレートはelmoと同じぐらいなのですが、どうやらelmoとは別路線の関数になってるようです。

余談：さらなる応用

定跡ごとに雑巾を作って、どのぐらい関数の形が変わるかを見てみる、強い評価関数の組成比を見て、それに近づくように学習や合成を調整するなどの工夫ができると思います。使い方は無限大ですよ！（多分

2017-07-16

評価関数ファイルの合成、学習元を解析するツールREsolveMUtationエンジンを公開します

todo もうちょっと可愛げのある文章に書き直す

WCSC26を制した評価関数elmoとやねうらお氏が人間の棋譜に一切頼らずに開発した評価関数リゼロ関数を1:1で合成した関数がelmoよりも強くなることを発端に、有志による評価関数の合成が密かなブームを迎えています。

また、学習用ツールの操作が簡易、コンパクト、高速化したことによる、有志による独自評価関数が可能になったことに伴い、各種関数を改造した野生の評価関数が最強の座を競っているようです。

しかし、そんなブームの到来は「あの関数なんだっけ」「この学習の効果ってどのぐらいよ」といった評価関数の迷子を多く生み出してしまっています。

そこで、せめて合成されたキメラ関数ぐらいは分解できたほうが良いだろうというわけで、やねうら王を改造し、評価関数の分解機能を実装しました。

ダウンロード（使い方もgithubのドキュメントをご参照ください）：

Release 評価関数分解機 REsouve MUtationエンジン · qhapaq-49/qhapaq-bin · GitHub

# 例にもれず、ドキュメントはクッソ不親切なのでわからないことはtwitterあたりでお尋ねいただけると幸いです。

動作原理：

$F = a_{0}f_{0} + a_{1}f_{1} + ... \delta$ 　（Fが分解したい評価関数 $f_{i}$ は既知の評価関数）といった形で未知の関数を既知の関数の線形和で近似した時、 $\delta$ の絶対値が最小になるように $a_{i}$ を調整しています。連立方程式を解かせることでこれらを解析的に解くことが可能です（大学前期課程ぐらいの数学だと思います。興味がある人は導出してみてください...）

正しい使い方：

合成した評価関数の合成比率を忘れてしまった、学習によってどのぐらい元の評価関数から変化するのかを調べたいといった際に便利だと思います。

正しくない使い方：

評価関数のパクリを判別することができる気がしないでもないです。なお、単純に既存の強い評価関数を合成しただけなら、ほぼ確実に分解可能（diffの値が極めて小さくなります）ですが、本解析を抜けながら評価関数をパクることはそう難しくない（ある程度数学をやってれば想像がつく方法で行けます）ですし、独自関数が何らかの評価関数の線形和と似たものにならないことは保証できていません。

名前の由来：

言うまでもなく、リゼロのキャラクターであるレムから来ています。評価関数合成の立役者がリゼロ関数という愛称を持っているのと、レム嬢が残したとある名言

（ヒント）

f:id:qhapaq:20170716040551p:plain

に由来しています。

人の悪意の介在を証明するには人間の賢さは致命的に足りていないということは将棋ファンならよく理解していると思いますが......

エンジン提供者的にはうまく使ってもらいたいところです。

2017-07-01

藤井四段と羽生三冠のどちらが強いか、流行の人工知能に聞いてみました

藤井四段がデビュー開始から連勝を重ね、遂に連勝記録を塗り替えたようです。想像を遥かに超える強さに将棋民は大いに盛り上がっています。

ここまで来ると藤井四段がどのぐらい強いか。もう少し俗な言い方をすれば、将棋界の新スター藤井四段と、将棋界のレジェンド羽生三冠とどちらが強いのかが気になることでしょう。

両者の直接対局はAbemaTVの炎の七番勝負とニコニコの獅子王戦の2局で成績は1勝1敗。拮抗した実力を見せているようにも見えます。

が、どちらが強いかという問いに答えるにあたり、2局はあまりに数が足りていません。人間同士の戦いだから仕方ないにせよ、統計学的な観点からは少なくとも1000本勝負位はして貰いたいところです。

しかし、そんなことは流石に出来ないので、今話題の人工知能にどちらが強いか聞いてみることにしました。

【実験方法】

※：数理的な詳細は次の記事で扱う予定です

今回の解析方法について簡単に解説します。両棋士は直接対局をしたことはありませんが、他の棋士との対局データであれば数十局（羽生三冠についてはもっと沢山あります）程度の棋譜を集めることが可能です。

これらの棋譜から、各々の棋士がどういった局面でどういった手を選ぶ傾向があるのかを解析します。と言っても私は将棋は殆ど解らないので、プロに近い力持つというコンピュータソフトに、局面の互角、有利、不利を分別してもらい、各々の状況でどういった手を指す傾向にあるかを計算してもらいました。

【藤井四段、羽生三冠の手のアンサンブル】

藤井四段

f:id:qhapaq:20170701214444p:plain

羽生三冠

f:id:qhapaq:20170701214500p:plain

その他の棋士

f:id:qhapaq:20170701214817p:plain

グラフは横軸xが自分の手番での局面の有利/不利度（右に行くほど有利）、縦軸yが手を指した後の局面の有利/不利度です。各々のドットは各棋士が実際に指した手に相当します。x=yの直線から下にあるほど、悪手を指しているということです。なお、コンピュータは基本的に自分が指す手が一番だと思っているので、余程の手を指さない限りはx=y（図の中の黒線）より上にはドットは行きません。

これらのグラフを見比べると、藤井四段、羽生三冠ともに、悪い局面(x=-500付近)での粘りが強いことが解ります。また、良くなった局面については、優位を逃すことはあっても不利には繋げない傾向が強いことが解ります。意外なことにも有利な局面で優位をキープできる確率は三者とも大差はないようです（ソフトとの手の一致率も似たようなものです）。どちらかというと、手を誤ってイーブンに戻すことはあっても不利にはさせない、上手にリスクを背負う技術に差がでるようです。

藤井四段と羽生三冠のグラフを比較すると、形状はよく似ていますが、序盤は少し藤井四段が良いように見えます。羽生三冠の相手の得意を受ける棋風が出ているのかも知れません。また、藤井四段の詰将棋で鍛えた読みの精度からくる、相手玉を寄せる技術（+1000点ぐらいからの手の正確さ）は流石の一言に付きます。

一方、羽生三冠は中盤の構想力が光ります。ソフトは基本的に自分の手が一番という傾向にあるとは言いましたが、それでもソフトの読みを凌駕する手が散見されます。

【解析結果を用いたエア対局】

解析によって、自身の有利不利によってどんな手を指しやすい傾向にあるかを取得できたので、このデータに基づいて戦った場合、両者の勝率がどのぐらいになるかを測定してみます。といっても、面白いグラフとかは出てきません。

結果：

藤井四段（65%）- 羽生三冠（35%）

意外とそれっぽい.... いや、流石に藤井四段を強く評価しすぎ？

【もう少し技術的な話】

ソフトの読みが人間より正確かという最強の問題以外にも、今回作ったデータでは矢倉、振り飛車といった棋風の考慮がされていないなどの問題があります。ソフトの評価が基本減点方式なので、自分がミスをするリスクを犯してでも、相手のミスを誘うような危険な局面へ誘導する棋風の人は評価を低くされがちです。こうした問題を回避するには戦型毎に解析を加えるなどの工夫が必要となるでしょう。

# 藤井四段の対局相手のレートは他の人に比べ低く出すぎる傾向にある気がします。仮に藤井四段が危険な局面を好む棋風なのだとしたら、レートはもう少し上がることになります...恐ろしや

【最後に】

ソフトによるレート測定は飽くまで一つの指標に過ぎません。上記問題の他にもソフトに理解できない人間の強さ、弱さは沢山あります。ただ、機械学習や人工知能を駆使した数理的な指標を礎にすれば、人間は更なる高みに到達できると思っています。藤井四段の30連勝、大台が見えた一番のおつまみとして楽しんでいただければ幸いです。

【ちょっと宣伝】

人間将棋が大盛り上がりですが、コンピュータ将棋界も此処最近、とても盛り上がっています。第27回世界コンピュータ将棋選手権では佐藤名人に勝ったという最強ソフトponanzaが新星elmoに敗れ、長かったponanza絶対王権に穴が開く結果となりました。そのelmoの学習ルーチン、評価関数がソースコードと共に公開されたことを契機にコンピュータ将棋は驚くべき速さで強くなり続けています。

そんなコンピュータ将棋ソフトたちが戦う次の舞台が第5回将棋電王トーナメントです。まだ大会予定も決っておらず、予算が出るのか今からヒヤヒヤしていますが、皆様が盛り上げてくれれば、当日きっと美味しい弁当にありつけると期待していますのでどうぞよろしくお願い申し上げます。

ちなみに私もqhapaqチームとして参加します。alpha go的な数の力を前提とした学習の時代に真っ向から逆らった、数理ベースの学習アルゴリズムを用いて今回も最終日生存を目指して頑張るつもりです。

最悪、qhapaqのことは応援しなくていいので、どうかコンピュータ将棋を盛り上げてくれると幸いです。

2017-06-10

【今日のゆるふわ出張版】 atcoderのbeginner contest 64に殴りこんでみた話

ponanzaチームがPFNの精鋭を加えてから暫く。競技プログラミング勢をもっとコンピュータ将棋に引き込みたい、それならまずはコンピュータ将棋勢が競技プログラミングに手を出してみるべきだということで、将棋ソフトレーティングサイトの自称上位ランカー（笑）である"qhapaq"の中の人が敢えて爆死しに行ってきました。

問題は此方からどうぞ：

AtCoder Beginner Contest 064 - AtCoder Beginner Contest 064 | AtCoder

結果概略：

全問正解はできましたが、問題の読み間違いや調子こいて変なコードを書いたせいでコンパイルエラーを喰らったりして順位的にはなんとも微妙なものになってしまいました。

f:id:qhapaq:20170610230141p:plain

【得られた知見１：思考停止も立派な戦術】

問1：

1-9の数字が3つの標準入力で与えられ、その3つをつなげて作られた3桁の数字が4の倍数か判別する問題。

例： 1 6 8 が与えられた場合、168は4の倍数なのでYES、4 0 1が与えられた場合401は4の倍数ではないのでNO。

少なくとも百の位は数字が何であっても影響はありません。十の位もmod4では2, 0, 2, 0を繰り返すだけです。故に、十の位の数☓2 ＋一の位のmod 4をとることで高速に判別が可能です。.....が、そんなことを考えないほうが問題は早く解けます。計算条件的には1 * 100 + 6 * 10 + 8のmod 4を計算するので十分です。

変な数理に目移りして暫く手が止まりましたが、ぐっとこらえて100の位だけ無視して10の位☓10＋1の位のmod 4を計算させて撃破。

【得られた知見2：言語の仕様に精通しよう】

問2：

１次元空間上のN個の家の位置が標準入力で与えられ、好きな場所からスタートして全ての家を通る際の移動距離の総和を計算する問題。

家の座標をsortして、最大値と最小値を計算すればいいので、vectorのsortでOKと思ったのですが、ここでまさかのコンパイルエラー。どうもvectorのsortにはalgorithmが必要だったようです。

コンパイルを通してsubmitしたら、ジャッジはまさかのエラー。なぜだなぜだとコードをいじくり回した結果、悪ふざけでreturnの値を-1にしていたのが不味かったことが発覚。コードに必要のない /* let's try computer shogi ! */という遺言を残す暇はなかったようです。

【得られた知見3：問題文をよく読み、必要なら質問をしよう】

問3：

競技プログラミングにおけるN人のプレイヤーのN個のレートが与えられ、プレイヤー全体が作る色の種類の最大/最小値を求める問題。各プレイヤーの色はレートによって定められているが、一定の値を超えると"好きな色"にできるとのこと（atcoderの仕様かな？）。

所謂場合分けをしっかりやらねばならない問題。N-M人のレートの色が固定されてる人が作る色の種類は固定（Aとする）であり、M人の好きな色を設定できる勢が作る色の種類は1-M種類であるため、答えは最小値はmax(A,1)、最大値はA+Mです（ただし、参加者が0人の場合は0を返す必要があります!）

が、"好きな色"の定義が本当に好きな色（ビリジアンとかも選べる）なのか、色固定組が持っている色の中から好きな色を選べるのかが解らず、誤った解釈（＝後者の解釈）をしてしまったため、物凄く時間を消費しました。よく見れば入力例で色固定組の色以外の色が出てきていたのですが、30分以上費やして、漸く問題の解釈ミスの可能性に気づき、質問掲示板で同様の質問と回答を見つけ、解釈ミスに気付いて撃破。

# 序に、レート色の境界線の以下と未満も読み違えてたのでメッチャ時間使いましたorz

【得られた知見4：消費時間のバランスと問題の解ける解けないの判断を正確にやろう】

問4：

"("と")"からなる文字列に"("と")"を付け足してカッコが閉じた文字列を作る問題。stringの使い方がよく解らず、延々とコンパイルエラーを出し続けましたが、アルゴリズム自体を偶然一発で導出できたのもあり、なんとか10分以内に通すことが出来ました。今回は問3も解けた＋問4との相性が良かったからあまり気にする必要はないですが、もう少し時間がタイトな大会などでは、早い段階で問3に見切りをつけるべきだったろうなと反省してます。

【得られた知見5：競技プログラミング強い人は凄い】

アルゴリズムを思いつくスキルもさることながら、高い文章整理スキル（日本語や英語の問題を正しく理解するスキル）やコンパイルエラーを出さないスキルの必要性を強く感じました。

私自身はその手の作業は正直あんまり好きではなく、得意でもないので今まで競技プログラミングを避けてきましたが、自分を鍛える意味で今後も続けてみたいと思います。

競技プログラミングは楽しいから、将棋勢ももっと殴りこみましょう。あと逆もしかり。