機械学習周りのプログラミング中心。 ポケモンバトルAI本通販中(4/5まで)

コミックマーケット97 入稿完了しました【PokéAI】

コミックマーケット97において新規刊行を目指し執筆しておりましたポケモンAI本の第3巻の入稿が完了いたしました。本が出ます!

頒布場所は火曜日(12月31日) 南3ホール リ―36a「ヤマブキ計算所」です。同人ソフトジャンルとなります。

第3巻は金銀導入編と称しまして、金銀ルールに対応することが主題となります。

分量は過去最大となる60ページです。内容とは別に新しい試みとして、カラー表紙にしてみました。正しいCMYKデータを作れる環境がないのでうまくいってるかはわかりませんが…

正式なお品書きは後日アップしますが、頒布予定についてお知らせします。

  • 第1・2・3巻すべて在庫を用意しております。1冊500円です。
    • 現金のほか、pixiv payに対応予定です。
  • 電子版のDLカード頒布は紙版完売時のみ実施する場合があります。割引は行いません。
    • 完売しないであろう数量印刷しております。
    • オペレーション簡略化のためご了承ください。
  • 電子版(PDFのダウンロード)についてはイベント当日朝にBOOTHにて販売開始いたします。
    • 技術書典と比べて大変な混雑が予想されますので、PDFデータだけ入手できれば良いという方はこちらをおすすめします。

最後に、表紙・目次等を掲示します。

f:id:select766:20191212211211p:plain
PokéAI #3表紙
f:id:select766:20191212211242p:plain
PokéAI #3目次
f:id:select766:20191212213859p:plain
PokéAI #3方策可視化

コミックマーケット97(12月31日)に出展します【PokéAI】

当ブログ筆者の個人サークル「ヤマブキ計算所」は、2019年12月31日に東京ビッグサイトで開催されるコミックマーケット97にサークル参加し、技術書の頒布を行います。

配置は火曜日(31日) 南3ホール リ―36aです。同人ソフトジャンルとなります。

頒布物はポケモンバトルのAIを開発する技術書シリーズ「PokéAI」です。技術書典5・6にて頒布した既刊の第1・2巻の再版に加え、現在第3巻を執筆中です。間に合えば新刊を頒布します。

内容の雰囲気については、すでに電子版を無料公開しております第1巻をご覧ください。

select766.booth.pm

第3巻に掲載する研究については本日12月3日に主な実験を終え、執筆を開始しました。

今回の進捗はポケモン第2世代である金銀のルールに対応したことです。初代(赤緑)ルールについては自作のルールシミュレータを開発しAIの学習に用いていましたが、別のルールへの対応は大変なのでオープンソースのシミュレータを活用する方針に転換し、AIとの接続インターフェースを実装しました。 金銀ルールの新要素として、ポケモンに道具を持たせるシステムが新設されています。どのような持ち物が有効なのか、従来研究の特徴量を拡張して調べました。 バトル中の行動の選択面では、あえて線形モデルを学習させてみて、AIの行動基準を可視化することを試みました。 今回はシミュレータ変更に伴うコード書き直しが大変だったという点があり、実装手段寄りの話題を多めに記載する見通しです。

目次などにつきましては、入稿が成功したら別の記事にてお知らせします。新刊が落ちないようご祈願ください!

技術書典5の本を無料化しました

技術書典5で発売した同人誌「PokéAI #1:初代1vs1編」を、発売後1年経過しましたので電子版を無料配布に切り替えました。 BOOTHのページからダウンロードできます。

select766.booth.pm

これまでイベントやオンライン販売でお買い上げいただいた方、誠にありがとうございました。

以下はコンテンツとは関係ない乱文です。

奥付のところに「刊⾏から1 年経過後よりCC-BY-SA 3.0 ライセンスで利⽤可能」とあらかじめ記載しておりました。 そのためすでに購入された方からの再配布は本日より許可されることになります。

あえてこのような文言を設けたのは、孤児作品を発生させないための予防的措置でした。 紙媒体はどうしても1冊ごとにコストがかかるためイベントで有料配布せざるを得ません。 電子版は無料で配布できるものの、最初から無料ですと紙媒体で買った人が損をした気分になるかもしれません。 そのため発売時点では電子版も有料としました。 一方で、販売サイトが10年先も存在する確証はなく、サイト閉鎖時点ですでに作者が同人活動を辞めていれば移転もされず入手不可能な作品になってしまいます。

これらのバランスを考えた結果として、発売から一定期間経過後、作者の関与なしに再配布可能としておくことにしました。

ジョウト地方への第一歩【PokéAI】

4月の技術書典6以来多忙でプロジェクトを一時停止していたのですが、再開していきたいと思います。なお、ネタが用意できていないため9月の技術書典7には出展致しません。

今まで初代ポケモンのルールに準拠してAIの開発と実験を行なっていましたが、ポケモン間の連携を取る補助技がなく、複雑な手順を踏まずに使える攻撃技でとにかく殴るという結果になりがちでした。この状況を打開するため、ポケモン金銀のルールへと移行したいと考えています。ポケモン金銀ではポケモンや技の種類が増え、またタイプ相性としてもエスパータイプ一強ではなくなっています。ゲームバランスの調整だけではなく、天候をはじめとした場の効果が導入されたことで、補助技で場を整える専門のポケモンと、整った場で相手にとどめを刺すポケモンという連携が可能になります。今後の技術開発で見応えある戦略が登場することを期待しています。

ルールを変更するにあたり、ポケモンバトルのルールを再現するシミュレータが必要になります。 今まで初代ルールを実装した自作のシミュレータを利用していましたが、流石に金銀のシミュレータを作るのは大変ですし、AI開発に集中したいのでオープンソースのシミュレータの活用を試みることにし、使い方を調べ始めました。

シミュレータとして、Pokémon Showdownが使えそうでした。 github.com オンライン対戦サーバシステムがTypeScriptで実装されており、その中のシミュレータ部分を抜き出せばAI同士の対戦がさせられそうです。

かなり複雑なシステムになっており全容を把握できていないのですが、とりあえずこのファイルPokemon-Showdown/battle-stream-example.ts at master · Zarel/Pokemon-Showdown · GitHubがサンプルになっていて、ランダムに生成したパーティ同士をランダムな行動で対戦させることができるようです。これをベースに、ランダムなパーティを生成・対戦させ、ポケモンや技の強さを回帰するモデルを学習させてみることとしました。ソースコードはこちらですpokeai/random.js at e2a150eac4549c97b12fb57ce4db8170a87ebf01 · select766/pokeai · GitHub。TypeScriptで記述されているので型情報などを使いたいところなのですが、ビルドスクリプトを見るとコンパイル済みJavaScriptコードを文字列置換する処理などが入っており、型情報を含んだライブラリとして使うことが難しそうです。 強さの回帰アルゴリズム自体は以前の記事と同じ物を実装しましたselect766.hatenablog.com

ポイントを解説すると、

  • Dex.generateTeam('gen2customgame')で第2世代(金銀)準拠のパーティが生成されるようです。6体分の情報が配列に入っているので、.slice(0, 3)で3体分を取り出して従来通り3vs3の対戦にします。
  • バトル中の行動自体はRandomPlayerAIとして実装されているものをそのまま使います。
  • シミュレータからのメッセージで、|win|1のような勝ったプレイヤー名が返ってくるので、これを抽出してパーティとその勝敗を記録します。

これで、パーティの生成と対戦を繰り返して記録を生成しました。1回の対戦に対しこのような情報が出力されます。 ポケモン名、技、個体値などの情報が入ったパーティと勝敗情報です。

{'parties': [[{'name': 'Nidoking',
    'species': 'Nidoking',
    'moves': ['earthquake', 'thunder', 'rockslide', 'lovelykiss'],
    'ability': 'None',
    'evs': {'hp': 255,
     'atk': 255,
     'def': 255,
     'spa': 255,
     'spd': 255,
     'spe': 255},
    'ivs': {'hp': 30, 'atk': 30, 'def': 30, 'spa': 30, 'spd': 30, 'spe': 30},
    'item': 'leftovers',
    'level': 68,
    'shiny': False,
    'gender': 'M'},
   {'name': 'Mew',
    'species': 'Mew',
    'moves': ['swordsdance', 'earthquake', 'shadowball', 'explosion'],
    'ability': 'None',
    'evs': {'hp': 255,
     'atk': 255,
     'def': 255,
     'spa': 255,
     'spd': 255,
     'spe': 255},
    'ivs': {'hp': 30, 'atk': 30, 'def': 30, 'spa': 30, 'spd': 30, 'spe': 30},
    'item': 'leftovers',
    'level': 64,
    'shiny': False,
    'gender': 'N'},
   {'name': 'Raichu',
    'species': 'Raichu',
    'moves': ['thunderbolt', 'surf', 'thunderwave', 'reflect'],
    'ability': 'None',
    'evs': {'hp': 255,
     'atk': 255,
     'def': 255,
     'spa': 255,
     'spd': 255,
     'spe': 255},
    'ivs': {'hp': 30, 'atk': 30, 'def': 30, 'spa': 30, 'spd': 30, 'spe': 30},
    'item': 'leftovers',
    'level': 78,
    'shiny': False,
    'gender': 'M'}],
  [{'name': 'Nidoqueen',
    'species': 'Nidoqueen',
    'moves': ['earthquake', 'thunderbolt', 'fireblast', 'lovelykiss'],
    'ability': 'None',
    'evs': {'hp': 255,
     'atk': 255,
     'def': 255,
     'spa': 255,
     'spd': 255,
     'spe': 255},
    'ivs': {'hp': 30, 'atk': 30, 'def': 30, 'spa': 30, 'spd': 30, 'spe': 30},
    'item': 'leftovers',
    'level': 70,
    'shiny': False,
    'gender': 'F'},
   {'name': 'Rapidash',
    'species': 'Rapidash',
    'moves': ['fireblast', 'sunnyday', 'hiddenpowergrass', 'bodyslam'],
    'ability': 'None',
    'evs': {'hp': 255,
     'atk': 255,
     'def': 255,
     'spa': 255,
     'spd': 255,
     'spe': 255},
    'ivs': {'hp': 6, 'atk': 28, 'def': 28, 'spa': 30, 'spd': 30, 'spe': 30},
    'item': 'leftovers',
    'level': 78,
    'shiny': False,
    'gender': 'M'},
   {'name': 'Pidgeot',
    'species': 'Pidgeot',
    'moves': ['return', 'thief', 'hiddenpowerflying', 'reflect'],
    'ability': 'None',
    'evs': {'hp': 255,
     'atk': 255,
     'def': 255,
     'spa': 255,
     'spd': 255,
     'spe': 255},
    'ivs': {'hp': 14, 'atk': 24, 'def': 26, 'spa': 30, 'spd': 30, 'spe': 30},
    'item': '',
    'level': 78,
    'shiny': False,
    'gender': 'M'}]],
 'winner': 0}

いくつか気になる点があり、ポケモンによってレベルが違ったり、個体値を調整して都合がいい「めざめるパワー」のタイプが選ばれたりしています。どういう仕組みでランダムなパーティを生成しているのかまだ調べられていないのですが、何かしらのバランス調整のための情報が用いられていると考えられます。そもそも進化前のポケモンが入っていません。パーティ構成をAIが考えるというコンセプト上、できれば純粋なランダム生成を実装したいところです。

対戦記録を15755件生成し、強さの回帰モデルを学習してみました。10万件生成しようとしたのですが、メモリリークが生じてクラッシュしていました。これもブラックボックスの弊害かもしれません。線形SVMを学習したところ、学習データ自体に対する勝敗の識別率は61%となり、あまり精度が良くないようです。前述のバランス調整の影響があると思われます。学習された係数のtop10, worst10を以下に示します。係数が大きいものは勝ちに寄与、係数が小さいものは負けに寄与していると見なせます。パーティに含まれるポケモンおよび技の特徴(P, M特徴)を用いています。

ポケモンor技 係数
バタフリー -0.377
プレゼント -0.354
セレビィ -0.296
ヤンヤンマ -0.292
うずしお -0.265
カモネギ -0.244
ワタッコ -0.208
じばく -0.200
はかいこうせん -0.197
ムウマ -0.195
ポケモンor技 係数
サイコウェーブ 0.182
てんしのキッス 0.183
ジュゴン 0.185
レアコイル 0.193
やどりぎのタネ 0.195
デンリュウ 0.196
バンギラス 0.196
ソーナンス 0.207
アーボック 0.244
めざめるパワーエスパー 0.286

「プレゼント」や「じばく」が悪く、「バンギラス」が良いのはなんとなくわかりますが、今ひとつの結果です。 進化前のポケモンが入っていないなどの影響で、明確に弱い特徴がデータセットに含まれていない可能性が高いです。

今回はAIを金銀ルールに対応させる最初の第一歩を踏み出すということでオープンソースのシミュレータの導入とランダムな対戦のみを行いました。まずはパーティの生成方法をコントロールするなど、シミュレータの扱い方を習得する必要がありそうです。

第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を行う場合は対局相手の時間の使い方にも依存するためまともに調整できません。

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