機械学習周りのプログラミング中心。 イベント情報
ポケモンバトルAI本電子書籍通販中

同人誌をコンビニで印刷してみた

明日からコミケコミックマーケット)が始まりますね。 私は出展しないのですが、紙媒体で発行する雰囲気を味わうためだけに先日オンラインで公開した同人誌select766.hatenablog.comをコンビニで印刷してみました。 紙媒体の冊子を量産する際のノウハウが少しだけ得られました。

セブンイレブンのコピー機がインターネットにつながっており、ネットサービス ネットプリント で登録したPDFファイル等を印刷することができます。

ユーザ登録して原稿のアップロードまで10分ぐらいで簡単にできました。コピー機に入力する「予約番号」がメールで来ます。

予約番号をコピー機に入力し、印刷。

f:id:select766:20171228143035j:plain

ホッチキスは別途必要です。コピー本らしい仕上がりになって満足です。

ただ、このやり方だとちょっとコストが高く、B5サイズ27ページ(紙は14枚)で540円かかりました。1ページあたり20円です。 会場で配布するものを製作するなら、データをUSBメモリで持参(ネット経由は単価が高くなる)し、B4サイズに小冊子形式で印刷して折ることで、1ページあたり5円まで下げられます。 ただし、紙を折り曲げて作った冊子をホッチキス止めする「中とじ用ステープラー」がないと不便です。Amazonで500円ぐらいで買えるようです。

セブンイレブン(というよりは印刷機供給元のゼロックス)は公式で同人誌印刷のやり方を解説しているようですね。機会があったら試してみたいと思います。 セブン‐イレブンのマルチコピー機で同人活動をもっと手軽に・もっと楽しく!

PokèAI ~人工知能の考えた最強のポケモン対戦戦略~

2017年も残すところあと1週間。皆様いかがお過ごしでしょうか。

クリスマスイブが暇だという方のため(?)に、ニッチな読み物を用意しました。

人工知能に「ポケモン」の戦略を考えさせたらどうなるか、というテーマで薄い本を書きましたので、興味のある方はぜひ手に取っていただければと思います。無料のPDFです。

次のリンクからどうぞ。 https://github.com/select766/pokeai/releases/download/book-201712/PokeAI-201712.pdf

発行所の「ヤマブキ計算所」ってのは深い意味はなくて、今回のためにつけた一人サークル名のようなものです。

第5回将棋電王トーナメント総括(本番編)

2017年11月11日から12日にかけて、ドワンゴ日本将棋連盟主催の「第5回将棋電王トーナメント」に「ねね将棋」というソフトで出場しました。この記事では、東京・六本木の「ニコファーレ」で行われた本番の感想などを述べます。

ソフト開発に関しては、以前書いた記事をご覧ください。

select766.hatenablog.com

戦績としましては、ねね将棋は、予選で3勝5敗となりました。予選落ちです。

前日準備

大会前日(金曜日)から会場にはマシンが用意されており、将棋ソフトのセットアップが可能でした。参加は任意ですが、時間が取れたのでこの日に会場でセットアップを行いました。

依存ソフトウェア問題

C++製のソフトだと、実行バイナリと評価関数ファイルを設置するだけで終わることが多いかと思います。ねね将棋はPython製で依存するライブラリが多いため、会場でセットアップするための事前準備が必要でした。会場でのネット環境が不明だったため、ライブラリをオフラインでインストールできるようにあらかじめダウンロードしてUSBメモリに入れて持っていきました。最近のソフトはインストーラがネット接続を前提としている場合が多く面倒でした。

結果的には会場のマシンからかなり高速なネット接続が可能で、そこまで準備することは必須ではありませんでした。本番対局中だけネット接続を切断するという運用がなされていました。

依存ソフトウェアの種類が多いため30分ほどはかかりましたが、事前準備をしっかりしていたため、会場でのセットアップと動作確認はすんなり進みました。Linux利用勢はここでOSの入れ替えが必要なので大変そうでした。

予選(11/11)

9:00ごろ会場入りしました。テスト対局を経て本番に臨む準備が整いました。ソフトのトラブル対応を見越してか時間には結構余裕が取ってありました。ほかの開発者と交流していればそんなに暇という感じではありませんでした。

会場はこんな感じです。

f:id:select766:20171214081828j:plain

第1局 vs Ponanza

初戦は誰と対局になるか事前に知らされておらず、いきなり対局が始まるという状況でした。

開始直後の表示がこちら。

f:id:select766:20171214081703p:plain

お、おう。

Ponanzaに勝てるわけがないので、ある意味プレッシャーは減りました。バグでおかしな挙動をしたり30手で詰まされたりしなければOKという意識です。

Ponanzaは山本さんではなく、今回新たに参加された大渡さんが改良および本番の操作をされていました。従来通りの高速な探索部と深層学習を組み合わせて強化されたそうです。極限までチューニング済みの探索部に、鈍足な深層学習を組み合わせるのは難しい仕事だっただろうと想像します。

対局は、Ponanzaが1手ごとに着実に評価値を上げていきねね将棋の負けとなりました。偶然にもPonanza引退の大会で対戦できたことを光栄に思います。選手権だとシードがあるので強いソフトと弱小ソフトと当たることはそもそもなく、貴重な機会でした。

第2局 vs Novice

各局の対戦相手は、それまでの勝ち数が同じになるように組まれます。ここでは1敗同士の対戦になりました。

Novice戦。Noviceは探索部の高速化を重視されているそうです。

35~45手目でねね将棋の指し手が迷走し、一気に敗勢となり2連敗となりました。

第3局 vs 十六式いろは改

ここまでねね将棋は2連敗。1勝はしたいという目標を掲げていたので、焦ってきました。

十六式いろは改戦。十六式いろは改が先手で、いきなり定跡(やねうら王の標準定跡を使用しています)を外されたためねね将棋が2手目を即指しせず、バグったかと焦りました。

十六式いろは改は、相手が動かした駒の周囲にある自分の駒を動かすというルーチン(!?)で動いているそうです。ねね将棋が8五歩と飛車先を伸ばすと、8六歩と応じてくる独特すぎる棋風でした。

飛車先をそのまま突破し、20手で詰みに至りました。ねね将棋の初勝利です。

f:id:select766:20171214081743j:plain

開発者の方が楽しそうにお話しされていて、対局の勝ち負けだけではなく楽しむことも大事だと改めて思いました。

第4局 vs TMOQ

TMOQ(「とくだいもっきゅ」と読むようです)戦。

この間にニコ生に出演。阿部先生に(ソフト名の元ネタの)ねねっちネタを拾えてもらえて満足。

対局のほうは悪手で一気に形勢が悪くなり、そのまま負けました。

第5局 vs Girigiri

Girigiri戦。

Girigiri側が飛車を活用できず、ねね将棋が徐々に評価値を上げる初の展開でした。

Girigiriは数手先の負けを見切ると投了ではなく反則負けをするというちょっと変わった仕様らしく、58手目でGirigiriの反則負け。棋譜解析では4手で詰む局面でした。

第6局 vs CGP

CGP戦。

CGPはしっかり読みを実装されているらしく、順調に評価値を稼がれてねね将棋の負けとなりました。

評価関数がなんであれ、探索部がしっかり実装されているソフトは強敵です。

第7局 vs にこあ将棋

にこあ将棋戦。

にこあ将棋が先手で、初手5八玉。またいきなり定跡を外れる展開でした。

早々ににこあ将棋が角を捨ててしまい、一気にねね将棋が駒を成る展開となりました。ねね将棋3勝目。

第8局 vs なのは

なのは戦。

24手目まで定跡が続く対局でした。

50手目で事件が起きました。ねね将棋がクラッシュし、時間切れ負けとなりました。

ログを見たところ、読み筋が千日手になった場合に置換表の参照部分がおかしくなることがあるようです。開発中には起きなかったバグで、痛恨の敗戦となりました。棋譜解析によれば互角の局面で、最後まで指したいところでした。

伝統あるなのはとの対局で、強さ以前のソフトの品質についてもっとよく考えなければいけないと学びました。

決勝トーナメント(11/12)

翌日の決勝トーナメントはニコ生で観戦していました。優勝者決定の前には会場に行こうかと思っていたのですが、体調が思わしくなく断念。

自分は野田さんの「平成将棋合戦ぽんぽこ」を応援していました。ぽんぽこ vs Ponanza、ぽんぽこ vs shotgunの戦いは特に緊張して見ていました。自分の将棋の棋力は低いですが、西尾先生の解説を聞きながら上位陣の巧妙な手筋に感服していました。

ぽんぽこ優勝、おめでとうございます。

今後に向けて

すでに述べた通り、ねね将棋は予選で3勝5敗となりました。2か月ほどのソフト開発でここまで達成できたことは満足しています。しかしやはり対局で負けると悔しいとも感じました。次はもっと勝ちたい、という気持ちを感じたので、2018年5月に開催されるであろう世界コンピュータ将棋選手権でぜひリベンジしたいと考えています。

深層学習を用いた将棋ソフトの開発技術はまだまだ成熟していません。設定すべきパラメータ、学習のさせ方等に大幅な改善の余地があるでしょう。また、長い手数の詰みを見つけるという点では従来の軽量な評価関数を用いた深い探索はなくならないでしょう。これらの融合というのも大きなテーマになると思います。

最後に、大会主催のドワンゴ様、日本将棋連盟様、大会で対局・交流させていただいた開発者の皆様、そのほかコンピュータ将棋を応援してくださる皆様に深く感謝申し上げます。

第5回将棋電王トーナメント総括(開発編)

2017年11月11日から12日にかけて、ドワンゴ日本将棋連盟主催の「第5回将棋電王トーナメント」に「ねね将棋」というソフトで出場しました。この記事では、ソフト開発の軌跡や本番の感想などを述べます。

開発を始めた経緯

もともと私が将棋ソフト開発に興味を持ったのは「たぬき」シリーズを開発されている野田さんに声をかけられたところがきっかけです。 2016年の世界コンピュータ将棋選手権(WCSC)以降、一応アピール文書には名前が出ていました。 自分は深層学習(deep learning)で評価関数か何かができないかと少し実験はしていたのですが、成果は出ず全く貢献はできませんでした。

2017年WCSCの時点で、深層学習を将棋に応用する試みはPonanza以外ではほとんど成功していないという状況でした。 たぬきシリーズはオープンソースの将棋ソフトを改良して強くするという基本方針で、ベースとなっているソフトが十分強いため、深層学習ベースの弱いモジュールをくっつけてすぐに成功するというのは難しいと私は思いました。 そのため、今回の電王トーナメントでは一人で独立したチームを作り、弱くてもいいから深層学習を中心に据えたソフトを戦わせたいと思い、開発を始めました。 これを思い立ったのが野田さんと電王トーナメントへの出場登録について相談した8月30日でした。最初に基本方針を定めて、9月1日からプログラムを書き始めました。

コンセプト・目標

一人で新しい将棋ソフトを開発するにあたり、そのソフトのコンセプトを次のように定めました。

  • DNNを使った将棋ソフト。
  • GPUを使って局面を評価するのに適した探索機構の採用。

電王トーナメントでは主催者が用意した統一ハードウェアを使うことになっており、2016年の時点でGPUNVIDIA GTX 1060というコンシューマ向けではそこそこ良い機種が搭載されていました。 しかし2016年のPR文書を読んだ限りではだれも使った形跡がなく、2017年に自分(やほかに出場するであろうチーム)が初使用することになるということで、大きな独自性を出せると期待しました。

私はやねうら王などのコードを少し読んだことはあるとはいえ、将棋ソフト全体を書くのは初めてで、またDNNを使うという試み自体が未知の要素だらけです。そのため、次のような現実的な目標を掲げて実装を始めることにしました。

  • 将棋ソフト全体のアーキテクチャを考え、動くものを作ること
  • 自分(ルールを知っている程度の弱い人間)に50%以上勝てること
  • (相手の反則負け以外で)1勝すること
  • 定数時間の0手読み(方策関数の出力そのままの利用)ではなく、持ち時間をちゃんと使って思考すること
  • 会場で他の作者と交流すること

主観的な項目もありますが、これらは結果的に達成することができたと考えています。

一方で、次のような要素は割り切って実装しませんでした。

  • 入玉宣言勝ち
    • 予選でそれをする局面はほとんど現れないと思われるため。
  • 自己対戦での強化学習
    • 既存の強いソフトの棋譜を吸収するだけで手一杯と思われるため。

「優勝」という目標を掲げてしまうと、上記のような要素を実装しなければならず無理が生じていたと思います。

DNN以外に必要なもの

今回はソフト全体を新規実装するわけですから、評価関数以外の部分も実装しなければなりません。次に掲げるモジュールを実装しました。

  • 通信部分
    • USIプロトコルに対応し、将棋所との連携を行う形式にしました。
  • 盤面の表現・合法手生成
    • シンプルに81要素の数値配列で表現しました。
    • bitboard等の高速化はしていません。
  • 既存の定跡の読み込み
    • やねうら王の標準定跡を読み込み、用いることにしました。
    • 定跡はなくても戦えますが、相手が定跡で動いている間に劣勢になってしまうと残念なので搭載しました。
  • 1手詰めルーチン
    • 探索部が全幅探索になっていないため、1手詰めすら見逃すことがありました。そのため評価関数なしで1手詰めだけは探索させることにしました。
    • 実装したのは大会前日。
    • 自分が詰めるほうはできますが、詰められるのを回避する機能までは実装しませんでした。
  • 時間管理
    • 持ち時間を認識して、次の1手の思考時間を決める機構です。
    • 単純に、「残り時間/50+秒読み」という形で体裁だけ整えました。
  • Ponder
    • 相手の手番でこちらも考える機構です。
    • 置換表(一度訪れた局面の評価値をキャッシュするテーブル)の実装ができていたので、相手の手番を自分の手番だと思って置換表の値を埋めるようにしておきました。
    • 自己対戦だと強くなった感じがしないので、何かバグっているかもしれません。

開発言語はPythonを利用しました。Python上で動く深層学習フレームワークChainerを使い慣れており、DNNの処理が重いのでその他の処理がC++より遅くても大きな影響はないだろうという判断でした。 結果的にはPythonで書かれた探索部のオーバーヘッドが意外と効いてしまい、開発終盤で苦労しました。

意外と重要で厄介な合法手生成

評価関数が何であれ、与えられた局面においてルール上次に指せる手(合法手)の生成(列挙)機能は必須でしょう。これがなければ投了すらできません。

WCSCや電王トーナメントの予選を見ていると、結構な頻度で反則負けが起きています。理由は様々だと思いますが、王手放置というのはよく上がる事例です。 評価関数が変で弱いのは仕方なくても、反則負けは絶対したくなかったので最初の時点で確実なものをつくることにしました。

合法手生成を確実に行うためのアイデアは、テストをちゃんと用意するということでした。 そのため、適当な棋譜からとってきた1万局面について、やねうら王で合法手生成を行った結果*1を正解として自分のプログラムと比較する機構を実装しました。 この方針は大成功で、高速化のために何度か合法手生成を書き直してもバグの不安はありませんでした。 開き王手*2、打ち歩詰め等の間違いやすい部分がちゃんとカバーできました。 ほかのソフトの手助けを絶対受けたくないという場合でなければ、フルスクラッチ勢にもかなりおすすめのテクニックです。

ただ、今回は「連続王手の千日手」だけは潰していません。指し手履歴の処理が必要となって盤面クラスだけから算出できないためです。開発中の対局で一度だけ発生しており、あり得ない話でもないので次回は潰しておきたいと思います。

最低限のUSI通信部を組み合わせてランダムプレイヤーを完成させるまでが5日ぐらいかかりました。残り60日ほどあるので大会には余裕で出られるとその時は思いましたが、思考部を書き始めると非常に大変でした。

思考ルーチン

将棋ソフトの思考にDNNを用いる場合、大きく分けて2つの使い方があります。

  • 方策関数
    • 局面が与えられたとき、次に指すべき1手を返す関数です。
  • 評価関数
    • 局面が与えられたときに、先手がどれぐらい勝ちやすそうかを返す関数です。DNNではありませんが、三駒関係などはこちらの部類になります。

最初は方策関数により、一切将来の局面を考えない思考ルーチンを実装しました。これでも動作はするのですが、思考時間を使ってより先の局面を検討することはできません。最終的に大会では、評価関数を用いるタイプの思考ルーチンを用いました。方策関数にも使い道がないわけではなく、探索を進めていくうえでどの手を最初に検討するかという評価に有用なようです(例: WCSC27のPonanza)。方策関数、評価関数を組み合わせるのが理想的ですが、検討が間に合いませんでした。コード上は方策関数を学習・利用する部分も残っています。

評価関数の学習

DNNはAlphaGoでも用いられたConvolutional Neural Network構造とし、盤面をシンプルに表現して入力し、評価値を出力するものにしました。

様々な条件で比較する余裕がなく、以下の内容は十分吟味した結果とはいえないのでご注意ください。

入力形式は空間方向に9×9、チャンネル方向に61のサイズとしました。9×9はそのまま将棋の盤面の形状です。61チャンネルの内訳を表に示します。

チャンネル 内容
0-27 先手・後手それぞれの盤上にある種類の駒が存在する箇所を1
28-41 先手・後手それぞれの持ち駒の種類ごとの枚数(9×9を同じ値で埋める)
42-50 特定の段に該当する箇所を1
51-59 特定の筋に該当する箇所を1
60 すべて1

DNNの構造はConvolutionを13層、fully-connectedを1層としました。Convolutionは3×3 window、64チャンネルです。3層をまとめてResidual構造にしてあります。

厳密なことはソースコードを参照してください。 Chainerのモデル定義 モデルパラメータ

学習は、やねうら王(KPPT評価)を用いてdepth=6で評価値付き棋譜を生成して教師あり学習としました。1億局面分学習に用いました。

損失関数の定義は、評価値を勝率に直して(sigmoid(評価値/600))、L2ロスにしました。本番では使いませんでしたが、この勝率から勝敗をサンプリングして(すなわち、勝率>random()なら1、そうでなければ0)、sigmoid cross entropyで学習することもできました。

棋譜は16手目以降しか含まれていないのですが、初手2六歩などを指せる評価関数が学習できました。一方で、勝勢の時に詰ませに行く、寄せに行くという行動はうまく実現できない感じでした。勝率ベースの損失なので、勝率98%も99%もほとんど区別できなかったのではないか、という疑念があります。

評価関数単独の強さですが、KPPT評価関数(浮かむ瀬SDT4+やねうら王エンジン)と3手読み同士で対局させた結果、DNN 7勝、KPPT 3勝となりました。もちろん同じ思考時間ではまったく勝てないですが、評価速度が圧倒的に遅いDNNを使う意義が最低限担保できたといっていいでしょう。

探索部

学習したDNN評価関数を用いて指し手を決める部分です。

DNNはGPUを用いて計算することに適しており、CPUより10倍以上の高速化が見込めます。今回のハードだと、CPUはCore i7-6700で100GFLOPs程度、GPUGeForce GTX 1080 Tiで10,000GFLOPs程度であり、大幅な差があります。 しかしGPUの性能が十分発揮できるのは、数百局面を同時に評価する場合に限られます。一方で、将棋ソフトで昔から用いられてきた探索手法であるalpha-beta法は1局面ずつ評価値が得られることを前提としており、相性が悪いといえます。

そこで今回は、WCSC27の「芝浦将棋Softmax」のアピール文書で示された"Monte Carlo Softmax Search"という手法をベースにしました。 彼らはCPU上でBonanzaの評価関数を用いて動作させているようですが、ねね将棋ではGPUで動作するように、すなわち多数の局面をまとめて同時に評価できるように実装しました。

アルゴリズムは次のようになります。

データ構造

  • ゲーム木
    • 局面をノード、指し手をエッジとする
    • ノードには評価値が付与される
  • DNNキュー
    • 評価させたい局面を投入するキュー
  • 評価値キュー
    • 局面の評価値を投入するキュー

アルゴリズム

2つのプロセスが同時に実行される。思考時間が尽きたら、思考開始局面の1手先の評価値が最大となる手を指す。

メインプロセス

  1. ゲーム木を末端までたどる
    1. 注目ノードを思考開始局面に設定
    2. 注目ノードが末端ノードなら末端までたどる処理が完了
    3. 子ノードすべての評価値を参照し、重みづけでランダムに次の注目ノードを選択。重みの集合に対してsoftmax関数により選択確率を定める。
  2. 末端ノードから1手指した先の局面をDNNキューに投入
  3. 評価値キューから評価値を取り出し、ノードと対応付ける
    1. ノードの評価値を設定
    2. 親ノードの評価値を、子ノードすべての評価値の重みづけ平均に書き換える。重みはゲーム木をたどるときと同様に定める。

DNNプロセス

  1. DNNキューから局面を取り出し、プロセス内のキューに蓄積。
  2. 一定数の局面が蓄積されたら、DNNで評価値を計算して評価値キューに投入。

概略としては上記のようになります。実際には、置換表を用いたり静止探索を入れたりしてもう少し複雑になっています。

開発上の反省点

  • 合法手生成が遅すぎた
    • 合法手生成の初期実装だと、1局面あたり40msかかるというものでした。DNNを使うならこれぐらい遅くてもかまわないかと最初は思っていたのですが、かなりのネックになってしまいました。GPUの使用率を100%にできなかった大きな原因です。
    • その後、cython実装、C++実装と2度書き換えることになりました。10倍以上の高速化にはなりましたが、中途半端な最適化をしようとした結果時間が無駄になってしまった感触があります。
  • DNNの吟味ができなかった
    • 評価関数本体の構造や学習方法などについて、いろいろな比較検討をする必要がありましたが間に合いませんでした。

次回の記事では、大会本番の様子を報告したいと思います。

*1:角の不成等は合法だが出てこないので注意

*2:駒を動かすことで、飛車などの長い利きが玉にあたる

記事投稿テスト

どうも。select766と申します。

2017年、大学院生活も終わりに近づき、やりたいことをやっておかないと後悔するだろうと思いまして、ネットに公開できるようなクリエイティブな趣味活動を始めようと思いました。

2017年9月からコンピュータ将棋のプログラムを書き始め、先日大会に出場することができました。その際の技術解説を手始めに、将棋に限らずいろいろな記事を書ければよいなと思っております。