第29回世界コンピュータ将棋選手権参加記録

2019年5月3日~5日に開催された、第29回世界コンピュータ将棋選手権(以下wcsc29)に参加しました。本ブログエントリは、その参加記録です。

狸王

tanuki- チームは、参加毎に参加名を変えています。今回の参加名は『狸王』としました。これは、第6回電王トーナメントの参加名として考えていたもので、第5回電王トーナメントで優勝したディフェンディングチャンピョンという意味が込められています。しかし、電王トーナメントが終了したことにより、お蔵入りとなっていました。今回 wcsc29 に参加するにあたり、当初考えていた参加名がチームメンバーに不評で、チームメンバーからの提案で『狸王』を使用することになりました。

評価関数

wcsc29 の注目すべき点の一つに評価関数がありました。 wcsc28 において、 tanuki- チームは CPU ベースのディープラーニング評価関数 『NNUE評価関数』を実装し、選手権に望みました。結果は 5 位で、独創賞もいただくことができました。 wcsc29 では、この『NNUE評価関数』をどこまで強化できるかがポイントだと考えました。

tanuki- チームでは半年をかけて『NNUE評価関数』で強化学習を行ってきました。その結果、野良で公開されている『orqha』と同程度のレーティングまで強化することができました。しかし、そこからは伸び悩みました。本番で使用したのは2018年11月頃に出来上がった評価関数だったと思います。

探索パラメーターの調整

tanuki- チームでは探索パラメーターを Tree-structured Parzen Estimator Approach (TPE) と Gaussian Process (GP) を用いて自動調整しました。 TPE が実装されている hyperopt を用いて、探索パラメーターと自己対戦の勝率をサンプリングし、その後 GP で最適な探索パラメーターを選択するという手順で行いました。サンプリングにはおよそ 1 ヶ月間程度かけたと記憶しています。その結果、もとの探索パラメーターに対して 54% 程度勝てる探索パラメーターを見つけることができました。

本番でこの探索パラメーターを使用したところ、読み抜けが多いように感じられました。サンプリングは 1 手 1 スレッド 10 秒の思考で行ったのですが、本番の環境との乖離が大きすぎたように感じました。そこで、 3 日目決勝リーグの第5回戦の前に、急遽探索パラメーターを元に戻すことに決めました。

配布している実行バイナリには、探索パラメータ調整あり・なしの両バージョンを収録しています。比較してみても面白いかもしれません。

クラスタ

tanuki- チームは、以下の手法を組み合わせたクラスタを実装しました。

  • Lazy Cluster (eXtream Lazy Smp)
  • ゲーム木の分割
  • Multi Ponder
  • 詰将棋専用ノード

Lazy Cluster (eXtream Lazy Smp)

eXtream Lazy Smp は Ponanza が wcsc27 で導入した手法です。これは、 Lazy Smp を複数の思考ノードにまたがって行うというものです。具体的には、探索したの局面に対する置換表エントリを、クラスタ上の他のノードにブロードキャストして共有します。

Lazy Cluster もほぼ同様の手法で、 Stockfish の実験ブランチで実験が進められています。 eXtream Lazy Smp との違いは、自分の理解が正しければ、探索した PV 上の局面の置換表エントリのみを他のノードと共有する点です。これにより、 eXtream Lazy Smp に比べて通信量は大幅に小さくなります。一方、置換表のヒット率は若干下がる可能性があります。

tanuki- チームでは Lazy Cluster を USI on ssh 上に実装しました。具体的には『tt』コマンドを追加しました。思考エンジンの各探索スレッドが反復深化の各探索深さの探索を終えるたびに、 PV 上の置換表エントリをエンコードし、『tt』コマンドを用いて クラスタマスタープログラムに送ります。マスターは受信した『tt』コマンドを、そのまま他の思考ノードに転送します。『tt』コマンドを受け取った思考エンジンは、内容をデコードし、置換表に格納します。これらの基本的な実装は、チームメンバー河野さんが担当されました。この場を借りてお礼申し上げます。

Multi Ponder

Lazy Cluster を実装し終えたあと、 Multi Ponder の実装をはじめました。 Multi Ponder は wcsc28 で白ビールが採用した手法です。これは、相手の手番で、複数の読み筋で Ponder を行うというものです。これにより、 Ponder のヒット率を向上させ、相手の思考時間を奪うことができます。白ビールはこの手法で wcsc28 で他のチームを圧倒しました。

tanuki- チームが実装した Multi Ponder の処理の流れは以下のとおりです。

  1. GUI から送られてきた position コマンドを保持しておく
  2. GUI から go ponder コマンドが送られてきたら、 直前の position コマンドの局面から 1 手戻した局面を思考ノード 1 台に渡し、その局面を Multi PV で 0.1 秒思考させる
  3. Multi PV 探索の結果の各 PV の 1 手目を指したあとの局面を各思考ノードに渡し、 go ponder コマンドで探索を開始する
  4. Ponder がヒットした場合は、ヒットした思考ノードを Root 思考ノードに昇格し、 ponderhit を送り、思考を継続させる。それ以外のノードに stop コマンドを送り、探索を停止させる。
  5. Ponder がヒットしなかった場合は、全ノードに stop コマンドを送り1 つの思考ノードを Root 思考ノードに昇格し、 position と go コマンドを送り、思考を開始する。

Ponder の候補を選ぶとき、直前に思考していたノードの読み筋を強制的に含めたほうがヒット率があがると思われます。しかし、実装を簡単にするため、この処理は入れませんでした。

ゲーム木の分割

上記に加え、 tanuki- チームでは、ゲーム木を分割し、分割した各部分木の Root 局面を各思考ノードに割り当てる機能も実装しました。処理の流れは以下のとおりです。

  1. GUI から送られてきた position コマンドを保持しておく
  2. GUI から go コマンドが送られてきたら、思考ノード 1 台を Root 思考ノードに昇格し、思考させる
  3. 直前の position コマンドの局面から 1 手戻した局面を別の思考ノード 1 台に渡し、その局面を Multi PV で 0.1 秒思考させる
  4. Multi PV 探索の結果の各 PV の 1 手目を指したあとの局面を、 Root 思考ノード以外の各思考ノードに渡し、 go infinite コマンドで探索を開始する

実装を簡単にするため、ゲーム木の分割は1段までとしました。

ゲーム木の分割に関する基本的なアイデアは、チームメンバーが岡部さんが少し前から提案してくださっていたものです。今回このような形で実現することができました。提案してくださった岡部さんにこの場をお借りしてお礼申し上げます。

詰将棋専用ノード

上記に加え、詰将棋専用ノードを思考ノードと同数導入しました。これらは Multi Ponder 時とゲーム木の分割時に、思考ノードと同じ局面を読ませるようにしています。また、詰みが見つかったときは、その読み筋を置換表エントリの配列の形に変換して、『tt』コマンドを用いてマスターに送るようにしています。これにより、詰み筋が思考ノードの置換表に書き込まれることになります。 Multi Ponder 中の局面およびゲーム木分割時の Root 局面については詰み筋を、ゲーム木分割時の子局面については頓死筋を発見することができます。負けそうな局面では、思考ログから頓死筋を発見していることが見て取れました。

その他

Multi Ponder とゲーム木の分割は、一部の処理が非常に似ていることがわかります。 tanuki-proxy の中では、これらを共通のルーチンを用いて処理しています。この部分は、 Multi Ponder のルーチンがあると、少しの変更で実装できてしまいます。このため、情報を公開したときに、他のチームがキャッチアップしてくるのではないかと思いました。これを避けるため、クラスタに関する情報公開を 5 月 5 日まで遅らせることにしました。情報公開の日時を調整するため CSA のスタッフの方に特別にお願いをしたりもしました。引き受けてくださった CSA 香山様に、この場をお借りしてお礼申し上げます。

対局

個人的に印象深かった対局を 2 つほど掲載させていただきます。

なお、自分は将棋の棋力は低いため、高段者の方から見ると普通の局面の可能性があります。

二次予選 9回戦 NineDayFever - 狸王

これに勝てば決勝リーグ進出という一番です。狸王と NDF は飛車と角を交換しました。狸王が角を敵陣に打ち込んで、 NDF が金を上げた局面。

f:id:nodchip:20190506161815p:plain

二次予選 9回戦 NineDayFever - 狸王 29 手目

そして 30 手目…。

f:id:nodchip:20190506161332p:plain

二次予選 9回戦 NineDayFever - 狸王 30 手目

飛車を打ち込んで切って金銀と交換。その後相手が合駒として打ってきた飛車を金で取り返して優勢になりました。見ていて興奮しました。

決勝 2回戦 elmo - 狸王

狸王が形勢を悪くし、 elmo からの攻めを受けている局面です。

f:id:nodchip:20190506162042p:plain

決勝 2回戦 elmo - 狸王 109 手目

ここで金を取るのかとおもいきや…、

f:id:nodchip:20190506162220p:plain

決勝 2回戦 elmo - 狸王 110 手目

逃走開始…。その後、相入玉模様となり、一点差を争う際どい勝負の中、 elmo のミスから点数で逆転。最終的には狸王の勝利となりました。数年前までコンピュータ将棋の弱点は入玉将棋だと言われていただけに、入玉将棋の熱い戦いに驚きました。

終わりに

狸王は3位入賞という、過去最高成績を獲得することができました。応援してくださった皆様のおかげです。本当にありがとうございました。これからもよろしくお願いいたします。

ソースコード・実行バイナリ・評価関数ファイル・定跡データベースを公開しております。ぜひお使いください。