🐉

ドラクエウォークと数理最適化

2022/02/14に公開

Python

Streamlit

数理最適化

tech

3行まとめ

ドラクエウォークのこころ情報をネット上の攻略サイトからスクレイピングしたよ
あなただけのオススメのこころセットを作ろうとしているよ
python+pulp+streamlitで簡単インタラクティブ最適化アプリを作れるよ

はじめに

DQWのゲーム性

みなさんドラクエウォークはプレイしていますか?私は軽くプレイしているエンジョイ勢 (全職業の合計レベル2854) です．

ゲームの説明は真面目にしないのですが (ドラクエ版ポケモンGo)，RPGといえば「レベル」という概念があり，ドラクエシリーズのレベル上げといえばメタルモンスター狩りというものがあります（経験値をたくさんくれるモンスターです）．

しかしウォークゲームであるドラクエウォークでは，レベルを上げても (特に後半に進めば進むほど) 強くなりづらくなっています．これは，そもそもレベルが上げづらいという物理的な事情があります（歩かないと敵が沸かないためです）．更にレベル上げに必要な経験値がおかしい量になりますし，レベルが上ってもステータス（HPやMP，ちからなど）が上昇しなくなるからです．

(余談) レベル上げと経験値の関係性

例えばレベル30,40,50,60,70,80からそれぞれレベルを1上げるために必要な経験値は

30→31: 105,884
40→41: 291,940
50→51: 1,318,767
60→61: 2,840,467
70→71: 3,811,548
80→81: 5,496,070

という頭がおかしいカーブを描きます．ちなみにシリーズおなじみの「はぐれメタル」さんの経験値は10,500です．こちらの情報はこのページの情報を参考にさせて頂きました． https://gamewith.jp/dq-walk/article/show/203794

そのためドラクエウォークで強いキャラを用意するには，「強い武器をガチャで当てる」か「強いこころを敵を倒して手に入れる」か，どちらか（もしくは両方）をやる必要があります．ここではガチャについては触れることができないので「こころ」というシステムを紹介します．

DQWのこころシステム

単にレベル上げではステータスが上がらなくなるため，ドラクエウォークで実装されている「こころシステム」を活用する必要があります．これはその名前の通り，各キャラに3つか4つの「こころ」と呼ばれる装飾品を装備できるシステムです．こころを装備すると，ドラクエウォークで使われている8つの基礎パラメータを上昇させたり，特殊な効果を得ることができます．

こころシステム	あるこころを装備	「おまかせ」の例

1つ目の画像はこころを装備する画面です．コスト (最大390) に収まる分だけ，最大4つまで選択できます．各職業ごとに色が決まっていて，色に合った心を装備すると，ステータスの上昇率が+20%されます．
2つ目の画像はこころの例です．あるこころ (コスト122) を選択すると，パラメータが上昇する様子です．
3つ目の画像はドラクエウォークの「おすすめ」機能が選んだこころ4つです．

1レベルが上がるときのステータス変化が最大で5ぐらいのことを考えると，こころシステムのステータス上昇はかなり大きい割合を占めることが分かるかと思います (上の例では，例えば HPなら+162です)．そのため敵やステージ，属性に応じて適切なこころを4つ選択し，ステージを進めていくことがゲーム性に関わってきます．

既知の課題

上で説明した「こころシステム」ですが，簡単に想像できる通りかなりポンコツな「おすすめ」機能になっています．これはインターネット上で「ドラクエウォークこころおすすめ」などをキーワード検索して貰えば分かるのですが，このゲームがはじまって2年以上経って特に改善されていないポイントです．巷の攻略サイトが「おすすめのこころセット」などの記事を出しているので，だいたいのプレイヤーはおすすめのセットを見ながらプレイしていると思います．

簡単に既存おすすめシステムの課題を考えると次の2つに分類されると思います．

Sランクのこころ持ってないよ問題

攻略サイトでプレイしている人はだいたいそこそこのやりこみ勢なので，武器やこころを潤沢に所持しています．ただし実際はSランクのこころを入手するには敵から直接ドロップするまで倒しまくる (確率0.2%ぐらい？) か，こころを合体させてSランクを作成する必要があります (例えばSランク1つ作るのにAランクが5つ必要，みたいなイメージ)．そのため，基本的に他の人のおすすめセットはあてになりません．

ほしいシステム

これまでの話をまとめますと，ドラクエウォークのこころシステムについて「自分が欲しい設定の基準でこころを選んでくれて」かつ「自分の持っているこころだけを使っていい感じに設定してくる」ようなシステムが欲しいということになります．

python+pulp+streamlitを使った数理最適化Webアプリの作成

本記事ではpython+pulp+stremlitのセットを使って上のシステムを実装します．最初に世の中の攻略サイトからデータを取ってきて，次に数理最適化を書き，最後にstreamlitでWebアプリの皮を無理やりかぶせます．

開発環境ですが特に大したものは使っていなくて，これぐらいの量です．

poetry add beautifulsoup4 numpy pandas pulp jupyterlab ipython tqdm streamlit

(1) 数理最適化用のデータを取得する

必要なデータを簡単に整理しておきます．

ドラクエウォークにおいて
- 各職業について
  - どのようなこころが良いのか (こころ枠)
- 各レベルで装備できる最大コスト数
- 各モンスターについて
  - 各こころ(S/A/B/C/Dと5種類あります)の性能はどのようなものか

これらの情報ですが，手作業でゲームから書き起こすのは無理ですが (おそらく)，世の中には攻略サイトを運営してくださる人たちがいるので，そちらを参考にしましょう．正確には，勝手にアクセスしてデータだけ借りてくることにします．データを具体的にどのように取ってくるかを書くと怒られるような気がしたので要点だけ書いておきます．

各職業のデータについて

例えばこういうサイトにレベルごとの枠数値が乗っています．ありがとうございます．

https://gamers-geo.com/dqwalk/levelup/

取ってきてこういう感じのjsonファイルを作りました (こういうデータのファイルはレポジトリには登録していません)．かなりクソjsonファイルだと思いましたが，そんなに重いデータではないので無視しました．

{
  "kihon": {
    "1": 10,
    "2": 12,
    /*..つづく..*/
  },
  "joukyu": {
    "1": 20,
    "2": 25,
    /*..つづく..*/
  }
}

各モンスターのデータについて

まずモンスターの一覧は例えばこういうところにあります．

https://game8.jp/dqwalk/290340

ここからrequests+BeautifulSoupを使って全モンスターにアクセスします．ただし一部「地域限定モンスター」というのが入っていて，扱いが面倒なので手作業で消しました．

# 別の処理

# 地域限定モンスターは消す
for idr, row in tqdm(df.iterrows()):
    url = row.page_url
    
    # 地域限定モンスターを使わない
    if 55 <= row.monster_id <= 62:
        continue
    if 123 <= row.monster_id <= 130:
        continue
    if 296 <= row.monster_id <= 300:
        continue

# 別の処理

個別のモンスターページですが，スライムさんのページを参考に必要な処理だけ簡単に書いておきます．こちらの説明に一部game8さんの画像をキャプチャしたものを引用させていただきます．

https://game8.jp/dqwalk/292586

こちらのページから，表をBeautifulSoupで適当に探してきて，「色情報が分かるテーブル」と「ステータスが分かるテーブル」と「特殊効果が分かるテーブル」の3つのテーブルを取得してきます．

色情報が分かるテーブル	ステータスが分かるテーブル	特殊効果が分かるテーブル

あとは頑張って日本語のパースと表の読解をやってもらって，次のようなjsonをつくりました．これはスライムのデータです．

{
  "1": {
    "special": {
      "Sランク": ["こころ最大コスト+4"],
      "Aランク": ["こころ最大コスト+3"],
      "Bランク": ["こころ最大コスト+2"],
      "Cランク": ["なし"],
      "Dランク": ["なし"]
    },
    "type": "黄",
    "cost": 3,
    "さいだいHP": [4, 3, 3, 2, 2],
    "さいだいMP": [3, 3, 2, 2, 1],
    "ちから": [3, 2, 2, 2, 1],
    "みのまもり": [3, 2, 2, 1, 1],
    "こうげき魔力": [1, 1, 1, 1, 1],
    "かいふく魔力": [1, 1, 1, 1, 0],
    "すばやさ": [3, 2, 1, 1, 1],
    "きようさ": [2, 2, 2, 1, 1],
    "id": 1,
    "name": "スライム"
  },
}

ちなみにこうやってデータを処理した後に処理をなめたところ，微妙にデータの表記ゆれなどがあったので，以下のように対応しています．

## もみじこぞうの色取得ミス
all_results[173]["type"] = "緑"

## デスピサロの色取得ミス
all_results[190]["type"] = "緑"

## こころ最大コストの+や%の表記ゆれ
all_results[140]["special"]["Aランク"][0] = "こころ最大コスト+3"
all_results[211]["special"]["Bランク"][0] = "こころ最大コスト+2"
all_results[376]["special"]["Sランク"][0] = "こころ最大コスト+4"
all_results[404]["special"]["Bランク"][0] = "こころ最大コスト+2"

その他にはPythonで職業情報を扱うために枠や色などを適宜定義しました．とはいえまとまって書かれているわけではないので，今後の開発ではもう少し真面目にプログラムを書きたいと思っています (こういう感じの情報は一度作ったらそんなに変更されることもないと思うので，とりあえず埋め込めばいいかなと思っていました)．

# 枠
class Color(IntFlag):
    Red = auto()
    Yellow = auto()
    Blue = auto()
    Purple = auto()
    Green = auto()
    RedYellow = Red | Yellow  # バトルマスター(2)
    RedBlue = Red | Blue  # レンジャー(2)
    PurpleGreen = Purple | Green  # 賢者(2,3,4)
    YellowPurple = Yellow | Purple  # 魔法戦士(2,3,4)
    YellowGreen = Yellow | Green  # パラディン(2)
    YellowBlue = Yellow | Blue  # 海賊(2)
    BlueGreen = Blue | Green  # スーパースター(2)
    Rainbow = Red | Yellow | Blue | Purple | Green  # 虹枠

# 職業と色
roles: List[str] = ["バトルマスター", "賢者", "レンジャー",\
                    "魔法戦士", "パラディン", "スーパースター", "海賊"]
# 職業ごとの枠
waku_dict = {
    "バトルマスター": [Color.Rainbow, Color.RedYellow, Color.Red, Color.Red],
    "賢者": [
        Color.Rainbow,
        Color.PurpleGreen,
        Color.PurpleGreen,
        Color.PurpleGreen,
    ],
    #...}

(2) 数理最適化を解く

だいたいのデータがここまでで準備できたので，後は数理最適化を使って「自分が好きなような目的関数でこころセットをつくる」という部分を準備すれば良さそうです．おそらく今のドラクエウォークも何らかの基準でオススメが選択されているはずですが，中身は分からないので自分で作らなければなりません．数理最適化を使うときに大事な「どのような決定変数を使うのか」「どのような制約が必要なのか」「どのような目的関数を定義するのか」を順番に考えていきましょう．

決定変数

ドラクエウォークの場合，基本職で3つ，上級職で4つのこころを選択します．そんなに個数が多くないので，インデクスが多い定式化をしてもpulpで解けそうな気持ちになります．ここでは次の目的変数を設定することにしました．

x_{i,j,k}\in\{0,1\}, 1\leq i\leq |\text{全モンスター}|, j\in\{0,1,2,3,4\}, k\in\{0,1,2,3\}

ここで $x_{i,j,k}=1$ は，モンスターIDが $i$ のモンスターのランク $j$ のこころ (便宜上 $j=0$ をSランク， $j=4$ をDランクにしておきます)を対象とするキャラの $k$ 番目の枠に設定するときに $1$ となる二値変数としました．現状全モンスターが400ぐらいなので若干雑な感じですが，排他性が結構あるので大丈夫そうです (要するに同じモンスターのこころを複数個つけられません)

制約

さて上の決定変数 $x_{i,j,k}$ でこころセットの選択され具合を表現できそうなので，制約を考えて行きます．とはいえドラクエウォークのこころシステムには現状変な制約はないので，当たり前の制約を書くだけです．書かなければならない制約は

各モンスターは1度しか使えない (同ランクを複数，別ランクを複数はダメ)
こころは最大4つしか選べない
各こころの設定位置には1つのこころしか設定できない
レベルで設定されたコストを超えない

1.から3.までの制約は，それぞれ次の式で書けるので，pulpで書けばOKです．

任意のモンスター $i$ について， $\sum_{j}\sum_{k} x_{i,j,k} \leq 1$
$\sum_{i, j, k} x_{i,j,k} \leq 4$
各位置 $k\in\{0,1,2,3\}$ について， $\sum_{i}\sum_{j} x_{i,j,k} \leq 1$

4.についてですが，データで取ってきた「こころ最大コスト+3」などの特殊効果が少し影響してきます．これは仮に最大コストが100しかないキャラであっても，あるこころが「こころ最大コスト+3」を持っていると，最大で103まで設定できるという補正項になります．この情報はjsonに入っているので，適当にパースしてきて，各モンスター $i$ のランク $j$ が持つ補正分を $r_{ij}$ (例えば $r_{\text{スライム},\text{Sランク}}=4$ です) で表すことにし，その場合の設定に必要なコストを $c_{ij}$ ，レベル $l$ のキャラの最大コストを $C_l$ とすると，要するに次の式になります．

$\sum_{i,j,k} (c_{ij} - r_{ij}) x_{ijk} \leq C_{l}$

これでfeasibleなこころ選択セットを表現することができました．

目的関数

最後に目的関数を書いて，自分の所望のいい感じのこころセットを作ります．とはいえ，とてもいい感じの目的関数を書くのは結構大変ですし，ここまでの処理で考慮していない効果（呪文の属性など）もあるので，ここでは簡単に2つの目的関数を考えます．

最大パラメータ総和

すごく簡単な目的関数ですが，要するに全パラメータ値の総和を最大にする目的関数です．ここで上に述べたルールとして，職業の枠と上手く合っている場合には評価値が1.2倍になる (+20%)という補正項だけを入れて実装します．これは辞書で取ってきた数値と決定変数 $x_{ijk}$ の積を全部足していったものです．考えているパラメータはこころに設定されている8つあります．

parameters: List[str] = [
    "さいだいHP",
    "さいだいMP",
    "ちから",
    "みのまもり",
    "こうげき魔力",
    "かいふく魔力",
    "すばやさ",
    "きようさ",
]

とにかく全部足しましょう！（脳筋）．

魔法重視・回復重視の目的関数

ここで思い出したのですが，そもそも「魔法戦士」のオススメで「魔力重視が出てこないやんけ！」というのが数理最適化するモチベーションでした（すごい個人的な恨みでしょうか…？）．そのためいい感じの目的関数を書き直してあげます．とはいえ多目的最適化について真面目に考えると大変になるので，簡単な方法で線形重み付けでいきます．

極端な方法としては，例えば，「こうげき魔力」だけを目的関数に使うというアプローチがありそうです．これは上のparameters上の重みを，こうげき魔力だけ1.0にして他を0.0にして足し合わせれば形式的に書くことができそうです．

とはいえ「こうげき魔力」だけでは実際だめで，魔法を使いながら長い時間プレイするには十分な「さいだいMP」も必要になります．そこで適当な重み付けをハードコーディングして，目的関数にできそうです．

実装

以下は現状の雑な実装です (誰かタスケテ…)．なんか冗長なクソ実装になっている気がします．

# 職業ごとの補正
coeff: np.ndarray = np.array(
    [
        # 黄   緑   赤   紫   青
        [1.2, 1.0, 1.0, 1.0, 1.2],  # さいだいHP
        [1.0, 1.2, 1.0, 1.2, 1.0],  # さいだいMP
        [1.2, 1.0, 1.2, 1.0, 1.0],  # ちから
        [1.2, 1.0, 1.0, 1.0, 1.0],  # みのまもり
        [1.0, 1.0, 1.0, 1.2, 1.0],  # こうげき魔力
        [1.0, 1.2, 1.0, 1.0, 1.0],  # かいふく魔力
        [1.0, 1.0, 1.2, 1.0, 1.2],  # すばやさ
        [1.0, 1.0, 1.2, 1.0, 1.2],  # きようさ
    ]
)

# 重み
weight_objs: np.ndarray = np.array(
    [
        # max  魔  回
        [1.0, 1.0, 1.0],  # さいだいHP
        [1.0, 2.0, 2.0],  # さいだいMP
        [1.0, 0.0, 0.0],  # ちから
        [1.0, 0.0, 0.0],  # みのまもり
        [1.0, 3.0, 1.0],  # こうげき魔力
        [1.0, 1.0, 3.0],  # かいふく魔力
        [1.0, 0.0, 0.0],  # すばやさ
        [1.0, 0.0, 0.0],  # きようさ
    ]
)

# 目的関数; 各位置について，色補正付きの項を計算する
obj = 0.0
W = weight_objs[:, list_objectives.index(objective)]
for loc in rng_k:
    color_loc = waku_dict[syokugyou][loc]
    # loc位置のパラメータごとの目的関数寄与分
    list_obj_loc = []
    for (idp, param) in enumerate(parameters):
        term_param = 0.0
        for mid in ids:
            mtype = colorname2color[monster_dict[mid]["type"]]
            vc = 1.0
            if mtype & color_loc == mtype:
                vc = coeff[idp, color2index[mtype]]
            for rank in rng_r:
                term_param += (
                    monster_dict[mid][param][rank] * vc * X[mid][rank][loc]
                )
        list_obj_loc.append(term_param)

    # 重み付け和
    for (idp, _) in enumerate(parameters):
        obj += W[idp] * list_obj_loc[idp]

実装を動かしてみる

とりあえずここまでで最適化はできるようになったはずです．コマンドラインから動かしてみましょう．ぶっちゃけ若干バグってる気がしているのですが，とりあえず動いたので見ないふりしておきましょう！ (具体的には位置補正が上手く入っていないような…)．実際にドラクエウォークで使われているおすすめと大差ないアホプログラムな気がしますが，MWPとしてはOKでしょう（嘘）．

魔法戦士 x {最大パラメータ，魔法重視，回復重視}

こころ1 438豪氷天グリザード (コスト122) (Sランク)
こころ2 153まおうのつかい (コスト99) (Sランク)
こころ3 278ワイトキング (コスト122) (Sランク)
こころ4 372竜王 (コスト107) (Sランク)
コスト 450/440

こころ1 377大神官ハーゴン (コスト111) (Sランク)
こころ2 278ワイトキング (コスト122) (Sランク)
こころ3 234ゾーマ (コスト84) (Sランク)
こころ4 427にじくじゃく (コスト117) (Sランク)
コスト 434/440

こころ1 272ボボンガー (コスト99) (Sランク)
こころ2 278ワイトキング (コスト122) (Sランク)
こころ3 425わたぼう (コスト99) (Sランク)
こころ4 379破壊神シドー (コスト113) (Sランク)
コスト 433/440

パラディン x {最大パラメータ，魔法重視，回復重視}

こころ1 438豪氷天グリザード (コスト122) (Sランク)
こころ2 153まおうのつかい (コスト99) (Sランク)
こころ3 278ワイトキング (コスト122) (Sランク)
こころ4 372竜王 (コスト107) (Sランク)
コスト 450/440

こころ1 278ワイトキング (コスト122) (Sランク)
こころ2 379破壊神シドー (コスト113) (Sランク)
こころ3 234ゾーマ (コスト84) (Sランク)
こころ4 427にじくじゃく (コスト117) (Sランク)
コスト 436/440

こころ1 379破壊神シドー (コスト113) (Sランク)
こころ2 272ボボンガー (コスト99) (Sランク)
こころ3 425わたぼう (コスト99) (Sランク)
こころ4 278ワイトキング (コスト122) (Sランク)
コスト 433/440

(3) streamlitでWebアプリの皮をかぶせる

このままでは使いづらいのでstreamlitを使ってWebアプリにしました．streamlitの使い方については適当にインターネットを見てください．一つポイントとして，session state variableを使っています．

見た目

最初に起動すると，デフォルトの「バトルマスター」「レベル55」の最適化がされます．最適化がpulpで回っている間はくるくる回るようになっています (たぶん)．職業とレベルのスライダーは適当に動かせます．目的関数は，上の例で使った3つの重みが実装されています．

最適化結果を出してくれるのですが，「Have?」というUIがくっついています．最初に言ったとおり「いやSランクのこころなんてもってないし…」というのがドラクエウォークあるあるなのですが，ここで「No」を選択して「Re-optimize」ボタンを押すと，「No」にしたこころは使わないように最適化をやり直ししてくれます．仕組みは簡単で，ここでNoが入力されたこころをsession state variableに保存し，次回pulpを使って最適化するときに強制的に使わない ( $x_{ijk}=0$ ) ような制約を追加します．

私は「竜王のS」をもっていないので（怒），Noにして最最適化します．

最最適化が終わると「まおうのつかいS」「ホークブリザードS」「おどるほうせきS」「メタルドラゴンS」が結果として出力されました．竜王はさようならです．

あとはこういう感じで何回も最適化すれば，プレイヤーがもっているこころだけを使った最良のこころシステムをゲットできます．

まとめ

ドラクエウォーク楽しいよ．このプログラムは永遠に開発途中です．データをインターネット上に公開してくれている攻略者の方々に深く感謝します．また前処理したデータ(JSON)がレポジトリに置かれていないので，このrepositoryをクローンしてもこのDQW Kokoroptimizerくんは動作しません，ごめんなさい．