最良優先探索ベースのパーティ生成【PokéAI】

以前の記事で、バトルなしにパーティの強さを予測する関数（以下では静的評価関数と呼ぶことにします）を学習しました。今回はこれを山登り法によるパーティ構成の最適化に組み込みます。

select766.hatenablog.com

山登り法でのパーティ構築は次のような手順でした。

1. ランダムなパーティXを生成する
2. Xのポケモンや技を1つ変更した近傍パーティY1,...,Ynを生成する
3. Y1,...,Ynを評価用パーティ群と対戦させ、強さ（レーティング）を計算する
4. 最も強いパーティをXに代入し、2に戻る

ここでの問題は、ステップ3でパーティの評価に多数のバトル（今は100回でやっています）が必要で、時間がかかるということです。 例えば、「ふぶき」を「たいあたり」に変更した明らかにダメそうなパーティにも時間を割く必要が生じ、時間効率が悪いです。 そこで、有望なパーティに限ってバトルでの評価を行うことで改善を試みます。改良後のアルゴリズムは次のようになります。

1. ランダムなパーティXを生成する
2. Xのポケモンや技を1つ変更した近傍パーティY1,...,Ym (m > n)を生成する
3. Y1,...,Ymに静的評価関数を適用し、上位nパーティをY1,...,Ynに代入する
4. Y1,...,Ynを評価用パーティ群と対戦させ、強さ（レーティング）を計算する
5. 最も強いパーティをXに代入し、2に戻る

これは最良優先探索の考え方を応用したものになっています。

実装して実験してみました。ランダムなパーティを初期値として、近傍生成数はm=100,n=10、山登り法の繰り返し10回としました。比較対象は、静的評価関数を使わないで山登り法を行ったもの(n=10とし、バトルでの評価を行うパーティ数を同数とする)、ランダムなパーティ、静的評価関数自体を最大にするパーティを用いました。

静的評価関数自体の最大化は、同様に山登り法で実現できます。対戦によって強さを測定する代わりに静的評価関数の結果をそのまま強さとして使えば実装できます。他と合わせて繰り返し10回のものと、とにかく評価関数を最大化するということで繰り返し1000回のものを作成しました。

各条件で初期値を変えて各100パーティ生成し、これらを混ぜてレーティング戦を行いました。行動戦略はすべてランダムで、強化学習は入っていません。

最適化条件	平均レート
(A)ランダム	1162
(B)バトル	1381
(C)静的評価関数+バトル	1655
(D)静的評価関数のみ(繰り返し10)	1588
(E)静的評価関数のみ(繰り返し1000)	1711

BとCを比較すると、静的評価関数を使うことで、バトルでの評価部分についてほぼ同じ計算コストでより強いパーティが生成できています。 また、CとDは途中で生成されるパーティ候補の数は同じですが、バトルで強さを評価したほうが強い傾向にあるといえます。 一方、最も強かったのはEでした。バトルを一切せず、静的評価関数の値が最大となるようなパーティを生成すれば十分強いという結果です。

対戦で上位レートを得たパーティをグループごとに示します。

↓(A)ランダム

1479.7354283838638
* シードラ (LV 50 HP 162/162)
  こうそくいどう バブルこうせん にらみつける みずでっぽう 
  ゲンガー (LV 55 HP 182/182)
  サイコウェーブ じごくぐるま さいみんじゅつ 10まんボルト 
  フーディン (LV 50 HP 162/162)
  ロケットずつき サイコキネシス トライアタック すてみタックル 

1447.0239174401538
* ニドキング (LV 55 HP 205/205)
  ちきゅうなげ じしん にらみつける ふぶき 
  ペルシアン (LV 50 HP 172/172)
  すてみタックル ひっかく どくどく かげぶんしん 
  カメックス (LV 50 HP 186/186)
  あわ メガトンキック あなをほる ハイドロポンプ 

1443.0889755952132
* ゲンガー (LV 55 HP 182/182)
  ねむる したでなめる サイコウェーブ サイコキネシス 
  スリープ (LV 50 HP 167/167)
  さいみんじゅつ トライアタック どくどく のしかかり 
  ダグトリオ (LV 50 HP 142/142)
  じしん ねむる いあいぎり いわなだれ 

↓(B)バトル

1644.178954863615
* ゴースト (LV 55 HP 166/166)
  ナイトヘッド 10まんボルト サイコキネシス 
  ニョロボン (LV 50 HP 197/197)
  じしん ふぶき さいみんじゅつ かいりき 
  プテラ (LV 50 HP 187/187)
  かみつく つばさでうつ はかいこうせん 

1632.4251737361622
* リザードン (LV 55 HP 202/202)
  じしん きりさく だいもんじ 
  フシギバナ (LV 50 HP 187/187)
  ソーラービーム やどりぎのタネ のしかかり ねむりごな 
  ジュゴン (LV 50 HP 197/197)
  なみのり れいとうビーム 

1607.3417191119063
* ラプラス (LV 55 HP 259/259)
  りゅうのいかり うたう サイコウェーブ れいとうビーム 
  ニドクイン (LV 50 HP 197/197)
  いわなだれ なみのり れいとうビーム ひっかく 
  サンダース (LV 50 HP 172/172)
  かみなり のしかかり どくどく 

↓(C)静的評価関数+バトル

1864.7585210905622
* ゲンガー (LV 55 HP 182/182)
  サイコキネシス ちきゅうなげ さいみんじゅつ ナイトヘッド 
  ライチュウ (LV 50 HP 167/167)
  のしかかり 10まんボルト はかいこうせん かみなり 
  フリーザー (LV 50 HP 197/197)
  ふぶき れいとうビーム そらをとぶ かげぶんしん 

1861.053481729282
* プテラ (LV 50 HP 187/187)
  はかいこうせん そらをとぶ ゴッドバード だいもんじ 
  ルージュラ (LV 50 HP 172/172)
  バブルこうせん のしかかり メガトンキック ふぶき 
  ゲンガー (LV 55 HP 182/182)
  さいみんじゅつ サイコキネシス ナイトヘッド 10まんボルト 

1852.1999935932283
* ルージュラ (LV 55 HP 188/188)
  ふぶき あくまのキッス れいとうビーム 
  ウインディ (LV 50 HP 197/197)
  かえんほうしゃ はかいこうせん だいもんじ あなをほる 
  ゲンガー (LV 50 HP 167/167)
  10まんボルト さいみんじゅつ ちきゅうなげ サイコキネシス 

↓(D)静的評価関数のみ(繰り返し10)

1789.8176242017867
* フシギバナ (LV 50 HP 187/187)
  ねむりごな はっぱカッター やどりぎのタネ のしかかり 
  ラプラス (LV 55 HP 259/259)
  ハイドロポンプ れいとうビーム かみなり ふぶき 
  ゲンガー (LV 50 HP 167/167)
  10まんボルト サイコキネシス ナイトヘッド さいみんじゅつ 

1778.564922781992
* ラプラス (LV 50 HP 237/237)
  ハイドロポンプ かいりき バブルこうせん れいとうビーム 
  フシギバナ (LV 50 HP 187/187)
  のしかかり メガドレイン はっぱカッター ねむりごな 
  スターミー (LV 55 HP 182/182)
  サイコキネシス ねむる じこさいせい ふぶき 

1778.3059349935693
* サンダー (LV 55 HP 215/215)
  かみなり はかいこうせん ドリルくちばし 10まんボルト 
  プテラ (LV 50 HP 187/187)
  そらをとぶ ゴッドバード だいもんじ すてみタックル 
  ニョロボン (LV 50 HP 197/197)
  ふぶき さいみんじゅつ れいとうビーム のしかかり 

↓(E)静的評価関数のみ(繰り返し1000)

1924.0833346696368
* サンダー (LV 55 HP 215/215)
  10まんボルト かみなり はかいこうせん ドリルくちばし 
  ラプラス (LV 50 HP 237/237)
  ふぶき ハイドロポンプ れいとうビーム バブルこうせん 
  ゲンガー (LV 50 HP 167/167)
  メガドレイン ナイトヘッド さいみんじゅつ サイコキネシス 

1866.9876553669278
* サンダー (LV 55 HP 215/215)
  かみなり ドリルくちばし でんきショック 10まんボルト 
  ケンタロス (LV 50 HP 182/182)
  かいりき れいとうビーム ふぶき はかいこうせん 
  ゴースト (LV 50 HP 152/152)
  サイコキネシス ナイトヘッド さいみんじゅつ メガドレイン 

1864.5993017504716
* ドククラゲ (LV 50 HP 187/187)
  ふぶき ハイドロポンプ なみのり れいとうビーム 
  ゲンガー (LV 50 HP 167/167)
  メガドレイン ナイトヘッド サイコキネシス さいみんじゅつ 
  サンダー (LV 55 HP 215/215)
  ドリルくちばし かみなり 10まんボルト はかいこうせん 

select766.hatenablog.com

前回はランダムに生成した100,000パーティのうちから静的評価関数が高いものを表示し、最強ではなさそうという結果でした。その時の予測レートは最大で2100程度（対戦相手が違うので、上の表との数値の互換性はありません）でした。しかし、静的評価関数が最大となるようパーティを最適化した結果、2400程度のパーティが得られています。実際、(E)の上位パーティはかなり強そうといって差し支えないのではないでしょうか。

ランダムに行動する条件下では、静的評価関数を学習したうえでそれを最大化するパーティを探索するという手法がかなり良さそうということがわかりました。 パーティ特徴量が1万次元ほどあり、それを1万種類のパーティで学習しているため、このパーティ数を増やすともう少し改善するかもしれません。

行動を強化学習する手法との組み合わせは悩みどころです。ランダムな行動では無意味な技の組み合わせが、強化学習した場合は有効なコンボとなる可能性があり、今の静的評価関数でそのような候補を弾いてしまうのは良くない可能性があります。しかし1万種類のパーティの行動をそれぞれ強化学習するというのは計算時間的に不可能で、その強さをベースに強化学習での戦略を考慮した静的評価関数を学習するのは困難かと思われます。引き続き手法を検討していきます。

パーティ強さの予測モデルに基づくパーティ候補の生成【PokéAI】

以前、パーティ構成のポケモンや技の組み合わせから、バトルなしに強さを予測するモデルを学習しました。

select766.hatenablog.com

今回はこのモデルを使い、ランダムに生成した大量のパーティから強そうなパーティを抽出してみました。

3体構成のパーティを100,000個ランダムに生成し、そのworst 10, top 10を抽出して表示します。処理は1分程度でした。

まずはworst 10。

predicted rate: 960.1960846745668
* コイキング (LV 50 HP 127/127)
  はねる たいあたり 
  コクーン (LV 50 HP 152/152)
  いとをはく どくばり かたくなる 
  ヒトカゲ (LV 55 HP 159/159)
  なきごえ ひのこ ロケットずつき ねむる 

predicted rate: 972.2634724955224
* カモネギ (LV 50 HP 159/159)
  ふきとばし かげぶんしん にらみつける こうそくいどう 
  トサキント (LV 55 HP 166/166)
  つのドリル こうそくいどう ねむる しっぽをふる 
  コイキング (LV 50 HP 127/127)
  はねる たいあたり 

predicted rate: 974.4966702093706
* コクーン (LV 55 HP 166/166)
  どくばり かたくなる いとをはく 
  オニスズメ (LV 50 HP 147/147)
  どくどく かげぶんしん かまいたち ふきとばし 
  ピカチュウ (LV 50 HP 142/142)
  でんこうせっか リフレクター とっしん こうそくいどう 

predicted rate: 988.8970502273767
* ビードル (LV 55 HP 160/160)
  いとをはく どくばり 
  キャタピー (LV 50 HP 152/152)
  たいあたり いとをはく 
  ケーシィ (LV 50 HP 132/132)
  フラッシュ テレポート とっしん リフレクター 

predicted rate: 997.5683222452317
* ビリリダマ (LV 50 HP 147/147)
  いやなおと どくどく だいばくはつ テレポート 
  ビードル (LV 55 HP 160/160)
  どくばり いとをはく 
  コイキング (LV 50 HP 127/127)
  はねる たいあたり 

predicted rate: 997.7929609782748
* ヒトカゲ (LV 50 HP 146/146)
  スピードスター なきごえ にらみつける ひのこ 
  トランセル (LV 50 HP 157/157)
  いとをはく かたくなる たいあたり 
  ズバット (LV 55 HP 160/160)
  かまいたち かげぶんしん かみつく つばさでうつ 

predicted rate: 1000.8366965109341
* ヒトデマン (LV 55 HP 149/149)
  かたくなる とっしん フラッシュ バブルこうせん 
  コイキング (LV 50 HP 127/127)
  たいあたり はねる 
  ビードル (LV 50 HP 147/147)
  どくばり いとをはく 

predicted rate: 1001.5095810479904
* コクーン (LV 55 HP 166/166)
  いとをはく どくばり かたくなる 
  ポッポ (LV 50 HP 147/147)
  リフレクター でんこうせっか ふきとばし ねむる 
  シェルダー (LV 50 HP 137/137)
  リフレクター ちょうおんぱ とっしん たいあたり 

predicted rate: 1002.0393486802535
* ズバット (LV 50 HP 147/147)
  かげぶんしん スピードスター ちょうおんぱ ふきとばし 
  マンキー (LV 55 HP 160/160)
  みだれひっかき じごくぐるま いわなだれ にらみつける 
  コクーン (LV 50 HP 152/152)
  かたくなる いとをはく どくばり 

predicted rate: 1003.5111618329934
* コイキング (LV 55 HP 138/138)
  たいあたり はねる 
  マダツボミ (LV 50 HP 157/157)
  せいちょう かげぶんしん しびれごな ねむりごな 
  ビードル (LV 50 HP 147/147)
  どくばり いとをはく 

順当にダメなパーティができています。

top 10はどうでしょうか。

predicted rate: 2136.761291977353
* ギャラドス (LV 50 HP 202/202)
  かみつく のしかかり なみのり どくどく 
  ゴースト (LV 55 HP 166/166)
  あやしいひかり かげぶんしん かみなり ねむる 
  ゲンガー (LV 50 HP 167/167)
  さいみんじゅつ すてみタックル はかいこうせん サイコキネシス 

predicted rate: 2113.2795838383868
* ゲンガー (LV 55 HP 182/182)
  どくどく したでなめる 10まんボルト さいみんじゅつ 
  ゴースト (LV 50 HP 152/152)
  サイコキネシス あやしいひかり ナイトヘッド したでなめる 
  ニドクイン (LV 50 HP 197/197)
  のしかかり かいりき れいとうビーム ロケットずつき 

predicted rate: 2112.1449667281267
* ケンタロス (LV 50 HP 182/182)
  つのドリル はかいこうせん だいもんじ かみなり 
  ハクリュー (LV 55 HP 183/183)
  なみのり でんじは りゅうのいかり ねむる 
  ゴースト (LV 50 HP 152/152)
  あやしいひかり サイコキネシス 10まんボルト ナイトヘッド 

predicted rate: 2110.3082249596196
* ゴースト (LV 55 HP 166/166)
  ねむる ナイトヘッド したでなめる 10まんボルト 
  ラプラス (LV 50 HP 237/237)
  バブルこうせん のしかかり れいとうビーム どくどく 
  ゲンガー (LV 50 HP 167/167)
  かみなり かいりき ねむる サイコウェーブ 

predicted rate: 2088.8757321632183
* ゲンガー (LV 50 HP 167/167)
  かみなり すてみタックル ちきゅうなげ のしかかり 
  キングラー (LV 55 HP 177/177)
  はさむ なみのり はかいこうせん ふみつけ 
  ゴースト (LV 50 HP 152/152)
  さいみんじゅつ どくどく ナイトヘッド 10まんボルト 

predicted rate: 2084.959730607545
* ケンタロス (LV 50 HP 182/182)
  ねむる だいもんじ れいとうビーム のしかかり 
  ラプラス (LV 55 HP 259/259)
  つのドリル のしかかり あやしいひかり ハイドロポンプ 
  ゴース (LV 50 HP 137/137)
  かげぶんしん 10まんボルト メガドレイン ねむる 

predicted rate: 2083.8192483283756
* ポリゴン (LV 50 HP 172/172)
  とっしん サイコキネシス ふぶき トライアタック 
  ゴースト (LV 55 HP 166/166)
  ねむる さいみんじゅつ ナイトヘッド かみなり 
  ギャラドス (LV 50 HP 202/202)
  バブルこうせん はかいこうせん 10まんボルト かみなり 

predicted rate: 2061.375318388595
* ドードリオ (LV 50 HP 167/167)
  はかいこうせん そらをとぶ とっしん すてみタックル 
  ガルーラ (LV 55 HP 232/232)
  ピヨピヨパンチ のしかかり とっしん はかいこうせん 
  ゴースト (LV 50 HP 152/152)
  ナイトヘッド メガドレイン かげぶんしん したでなめる 

predicted rate: 2055.8270020078944
* ガルーラ (LV 55 HP 232/232)
  とっしん ピヨピヨパンチ 10まんボルト だいもんじ 
  ジュゴン (LV 50 HP 197/197)
  すてみタックル ふぶき かいりき オーロラビーム 
  カブトプス (LV 50 HP 167/167)
  はかいこうせん かげぶんしん みずでっぽう きりさく 

predicted rate: 2051.331277990781
* ニョロボン (LV 55 HP 215/215)
  なみのり れいとうビーム ねむる さいみんじゅつ 
  ギャラドス (LV 50 HP 202/202)
  バブルこうせん のしかかり かみなり だいもんじ 
  ケンタロス (LV 50 HP 182/182)
  じわれ つのドリル かげぶんしん 10まんボルト 

そこそこ順当な結果です。技単体としては最も強さへの寄与度が高い、ふぶきばかりが採用されるわけではないようです。 また、最上位のパーティで同系統のゴーストとゲンガー両方が入っており、相性補完がよろしくありません。 このように、予測のための特徴量やモデル学習の不完全さがあるため、これだけで最強のパーティを作ることはできないといえます。 この手法はあくまで（コストがかかる）バトルで強さを測定する前段階の候補生成に使うつもりですので、これで問題ありません。

次回、山登り法での最適化と組み合わせます。

3体構成での強化学習【PokéAI】

PokéAIで、従来の1vs1から3vs3バトルへの拡張を進めています。今回は、技を選択する部分の強化学習の仕組みを3vs3に対応させました。

エージェントの入出力の拡張

強化学習におけるエージェントとは、バトルの状態を入力として受け取り、行動を出力する関数です。勝率を高めるような行動がとれるよう関数のパラメータを調整することが強化学習の目的となります。

1vs1のときは、行動はポケモンが覚えている技4種類のうち1つを選択するものでした。今回は3vs3なので交代も可能にしたいです。また、1匹目のポケモンと2匹目のポケモンで、同じ1番目の技でも全く違う技なので、これも別の出力として表現したほうがよいでしょう。

index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
行動	ポケ0技0	ポケ0技1	ポケ0技2	ポケ0技3	ポケ0に交代	ポケ1技0	ポケ1技1	ポケ1技2	ポケ1技3	ポケ1に交代	ポケ2技0	ポケ2技1	ポケ2技2	ポケ2技3	ポケ2に交代

このように15個の候補から1つを選ぶ形式にしました。例えばポケモン0が出ているときは、ポケ0技0～ポケ0技3と、ポケ1に交代、ポケ2に交代の6種類が有効な選択肢です。 ただし、瀕死になっているポケモンには交代できません。 無効な選択肢も出力できてしまいますが、その場合は有効なものからランダムに実行することにします。

このようにどのポケモンが場に出ているかで有効な選択肢が変わるため、エージェントへの入力としてその情報を与える必要があります。

1vs1の場合、入力としては相手ポケモンのタイプ、{自分,相手}の{残りHP率、状態異常、ランク補正}の41次元の値を与えていました。 これに対し、自分の3匹のポケモンのうちどれが場に出ているか（3次元）、どれが瀕死でないか（3次元）という情報を追加します。 相手の残りポケモン数なども役に立つ可能性はありますが、複雑化するためまずは最低限の情報にとどめました。

報酬の改良、対戦相手の変更

上記の入出力変更だけで学習を試みたのですが、戦略があまり学習されず、そもそも無効な選択肢を選ぶ確率が60%近くあるなどうまくいきませんでした。

従来の報酬は、ゲーム終了時のみ勝ったら1、負けたら-1を与えていました。まず無効な選択肢を選ばないように誘導するため、無効な選択肢を選んだ場合は報酬として-0.1を与えるようにしたところ、この点は改善しました。

ポケモンが3匹瀕死にならないとバトルが終了しないため、1匹のときよりターン数が多く、行動と勝敗の因果関係を学習することが難しくなっています。そのため補助的な報酬として、ダメージに基づくものを加えました。 相手に与えたダメージ（HP割合）および、瀕死にした際に即時に0.1程度の報酬を与えます。逆に自分がダメージを受けたり瀕死になったら逆の符号の報酬を与えます。

また、強化学習の際に対戦する相手はランダムに行動していましたが、これだと簡単に90%以上の勝率となってしまい戦略の優劣がつきにくくなっていました。そのため、相手をすでに学習されたエージェントに従って行動させることにしました。パーティごとにエージェントのパラメータを学習しないといけないため、相手パーティの多様性は減ってしまいますが、まずは固定した20パーティを相手に何度も対戦させるようにしました。

定性的な結果

これらの改良を加えた結果、3vs3のバトルにおいてちょっと賢そうな戦略が見られるようになりました。

与えたパーティに対して学習された戦略をいくつか紹介します。戦略の意味付けは対戦ログから私が主観で判断しています。

* ゲンガー (LV 50 HP 167/167)
サイコキネシス すてみタックル 10まんボルト
カブトプス (LV 50 HP 167/167)
いあいぎり なみのり きりさく かげぶんしん
ルージュラ (LV 55 HP 188/188)
れいとうビーム あくまのキッス サイコキネシス

ルージュラは、相手が眠っていなければあくまのキッスを使い、眠っていれば攻撃技を選択します。相手としてフリーザーが出てきたら、ルージュラに交換するという行動も見られました。ふぶきで凍らされないための知恵といえます。

* カイロス (LV 55 HP 188/188)
ちきゅうなげ つるぎのまい のしかかり はかいこうせん
カイリキー (LV 50 HP 197/197)
いわなだれ だいもんじ あなをほる メガトンパンチ
フリーザー (LV 50 HP 197/197)
れいとうビーム ふぶき

カイロスは、つるぎのまいを積んでからのしかかりのコンボを狙っています。エージェントの入力としてランク補正が入っているので、積んでから攻撃という挙動は実現可能で、実際に学習されました。 しかしながら実際は積んでいる間に倒されたり、急所に当たって積んだ効果がなかったり（初代特有の仕様）する場面が多いようでした。

* サンダー (LV 55 HP 215/215)
ドリルくちばし 10まんボルト
ニョロボン (LV 50 HP 197/197)
かげぶんしん れいとうビーム さいみんじゅつ
ガルーラ (LV 50 HP 212/212)
のしかかり かいりき とっしん ちきゅうなげ

サンダーはサイドンに対して効果のない10まんボルトを選択してしまい、うまく学習ができていません。 ニョロボンはさいみんじゅつで相手を眠らせたうえでかげぶんしんを積み、その後れいとうビームを連打するという凶悪な戦法をとることもありました。

面白い例をいくつかピックアップしましたが、全体的にはうまくいかない例が多く、学習方法の改善が必要と思われます。

第29回世界コンピュータ将棋選手権 参加登録しました【コンピュータ将棋】

2019年5月3日開催の第29回世界コンピュータ将棋選手権の暫定チーム一覧が出ています。（1/11時点、シードチームは非表示？）

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

私が開発している「ねね将棋」も出場登録しました。忘れないようにと最低限の事項を書いたアピール文書も、もう公開されていますね。

昨年の選手権のあとは内部構造の刷新を行っただけで、棋力的にはアップしていません。

将来的に強化学習を実装しやすい構造にはなったのですが、手持ちの計算資源を考えると今すぐ取り掛かるのは得策ではないため、 今回はそれ以外の部分の整備をしっかり進めて来年につなげようと考えています。

今回解決したい課題としては、次のようなものがあります。

• 短い思考時間でのバッチサイズ問題
  • MCTSで探索をするのですが、評価関数をGPUで計算するためスループットを上げるには100~1000局面を同時に評価（バッチ評価）する必要が生じます。しかし、評価が完了していない局面の子を探索できないためバッチサイズを上げると探索深さが浅くなり（PVを深くする代わりに兄弟局面を評価することになる）、棋力としては下がるようです。持ち時間が短く、GPU性能が高いとトレードオフが顕著で、うまい妥協点を探したいところです。
• 思考時間管理
  • MCTSにおいて、思考内容に依存して思考時間を変化させるにはどうすればいいか検討しています。

もしかしたら囲碁界隈にノウハウがあるかもしれないので、調べる必要があります。

これらがうまくいけば、昨年よりちょっと強いねね将棋をお見せできると思います。

GPU1枚でのfloodgate対局と学習の両立【コンピュータ将棋】

12月24日、来年の世界コンピュータ将棋選手権(WCSC29)の募集が開始されました。 ねね将棋もこの大会に向けて徐々にですが改良を続けています。

ねね将棋はDeep Learningベースの評価関数を用いており、その学習にも対局エンジンの探索部からの評価もGPUを必要とします。 いろいろな評価関数のモデルパラメータを試していますが、1つのモデルを学習するのには数日かかります（強化学習はまだやっていません）。 学習と同時に対局エンジンからもGPUを使おうとすると、GPUが1枚しかないので競合して速度が下がってしまい、正しく強さを測れません。 対局エンジンを動かすたびに手動で学習を一時停止するのは面倒なので、これを自動化してみました。 特に、floodgateのように30分毎に対局が開始し、対局が終わると暇になるような状況だと、対局が開始した際に学習を一時停止、終了した際に再開できるので便利です。

環境はWindowsで、このような用途にはMutexを使うことができます。 Mutexは次のような性質を持ちます。

• CreateMutexで、指定した名前のMutexを作成するか、すでにあれば開く。
• OpenMutexで、指定したMutexがすでにあれば開く。存在しなければエラー。
• CloseHandleで、既に開いてあるMutexを閉じる。これを用いなくても、プロセスが終了すれば自動的に閉じられる。
• すべてのプロセスがMutexを閉じると、そのMutexは存在しなくなる。

Mutex本来の用途とは少しずれるのですが、二重起動防止などで使われるテクニックに似ています。

これを用いると、次のような処理が書けます。

• 学習プロセスでは、定期的にOpenMutexを実行し、Mutexが存在するかどうか確認する。存在すれば、存在しなくなるまで待機。
• 対局エンジンでは、GPUを使い始める時にCreateMutexを実行する。使い終わったらCloseHandleで閉じる。もしクラッシュしても自動で閉じられるので問題ない。

学習プロセス側では、次のコード(python)で、1バッチ進むごとにwait()を呼び出します。もしその際Mutexが存在していればブロックすることにより、学習が一時停止するわけです。

"""
Mutexを用いて、将棋エンジンが動いている間は学習を止めるユーティリティ。
"""
import win32api
import win32con
import win32event
import pywintypes
import time

MUTEX_ALL_ACCESS = win32con.STANDARD_RIGHTS_REQUIRED | win32con.SYNCHRONIZE | win32con.MUTANT_QUERY_STATE


class MutexStopper:
    def __init__(self, mutex_name="NENESHOGI_GPU_LOCK"):
        self.mutex_name = mutex_name

    def wait(self):
        n_wait_seconds = 0
        while self._is_mutex_exist():
            n_wait_seconds += 1
            time.sleep(1)
        return n_wait_seconds

    def _is_mutex_exist(self):
        try:
            hMutex = win32event.OpenMutex(MUTEX_ALL_ACCESS, False, self.mutex_name)
            win32api.CloseHandle(hMutex)
        except:
            return False
        return True

対局エンジン(C++, やねうら王を改造)では、次のように関数を定義しています。

#include "../../extra/all.h"
#include <Windows.h>

// GPUロックタイムアウト
// epochからの秒数がこの値以上の時、ロックを解放する。
static atomic<std::chrono::seconds> gpu_lock_timeout(std::chrono::seconds(0));
static std::thread* gpu_lock_thread = nullptr;

// GPUをロックするスレッド。
// 特定のMutexを作成することで、学習プロセスはそれを察知してGPU利用を一旦停止する。
// タイムアウトでMutexを削除する。
static void gpu_lock_thread_main()
{
    HANDLE hMutex = NULL;
    while (true)
    {
        std::this_thread::sleep_for(std::chrono::seconds(1));
        auto current = chrono::duration_cast<chrono::seconds>(chrono::system_clock::now().time_since_epoch());
        if (hMutex && gpu_lock_timeout.load() < current)
        {
            // Mutex削除
            sync_cout << "info string release gpu lock" << sync_endl;
            CloseHandle(hMutex);
            hMutex = NULL;
        }
        else if (!hMutex && gpu_lock_timeout.load() >= current)
        {
            // Mutex作成
            sync_cout << "info string acquire gpu lock" << sync_endl;
            hMutex = CreateMutex(NULL, FALSE, TEXT("NENESHOGI_GPU_LOCK"));
            if (!hMutex)
            {
                sync_cout << "info string FAILED acquire gpu lock" << sync_endl;
            }
        }
    }

}

// GPUをロックするスレッドを開始する。
void gpu_lock_thread_start()
{
    if (!gpu_lock_thread)
    {
        gpu_lock_thread = new std::thread(gpu_lock_thread_main);
        gpu_lock_thread->detach();//プロセス終了時に自動的に終了させる
    }
}

// GPUのロックタイムアウトを延長する。
void gpu_lock_extend()
{
    sync_cout << "info string extending gpu lock" << sync_endl;
    auto next_timeout = chrono::system_clock::now() + chrono::seconds(60);//1手60秒以上はめったにないのでこれぐらいで
    gpu_lock_timeout.store(chrono::duration_cast<chrono::seconds>(next_timeout.time_since_epoch()));
}

まず対局エンジン開始時にgpu_lock_thread_start()を呼んでおきます。そして、1手ごとの思考開始時にgpu_lock_extend()を呼びます。そうすると、その時点から60秒間Mutexが存在するようになり、学習側が一時停止するという仕掛けになります。USIのgameoverを受信した際にMutexを閉じるという実装でもよいかと思います。

この記事のコードについては、特に権利を主張しませんので適当に組み込んでご利用ください。

こんな感じで、限られたリソースを便利に使う機構を作ると作業がはかどります。棋力には関係ないですが。

2技関係によるパーティ強さの予測(初代全ポケモン参加)【PokéAI】

前回の記事で、山登り法によるパーティの最適化をポケモン3匹のパーティについて実験しました。

select766.hatenablog.com

そこで生じた問題の1つは、探索空間が広すぎるためか最適化結果が芳しくないというものでした。 1匹のポケモンの構成パターンが仮に1億通り*1あるとして、3匹の組み合わせとなると1億の3乗となり、大幅に最適化が難しくなっている可能性があります。

解決策として、ランダムに探索を行うよりも有望なパターンに絞って探索を進める方法が考えられます。 例えば、現在の方法だと技「なみのり」を強力な「ふぶき」に置換した場合と明らかに弱い「みずでっぽう」に置換した場合を等確率で生成し、 ランダムに対戦させて強さを測る（それなりに時間がかかる）という方法になっています。 ここで明らかに良さそうな「ふぶき」のパターンを生成する確率を高めることで、探索の無駄を減らせるはずです。 そのための考え方として、経路探索におけるA*のように、解の良さを近似的に表現してくれるヒューリスティックの導入を考えます。 ここでは、パーティ構成を与えると、その強さの近似値を出力するような関数を作成します。 もともと山登り法で強いパーティを選択する方法は他のパーティと多数対戦させて勝率（レート）を計算するというものであり、 そのパーティ候補を作成するためのヒューリスティックなので、これより圧倒的に高速に計算できないと意味がありません。

そこで、パーティに含まれるポケモンや技に対して点数を与え、合計得点によって強さを予測（近似）する手法を提案します。 簡単に言えば、パーティにフーディンがいれば+10点、コイキングがいれば-10点、サイコキネシスを覚えていれば+5点…のようにパーティの要素それぞれに点数をつけることでその強さを予測しようという発想になります。

技術的には以前の記事の焼き直しになりますので、先にそちらをご覧ください。 以前との違いは、ポケモンの種類が20種類から151種類（初代全ポケモン）に拡張されたこと、回帰先が勝率から正規化されたレートに変更された点です。

select766.hatenablog.com

特徴量は上の記事と変わりませんが、ポケモン・技の種類が増えているので次元数は大きく増えています。該当する要素が1、それ以外が0となるベクトルで、正規化はしていません。

• P
  • 単独のポケモン (151次元)
• M
  • 単独の技 (165)
• PP
  • パーティ内のポケモン2匹 (151*(151-1)/2=11325)
• MM
  • あるポケモンが覚えている2つの技の組 (165*(165-1)/2=13530)
• PM
  • ポケモンと、それが覚えている技の組 (151*165=24915)

合計で50086次元となります。

データ

データは、ランダムに生成された10,000パーティを相互に対戦させて得たレートです。 パーティから対戦なしにレートを予測するモデルをリッジ回帰で学習します。 ライブラリはscikit-learnです。

入力となるパーティとレート（上に表示）の例を示します。上位、下位を抜粋しています。

2038.1734179741654
* ゲンガー (LV 50 HP 167/167)
  のしかかり ちきゅうなげ 10まんボルト メガトンキック 
  タッツー (LV 50 HP 137/137)
  みずでっぽう あわ スピードスター すてみタックル 
  カイリュー (LV 55 HP 216/216)
  のしかかり だいもんじ りゅうのいかり ふぶき 

2036.6117272435956
* サンダー (LV 50 HP 197/197)
  ドリルくちばし 10まんボルト かみなり ふきとばし 
  プテラ (LV 55 HP 204/204)
  つばさでうつ ねむる すてみタックル はかいこうせん 
  ゲンガー (LV 50 HP 167/167)
  さいみんじゅつ あやしいひかり ナイトヘッド どくどく 

2023.1601683063693
* バタフリー (LV 50 HP 167/167)
  ふきとばし サイコウェーブ ねんりき しびれごな 
  アーボック (LV 50 HP 167/167)
  あなをほる すてみタックル じわれ はかいこうせん 
  ゲンガー (LV 55 HP 182/182)
  サイコキネシス サイコウェーブ あやしいひかり かみなり 

873.1324613556571
* コイキング (LV 55 HP 138/138)
  はねる たいあたり 
  コクーン (LV 50 HP 152/152)
  かたくなる どくばり いとをはく 
  パラス (LV 50 HP 142/142)
  キノコのほうし つるぎのまい すてみタックル しびれごな 

869.9415352355768
* マルマイン (LV 55 HP 182/182)
  だいばくはつ ソニックブーム リフレクター はかいこうせん 
  タマタマ (LV 50 HP 167/167)
  さいみんじゅつ リフレクター どくのこな テレポート 
  コイキング (LV 50 HP 127/127)
  はねる たいあたり 

868.9717116445033
* コイキング (LV 50 HP 127/127)
  たいあたり はねる 
  ドガース (LV 50 HP 147/147)
  どくどく ヘドロこうげき じばく だいもんじ 
  トランセル (LV 55 HP 171/171)
  かたくなる たいあたり いとをはく 

リッジ回帰の精度

各特徴を用いた場合に、回帰精度がどう変化するかを調べました。 リッジ回帰のパラメータ"C"は、{1e-4, 1e-3, 1e-2, 1e-1, 1e0}の中から5-fold cross validationで最善のものを選択しました。特徴の組み合わせごとに別の値になっている場合があります。

精度は決定係数で表示しています。1に近いほど良い結果を意味します。

P	M	PP	MM	PM	決定係数
Y					0.509
	Y				0.480
Y	Y				0.749
		Y			0.217
Y		Y			0.482
			Y		0.432
	Y		Y		0.494
Y	Y	Y	Y		0.737
Y	Y	Y	Y	Y	0.769

すべての特徴量を使用した場合が一番いい結果となりました。PP特徴だけの場合は極端に精度が悪いことがわかりました。 PPはポケモンの組み合わせなので、10000次元ほどあるうちで1パーティでは3つしか要素がありません。10000パーティあっても各次元は平均3回程度しか使用されず、学習データ不足だといえます。

学習結果の観察

学習したモデルは線形モデルなので、各要素の重みから重要度を読み取ることができます。ここでは、正の値ならパーティを強くする方向に、負の値なら弱くする方向に作用している要素だとみなすことができます。

全特徴を利用して学習したモデルについて、特徴の種類ごとにtop10, worst10を表示しました。

P特徴

重み	意味
0.394	ゲンガー
0.362	ケンタロス
0.333	ギャラドス
0.314	ラプラス
0.310	カイリュー
0.268	スターミー
0.268	フリーザー
0.263	サンダー
0.259	カブトプス
0.256	オムスター
-0.312	プリン
-0.259	ニョロモ
-0.241	コラッタ
-0.237	ミニリュウ
-0.227	ヒトカゲ
-0.224	ゼニガメ
-0.217	コダック
-0.215	ケーシィ
-0.214	コンパン
-0.211	ズバット

ゲンガー・ケンタロスなどおなじみのポケモンが強いという結果です。5位にカイリューが来ています。ランダムに生成したパーティなので、ふぶきが多用されないことが上位に来られた理由だと思われます。 逆に言えば、強いパーティばかりの環境においてモデルを学習すれば違う値になるだろうと予想できます。 下位のほうは意外な結果です。コイキングやトランセルが来るわけではないようです。

M特徴

重み	意味
0.339	ふぶき
0.281	サイコキネシス
0.259	ハイドロポンプ
0.241	ナイトヘッド
0.237	れいとうビーム
0.217	はなびらのまい
0.198	はかいこうせん
0.198	なみのり
0.195	10まんボルト
0.193	かえんほうしゃ
-0.361	じばく
-0.281	いとをはく
-0.236	だいばくはつ
-0.218	はねる
-0.214	ふきとばし
-0.204	テレポート
-0.203	こうそくいどう
-0.185	なきごえ
-0.181	にらみつける
-0.177	せいちょう

上位は強い技、下位は弱い技が順当に出ています。じばく・だいばくはつは適切なタイミングで使えば強力ですが、ランダムに発動しているため最悪です。 ここでトランセルが覚えるいとをはくや、コイキングが覚えるはねるがかなり負の大きな係数になっているので、 技だけで十分予測ができてしまいポケモンの側ではこれらの係数があまり大きくならなかったのかもしれません。

PP特徴

重み	意味
0.060	ニョロボン,ベトベター
0.060	オニスズメ,ペルシアン
0.059	ラッキー,ヒトデマン
0.056	リザードン,カメックス
0.055	コダック,アズマオウ
0.052	ガルーラ,ハクリュー
0.052	ピカチュウ,ウツボット
0.050	マルマイン,ナッシー
0.050	トランセル,サイドン
0.050	マタドガス,カビゴン
-0.068	ゼニガメ,アーボ
-0.060	ディグダ,ニャース
-0.060	スリープ,ミニリュウ
-0.057	エビワラー,ドガース
-0.056	トランセル,パラス
-0.056	ダグトリオ,スリープ
-0.051	ズバット,タマタマ
-0.050	リザード,ポッポ
-0.050	バタフリー,トサキント
-0.050	ニドラン♀,プリン

ポケモン同士の相性補完などが表現されることを期待したのですが、解釈しづらい結果です。係数が小さく、ほとんど役に立っていないという状況です。 ポケモンの行動がランダムなので、相性が悪いときに交代するなどの戦略が加味されていないという原因もありそうです。

MM特徴

重み	意味
0.161	だいばくはつ,じばく
0.142	ナイトヘッド,サイコキネシス
0.132	さいみんじゅつ,メガドレイン
0.129	サイコキネシス,でんじは
0.123	はかいこうせん,つるぎのまい
0.117	メガドレイン,ねむりごな
0.112	かげぶんしん,ナイトヘッド
0.112	さいみんじゅつ,サイコキネシス
0.112	いあいぎり,ちきゅうなげ
0.109	サイコウェーブ,10まんボルト
-0.188	はねる,たいあたり
-0.172	だいばくはつ,ナイトヘッド
-0.163	どくばり,いとをはく
-0.163	いとをはく,たいあたり
-0.157	さいみんじゅつ,じばく
-0.151	メガドレイン,じばく
-0.148	かげぶんしん,ふきとばし
-0.148	サイコウェーブ,じばく
-0.145	だいばくはつ,ねむる
-0.123	にらみつける,ふきとばし

意外にも、だいばくはつ,じばくの組が最上位です。M特徴でどちらも非常に大きい負の値ですが、両方覚えていたとしても片方を覚える以上に悪くならないということで補正がかかっているようです。 上位では有力な攻撃技と補助技の組み合わせが良く出てきているようです。

PM特徴

重み	意味
0.195	フリーザー,れいとうビーム
0.193	サンダー,10まんボルト
0.184	ゴースト,ナイトヘッド
0.183	フーディン,サイコキネシス
0.180	サンダー,ねむる
0.169	サンダース,かみなり
0.166	フリーザー,ふぶき
0.165	ナッシー,サイコキネシス
0.160	ファイヤー,ゴッドバード
0.159	ファイヤー,だいもんじ
-0.191	ゴースト,だいばくはつ
-0.182	ゲンガー,じばく
-0.181	ゴースト,じばく
-0.179	コイキング,たいあたり
-0.179	コイキング,はねる
-0.163	ゲンガー,だいばくはつ
-0.152	キャタピー,たいあたり
-0.152	キャタピー,いとをはく
-0.150	ヤドン,じわれ
-0.147	パウワウ,つのドリル

上位はタイプ一致攻撃技が主です。同じ技でも運用するポケモンとの相性のような部分を取り出せていることが期待できます。 下位は有用でない技が出てきています。じわれは一見強そうですが、初代では相手より素早くないと命中しないため、素早さが低いヤドンでは有効でないということでしょう。

定性的にも面白い結果が得られました。定量的にもある程度うまくいっているようなので、今後このモデルを探索に組み込んでみようと思います。

*1:ポケモン150種類×技候補30種類の4乗ぐらい

技術書典5の本を国会図書館に納本しました

先日、「技術書典5で頒布した本を国立国会図書館に納本した」との記事を見かけました。

note.mu

制度の概要については上の記事が詳しいのでそちらをご覧ください。

納本のお願い｜国立国会図書館―National Diet Library

国会図書館にはあらゆる本が入っているとは聞いたことがありましたが、同人誌であっても納本は義務なんですね。しかも罰則規定あり。 同人誌を納本するという記事があえて存在するぐらいなので、ほとんどの人は納本していないと思われます。 「同人作家の9割は犯罪者！」という表現が成り立ちそうでちょっと怖いところです。

郵送でもいいらしいのですが、国会図書館に行ったことがなかったので見物がてら納本しに行きました。

国会図書館は国会議事堂のすぐ近くにあります。普通の入り口ではなくて、関係者用っぽい西口から入る必要がありました。

納本手続きのカウンターへ行き、現物を提出の上氏名・住所・書名などを書けばすぐに納本できました。

受領書がこちら。あとで郵送でももらえるようです。

書名が長くてすみません。

これにて私の本は、日本が続く限り未来永劫残り続けるでしょう。なんか生きた証を残したような気分です（大袈裟）。

5月に同人誌を納本した方がいるのですが、国立国会図書館サーチにおいてタイトルで検索したら出てくるのか試してみました。

prehyou2015.hatenablog.com

プリキュアの数字ブログのほん (@kasumi): 2018｜書誌詳細｜国立国会図書館サーチ

ちゃんと出るようです。納本の時の書類に自分の名前は書いたのですが、本の発行者名などを書く場所はありませんでした。この辺は奥付などから入力されるのでしょうか？ 自分の本がもし検索にかかるようになったら見ておきたいと思います。

納本した本は国会図書館で読めると思いますが、面倒だという方のために（？）オンラインで電子書籍を販売していますのでよろしければどうぞ。

select766.booth.pm

以下、2018-11-19追記

郵送で受領書が届きました。そして検索にもかかるようになっていました。これにて納本完結。

http://iss.ndl.go.jp/books/R100000002-I029322458-00