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

ポケモン×人工知能 2技関係によるパーティ強さの予測(実験編)

ポケモンバトルAI

手法編からの続きです。

実験

まず、学習データの準備です。パーティを10,000個用意して、別の100個のパーティとバトルさせることにより勝率を求めました。

各特徴量を用いてパーティの勝率へ線形回帰します。 単純な最小二乗法でも学習は可能でしたが、「多重共線性」という問題があるため重み \boldsymbol{w}の要素が1,000以上の大きな値になってしまい、分析が困難でした。 そのため、リッジ回帰という手法を用いることで完全ではないにせよ分析可能な結果を得ることができました。

リッジ回帰の実装はscikit-learnライブラリを用いました。

http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.RidgeCV.html#sklearn.linear_model.RidgeCV

9,000個のデータで学習し、残りの1,000個で評価しました。

まず、使用した特徴量ごとの回帰精度を示します。以前の記事で示したように、Pはポケモンの種類、Mは技の種類です。PMはポケモンとその技の組み合わせを示しています。

P PP M MM PM 決定係数R2
Y 0.388
Y 0.312
Y Y 0.691
Y Y 0.388
Y Y 0.383
Y Y Y 0.847
Y Y Y Y Y 0.874

決定係数R2は回帰の良さを表す指標で、もっとも良い場合で1、最も悪い場合で(回帰先の期待値を定数で出すモデルで)0となります。 ポケモンと技の組み合わせ情報がパーティの強さを予測するうえで有用であることがわかりました。 ポケモンの情報だけ、技の情報だけの場合より、両方の情報がある状況のほうが大きく精度が向上することがわかります。

そして、線形モデルの良い点は、学習で求められた重み \boldsymbol{w}から各特徴量次元の寄与度を測れる点です。 今回、特徴量 \boldsymbol{x}の要素はすべて0か1であり、勝敗({1, -1})に回帰しているため、対応する重みが正の大きな値であればパーティを強くする効果のある特徴、負の大きな値であればパーティを弱くする効果のある特徴であるとみなすことができます。

現在実装されているポケモンは9種類、技は20種類に制限されていることに注意してください。

実装したポケモン：ダグトリオ・フーディン・ゲンガー・ナッシー・スターミー・ルージュラ・ケンタロス・ラプラス・サンダース

実装した技：ふぶき・１０まんボルト・サイコキネシス・のしかかり・じこさいせい・リフレクター・でんじは・かげぶんしん・きりさく・いわなだれ・はかいこうせん・あくまのキッス・どくどく・ あなをほる・にどげり・かいりき・メガドレイン・あやしいひかり・ナイトヘッド・はねる

まずはP特徴のみで回帰したときの係数を、大きい順に並べて示します。

特徴の意味 係数
ゲンガー 0.251
ナッシー 0.137
ケンタロス 0.031
スターミー -0.012
ラプラス -0.042
フーディン -0.043
サンダース -0.053
ダグトリオ -0.126
ルージュラ -0.144

ゲンガーの係数が最大です。これは、ゲンガーがパーティに入っていると勝率が大きく高まるということを意味しています。ゲンガーはゴーストタイプで、20種類の技のうち5種類を無効化できるところが強い要因だと思われます。 ダグトリオは係数が低いです。この環境だと強力な技「じしん」が使えない点が厳しいものと思われます。ルージュラは「ふぶき」で凍らないというメリットがありますが、意外にも最下位となりました。

次にM特徴のみで回帰したときの係数を、大きい順に並べて示します。

特徴の意味 係数
ふぶき 0.111
サイコキネシス 0.101
10まんボルト 0.095
あくまのキッス 0.069
じこさいせい 0.067
きりさく 0.062
はかいこうせん 0.039
のしかかり 0.037
いわなだれ 0.025
どくどく 0.023
あやしいひかり 0.022
かげぶんしん 0.018
かいりき 0.009
メガドレイン -0.003
あなをほる -0.010
にどげり -0.037
ナイトヘッド -0.084
でんじは -0.107
リフレクター -0.109
はねる -0.177

妥当な順位だといえるのではないでしょうか。こおりタイプ以外の相手を27%の確率で即死させるふぶきが最強です。何の効果もない「はねる」がちゃんと最下位になりました。 「でんじは」も使い方によっては強力ですが、行動選択がランダムなため複数回無駄に使ってしまうなどの事態が生じやすいと思われます。 この序列はあくまで「行動をランダムに選んだ場合」の技の良さを示すものであることに注意が必要です。

最後に、すべての特徴量(P, PP, M, MM, PM)を用いて回帰したときの係数を示します。

まずは値が大きいものから10個示します。

特徴の種類 特徴の意味 係数
PM フーディン&サイコキネシス 0.156
PM ナッシー&サイコキネシス 0.139
PM ケンタロス&きりさく 0.134
PM サンダース&10まんボルト 0.128
PM スターミー&サイコキネシス 0.123
PM ケンタロス&はかいこうせん 0.119
PM ゲンガー&サイコキネシス 0.111
P ゲンガー 0.107
PM ゲンガー&10まんボルト 0.105
PM ゲンガー&ふぶき 0.105

ポケモンとタイプが一致する技の係数が非常に高いことがわかります。ポケモン単独、技単独では測れないポケモンと技の相性のよさを定量化することができていると考えられます。

次に、値が小さいものから10個示します(一部省略)。

特徴の種類 特徴の意味 係数
PM ナッシー&はねる -0.156
PM (はねる関係省略)
PM ケンタロス&ナイトヘッド -0.097
PM ナッシー&でんじは -0.096
PM (でんじは関係省略)
PM (ナイトヘッド関係省略)
PM ゲンガー&リフレクター -0.088
MM でんじは&あくまのキッス -0.084
P ルージュラ -0.065
PM (リフレクター関係省略)
PM フーディン&にどげり -0.054
PM ルージュラ&あなをほる -0.053
P ダグトリオ -0.053
PM (にどげり関係省略)
PM ケンタロス&メガドレイン -0.049

まず、はねる等の弱い技とポケモンの組み合わせが目立ちます。次に、「でんじは&あくまのキッス」という技と技の組み合わせが登場しました。 どちらも相手を状態異常にする技ですが、状態異常は複数種類掛けることができないため、この2つの技を両方覚えるのは良くないということが係数に表れています。 また、「フーディン&にどげり」や「ケンタロス&メガドレイン」のように、ポケモンの「こうげき」「とくしゅ」の能力値の大小関係と技が合っていない場合の係数が低いことがわかります。

以上で分析したように、2技関係特徴量により、ポケモンプレイヤーの直観に沿う形でパーティの強さを定量的に予測できることがわかりました。 この技術を用いることで、ランダムにパーティを組み替えるよりも効率的に強いパーティを探索できるようになることが期待できます。

今後はまずポケモン・技の種類を増加させる実装を行ったうえで、今回提案した手法を取り入れながら強いパーティの構築技術を模索していきたいと考えています。

ポケモン×人工知能 2技関係によるパーティ強さの予測(手法編)

ポケモンバトルAI

PokéAI(ポケモン×人工知能)ネタです。

数日前の記事にて研究の構想を発表しました。まだご覧でない方は先にリンク先をご覧ください。

select766.hatenablog.com

今後はブログで研究の進捗を掲載しつつ、1年に1～2回程度まとめ記事を作れたらよいなと考えています。

最適化手法の問題点

以前発表した手法では、パーティの構築とそのパーティを使った行動の学習の2つの最適化を交互に行うことが重要でした。 行動の学習は（深層）強化学習を用いているのに対し、パーティの構築は単純な山登り法でした。 その手法の概略は、

  1. ベースとなるパーティを用意する。（最初はランダム）
  2. パーティ内のポケモン・技をランダムに変えたものを多数用意する。
  3. 各パーティの行動選択方法を学習し、勝率が最大のパーティを選択する。
  4. 2に戻る。

というものでした。強化学習がそれなりにコストのかかる（1パーティにつき数分）処理なのに、学習対象のパーティがランダムというのは効率が良くありません。 ある程度有望なパーティに対してのみ強化学習を行ったほうが良いのではないでしょうか。 ここで、パーティを実際に対戦させなくても、強さがある程度予測できるのではないかという仮説を立てました。 例えば、「サイコキネシスを覚えたフーディン」がいるパーティと、「はねるを覚えたコイキング」がいるパーティなら、前者のほうが明らかに強そうです。 そこで、パーティ構成を入力とし、対戦シミュレーションをせずに勝率を予測する関数が作れるかどうかについて検討しました。

問題の定義

ここでは、パーティ構成を入力、勝率を出力とするような関数を機械学習で求めることにします。 今回は強化学習は用いずに、バトル中の行動選択はランダムとします。また、対戦相手はランダムに構築された100種類のパーティとします。 この条件下で、勝率の予測をできるだけ正確に行うことが課題となります。

この問題は教師あり学習で解くことができます。ランダムなパーティを生成して、実際にバトルを行った勝率を正解データとします。 パーティの勝率を、バトルなしに求める関数のパラメータを学習することが目的です。

ここで、勝率予測関数に入力する特徴量の設計が必要です。 ポケモンの種類・技の種類をシンプルに並べたベクトルを特徴量とし、深層学習で求めてしまうというのも1つの手です。 しかしこれだと、入出力関係がブラックボックスになってしまいあまり面白くありません。 今回は、特徴量を手動で設計し、線形モデルによって勝率を求めることとしました。

特徴量の設計

前述のように、今回は線形モデルでパーティの勝率を予測します。式で書けば、

{ \displaystyle y = \boldsymbol{w}^T \boldsymbol{x} + b }

となります。 yは勝率ですが、ここでは-1(全敗)～+1(全勝)の値域としました。 \boldsymbol{x}がパーティの構成を表す特徴量です。 \boldsymbol{w}は各特徴量に対する重みで、学習によって求めます。 bはバイアスですが気にしなくて構いません。

特徴設計ですが、例えば次のような要素が必要と考えられます。

このように、単独のポケモンや技の強さのほか、いくつかのポケモンや技の組み合わせがパーティの強さの指標になると予想できます。

今回は、次のような特徴を考案しました。

P=Pokémon(ポケモン)、M=Move(技)を指しています。 例えば、PM特徴だと、 \boldsymbol{x}=(ダグトリオ&ふぶき, ダグトリオ&10まんボルト, フーディン&ふぶき, フーディン&10まんボルト, ...)のように各要素が定義されます。 パーティ内にふぶきを覚えたダグトリオと10まんボルトを覚えたフーディンがいる場合、 \boldsymbol{x}=(1, 0, 0, 1, ...)という値になります。 現在実装されているポケモンは9種類、技は20種類なので9*20=180個の要素があり、そのうちいくつかが1になったベクトルとして表現されます。

実はこの考え方は、将棋AIで使われる「2駒関係」という特徴量のアナロジーになっています*1。 将棋では3駒関係が主流で、1億要素以上のベクトルで盤面を表現しています。

今回提案した特徴量を総称して「2技関係」と呼ぶことにします。将来的には、3つのポケモンや技の関係を考えることが可能です。ただしその分次元数が増加し、学習が難しくなるというのがデメリットです。 また、「ポケモンと、別のポケモンが覚えている技」という2要素の関係性を考えることも可能です。 金・銀バージョン以降だと「あまごい」や「まきびし」等、場に作用して後続のポケモンに影響を与える技があるため、特に有用な可能性があります。

実験結果は近日公開します。

(2017-12-30 続きを公開しました。)

*1:参考 金子 知適ら「駒の関係を利用した将棋の評価関数」 http://www.graco.c.u-tokyo.ac.jp/~kaneko/papers/gpw03.pdf

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

イベント

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

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

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

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

f:id:select766:20171228143035j:plain

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

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

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

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

ポケモンバトル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年の時点でGPUにNVIDIA GTX 1060というコンシューマ向けではそこそこ良い機種が搭載されていました。 しかし2016年のPR文書を読んだ限りではだれも使った形跡がなく、2017年に自分（やほかに出場するであろうチーム）が初使用することになるということで、大きな独自性を出せると期待しました。

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

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

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

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

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

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

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程度、GPUはGeForce 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月からコンピュータ将棋のプログラムを書き始め、先日大会に出場することができました。その際の技術解説を手始めに、将棋に限らずいろいろな記事を書ければよいなと思っております。