この記事はニューノーマルぴょこりんクラスタ Advent Calendar 2020のために書きました。

はじめに

少し前にこんな記事を書きました。 capp365.hateblo.jp

リアルタイムに高度な意思決定が必要なゲーム（？）の一例として、ぱちゅコンを扱っています。ぱちゅコンは一定時間内、人形を戦わせて図書館の蔵書を守るゲームです。ゲーム中、以下のような意思決定が求められます。

どの人形をどれだけ購入するか
各人形のレベルアップをするか
各人形をどこに配置するか
スペルカードをどのタイミングで使うか

前回の記事では、1～3を自動でランダムに実行する部分を実装しました。ってことは4か、という話になるんですが、4は扱いません。いわゆる緊急回避的な必殺技(5種類)なのですが、別に使わなくても勝てると思っているので、あと各１回ずつしか使えず、ちょっと最適実行タイミングをデータから学習するってのも微妙な気がしたので・・・。

というわけで今日取り扱うのは「1. どの人形をどれだけ購入するか」、すなわち購入する人形の比率とその合計数です。これを雑にチューニングしてやろうというやつをやります。

目的関数はゲームをプレイしたときのスコア、となるんですが、画面上のスコアの数字をテンプレートマッチングするのがめんどくさかったので、経過時間を目的関数とすることにしました。ゲームオーバーにならずにクリアできるまで続けられれば当然スコアが高くなるので、まぁ悪くない指標でしょう。

有識者の予想

前回同様の愉快な仲間たちです。

f:id:cappsLk:20201206151039p:plain

僕の普段の配分からすれば、 (中国、メイド長、ぱちぇ、おぜうさま、フランちゃん)=(0.4,0.4,0.1,0,0.1)で、合計40体もいればノーマルは十分かなと感じています。というか近接型の中国と、メイド長で合計２０体もいればクリアできるんじゃないかなと思っています。おぜうさまは正直ほとんど使うことがないです。飛距離の長い弾幕型なのですが、高価だし、復活が遅いし、敵とかなり距離を置こうとする（逃げる）ので、扱いづらいのです。

最適化の概要

最後に詳細を書くつもりなので（書いてなかったらごめんなさい）、ここでは簡素に。最適なパラメータを得るために、逐次更新をしていきます。ランダムにパラメータを振ってゲームをプレイし、プレイ結果が良かったら最適化したいパラメータをそっち側に寄せる、というのをひたすら繰り返します。

ひたすらランダムに振ってても芸がないので、徐々に完全にランダムではなく現在のパラメータの値近傍で乱数を振るようにします。現在のパラメータが50体、(0.2,0.2,0.2,0.2,0.2)だったら、50体、(0.18,0.22,0.24,0.12,0.24)みたいなイメージ。

結果と考察

ノーマルモードを50回繰り返しました。その間の各人形の選択確率の遷移を以下の図に示します。縦軸が確率、横軸が反復回数。あ、ちなみに最適な人形数は50となりました。

f:id:cappsLk:20201223104624p:plain

最重要人財はメイド長（線の色：オレンジ）ということになっています。メイド長は前述のとおり僕も普段からよく使う子なのですが、一方でもう片方の主戦力である中国（線の色：青）はずいぶんと落ち込んでいます。

普段はほぼ無用のおぜうさま（線の色：赤）２番手、結構重要な扱いを受けています。僕の想像と全然違うぞ？？？？？

本当によくなってるのか、悩ましくなってきました。以下は縦軸スコア（プレイ時間）、横軸反復回数をプロットしたものです。

f:id:cappsLk:20201223102156p:plain

オレンジの点は前述した、「現在のパラメータの値近傍で乱数を振る」ケースを表しています。後半になるにつれてその出現比率が増加します。加えて、オレンジの点がついているスコアは、特に後半で高くなってくれることを期待しています（推定した最適パラメータの近傍のはずなので）。実際に多少のばらつきはあるものの、やんわりスコア高めを維持できているのではないでしょうか。

ちなみに前回の動画が12分程度なのでスコア、今回で言うところの所要時間は720秒程度、クリアの所要時間は大体1100秒になっています。まぁまぁいいところまで行ってるんじゃないでしょうか。ほんとはベストなパラメタに基づくプレイ動画も貼りたかったんだけど時間がないのでここまで。

有識者の予想（）と大きく結果が異なることへの解釈

まぁそもそも局所解に落ちてる可能性もありますが、あくまで今回の結果を信じて考察してみましょう。

人形には３種類のタイプがある、と以前の記事で説明した記憶があります。近接型、弾幕型、飛行型です。近接は弾幕に、弾幕は飛行に、飛行は近接に強いというじゃんけんのような関係になっています。

この観点でいくと、近接型であるフラン、中国（特に中国）の出現確率が低くなっています。

一つの仮説として、上手に配置ができない状況では近接型はうまく立ち回れない、ということが考えられます。逆に遠距離射撃ができたり、いつでも好戦的というわけではなく、時には敵と距離を取ることがある弾幕型、飛行型のほうが、配置が下手っぴでも上手に振る舞えるため、立場が逆転したのではないかと考えられます。敵に対して適切な位置につけないというのは結構致命的だと改めて感じていて、時々眺めていると、遠距離攻撃の得意な大量のおぜうさまが遠くから敵をエイムして爆殺しているシーンや、逆に遠距離射撃の得意な敵が大量に遠くに生き残っていて、画面中央部の僕の人形たちは距離が十分にあるので遠方の敵にヘイトが向かず、無抵抗で虐殺されるシーンなどが見られたりすることがありました。

今後の課題

今回やっぱり人形数だけを制御しても限界があるなと思ったので（ノーマルですらギリギリクリアできるかできないかだったので）、敵が来たときのリアルタイムの人形配置もうまくやりたいなぁと思っています。そのための地味に大きな課題が地味に学習データをたくさん集めることで、やっぱり1プレイにかかる所要時間がでかすぎるんですよね。今回のように50回プレイするのに一晩使っちゃったりするので、ちょっと地道に今回書いたスクリプトを動かし続けて、学習データを集めたり死体かなと思っています。

あぺんでぃくす：モデルとパラメタ更新（雑）

ごめんねごめんね、ちょっとテンパってて記事をちゃんと書く時間がないの。

$n$ : 購入を試行する人形の数
$\boldsymbol{p}=(p_0,p_1,p_2,p_3,p_4)$ : 各人形を購入する分配確率
としたとき、ゲームをプレイして結果のスコアを得ることは、これらのパラメータに応じて、何らかの分布からスコア $s$ が生成されると解釈することができます。
$s \sim p(s|\boldsymbol{p}, n)$ どうせ分布の形もわからないし、めちゃめちゃ雑に $n$ 、 $\boldsymbol{p}$ のチューニングをしましょう。

まず $n$ を制限します。 $n \in$ { $10, 20, 30, 40, 50, 60 ,70, 80, 90, 100$ }としましょう。この時のスコアの期待値を変数として保持しておくことにします。

$n$ や $\boldsymbol{p}=(p_0,p_1,p_2,p_3,p_4)$ を適当にサンプリングして、その結果に応じて期待値を更新していきます。

平均の逐次計算といえば、 $\mu_{i+1}=\frac{1}{i+1} (\mu_i + x_{i+1})$ ですが、雑に $\mu_{i+1}=\frac{\mu_i + x_{i+1}}{2}$ とします。雑な定式化なので適切な解釈を求められても困りますが（？？？？）、あえて解釈を与えるなら過去のサンプルをあまり信用していない、最新のサンプルを信用して大きな重みを与えていると解釈していただければ。

そして最適分配確率 $\boldsymbol{q}=(q_0,q_1,q_2,q_3,q_4)$ 、は適当に初期値を与えておいて、サンプリングしたパラメータでプレイしたゲームのスコアが良かったらそのパラメータに寄せて、悪かったらそのパラメータから離すといった処理をしていくことにします。

勾配法的なノリなのですが、そもそも微分できないし（関数が未知）、傾きを計算して勾配の代わりにしても、そもそも同じパラメータでもスコアがばらついたりと、あんまり真面目に勾配計算するのも馬鹿らしいので（？？？）、スコアが良い悪いだけ判断して、良くなる方向に一定割合 $\rho$ だけ近づける、つまり符号の方向だけ信用して更新することにします。 $\rho$ さえ徐々に小さくしてけばまぁ収束はするでしょ（雑

ここまでスコアが良くなったら、悪くなったらと言ってきましたが、このスコアの良し悪しの基準に前述の期待値を使うことにします。前述の期待値と比べて高いスコアが出たらよくなってる、低いスコアになったら悪くなってると判断します。

まとめるとこんな感じ。

期待値と最適分配確率 $\boldsymbol{q}$ の初期値を設定
期待値600秒、最適配分をそれぞれ0.2とした。
ランダムに $n'$ や $\boldsymbol{p'}$ を得る
得たパラメータでゲームをプレイ
スコア $s$ を得る
$n=n'$ のときの期待値と比較
スコア $s$ が大きければ、 $\boldsymbol{p'}$ に $\boldsymbol{q}$ を近づけ、小さければ遠ざける(塩梅は学習率 $\rho$ でよしなにやり、反復回数に応じて $\rho$ を小さくしていく)。
期待値 $E(s|n=n') = \frac{E(s|n=n') + s}{2}$ で期待値を更新する。
2に戻る