第29回世界コンピュータ将棋選手権振り返り【コンピュータ将棋】

私が開発しているコンピュータ将棋AIの「ねね将棋」は2019年5月3日開催の第29回世界コンピュータ将棋選手権に参加しました。

ソースコード・バイナリをこちらで公開しました。

github.com

大会直前と本番をちょっとだけ振り返ります。

数週間前の準備

AWS(クラウド)を使用して対局するため、2週間前ごろにサーバ上の環境をセットアップしました。 ローカルには1GPU環境しかないのですが、実装上はAWSの8GPU環境でもちゃんと動作するように実装したつもりでした。 しかしながら動かしてみると原因不明のクラッシュが生じることがわかりました。 応急処置として、マルチスレッドで1スレッド=1GPUへ対応していたところ、GPUごとにプロセスを立ててソケット通信で結合することにしました。 なお、GPU評価の結果を処理している間に同じGPUで次の評価を開始するよう、1GPUに対して2つのプロセスを立てることでスループットが上がります。 TCP/IPで通信しているので、やろうと思えば複数のマシンで分散計算させることも容易です。

1次予選当日準備

f:id:select766:20190505182601j:plain
設営風景

これで動作確認できていたのですが、当日朝に会場で動作確認をしていると、1GPUあたり2プロセスを立てて動かすとなぜか起動しなかったり、探索終了予定時間になってから指し手を出力するまでに5秒以上かかるという不具合が急に生じました。これでは動作不良で負けになる恐れがあるので、1GPUあたり1プロセスに下げることにしました。 もともと最大3万nps程度出ていたところ、この変更で2万台に落ちてしまいましたが仕方ありません。 ともかくこれでテスト対局を乗り切りました。

ソフトのトラブルだけでなく、インターネット回線の不良やAWS側でGPUインスタンスが不足する事態もあり得ます。 非常時対応としては、ローカルの端末でCPUで方策関数だけで指し手を決定するものを用意していました。

対局

過去の大会では初戦に勝ったことはなかったのですが、今回は最初の3戦に連勝し、幸先良いスタートとなりました。

勝率が近い相手同士で対局が組まれるので、ここからは厳しくなってきました。

Daigorilla戦で負けたのち、ついにDeep Learning勢のdlshogiと対局になりました。

dlshogiの山岡さんは1年中強化学習の計算をしていたとのことで、評価関数が優れていたようです。公式戦初対局はねね将棋の負けとなりました。

7回戦は同じくDeep Learning勢、フランスから参戦したCrazy Shogi戦となりました。

棋譜って英語でなんて言うのか?」など困惑しながらつたない英語で開発の状況、使っているマシンなどを教えてもらいました。

Crazy Shogiは強化学習を3週間行ったそうです。前回大会にも出場されていて1年間時間はあったが、囲碁、連珠などいろいろなゲームに挑戦しているので将棋に割けた時間がその量だったということらしいです。

90手目ぐらいまで拮抗し、最後にCrazy Shogi側に悪手が出たようでねね将棋の勝利となりました。

7戦目までで5勝2敗、もし最終戦で勝てば2次予選に進めるという状況でした。しかし最終戦の相手はやねうら王。レートに1000以上の開きがあり、とても勝てそうにありません。

千日手を願いました。途中でやねうら王が一瞬千日手を読んでいたのですが、打開されてしまいました。60手目ぐらいでねね将棋に悪手が出て、負けてしまいました。それでも129手まで粘ることができました。

負けてはしまいましたが、大型新人との対局、楽しかったです。

終結果は5勝3敗。順位は10位。ソルコフ(対戦相手の勝ち数の合計)でほかの5勝3敗ソフトに敗れ、2次予選には進めませんでした。

来年に向けて

去年に引き続き、ぎりぎり2次予選に進めませんでした。悔しいです。改良できるところがたくさんあるので、今後も開発をしたいと思います。多忙になるので開発再開は秋になりそうです。

去年と比べ、開発用のシステムとしては自己対局での強さ評価、学習率の自動調整などの機構を作ったものの、直接的に強さに関与する部分はあまり作れませんでした。評価関数モデルをより大きなものにした、末端ノードでの詰み探索を加えたというぐらいです。

評価関数が、今使っている教師あり学習ではそろそろ限界と思われます。読み抜けて悪手を指し、それをとがめられると一気に評価値が下がるという対局が本番にもありました。valueはある程度正しくて、policyが間違っているものと思われます。選択的探索を行う以上、間違ったpolicyでは計算リソースによらず一定以上の強さを望めません。この穴を埋めるには強化学習をすべきでしょう。

まずは強化学習の基盤を整えたいと思います。しかし、計算リソースを考えると評価関数での勝負に持ち込むのは厳しいものがあるので、探索部にも手を加えていきたいと思います。

このたびは対局してくださった方、また運営の方々に感謝申し上げます。次回があればどうぞよろしくお願いいたします。

技術書典6 振り返り(出展側)

2019年4月14日、池袋サンシャインシティにて開催された技術書典6にサークル「ヤマブキ計算所」として出展したので、参加記録を書きます。

今回の頒布物はBOOTHでも販売中ですので、会場には来られなかったが興味があるという方は是非ご利用ください。(PDF版のみ)

PokéAI #2:初代3vs3編 - select766 - BOOTH PokéAI #1:初代1vs1編 - select766 - BOOTH

技術書典へは昨年10月の第5回に引き続き、2回目の出展となります。まだまだ初心者ではありますが、初回よりはスムーズに準備できました。

タイムライン

日付 できこと
2018-11-01 技術開発開始
2019-01-06 開催要項発表
2019-01-20 出展申し込み
2019-02-05 当選
2019-03-05 技術開発ほぼ終わり、執筆開始
2019-03-17 一般向けサークルリスト公開
2019-03-23 第1巻増刷入稿
2019-04-02 第2巻入稿、DLカード発注
2019-04-14 イベント当日

技術開発~参加申し込み

私のテーマはポケモンバトルのAI開発なので、まず出版に値する技術を開発する必要があります。既存フレームワークの解説書とはこの点が違っていて、開発がうまくいく見通しが立ってから出展申し込みをしました。

当選~執筆

2月5日に出展サークルの抽選結果が発表され、当選したので出展できることになりました。まだこの時点では技術開発は完了していなかったので、2月いっぱいは開発を続行しました。

3月5日にほぼ開発および実験が完了したので、執筆を開始しました。

執筆環境は前回に引き続きRe:VIEWを用いました。バージョンが2から3に上がっていたので、新しい3に対応して執筆することとしました。テンプレートはTechBoosterのものを利用させていただいています。自宅のlinuxマシンでdockerを用いてビルドするよう環境構築しました。

一般向けサークルリスト公開

3月17日にサークルリストが公開され、参加者が気になるサークルをチェックするフェーズに入ります。見逃されてしまうともったいないので、執筆は途中でしたが暫定的な目次を上げておきました。

第1巻増刷入稿

今回の新刊として第2巻を出版するつもりでいましたが、第1巻も需要があると予想しました。前回イベントで完売していたので、 誤植を訂正したバージョンを印刷することにしました。

印刷所は前回と同じねこのしっぽで、20%割引の期間中に入稿しました。

第2巻入稿、DLカード発注

4月2日に新刊である第2巻の執筆が完了し、印刷所に入稿しました。ねこのしっぽの「オンデマンドのぱっく」、表紙本文とも黒1色です。

本文はRe:VIEWで生成したPDFそのままで受け付けてもらえました。 表紙は前回に引き続き、Wordで表と裏を別々のPDFとして作成しました。デザインはあまり変わってないですが、第1巻と見分けやすいよう、灰色のべた塗りを加えました。フチなし印刷をしようと思うと、塗り足しやトンボが必要になってきて技量がないので、それが不要な範囲のデザインとしました。

f:id:select766:20190416185819p:plain:w100
第1巻表紙
f:id:select766:20190416185841p:plain:w100
第2巻表紙

また、完売に備えてDL(ダウンロード)カードを作成することにしました。前回はコンビニで普通のコピー用紙に印刷したレシートみたいなものだったのですが、さすがに見劣りするので名刺型のカードを作成しました。 ねこのしっぽで発注しようと思うとphotoshop形式のファイルが必要なのですが、持ってないのでデザイナーではない素人向けの名刺印刷サービスを活用することにしました。 選定した業者はラクスルです。Webブラウザ上で画像や文字を並べてデザインする機能があり、デザインソフトが不要かつファイル互換性等のトラブルが起きないというメリットがあります。 表紙画像を表に、ダウンロード用のパスワード等の情報を裏に記載しました。片面印刷のほうが安いのですが、購入者が戦利品画像を上げられないというデメリットが生じてしまうので配慮しました。 名刺印刷は競合が激しく、かなり安いです。1枚当たり10円未満で作れました。

f:id:select766:20190416191746j:plain
DLカード

DLカードは写真のような内容です。PDFを暗号化zipに入れて公開し、URLと解凍用パスワードをカードに記載する単純な方式です。

当日

イベント当日です。ワンオペは厳しいので、知人に交通費+時給を出して売り子として来てもらいました。

印刷した本はブースに直接搬入されているので、開封の儀を執り行いました。期待通りの出来でした。1点だけ気になるとすれば表紙の灰色のベタ塗りがちょっと難しい点でしょうか。

11:00に頒布開始となりました。入り口からかなり遠く、まっすぐうちのブースへ向かっても2分ぐらいはかかるので、最初の数分はほとんど人がいませんでした。その後はかなり混雑しました。 14:27に第1巻の紙版が売り切れました。次に15:02に第2巻の紙版が売り切れとなりました。その後もDLカードの頒布は続けましたが、やはり紙志向が強いらしく、完売直後に2人に立て続けに紙版がないなら買わないと断られてしまいました。 17:00に終了となりました。まだ会場にはたくさんの一般参加者がおり、本当に終わっていいのかわからないという感じでした。

振り返り

被チェック数の推移を記録しました。被チェック数というのは、公式サイトのサークルリスト上で当サークルにチェックを付けた参加者の人数です。

f:id:select766:20190416194657p:plain
被チェック数推移

今回はサークルリスト上で最後のほうに配置されていたためか、前回より被チェック数は少なめになりました。イベント終了直後の時点で169となりました。

第1巻は50冊、第2巻は100冊印刷しました。チェック数が少なめなので売り切れないと思ったのですが、売り切れてしまいました。紙版が欲しい方のご期待に沿えず申し訳ございませんでした。

DLカードのほうは合計40枚程度しか売れず、ある意味大爆死になりました。印刷費は回収できているので問題はありません。

新刊である第2巻ばかり売れるというわけではなく、第1巻だけを購入するという方も多かったです。第2巻から読んでも理解できるようには書いたのですが、今後シリーズが長くなった時にどうするかが悩ましいところです。毎回同じような導入を書くと既存の読者にとっては冗長になってしまう一方、全巻揃えないと最新の話題を理解できないというのも新規読者にとってよろしくないです。既存の読者でも半年経過すれば内容を忘れてしまうでしょうから、導入の重複は冗長でも必要だろうと考えています。

次回に向けて

すでに書いたようにAI開発が進まないと書く内容がないので、まずはそれが課題となります。

技術書典7があればまた出展したいですね。コミケも人生で一度ぐらい出展してみたいので、検討してみます。

最後になりますが、当サークルのブースへお越しいただいた皆様、ありがとうございました!

MCTSでの時間管理【コンピュータ将棋】

ねね将棋では探索アルゴリズムとしてMCTSを採用しているのですが、今まで1手あたりの思考時間は一定でした。 その結果として、飛車先の歩を交換するタイミングなど、有効な手が1つしかない場合でも10秒以上思考してしまって見栄えが悪いです。

明らかな手がある場合にはさっさと指すようにしたいので、どうすれば実装できるか考えてみました。

αβ法による反復深化探索だと、深さが1つ進むたびに読み筋や評価値の変化を指標として定める方法があるようです。次のリンクは、やねうら王での実装箇所です。 https://github.com/yaneurao/YaneuraOu/blob/9f9fb248177b44046d4f26c6b1480502310695bc/source/engine/2018-otafuku-engine/2018-otafuku-search.cpp#L2738 言葉にするのは簡単ですが、229, 715などのマジックナンバーがあって、これを調整するのは大変そうですが…

MCTSの場合は選択的に探索を行うため、ゲーム木全体の深さが1増加するごとに停止を判定するというやり方が取れません。 どういうときに探索を終了していいか考えると、指し手が今後変化する見込みがないときです。 MCTSでの指し手の決定方法は、ルートノードの子ノードへの訪問回数が最大のものを選択します。 つまり、「訪問回数が最大のノード(bestmove)の訪問回数 >> 訪問回数が2番目のノードの訪問回数」となっていれば指し手が変化する見込みが低いといえるでしょう。

実際に探索を行って、一定探索ノード数ごとのbestmoveを記録しました。そしてある時点でのbestmoveが将来的に変化したかどうかを調べました。 訪問回数を比較するにあたり、絶対数と比率の2つの軸があると考えられます。 そのため、全ての子ノードへの合計訪問回数Nと、bestmoveの訪問回数/Nごとに、合計訪問回数が増えた時の変化をプロットします。

bestmoveの変化は563種類の異なる互角局面からスタートし、それぞれ262144回探索して記録しました。

f:id:select766:20190406185718p:plainf:id:select766:20190406185732p:plainf:id:select766:20190406185739p:plain

グラフの左端が現在の合計訪問回数、探索が進むと合計訪問回数が右に進んでいきます。探索が進むにつれて、bestmoveが変化する確率が上がっていきます。 1つの局面に対して変化するかしないかは決定的なものですが、局面によって初期条件が同じでも結果が違うため確率であらわすことになります。 線は現在のbestmoveの訪問回数/全ての子ノードへの合計訪問回数の範囲ごとに分かれています。 例えばprob=0.9~1.0となっているのは、90%以上の探索が現在のbestmoveに向かっており、安定している状況です。 このような状況では、将来的にもbestmoveが変化する可能性は低いという順当な結果になります。 逆にprob=0.1~0.2は、5つ以上の指し手候補で迷っている状態なので変化する確率が高いです。 なお、一度変化してから元に戻ってきても変化したとして扱っていますので、必ず右上がりの曲線になります。 現在の合計訪問回数が多ければ、それだけ変化する確率は全体的に下がります。

このグラフを何らかの関数で近似してやり、残り思考時間が尽きるまでにbestmoveが変化する確率が十分低いと判定すれば探索を終了できます。

今回の実験で計測した範囲よりも大会本番のほうが長時間の対局になるので、外挿しても大きく乱れないような単純な関数にする必要があります。 これを満たす関数として、3つの特徴量「bestmoveの訪問回数/N」・「log2(現在の合計訪問回数)」・「log2(将来の合計訪問回数-現在の合計訪問回数)」を入力として、bestmoveが変化する確率(0~1)を出力する線形モデルを設計しました。学習はロジスティック回帰としました。

学習された関数をプロットします。

f:id:select766:20190406191839p:plainf:id:select766:20190406191850p:plainf:id:select766:20190406191857p:plain

測定結果を近似できているような気がしなくもありません。

ねね将棋にこのモデルを組み込んで、指し手が変化する確率が5%以下になったらすぐに指すよう実装しました。 定性的な結果として、わかりやすい局面では早めに指すという挙動が実現できました。

時間管理の本来の目的は、難しい局面で持ち時間を多く使うことで勝率を上げることです。 しかし、これを実現するのは結構難しいです。ちょっとやってみてわかったのですが、指し手が変化しない場合でも無駄に探索を行ったほうが強い場合があるようです。 一見無駄な探索でも、置換表に結果が残るため、将来の思考の時に役立ちます。 現局面に対する指し手が確定した時点で打ち切ることを続けていると、時間を余らせて負けるという問題が生じてしまいます。 この対処のため1手あたりの思考時間の基準値を引き上げる(やねうら王で言えば"SlowMover")必要があるのですが、持ち時間の絶対量に依存するうえ、ponderを行う場合は対局相手の時間の使い方にも依存するためまともに調整できません。

結論としては、定性的に賢く見えそうなので実戦投入するが、定量的に強さに寄与しているかは測定不能ということになります。

技術書典6 ヤマブキ計算所(こ35) おしながき

技術書典6での当サークル「ヤマブキ計算所」の頒布物をお知らせします。

f:id:select766:20190405131320p:plain
技術書典6おしながき

新刊として「PokéAI #2:初代3vs3編」を発行します。ポケモンバトルの戦略を人工知能に考えさせるというテーマで技術開発を行った成果を掲載しています。 第1巻との違いはバトルのルールが1vs1から3vs3に拡張され、より一般的に遊ばれているルールに近づいたことです。技術・結果ともに新規の内容となっています。 第1巻から読むことを推奨しますが、第2巻だけでも必要な基礎は解説しています。

技術書典5の既刊「PokéAI #1:初代1vs1編」は完売していますが、増刷の上頒布いたします。

いずれも紙の本は1冊500円です。電子版(PDFダウンロードカード)は1冊300円です。 第1巻については、電子版のみとなりますがBOOTHで今すぐ購入可能です。PokéAI #1:初代1vs1編 - select766 - BOOTH

支払いは現金と技術書典かんたん後払いに対応します。

※かんたん後払いアプリの初期設定は当日だと困難な場合があるので、前日までにお願いします。

イベント公式サイトの当サークルの情報はこちら: techbookfest.org

それでは4月14日、池袋サンシャインシティ、配置「こ35」でお会いしましょう。

「ポケモン」のアクセント記号【PokéAI】

技術書典6向けの本の執筆をつづけているのですが、重大なことに気づきました。

英語版ポケモンの公式ロゴがこちら。公式ページより

f:id:select766:20190323153044j:plain
ポケモン英語公式ロゴ
(ロゴ部分だけの大きな画像が公式サイトになかった)

ところで、技術書典5で発行した本の表紙の上部がこちら。

f:id:select766:20190323153403p:plain
技術書典5表紙

…おわかりいただけただろうか。

アクセント記号のついた「e」が「é」と「è」で異なっています。

表紙の4文字目で間違うやつおる???

点が右上から左下に向かうアクセント「é」が「アキュート・アクセント」でポケモンの「e」に使う記号。左上から右下へのアクセント「è」は「グレイヴ・アクセント」という別物らしい。違いを認識しておらず、誤植になってしまいました。違和感を持たれた方がいれば失礼しました。

今後は「PokéAI」で統一していきます。旧刊は完売していますが、誤植訂正版を技術書典6で若干数増刷して頒布しようと考えています。 頒布物情報は技術書典6のサークルページで更新していきますのでご確認ください。

CNNの複雑さとnpsと棋力【コンピュータ将棋】

CNN (Deep Learning)ベースの評価関数を使った将棋AIをチューニングするにあたり、難しい点の1つが評価関数の複雑さ(計算量)の調整です。

層やチャンネルの数を増やせば静的評価の精度は上がるものの、計算時間が増加するため探索に組み込んだ時の評価局面数(nps=node per second)が下がってしまうトレードオフにあります。

そこで、いくつかのモデルを学習させ、同じ探索ノード数又は探索時間における強さの比較を行うことにしました。

モデル構造は、3x3 convolutionを2つ重ねたResidualブロックを基本ブロックとして、19ブロックまたは39ブロック重ねたものです。ブロック数*2がconvolution層の数ということです。チャンネル数は128,192,256としました。AlphaZeroと類似の方式で、盤面を入力として評価値と各指し手の確率を出力します。探索はMCTSで行います。

モデルの学習はやねうら王のサイトで配布されていたshuffle_sfen1.7zを用いて教師あり学習としました。

強さの評価は、探索込みで詰むまで対戦させた勝敗で行います。対戦開始局面は互角局面集2017-05-19を使い、100局で統計を取りました。

まずはノード数を固定し、モデルを変更した場合の結果です。

チャンネル数 ブロック数 ノード数 基準に対する勝率[%]
128 19 4096 (基準)
128 39 4096 74
192 19 4096 75
192 39 4096 80
256 39 4096 91

モデルが複雑になるほど勝率が上がる傾向が見て取れます。

次に、モデルの計算量に反比例してノード数を減少させた場合の結果を示します。一定の制限時間で指す場合の強さに相当するものです。 計算量ですが、理論値で扱います。チャンネル数がN倍になればN2の計算時間、ブロック数がN倍になればN倍の計算時間がかかると考えます。 チャンネル数1.5倍の場合は2倍の計算時間とみなしました。

チャンネル数 ブロック数 ノード数 基準に対する勝率[%]
128 19 4096 (基準)
128 39 2048 49
192 19 2048 53
192 39 1024 24
256 39 512 12

基準とした128チャンネル、19ブロックのモデルに対し、計算量2倍のモデルは強さがほとんど変わらないことがわかりました。「仕事の原理」みたいで面白いですね。 一方で2倍より複雑なモデルでは明らかに弱くなってしまっています。モデルの予測性能が頭打ちになり、探索量の不足による影響のほうが大きくなっているものと思われます。

ここまでの結論としては、モデルを複雑にした場合、計算量を無視すれば棋力が上がるが、計算量を考慮するとあまり大きくするのは得策でない、ということが言えます。

ただし、実際のGPUで計算する場合、小さなモデルは計算コアが余ったり制御部分のレイテンシが相対的に大きくなったりして、理論値ほど大きなモデルは不利ではないという実情があります。 本番マシンは高価なため強さの測定までやることは現実的ではありませんが、純粋なnpsを測定しながらパラメータ調整を進めたいと思います。

2019-03-09 20:19 読者の指摘によりチャンネル数とブロック数が逆になっていた誤植を訂正。

技術書典6 当選しました

2019年4月14日に開催される技術書オンリーイベント技術書典6」に当選しました。 サークル名は「ヤマブキ計算所」です。

2019-02-20追記: 配置は「こ35」に決定しました。

前回に引き続き、ポケモンバトルの戦略を人工知能技術を用いて開発する本を頒布する予定です。 今回の目玉は、ポケモンを3体ずつ出し合う3vs3ルールへの対応です。 1vs1の時と比べ、パーティ編成の自由度が大きく増加、行動選択にも「交代」という要素が加わります。

今までの成果は過去の記事で紹介しています。行動選択部分が不十分なので、2月中は技術開発を続行し、執筆に臨もうと考えています。

前作はPDF販売中ですのでよろしければご覧ください。 select766.booth.pm