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

第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:駒を動かすことで、飛車などの長い利きが玉にあたる