Character

Character

Deceptive Cadence

Ramuh (Elemental)

You have no connection with this character.

Follower Requests

Before this character can be followed, you must first submit a follower request.
Do you wish to proceed?

  • 0

黒魔道士のスキル回しを組合せ最適化問題として捉えてみよう(第1回)

Public


黒魔道士のスキル回し説明コンテンツが人気
よくYoutubeなどで、スキル回しを説明した動画が人気ですね。
でも、あれが最適かという判断はできるでしょうか?
配信者本人もそれは説明できないでしょう。あの手のコンテンツは「配信者が思う最適」です。

経験からくる推測を前提にしていては解は求まらない
出力に「黒魔道士の単位時間あたり最大の与ダメージ」が出るパス(最適パス)を探すような問題では、その命題の前提がヒューリスティックな帰納的な推論である限り、答えられません。
ある制限(pain)の中で利益(gain)を最大にする条件の組み合わせを探すような問題は、「組合せ最適化問題」と呼ばれ、昨今話題となっている量子コンピュータ(とりわけ量子アニーリング方式の)が得意とする問題のカテゴリになります。

余談ですが、量子コンピュータはどんな計算でも速い訳ではありません。
というよりも通常の計算機(決定論的チューリングマシン系)ではクラスNPに属しクラスPではない問題に対する有効なアルゴリズムは無いと予想されており、解きたいならば総当たりで確認していく方法しかありません。
※多少の工夫の余地はあるが、抜本的な改善を与えるものではない
量子アニーリング方式の量子コンピュータは、決定論的チューリングマシンでは無いので、こういった問題に対して強いということになります。(それでも最適解である保証もありません。現実的な問題では最適である必要はなく最適解に近い良解であればいいことが多い)


演繹的な推論で正しい結論を導くための絶対条件は、前提が絶対的・普遍的に正しいことです。

NP問題の解法の王道
では、通常の計算機では答えを求めることができないのか?というと、そうではありません。
クラスNPの問題は、全て別のクラスNPの問題に多項式時間で帰着させることができることが証明されています。
この帰着後の問題は、全てのNP問題を含んでいるので、もっとも難しいNP問題(NP完全問題)と呼ばれます。
つまり、NP完全問題の解き方を考えることで、全てのNP問題に対応できるということになります。
そして、NP完全問題としてよく知られているのが、「充足可能性問題」です。

充足可能性問題
充足可能性問題はステファン・クックによってNP完全であることが証明されました。
この充足可能性問題を高速に解く方法(SATソルバー)の開発が盛んに研究されています。
どんなNP問題も充足可能性問題に変換できるのだから、SATソルバーで解けばいいということになります。
組合せ最適化問題も一度、充足可能性問題に変換することで、SATソルバーで最適解を見つけることができるということになります。

観測値から計算モデルのパラメータ尤度推定
ダメージの総和を比較するのですが、装備品や他パラメータで影響を受けるので、もともとスキルが持つ攻撃力の値の積算で比較したいと思います。
ただし、スペルスピードは実際の詠唱時間に直接影響を与えるので、この関係はモデル化(数式化)が必要です。
こういうものはベイズ推定が使えます。

実際のキャストタイムは、スペルスピードとスキルの標準キャストタイムを変数に持つ関数で決定されます。(予想です)
時間の削減のされ方をイメージして、リニアなのかエクスポーネンシャルなのかを勘で決めましょう。
もしかしたらスペルスピードで加速度的に速くなっていくかもしれないので、2次関数だと仮定します。
スペルスピードを変数に持つ二次関数に標準キャストタイムが合わさって、実際の詠唱時間が決められていると仮定して数式を作ります。この時の変数の倍率は適当で構いません。
そして、データをとります。色々なスペルスピードで実際に魔法が何秒で発行されるのかをデータ集めします。

この観測値に近づくように変数の方を推定していきます。推定の方法にもいくつかあります。代表的なものでは偏微分方程式を解くものと、モンテカルロ・マルコフ・チェインによるシミュレーションでの尤度推定かな。
これらの結果をフィードバックすると、詠唱時間の削減はリニアな傾向がある(2次の倍率はほぼゼロ)ようなので、
計算がシンプルな一次関数でブラッシュアップしました。
スペルスピード、黒魔紋による補正で標準キャストタイムからどのくらい縮むのかを予測する式を作り計算した結果です。(10ms単位で計算する予定なので数値はそれに合わせてある)



同じようにアストラルファイアのスタック数がダメージに与える補正量に関しても求めることができます。

ちなみに、このような手法は最近ではAI(機械学習)にもよく使われます。


さて、準備はできました。では実際に計算のための環境を作っていきましょう。
次回は黒魔道士スキルモデルの設計です。
Comments (0)
Post a Comment
ForumsMog StationOfficial Blog

Community Wall

Recent Activity

Filter which items are to be displayed below.
* Notifications for standings updates are shared across all Worlds.
* Notifications for PvP team formations are shared for all languages.
* Notifications for free company formations are shared for all languages.

Sort by
Data Center / Home World
Primary language
Displaying