LoginSignup
6
4

More than 1 year has passed since last update.

@iMasanari

整数計画法でモンハンのスキルシミュを実装する

Posted at

この度、「モンスターハンター Rise」というゲームのスキルシミュレーターを作成しました。

GitHub: https://github.com/iMasanari/mhrise-simulator

その宣伝を兼ねて、シミュレーター部分のロジックをハンズオンのような形式で解説していきます。この記事を読むと、下記のスキルシミュレーターを作成できます。

  • スキルを指定することで、そのスキルが発動する装備（防具・護石・装飾品の組み合わせ）を1つ検索する
  • 検索結果が複数ある場合、防具の守備力の合計がもっとも高いものを選ぶ

説明の簡易化のため、実際のモンスターハンターとは異なるデータを使用して説明していますが、ほんの少しの修正で対応できます。

スキルシミュレーターと整数計画法

モンスターハンターでは、防具・護石・装飾品の組み合わせ（以下、装備）によって発動するスキルが決まります。スキルシミュレーターは、先に発動したいスキルを選び、そのスキルから装備を逆算するツールです。

装備の組み合わせは無数にあるので、全探索で行うには時間がかかりすぎてしまいます。なので、拙作のスキルシミュレーターは、次の論文資料をもとに整数計画法を使用して作成しました。

すごく難しいことが書いてありますが、まとめると下記のとおりです。

  • モンハンのスキルシミュレーター機能は、整数計画問題に帰着できる
  • 整数計画問題ライブラリを使えば、ライブラリ側が最適化した高速なアルゴリズムで解いてくれる（はず）

また、上記資料の執筆者は、説明用の簡易版として以下のPDFを公開しています。

mhw の巨大なシステムでは説明が大変だから、新しいモンハンを考えたよ。

(1) 防具は 2 部位。上半身防具と下半身防具。
(2) スキルは 3 種類。「さわやか」「よそいき」「汚れ耐性」
(3) スロットは Lv3 まで

それぞれの装備のパラメータは次の表に書くよ。

種類 名前 スロット 防御力 スキル
上半身防具 Yシャツ Lv1 15 さわやか Lv1, よそいき Lv1
上半身防具 ポロシャツ Lv2 10 さわやか Lv1
下半身防具 スラックス Lv1, Lv1 8 よそいき Lv1
下半身防具 ジーパン Lv3 14 さわやか Lv1, 汚れ耐性 Lv2
護石 爽護石 さわやか Lv1
護石 汚れ護石 汚れ耐性 Lv1
装飾品 爽珠【1】 Lv1 さわやか Lv1
装飾品 他所珠【1】 Lv1 よそいき Lv1
装飾品 汚れ珠【1】 Lv1 汚れ耐性 Lv1
装飾品 他所珠【2】 Lv2 よそいき Lv2
装飾品 汚れ珠【2】 Lv2 汚れ耐性 Lv2
装飾品 逢引珠【3】 Lv3 さわやか Lv1, よそいき Lv1

この記事も説明の簡易化のため、上記のシステムを使用して解説していきます。

上記資料では整数計画問題への帰着方法を目的にしていますが、この記事では実際に実装することを目的とします。説明の順序は異なりますが、上記の資料を読むことでより一層理解できると思います。
また、この記事では整数計画法とは何かを説明しません。気になる方は、上記資料をご参照ください。

なお、実装はJavaScriptの線形計画法ライブラリ jsLPSolver を使用して行います。
他の言語、ライブラリで実装する際は、モデルの書き方がライブラリによって大きく異なりますので、ご注意ください。

ステップ1: 防御力が高い装備を検索する

整数計画法を使用したスキルシミュレーターでは一般的に、指定したスキルが発動する防御力が一番高い装備を検索します。
まずは、スキルの検索は行わず、防御力が最大になる装備を検索しましょう。

装備を求めるには下記の制約条件があります。

  • 上半身防具の個数は1個以下
  • 下半身防具の個数は1個以下

※上半身防具、下半身防具の個数は整数（小数不可）
※護石、装飾品は一旦無視する

この条件を線形計画問題の（疑似）モデルに落とすと、下記のようになります。

最大化: 
「Yシャツ.防御力: 15」 * Yシャツの個数 + 「ポロシャツ.防御力: 10」 * ポロシャツの個数 + 「スラックス.防御力: 8」 * スラックスの個数 + 「ジーパン.防御力: 14」 * ジーパンの個数

制約条件:
「Yシャツ.上半身防具: 1」 * Yシャツの個数 + 「ポロシャツ.上半身防具: 1」 * ポロシャツの個数 ≦ 1
「スラックス.下半身防具: 1」 * スラックスの個数 + 「ジーパン.下半身防具: 1」 * ジーパンの個数 ≦ 1

整数:
Yシャツの個数、ポロシャツの個数、スラックスの個数、ジーパンの個数

そして jsLpSolver へは下記の形式で渡します。

const solver = require('javascript-lp-solver')

const model = {
  optimize: '防御力',
  opType: 'max',
  constraints: {
    '上半身防具': { max: 1 },
    '下半身防具': { max: 1 },
  },
  variables: {
    'Yシャツ': { '上半身防具': 1, '防御力': 15 },
    'ポロシャツ': { '上半身防具': 1, '防御力': 10 },
    'スラックス': { '下半身防具': 1, '防御力': 8 },
    'ジーパン': { '下半身防具': 1, '防御力': 14 },
  },
  ints: {
    'Yシャツ': 1,
    'ポロシャツ': 1,
    'スラックス': 1,
    'ジーパン': 1,
  }
}

const result = solver.Solve(model)

console.log(result.feasible ? result : null) // { feasible: true, result: 29, bounded: true, isIntegral: true, 'Yシャツ': 1, 'ジーパン': 1 }

各パラメータについて、詳しく見ていきましょう。

optimize / opType

  optimize: '防御力',
  opType: 'max',

最適化 (最小化または最大化) する対象です。今回は防御力を最大にします。
最小にする場合は opType に min を指定します。

constraints

  constraints: {
    '上半身防具': { max: 1 },
    '下半身防具': { max: 1 },
  },

制約条件です。上半身防具、下半身防具の個数がそれぞれ1個以下になるよう指定します。
max の他、min や equal が指定できます。

variables

  variables: {
    'Yシャツ': { '上半身防具': 1, '防御力': 15 },
    'ポロシャツ': { '上半身防具': 1, '防御力': 10 },
    'スラックス': { '下半身防具': 1, '防御力': 8 },
    'ジーパン': { '下半身防具': 1, '防御力': 14 },
  },

求める変数です。今回の問題では「Yシャツ、ポロシャツ、スラックス、ジーパンはそれぞれいくつ必要か」を求めます。
変数にはそれぞれ属性（{ '上半身防具': 1, '防御力': 15 } 等）を設定できます。属性は上記の制約条件（constraints）を満たす必要があるため、Yシャツが2個になったり、Yシャツとポロシャツが両方1個になったりすることはありません。

ints

  ints: {
    'Yシャツ': 1,
    'ポロシャツ': 1,
    'スラックス': 1,
    'ジーパン': 1,
  }

整数値のみである変数（variables）の一覧です。防具を指定します。
これを指定しないと、Yシャツとポロシャツを0.5個ずつ同時に装備することができてしまいます。

返り値

console.log(result.feasible ? result : null) // { feasible: true, result: 29, bounded: true, isIntegral: true, 'Yシャツ': 1, 'ジーパン': 1 }

結果から、Yシャツとジーパンを装備した際に、防御力の最大の29になることがわかります。
feasible: true は、実行可能なことを示しています。解なしの場合は feasible: false になります。

コードでモデルを組み立てる

上記のように直接パラメータとして書くと、装備や制約が増えた場合に修正する部分が多くなってしまいます。なので、別途用意したデータから、モデルを生成するように変更します。

data.js
exports.armors = [
  { type: '上半身防具', name: 'Yシャツ', slots: [1], def: 15, skills: { さわやか: 1, よそいき: 1 } },
  { type: '上半身防具', name: 'ポロシャツ', slots: [2], def: 10, skills: { さわやか: 1 } },
  { type: '下半身防具', name: 'スラックス', slots: [1, 1], def: 8, skills: { よそいき: 1 } },
  { type: '下半身防具', name: 'ジーパン', slots: [3], def: 14, skills: { さわやか: 1, 汚れ耐性: 2 } },
]

const solver = require('javascript-lp-solver')
const { armors } = require('./data')

const simulate = () => {
  const constraints = {
    '上半身防具': { max: 1 },
    '下半身防具': { max: 1 },
  }

  const ints = {}
  const variables = {}

  // 防具
  for (const armor of armors) {
    ints[armor.name] = 1
    variables[armor.name] = {
      [armor.type]: 1,
      '防御力': armor.def,
    }
  }

  const model = {
    optimize: '防御力',
    opType: 'max',
    constraints,
    variables,
    ints,
  }

  const result = solver.Solve(model)

  return result.feasible ? result : null
}

const result = simulate()

console.log(result) // { feasible: true, result: 29, bounded: true, isIntegral: true, 'Yシャツ': 1, 'ジーパン': 1 }

ステップ2: スキル指定して検索する（装飾品なし）

ここから、スキルの検索を実装していきます。装飾品は一旦、後回しにします。

まずは、護石を追加します。護石は守備力が0の防具と考えると、簡単に実装できます。

data.js
exports.armors = [
   { type: '上半身防具', name: 'Yシャツ', slots: [1], def: 15, skills: { さわやか: 1, よそいき: 1 } },
   { type: '上半身防具', name: 'ポロシャツ', slots: [2], def: 10, skills: { さわやか: 1 } },
   { type: '下半身防具', name: 'スラックス', slots: [1, 1], def: 8, skills: { よそいき: 1 } },
   { type: '下半身防具', name: 'ジーパン', slots: [3], def: 14, skills: { さわやか: 1, 汚れ耐性: 2 } },
+  { type: '護石', name: '爽護石', slots: [], def: 0, skills: { さわやか: 1 } },
+  { type: '護石', name: '汚れ護石', slots: [], def: 0, skills: { 汚れ耐性: 1 } },
]

護石は、防具と同じく1つしか装備できないため、その制約を追加します。

   const constraints = {
     '上半身防具': { max: 1 },
     '下半身防具': { max: 1 },
+    '護石': { max: 1 },
   }

護石が追加できたので、スキル検索部分を作成します。
例として、さわやかLv2とよそいきLv2が発動する装備を検索したいとします。

const result = simulate({ 'さわやか': 2, 'よそいき': 2 })

その場合、次のような制約条件をコードに追加します。

制約条件:
「Yシャツ.さわやか: 1」 * Yシャツの個数 + 「ポロシャツ.さわやか: 1」 * ポロシャツの個数 + 「ジーパン.さわやか: 1」 * ジーパンの個数 + 「爽護石.さわやか: 1」 * 爽護石の個数 ≧ 2
「Yシャツ.よそいき: 1」 * Yシャツの個数 +「スラックス.よそいき: 1」 * スラックスの個数 + 「ジーパン.よそいき: 1」 * ジーパンの個数 ≧ 2

まずは、発動したいスキルを制約条件に加えます。これにより、さわやかLv2以上、よそいきLv2以上が発動する装備のみを検索するよう指示します。

+const simulate = (skills) => {
-const simulate = () => {
   const constraints = {
     '上半身防具': { max: 1 },
     '下半身防具': { max: 1 },
     '護石': { max: 1 },
   }

+   // 検索スキル
+   for (const [skill, point] of Object.entries(skills)) {
+     constraints[skill] = { min: point }
+   }
+
   const ints = {}

次に、スキルが発動する防具の情報を追記します。

   const ints = {}
   const variables = {}

   // 防具
   for (const armor of armors) {
     ints[armor.name] = 1
     variables[armor.name] = {
       [armor.type]: 1,
       '防御力': armor.def,
+      ...armor.skills,
     }
   }

たったこれだけで、防具スキルを検索できるようになります。

const result = simulate({ 'さわやか': 2, 'よそいき': 2 })

console.log(result) // { feasible: true, result: 23, bounded: true, isIntegral: true, '爽護石': 1, 'Yシャツ': 1, 'スラックス': 1 }

コード全体
data.js
exports.armors = [
  { type: '上半身防具', name: 'Yシャツ', slots: [1], def: 15, skills: { さわやか: 1, よそいき: 1 } },
  { type: '上半身防具', name: 'ポロシャツ', slots: [2], def: 10, skills: { さわやか: 1 } },
  { type: '下半身防具', name: 'スラックス', slots: [1, 1], def: 8, skills: { よそいき: 1 } },
  { type: '下半身防具', name: 'ジーパン', slots: [3], def: 14, skills: { さわやか: 1, 汚れ耐性: 2 } },
  { type: '護石', name: '爽護石', slots: [], def: 0, skills: { さわやか: 1 } },
  { type: '護石', name: '汚れ護石', slots: [], def: 0, skills: { 汚れ耐性: 1 } },
]

const solver = require('javascript-lp-solver')
const { armors } = require('./data')

const simulate = (skills) => {
  const constraints = {
    '上半身防具': { max: 1 },
    '下半身防具': { max: 1 },
    '護石': { max: 1 },
  }

  // 検索スキル
  for (const [skill, point] of Object.entries(skills)) {
    constraints[skill] = { min: point }
  }

  const ints = {}
  const variables = {}

  // 防具
  for (const armor of armors) {
    ints[armor.name] = 1
    variables[armor.name] = {
      [armor.type]: 1,
      '防御力': armor.def,
      ...armor.skills,
    }
  }

  const model = {
    optimize: '防御力',
    opType: 'max',
    constraints,
    variables,
    ints,
  }

  const result = solver.Solve(model)

  return result.feasible ? result : null
}

const result = simulate({ 'さわやか': 2, 'よそいき': 2 })

console.log(result) // { feasible: true, result: 23, bounded: true, isIntegral: true, '爽護石': 1, 'Yシャツ': 1, 'スラックス': 1 }

ステップ3: 装飾品を含めて検索する

この記事最後のステップです。装飾品込みで検索できるようにし、スキルシミュレーターを完成させましょう。

装飾品が防具・護石と違うのは、装備可能な個数が決まっていないところです。防具・護石に設定されているスロットの数まで装飾品を装備できますが、防具・護石が変わればスロットの数も変化します。スロットLvもあるため、下記の方法で求める必要があります。

(防具の Lv1 以上スロット数) ≧ (Lv1 以上スロットを必要とする装飾品数)
(防具の Lv2 以上スロット数) ≧ (Lv2 以上スロットを必要とする装飾品数)
(防具の Lv3 以上スロット数) ≧ (Lv3 以上スロットを必要とする装飾品数)

相棒でもわかる mhw スキルシミュレータの作り方
http://nap.s3.xrea.com/lpsimshort.pdf

つまり、下記の制約条件を追加します。

制約条件:
「Yシャツ.Lv1以上スロット数: 1」 * Yシャツの個数 + 「ポロシャツ.Lv1以上スロット数: 1」 * ポロシャツの個数 +「スラックス.Lv1以上スロット数: 2」 * スラックスの個数 + 「ジーパン.Lv1以上スロット数: 1」 * ジーパンの個数 - 「爽珠【1】.Lv1以上スロット数: 1」 * 爽珠【1】の個数 - 「他所珠【1】.Lv1以上スロット数: 1」 * 他所珠【1】の個数 - 「汚れ珠【1】.Lv1以上スロット数: 1」 * 汚れ珠【1】の個数 - 「他所珠【2】.Lv1以上スロット数: 1」 * 他所珠【2】の個数 - 「汚れ珠【2】.Lv1以上スロット数: 1」 * 汚れ珠【2】の個数 - 「逢引珠【3】.Lv1以上スロット数: 1」 * 逢引珠【3】の個数 ≧ 0
「ポロシャツ.L2以上スロット数: 1」 * ポロシャツの個数 + 「ジーパン.Lv2以上スロット数: 1」 * ジーパンの個数 - 「他所珠【2】.Lv2以上スロット数: 1」 * 他所珠【2】の個数 - 「汚れ珠【2】.Lv2以上スロット数: 1」 * 汚れ珠【2】の個数 - 「逢引珠【3】.Lv2以上スロット数: 1」 * 逢引珠【3】の個数 ≧ 0
「ジーパン.Lv3以上スロット数: 1」 * ジーパンの個数 - 「逢引珠【3】.Lv2以上スロット数: 1」 * 逢引珠【3】の個数 ≧ 0

整数:
爽珠【1】の個数、他所珠【1】の個数、汚れ珠【1】の個数、他所珠【2】の個数、汚れ珠【2】の個数、逢引珠【3】の個数

では、実装に入ります。
まず最初に、装飾品のデータを追加します。

data.js
+exports.decos = [
+  { name: '爽珠【1】', size: 1, skills: { さわやか: 1 } },
+  { name: '他所珠【1】', size: 1, skills: { よそいき: 1 } },
+  { name: '汚れ珠【1】', size: 1, skills: { 汚れ耐性: 1 } },
+  { name: '他所珠【2】', size: 2, skills: { よそいき: 2 } },
+  { name: '汚れ珠【2】', size: 2, skills: { 汚れ耐性: 2 } },
+  { name: '逢引珠【3】', size: 3, skills: { さわやか: 1, よそいき: 1 } },
+]

次に、制約を追加します。
防具スロット数 ≧ 装飾品スロット数 という条件は、防具スロット数 - 装飾品スロット数 ≧ 0 と式を変形できるので、各Lvの空きスロット数がそれぞれが0以上となるように設定します。

   const constraints = {
     '上半身防具': { max: 1 },
     '下半身防具': { max: 1 },
     '護石': { max: 1 },
+    'Lv1以上空きスロット数': { min: 0 },
+    'Lv2以上空きスロット数': { min: 0 },
+    'Lv3以上空きスロット数': { min: 0 },
   }

最後に、防具のスロット数と装飾品の情報を追加します。

   // 防具
   for (const armor of armors) {
     ints[armor.name] = 1
     variables[armor.name] = {
       [armor.type]: 1,
       '防御力': armor.def,
       ...armor.skills,
+      'Lv1以上空きスロット数': armor.slots.filter(v => v >= 1).length,
+      'Lv2以上空きスロット数': armor.slots.filter(v => v >= 2).length,
+      'Lv3以上空きスロット数': armor.slots.filter(v => v >= 3).length,
     }
   }

+  // 装飾品
+  for (const deco of decos) {
+    ints[deco.name] = 1
+    variables[deco.name] = {
+      ...deco.skills,
+      'Lv1以上空きスロット数': deco.size >= 1 ? -1 : 0,
+      'Lv2以上空きスロット数': deco.size >= 2 ? -1 : 0,
+      'Lv3以上空きスロット数': deco.size >= 3 ? -1 : 0,
+    }
+  }
+
   const model = {

装飾品込みの検索も、たったこれだけの修正で出来ます。

const result = simulate({ 'さわやか': 2, 'よそいき': 4, '汚れ耐性': 3 })

console.log(result) // { feasible: true, result: 29, bounded: true, isIntegral: true, '汚れ護石': 1, '他所珠【1】': 1, '他所珠【2】': 1, 'Yシャツ': 1, 'ジーパン': 1 }

コード全体
data.js
exports.armors = [
  { type: '上半身防具', name: 'Yシャツ', slots: [1], def: 15, skills: { さわやか: 1, よそいき: 1 } },
  { type: '上半身防具', name: 'ポロシャツ', slots: [2], def: 10, skills: { さわやか: 1 } },
  { type: '下半身防具', name: 'スラックス', slots: [1, 1], def: 8, skills: { よそいき: 1 } },
  { type: '下半身防具', name: 'ジーパン', slots: [3], def: 14, skills: { さわやか: 1, 汚れ耐性: 2 } },
  { type: '護石', name: '爽護石', slots: [], def: 0, skills: { さわやか: 1 } },
  { type: '護石', name: '汚れ護石', slots: [], def: 0, skills: { 汚れ耐性: 1 } },
]

exports.decos = [
  { name: '爽珠【1】', size: 1, skills: { さわやか: 1 } },
  { name: '他所珠【1】', size: 1, skills: { よそいき: 1 } },
  { name: '汚れ珠【1】', size: 1, skills: { 汚れ耐性: 1 } },
  { name: '他所珠【2】', size: 2, skills: { よそいき: 2 } },
  { name: '汚れ珠【2】', size: 2, skills: { 汚れ耐性: 2 } },
  { name: '逢引珠【3】', size: 3, skills: { さわやか: 1, よそいき: 1 } },
]

const solver = require('javascript-lp-solver')
const { armors, decos } = require('./data')

const simulate = (skills) => {
  const constraints = {
    '上半身防具': { max: 1 },
    '下半身防具': { max: 1 },
    '護石': { max: 1 },
    'Lv1以上空きスロット数': { min: 0 },
    'Lv2以上空きスロット数': { min: 0 },
    'Lv3以上空きスロット数': { min: 0 },
  }

  // 検索スキル
  for (const [skill, point] of Object.entries(skills)) {
    constraints[skill] = { min: point }
  }

  const ints = {}
  const variables = {}

  // 防具
  for (const armor of armors) {
    ints[armor.name] = 1
    variables[armor.name] = {
      [armor.type]: 1,
      '防御力': armor.def,
      ...armor.skills,
      'Lv1以上空きスロット数': armor.slots.filter(v => v >= 1).length,
      'Lv2以上空きスロット数': armor.slots.filter(v => v >= 2).length,
      'Lv3以上空きスロット数': armor.slots.filter(v => v >= 3).length,
    }
  }

  // 装飾品
  for (const deco of decos) {
    ints[deco.name] = 1
    variables[deco.name] = {
      ...deco.skills,
      'Lv1以上空きスロット数': deco.size >= 1 ? -1 : 0,
      'Lv2以上空きスロット数': deco.size >= 2 ? -1 : 0,
      'Lv3以上空きスロット数': deco.size >= 3 ? -1 : 0,
    }
  }

  const model = {
    optimize: '防御力',
    opType: 'max',
    constraints,
    variables,
    ints,
  }

  const result = solver.Solve(model)

  return result.feasible ? result : null
}

const result = simulate({ 'さわやか': 2, 'よそいき': 4, '汚れ耐性': 3 })

console.log(result) // { feasible: true, result: 29, bounded: true, isIntegral: true, '汚れ護石': 1, '他所珠【1】': 1, '他所珠【2】': 1, 'Yシャツ': 1, 'ジーパン': 1 }

おまけ: 実際のモンスターハンターのデータを使用する

実際のモンスターハンターで使用するには、データを用意する必要がありますが、コードは少しの修正だけで対応できるはずです。

   const constraints = {
-    '上半身防具': { max: 1 },
-    '下半身防具': { max: 1 },
+    '頭防具': { max: 1 },
+    '胴防具': { max: 1 },
+    '腕防具': { max: 1 },
+    '腰防具': { max: 1 },
+    '足防具': { max: 1 },
     '護石': { max: 1 },
     'Lv1以上空きスロット数': { min: 0 },
     'Lv2以上空きスロット数': { min: 0 },
     'Lv3以上空きスロット数': { min: 0 },
   }

最後に

上記の方法で、スキルシミュレーターが最低限必要な機能が完成します。
今回は省略しましたが、下記を実装するとよりスキルシミュレーターらしくなります。

  • 検索結果を複数表示する（前回の検索結果を除外して再検索）
  • 指定したスキルに追加で発動できるスキルの検索機能
  • 風雷合一の対応（スキルAのLv3で検索した時、スキルAのLv2+風雷合一Lv4等も検索できるようにする）

上記は、拙作のスキルシミュレーターでは実装済みです。もしよろしければ、ソースコードをご参照ください。

また、私は実装していませんが、下記の機能を実装しても良いでしょう。

  • 装飾品作成に必要なレア素材である、瑠璃原珠の個数が一番少なくなるように装備を検索する
  • ダメージシミュレーター機能を組み込んで、一番攻撃力が高くなるように装備を検索する
  • 手持ちの護石で装備が見つからない場合、発動する護石の検索を行う

以上、スキルシミュレーターの作り方、及び、拙作のスキルシミュレーターの宣伝でした。
モンスターハンターRiseをプレイされている方は、ぜひ使用してみてください。そして、もっと良いものを作れるぜという方は、ぜひ作って公開していただけたらと思います。

6
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
4