リレー対局で最強将棋ソフトの三すくみを解消する話

【最強将棋ソフトの三すくみ】

第29回世界コンピュータ将棋選手権(WCSC29)が終了し、入賞ソフトたちの評価関数が公開されました。準優勝のKristallweizenや、初参加+デスクトップPCで7位入賞の水匠、有志作成の最強関数であるillqha4などが公開されました。

様々な関数が公開されれば「どの関数が一番が強いのか」を知りたくなるのが人間の性。ところが困ったことに、今の評価関数は上位の評価関数について三すくみ状態にあるというのです。

三すくみに参加しているのは前述のKristallweizenillqha4、そして2018年末からSOTAに居座っていたorqha1018(illqhaをベースに筆者が改造したもの)です。(因みに水匠、水匠改も同じぐらい強い)

評価関数の表現力が有限である以上、相性問題はあってもいいのですが、最強ソフトを使って検証をしたい人たちにとってはなんとも落ち着きの悪い話です。そこで本稿では三すくみを起こしているソフトたちを殴り倒すことを目指してみます。


【リレー対局】
将棋ソフト同士の相性問題については、WCSC29の覇者であるやねうらお氏による考察が既に存在しています。

yaneuraou.yaneu.com

端的に言えばorqhaは定跡offでは強い一方で特定の戦型を指定した上での対局ではあまり強くないということです。orqhaは少数高精度のデータで学習を行っているため、序盤の戦型選びに特化した作りになっている可能性は高いです。

しかしこれ、言い換えれば序盤に特化した将棋ソフトを作れているとも言えます。それならば、序盤だけorqhaに指させて、終盤を他ソフトに指させればもっと強い将棋ソフトを実現できるのではないでしょうか?


【実験】
というわけで、定跡オフ、1手1秒、スレッド数4で「序盤30手はorqha、それ以降はKristallweizen」というクソコラエンジンを作成し、orqhaと戦わせてみました。

三すくみの図曰く、この状態ではorqhaが勝ち越しそうですが

結果:
[クソコラ] 270 - 227 [orqha] (引き分けは除外。もとい、対局設定をミスってカウントしてくれなかった)

と、クソコラ関数が勝ち越す結果になりました。統計的にはまだ微妙に怪しいレベルですが、やねうら仮説が正しいこと、リレー対局をすれば将棋ソフトがまだまだ強くなるだろうことが示唆されました。


【実験用コード】
こちらからダウンロードできますやねうらお氏が開発中のやねうら王用のpython wrapperの「あやねる」の拡張エンジンとなっています。pythonが自力でかけないと使うのは難しいと思われます。

# リレー対局の有効性が示されたら本家やねうら王にも実装されるかも.....知れません


pythonわからない】
序盤の考察にはorqha、終盤はKristallweizenを使おう(多分 水匠やillqha4もいいぞ!


【技術書典にでます(宣伝)】
次の技術書典にQhapaqも出ます。今回はコンピュータ将棋本(棋譜解析や最弱将棋エンジン開発を中心にした技術を紹介する予定)と機械学習本(Gigazineに掲載された文章要約エンジンIMAKITAなどの機械学習ネタを突っ込んだ本)を頒布予定です。

長文を3行ぐらいで纏めてくれるChrome拡張 IMAKITA on Chromeを作ってみました

半年ぐらい前にGigazineデビューした文章要約エンジンIMAKITAが遂にChrome拡張になって帰ってきました。

 

chrome.google.com

 

唐突ですが皆様は偉い人の長話に苛々したことはないでしょうか。言いたいことは短いのに枝葉をつけた長文を送られるのにウンザリしたことはないでしょうか。

 

そんな皆様の声(?)を受けて、半年前に長文を3行ぐらいで纏めてくれる(厳密には、文章全体の中で特に重要度の高い文を抽出してくれる)エンジン IMAKITAを作ってみました。

https://www.qhapaq.org/imakita/

 

IMAKITAは私の想像以上に好評であり、なんとGigazineにも掲載してもらえました。そして、多くのユーザから「ハイライト機能が欲しい」「逐一サイトにデータを貼り付けるのが大変だ」というアドバイスをいただきました。

 

そこで、IMAKITAをブラウザ用のアプリにすることにしました。使い方は至ってシンプル。テキストを選択して右クリックからIMAKITAを呼び出すだけ。簡単!!

 

【使用例】

ニコニコニュースを参考に、いかがでしたかブログの王道である「綾瀬はるか 恋人」で検索し最初に出たページを圧縮してみました。要約する行数は7行、各々の要約文の長さは10文字以上になるように設定した結果が以下のとおりです。

 

----------

綾瀬はるかの本名や年収は?熱愛中彼氏と結婚?髪型がかわいい – ロバ耳日誌 https://robamimireport.com/ayaseharuka-honnmyou/
綾瀬はるかの本名は?
綾瀬はるかさんの本名は蓼丸綾というみたいですよ.
読み方は「たでまる あや」です.
綾瀬はるかの年収はどのくらい?
綾瀬はるかさんはほぼ毎日テレビに出ていますよね.
CM1本あたりのギャラは4500万円ですから、CMだけで7億2000万円ですよ!
 
 
ドラマや映画にも出ていますから、10億円を超えていると考えられますね.
ちょっと綾瀬はるかさんの髪型画像を集めてみました.
綾瀬はるかさんは前髪を常に短く作るのが特徴ですよね.
童顔の人が真似すると幼くなりすぎてしまうので注意が必要です.

---------

 

本名と推定年収と髪型に関する要約が綺麗に抽出出来ました。彼氏については結論が出ていなかったからかAI様は完全にスキップしてしまいました。

 

【機能について補足】

生成された要約はクリップボードに自動的にコピーすることが出来ます。キュレーションサイトを圧縮して呟くという賽の河原遊びも楽々出来ることでしょう。

 

要約分に対応する文字をハイライトする機能も実装していますが、jqueryの仕様なのかhtmlタグが入っていると上手く機能しません。解決方法知ってる人教えてください><

 

また、本家IMAKITA同様、多言語にも対応しています。英語、フランス語、スペイン語、ドイツ語に対してもテキストから原語を自動で推定し、要約を生成してくれます。

 

形態素解析(文章の単語を区切る機能)の精度が悪いため、恐らく本家に比べると精度がやや劣ります。

 

【ソースコートと論文】

IMAKITA on Chromegithubでコードを公開しています。また、技術的解説文書もアップされています(日本語版の解説記事も書く予定ですが予定は未定ですorz)。

新時代のクラスタシステム ~MultiponderとPreponder~

第29回世界コンピュータ将棋選手権に参加された皆様、感染してくださった皆様、改めてお礼申し上げます。Qhapaq di molto(QDM)は5位入賞という結果を残すことが出来ました。

 

本大会でQDMはPreponderを使ったクラスタシステムを構築しました。Preponderは前年度優勝ソフトであるHefeweizenが採用したMultiponderを発展させたシステムです。本稿ではQDMの躍進の屋台骨となったPreponderについて解説していきます。

 

ソースコードは此方からどうぞ

github.com

 

【システムの概要】

【Ponder】

コンピュータ将棋におけるPonderとは相手の手番中に先の展開を予想しておくことを意味します。人間の将棋でも予想外の手に慌てふためいたり、逆に自分の手を相手に読まれた結果、とっておきの一手が即指しで返されてしまったりすることがあると思いますが、コンピュータ将棋でも同様のことが起こります。

従来の将棋ソフトの多くは自分の指し手を決める際に相手の返しの手を一つ予想しておき(予想手)、相手の手番中に予想手を指された後の局面を検討します。予想手が当たれば相手の思考時間を自分の持ち時間に加えられるし、外れればその読みは破棄します。予想手の一致率はソフトの相性にもよりますが5割強程度と考えられています。

f:id:qhapaq:20190507190246p:plain

Ponderのイメージ図

 

【Multiponder】

一方、Multiponderでは予想手を複数用意し、それぞれの予想手について先の展開を読みます。予想手を5〜6程度用意すればほぼ全ての局面で相手の手を当てることが出来ます。複数の計算ノードを用意し、それぞれに局面を割り振ることで、実効的な持ち時間を3割程度増やすことが出来ます。

f:id:qhapaq:20190507190205p:plain

Multiponderのイメージ図

【Preponder】

PreponderではMultiponderに加え自分の手番中に2手先の展開を読ませることで実効的な持ち時間をさらに増やすことができます。2手先を読む都合上、Multiponder程の的中率は出ませんが、当たると時間を大幅に稼ぐことが出来ます。Preponderが外れた(自分の手が予想手と一致しなかった)場合はPreponderはMultiponderと等価になります。

 

f:id:qhapaq:20190507190145p:plain

Preponderのイメージ図

【実験結果】

Qhapaqの自己対局でPonder、Multiponder、Preponderを比べた所、PreponderはPonderだけの時に比べ実効的な持ち時間が5割増し程度になることが解りました。大会当日でもPreponderによって序盤から長考をした結果、有利な戦型持っていけたケースが多かったと考えています。

f:id:qhapaq:20190507190112p:plain

Ponder, Multiponder, Preponderの比較

 

数値計算屋がFortranを捨てるべき3つの理由

パンチカード時代の負の遺産として数値計算系を中心に今も生き続けている言語Fortran。本稿では仮に数値計算用途であってもFortranを使うべきでない理由を説明することで、悪しき文化の終幕を促進したいと思います。

因みに筆者は量子系を中心にした数値計算を生業としています。C++Pythonがメインですが数値計算ライブラリの拡張などの用途でFortran77も90も触ったことがありますし、Fortran製のライブラリは頻繁に利用しています。

あくまで筆者の経験に基づいたものでありFortranを使っている技術者からすれば反論もあるものとおもいます。

 

【1.教材として不適切である】

Fortranの長所として計算向けに設計されているため、行列や複素数の計算が簡単であるという点がよく挙げられます。確かに、Fortranの計算はC++などに比べ直感的で簡単です。しかし、高度なプロダクトを開発する上でボトルネックとなるのは実装ではなく、エラー処理やバグ取りなどの設計/実装後の処理です(*)。バグ取りという観点においてFortranは最悪です。まずユーザが少ないので些細な文法ミスでも原因を探すのに苦労します。C++であれば大抵のバグは誰かが引いていて何らかの記事があるものですが、Fortranでは逆に、大抵のバグの解決方法はQiitaやstackoverflowには記載されていません。

更に悪いことに、Fortranで書かれ現役で使われているライブラリの多くは前時代的で劣悪なコード設計となっています。変数の文字名が1文字であったり、関数の名前が名前から機能を推定するのが不可能なレベルであることはザラです。例えば行列計算でお馴染みのblasの関数の一つ"sgemv"をsingle精度で計算されるgeneralなmatrixとvectorの積であると初見で理解できる人はいないでしょう。この手のネーミングはコードの長さに厳しい制約があった時代の負の遺産であり、今のコーディング規約的には真似するべきではありません。この他にも、Fortranの規約を守っていないため古いgccでないとコンパイルできない量子計算ライブラリ(**)や、入力ファイル、出力ファイル、中間ファイル(全部で10個以上ある)を全て同じディレクトリに置きたがるディレクトリ汚しなど、負の遺産はデザインやUIにも深く根付いています。即ちFortranは先人から学べば学ぶほどクソコードが再生産されるという悲劇的な仕様を持っているのです。


*自身の経験に加え https://www.quora.com/How-much-time-does-a-programmer-spend-on-debugging などを参考にしています。より統計的なデータがあったら教えてください。

** Quantum EspressoかWannier90のどちらかだと記憶しています。どちらだったかは覚えていません。そして再現実験はやりたくないです許してください。


【2.計算が早い言語としての価値が急激に失われている】

Fortranの第二の長所として計算が高速であることが挙げられます。Fortranは用途を狭くする代わりにコンパイラの最適化が行いやすく、他言語で書かれたエンジンに比べ高速で動作することが多いのです。しかし、計算が早いことのメリットは年々小さくなってきています。

高速化の究極的なメリットは時間の節約です。しかし、計算機の普及と計算手段の増加に伴い、計算そのものの高速さは急激に重要度を失っています。クラウドを使えば計算時間をお金で買うことができますが、コーディングそのものはお金で高速化することは出来ません。前世紀と違い、今は人間の時間のほうがコンピュータの時間よりも遥かに高額です。それ故、計算機言語にも学習がしやすく、再利用できる先人の財産が多いといったユーザフレンドリーさが求められています。コミュニティが小さく、学習環境が劣悪なFortranはこの観点においてライバル候補に比べ遥かに劣っています。

また、昨今の計算のニーズの多様化に伴い、高速化の手法にも多様化の波が訪れています。GPUやTPUの躍進に加え、将来的には量子アニーリングマシンが出てくるかも知れません。Rustのように堅牢性と速度を両立した言語も生まれつつあります。幸い、FortranはまだCUDAのサポートは受けられているようですが、早いといえばFortranと言われる時代は何時終わってもおかしくありません。


【3.Fortranのライブラリを拡張するのにFortranの知識は必要ない】

私自身は量子物理系の数値計算屋としてFortranのライブラリを解析/拡張したことがあります。先人のライブラリの流用はFortranの利用が正当化される数少ないケースです。しかし、Fortranで書かれた100のプロダクトを101にする上でFortranの知識は重要な要素にはなりません。

というのも、先人のライブラリを拡張する上で一番時間がかかるのはコードを書くことではなく、ライブラリの意図を理解することだからです。そして、先人のコードを読む上で重要なのはFortranの知識ではなく、ライブラリの実装が糞であるか否かに依存した運の良さと、クソコードの設計思想を脳内でエミュレートしてコードの意味を忖度する勘の良さだからです。

C++erがFortranのコードを読む上で理解しなければいけない文法はそう多くありません。モジュールの読み込みのルールと、配列のdimensionが可変であることあたりを理解していれば大体読むことが出来ます。コードを書くとなると配列が1スタートであるとか、多次元配列のアクセス順序がC++と異なるとかを覚える(そして苛つく)必要がありますが、コードを読む作業に比べれば誤差みたいなものです。

できるだけ既存ライブラリを書き換えない形で拡張が出来ないかを考え、無理だったら祈りながらコードを読み、書くべきコードが理解できたら検索とコピペを繰り返して実装するぐらいがFortranとの適切(かつ、合理的な)付き合い方だとおもいます。


【4.最後に】

私はFortranを激しく嫌っていますが、Fortranが生み出した様々なプロダクトの恩恵を享受してもいます。素晴らしいプロダクトを生み出してくれた先人たちには感謝しているし、尊敬もしています。ただその一方で、計算機系の研究室に入ったからFortranでプログラミングを勉強するという行為は絶対に避けるべき愚行であると考えていますし、乳歯が生え変わるようにFortranはその役割を次の言語に託し滅びるべき時代に入ったと思っています。

億万長者になった暁にはFortran製のライブラリを滅ぼしてくれる計算系研究者に科研費をばらまくのでその時はよろしくお願いします。いや、それまでに滅んでいてくれFortran

レート4390ぐらい(今のSOTA+20-30)の評価関数orqha1018を公開します

将棋ソフトのレーティングサイト基準で、最強格と言われる評価関数に55%〜60%程度勝ち越せる評価関数orqha1018を公開します。

 

ダウンロードは此方のページからお願いします。

https://www.qhapaq.org/shogi/kifdb/

 

【使い方】

使い方は下記サイトを参考にすると良いでしょう。

migigyoku.com

【主な測定結果】

レーティングはこちら

illqha3(今のSOTA)に対して 278-232

QQR(KPPTのSOTA) に対して 228-96

 

【以下、ポエム】

orqhaはillqha1からの追加学習で作られています。WCSC29のルール的にorqha1018を直接用いることは(流用は勿論、追加学習の元としても、教師生成の元としても) 難しいと思われます。大会ルールで解らない点は大会運営にお問い合わせください。

 

【謝辞】

illqhaの開発者のめきっとさん、測定に協力してくださったロタさん、素晴らしいライバルであるたややんさん、NNUEの開発者であるtnkチームの皆さん、やねうら王の開発者やねうらおさん、その他コンピュータ将棋を盛り上げてくれた皆様にお礼申し上げます。楽しんでいただければ幸いです。

コンピュータ将棋のセミナー@東大 で出てきた Q&A 抜粋

コンピュータ将棋セミナー@東大に参加してくださった皆様、ありがとうございました。

www.issp.u-tokyo.ac.jp

備忘録を兼ねて、セミナーで出てきたQ&A(のうち、比較的単体で理解できそうなもの)を書き下していきます。

 

# 質問、回答ともに解説記事向けに内容を編集しています

# 何となく数学ネタを中心に集めましたが、「この質問も加えてちょ」的なコメントをツイッタか何かでいただければ追記します

 

こうしてみてみると、今回の参加者の数学レベル超高いな......

 

Q. NNUEの非線形性はどのように機能しているのでしょうか?

A. 3駒以上からなる重要な特徴量を扱えている可能性が高いと考えています。表現力として過不足がないかを確かめる方法は現在のQhapaqの研究対象の一つです。愚直にやるならback propagationですが、それで十分なのかなど。

 

Q. 探索部の最適なパラメタは評価関数の質に依存するのではないでしょうか?

A. 依存すると思われます。それ故に、探索パラメタの最適化の高速化は重要な課題です。

 

Q. 過学習回避のために行う、特徴量の出現回数を利用したフィルタリングについて、ノイズの大きさの絶対量ではなく、S/N比を指標としているのなぜでしょうか?

A. 3駒関数では学習にAdaGradを使っていて、目標関数の勾配の絶対量が各ステップの特徴量の変位には影響しないからです。即ち、AdaGradを使わないような問題については別の方法(学習率の調整など)で対応する必要があります。

 

Q. 正規化の代わりにフィルタリングを使う理由はなぜでしょうか?

A. 現状の強化学習の関数の多くが正規化を用いておらず(経験的にそのほうが強い)、極端に少ないデータで学習をする際に正規化を行うと本来消してはいけないデータも消えてしまいかねないからです。

 

Q. 評価関数の教師の質の良し悪しを神の評価値と深く読んだ場合の評価値の差の絶対値で現すとして、その関数の形を明確に定義する(一次関数かも知れないし、logかもしれない)のは困難なのではないでしょうか。その条件下でも出現回数によるフィルタリングは機能すると言えるのでしょうか?

A. 関数の形の定義は困難だと思います。故に、神の評価値と深く読んだ評価値の差が平均値0の分布を持っていることを仮定する必要があります(そんなに無理な仮定ではないと思っています)。この仮定を認めれば、中心極限定理を用いることで、ノイズの大きさをガウス分布に焼き直すことができます。

 

Q. 定跡生成のアルゴリズムから量子アニーリング感があんまりしない気がします

A. 確かにそうですね。モデルを構築する際は定跡の固有状態とか、定跡のエネルギーを決めるハミルトニアンとかを定義していたのですが、最終的なアルゴリズムの形は進化アルゴリズムに近く、アルゴリズムの頑強性を量子アニーリングのアナロジーで確認しているという方が正しいかも知れません。

 

Q. AlphaZeroの論文と比べ、生成された定跡の手が広い気がしますが、学習の長さやランダム項の大きさの違いなどが原因でしょうか?

A. 将棋は囲碁に比べると定跡空間が狭く、相手と定跡が被るリスクが高いです。故に、AlphaZeroのような比較的一般的な戦型は相手にも対策されている可能性があります。大会では相手によって定跡を切り替えることが許されているので定跡の手は広く確保しておくのが大会戦略として実戦的なのです。

 

Q. 持ち時間制御について、序盤中盤終盤の割り振りの他に各手の複雑さに起因した割り振りも必要なのではないでしょうか?

A. その通りです。現在の将棋ソフトの時間の割り振りは、1.残り時間から消費時間の指標値を決める 2.消費時間の指標値から、読み筋のブレの許容値(消費時間の指標値に反比例)を決める 3.探索の過程の中で手のブレ幅モニタし、2の許容値を下回ったら探索を終える という作りになっています。ブレ幅の定義や導出は割愛しますが、消費時間の指標値を一定にすることで、局面の複雑さが変化するような場合でも、各手の消費時間の増加に対する勝率の上昇値は一定にすることが出来ます。

 

Q. 数理を用いてゲームAIに進出する上で問題の難易度を見積もるにはどんな指標がありますか?

A. 合法手の多さ、局面を表現する要素の多さ、エミュレータの作成の難しさが指標になると思います。

東大(柏キャンパス)でコンピュータ将棋のセミナーをやります

【注意】場所が変更になりました

場所 : 東大柏キャンパス物性研究所本館6階 第5セミナー室 (A615)→ 物性研究所本館6階 大講義室(A632)
※:同じフロアの大きい部屋になりました
 

 

嘗て物理を学んだ柏キャンパスに凱旋できるとは感慨深い......

www.issp.u-tokyo.ac.jp 

日程 : 2019年1月28日(月) 16:00 - 17:00
場所 : 物性研究所本館6階 大講義室(A632) (同じフロアの広い部屋に変更になりました)
注:柏キャンパスです。千葉です。駅から遠いです。徒歩だと20分位掛かります
注:誰でも参加できます。よろしやす
 
【講義の内容】
コンピュータ将棋の数理をお題にゲームAI開発に殴り込む方法を紹介したいと思います。数学レベル的には大学生〜大学院生を主な対象としています。
 
昨今のAlphaZeroなどの躍進で、機械学習強化学習を知っている人が増えている一方で、問題への優れた知見(例えば将棋の有段者であるとか)を持つ人や、高度な数学を使いこなせる人がAI開発に乗り込むのには未だ大きな課題が残っています。
 
私が特に足りていないと感じているのは、AI開発における水面下の戦いに関する情報です。水面下の戦いは悪く言えばマニアックですが、マニアックだからこそ、多様な人材が多様なスキルを駆使して殴り込む余地があるとも言えます。
 
そこで本公演ではQhapaqがこれまで水面下で使ってきた小技を中心に、コンピュータ将棋に潜む豊かな技術課題を紹介していきたいと思います。
 
 
【スライドのサンプル】
# 既に60ページぐらい創っていますが現在未だ改良中です