刺身の上にたんぽぽ乗せる日記

プログラミングしたり、自販機の下に落ちてる小銭を集めたりしてます

モンスターハンタースキルシミュレータのアルゴリズム

この記事はモンハン Advent Calendar 2013 23日目のエントリーです。

こんにちわ!kudzuです。よろしくっく!
MH4用のスキルシミュレータのMH4スキルシミュ(泣)*1や、お守りスナイプ用のウェブページ*2とかを作ってます。


現在HR289で、好きな武器はライトボウガンです。たまに近接で大剣や片手を使うことはありますが、大体ライトボウガンヘビィボウガンを使うことが多いです。

MH3Gでは水冷と麻痺が速射できるイケメンのガノシュトロームが愛銃でしたが、今作は属性速射と麻痺速射が使える銃が大きく減った上に、高レベルギルクエの状態異常耐性の上昇率の高さのせいで、麻痺速射が大幅に弱体化してしまい、大変がっかりしてしまいます。
MH4では、普段は烈日やブリザードタビュラを担いでいます。後はラージャン狩りにアイルーヘルドール。あまり使いませんが、ダークデメントや鬼ヶ島も大好きです。
あまり使う人を見ないですが、ライトボウガンは速射、リミカ、サポと、プレイスタイルが幅広い上に、納刀(納銃?)も素早いので、戦闘中に罠や閃光玉なども織り交ぜやすく、機動力が高く、立ち回りがしやすく、ヘビィほどではありませんが、火力も十分高く、とても面白い武器です。
貫通しゃがみヘビィをお使いの方は、増弾リミカタビュラを是非お試しください。フルリロードからの立ち貫通弾20連発は大変爽快です。

スキルシミュレータのアルゴリズム

前置きはこのくらいにして、MH4スキルシミュ(泣)の中のアルゴリズムを少し紹介したいと思います。

MH4の防具は、各部位に300+の装備があり、それに加えて、お守りという、コンピュータで網羅するにも禿げ上がるような組み合わせの数があります*3。それにくわえて、今回開発したシミュレータは、携帯上のJavascriptで動かさなくてはいけないため、デスクトップアプリの十倍くらいのハンデがあります*4

そんなわけで、一層高速に探索ができるアルゴリズムが必要なわけですが、速度を上げるために、false-negativeが出てしまうと、「このシミュレータはこの装備の組み合わせが出ないぞ!」という話になってしまい、信用がなくなってしまうので、ヒューリスティックを元にアグレッシブな最適化を行うことはできません。

そこで、組み合わせの数を最小限に抑え、枝刈りを保守的に最大限に行い、条件がきついものは枝刈りで素早く結果を出し、条件が緩いものは、最大結果件数で切り上げることで、ある程度実用性がある感じの時間で結果を出すようにしています。

装備の組み合わせを見つける処理はざっくり5つのステップで行われています。

  • フィルタリング
  • グルーピング
  • 装備のスコアリング
  • 装備の選択
  • 装飾品の選択

フィルタリング

まず要求された条件に関係ない防具を除外します。
例えば女性であればアーク一式は装備できなく、逆に男性はフィリアが装備できないので、除外します。他にも剣士・ガンナーの装備の除外、進行度による除外、固定装備・除外装備などの設定を元に、探索対象となる装備を選びます。

グルーピング

残った防具の中から、要求されたスキルポイントの値とスロットが同じものは、組み合わせを減らすために、一つの防具としてまとめます。
例えば切れ味+1で検索した場合、クロオビメイルアカムトウルンテは両方共匠+2、スロット1なので、同じ防具として扱っても大丈夫なわけです。
同様に、胴系統倍加の防具や空きスロット1-3の防具もまとめられています。

装備のスコアリング

ここからが重要です。
探索を枝刈りするためには、枝刈りするための指標が必要となります。
自分がとったアプローチは、装備にスコアをつけ、スコアの高いものから防具を試し、足りないスキルと、残っている防具のスコアを元に、枝刈りを行うというアプローチです。枝刈りの仕組みについては後で説明します。

スコアの付け方ですが、検索対象となるスキルが装飾品でスロット数いくつ相当か、ということになります。
先ほどの例の切れ味+1とクロオビメイルでは、クロオビメイルは匠+2で、匠+2は匠珠(3)相当なので、3スロット分の価値があり、かつ空きスロットが1あるため、合計4ポイントとなります。

匠珠(2)と匠珠(3)のように、いくつかスキルポイントの設定が異なる装飾品がある場合、スキルポイントごとのスロット数が低いものを採用します。なので、匠+1の防具は、本当は匠珠(2)相当の2スロットですが、ポイントは3 / 2の1.5となります。

装飾品がない潔癖などのスキルポイントは1ポイントあたり100という扱いにすることで、真っ先にそのスキルを持つ防具を試すように作ってあります。何故か剣士の検索してるのに、頭がガンナーばっかりという時は、大抵ガンナー頭のほうがスキルポイントが多めにあるため、優先的に試された結果、検索結果の最大件数全てガンナー頭になってしまった、ということです。

装備の選択

スコアにもとづき、一番スコアの高いものから順番に総当りで試していきます。
まずトリッキーなのは、胴系統倍加。これは胴の防具が選ばれたら順番に空いてる部位に胴系統倍加防具を試しはじめるという仕組みになっています。

そしてこのアルゴリズムで最も重要な枝刈りですが、

足りないスキルポイントのスロット数換算 > 空いている装備のスロット数 + (今選んだ防具のポイント * あと装備できる箇所の数)

となります。わかりにくいので、もう少し例を出しながら説明すると、回避性能+3のスキルをつけるべく、回避性能のスキルポイントを20集めようとした時、防具はスコアが高いものから順番に試されます。
お守りも含めて4つの防具を装備して、スキルポイント10と2スロットがあるとすると、残り2つと空きスロットでで10ポイント相当をカバーしなくてはいけません。2スロットは回避性能+3ポイント相当なので、残り2つの防具で回避性能+7を加えなくてはいけません。試している順番はポイントが高い順なため、次に選ぶ防具が回避性能+3スロット0だった場合、これより後に回避性能+3スロット0より高性能な防具がないことがわかっているため、足りない回避性能4ポイントは絶対に埋めることができない、ということがわかります。ここで枝刈りを行います。
先ほどの数式をこの例で書くと、

2 / 3 * 10 > 2 + (n * 2)
20 / 3 > 2 + (n * 2)
14 / 3 > (n * 2)
7 / 3 > n

と、次の防具が最低2と1/3ポイントの防具でないと無理だということがわかります。回避性能+3は2ポイント相当なので、無理だということがわかります。

そして、逆に

足りないスキルポイントのスロット数換算 <= 装備のスロット数

を満たした場合、装飾品を埋めることで要求スキルを満たすことができるかもしれないので、装飾品を試し始めます。

装飾品の選択

装飾品を試すのは、比較的簡単で、

  • 胴系統倍加がある場合、胴をまず埋める
  • スキル系統ごとにスロット数が最も高い(コストの高い)スキルから試す
    • 満たせないことが早い段階でわかりやすい
  • 同じスキルポイントの装飾品は、スロット数が多いものから試す

という感じで、唯一トリッキーなのは、どの装飾品をどのスロットにはめるかということで、例えば空きスロットが3と2だった場合、1スロの装飾品はどこにはめるべきかでしょうか?3にはめた場合、2-2となり、3スロの装飾品を試せなくなり、2にはめた場合、3-1となり、2スロの装飾品を一つしか試せなくなります。
で、どうすればいいかというと、新しい装飾品を試すたびに、今まで選んだ装飾品を見て、新しい装飾品のスロット数のものを一番多くはめるにはどうすればいいかを計算しなおします。
計算式は1スロは超単純で、空きスロを数えればいいです。3スロはまず丁度いいサイズのスロットを全部埋めて、その後は優先的に2スロを埋めて3スロをあけるようにします。2スロが若干面倒で、同じく丁度良いサイズを全部埋めた後に、3スロに1スロの装飾品をはめて2スロに変換した上で、余った1-2スロの装飾品を*5埋める感じになります。

以上がMH4スキルシミュ(泣)の仕組みでした。

実は頑シミュさんもアルゴリズムを公開しているのですが、そんなことは知らずに自分で作り始めたので、全体的なアプローチが異なっています。もしご興味がある方はこちらも御覧ください。色々と組み合わせるともっと速くなるかもしれません。

次回はyoruakiさんの「地雷について考えます」です。おつかレイア

*1:なんでこんな名前かというと、シミュレータスレの79番だったから

*2:こっちは306番とかだった気がするけど、別に特に名前つけてない

*3:昔は20分かかる検索があったとか。参照:http://www.geocities.jp/masax_mh/logic/page3_hone.html

*4:参照:http://sealedabstract.com/rants/why-mobile-web-apps-are-slow/。シミュレータでも十倍かは不明だけど間違いなく遅い

*5:3スロの装飾品は3スロ以外でははまらないため、ちょうどいいサイズの空きが必ずあるはず