Lord of Monsters Regenerate 1 を遺伝的アルゴリズムで解く

Lord of Monsters Regenerate 1 をご存知でしょうか？かつてCGIゲームがインターネット上のあちこちにあったときに、知る人ぞ知るLindwurmが製作したちょっとしたウェブゲームです。本家のLord of Monstersはプレイしたことはないのですが、シンプルで簡単に遊べるゲーム性がこのLoMR1にはあり、当時たびたび思い出してはプレイしていたことを思い出します。今回はふと遺伝的アルゴリズムを使えばLoMR1の最強編成を導き出せるのではないかと試してみました。

現在はFlashの終了とサーバサイドの不具合によって遊べないため、細かな仕様については記憶に基づいているところがありますが、あらかじめご了承ください。

LoMR1の仕組み

LoMR1のユーザインタフェースはFlashで作成されていて、Flash上でチーム名、勝利・敗北時のメッセージ、モンスターの編成を決めるようになっています。戦闘開始ボタンをクリックすると、その内容をHTTP Postでサーバーに送信し、サーバー側のPHPスクリプトが送信された内容に基づいて戦闘結果を返します。Flashではそれ受け取って、アニメーションという形でユーザに戦闘結果を通知します。

戦闘は12人のランキング保持者との連戦で敗北するまで続けられ、負けたところでその順位にランキング保持者として挿入されます。

基本的なルール

ルールのページに一通り書かれていますが、大事な部分を列挙しました。

編成

• 召喚ポイント(SP): モンスターごとに定められている編成コストです。10SP以内で編成する必要がある。足りない分には構わないがそれによる利点はありません。
• 特攻隊長: 最初に配置したモンスターはHP+1と被弾率上昇の効果を受けます。上昇率は不明です。
• 戦闘システム: 各モンスターは1ターンに1回の攻撃ができます。ただしターンごと攻撃順序はランダムで、敵味方の攻撃順序も入り乱れます。攻撃目標も攻撃の有効無効に関わらず決定されます(1体ずつ攻撃していき、全員が攻撃したところで攻撃順をシャッフルする)。
• トーナメント戦: ランキングに載っている12人の編成と負けるまで順番に戦い、勝てたところまでで新たなランキング保持者として登録されます。例えば5人目で負けた場合には4人目として登録され、1～4人目のランクはひとつ下がり、1人目は押し出されてランキングから消えます。

つまりプレイヤーがゲームに干渉できるのはモンスターの編成だけであって、そのあとは自動的に処理が進みます。

モンスターとその能力

全部で9体のモンスターがいます。

名前	SP	HP	攻撃	防御
Skeleton	1	1	Slash
Gnome	1	1	Shoot
Hellhound	2	2	Slash	Resist
Falcon	2	2	Slash	Flying
Lizardman	2	2	Slash	Armor
Elf	2	2	Shoot	Armor
Ogre	3	4	Crush
Golem	4	4	Crush	Armor
Dragon	6	8	Breath

• 攻撃
  • Slash: 地上の敵に2ダメージ。空中の敵には攻撃できない。
  • Shoot: 地上の敵に1ダメージ。空中の敵に2ダメージ。
  • Crush: 地上の敵に2ダメージ。空中の敵には攻撃できない。Armorの効果を無視する。
  • Breath: 地上・空中の敵全体に1ダメージ。Armorの効果を無視する。
• 防御
  • Armor: ダメージを1ポイント軽減する。低確率で効果が発動しないことがある。
  • Flying: SlashとCrushダメージを受けない。空中の敵に攻撃できる。
  • Resist: Breathダメージを受けない。

注目すべきはなんといってもDragonの存在です。HP8という強靭さを持っていますし、SkeletonやGnomeを並べられても全体攻撃で一掃できます。ですがHellhoundには弱く、1対1の戦いになったときにDragonに勝ち目はありません。しかしHellhoundは対空攻撃を持たないのでFalconに弱くなっています。Falconは唯一のFlyingを持ちますが、Shootで攻撃するGnomeとElfのほか、Falcon自身にも倒される可能性があります。

GnomeとElfは地上の敵には1ダメージしか与えられない上にArmor持ちにはほとんどダメージを与えられません。ですがArmorは確実性がなくOgreとGolemはそれを無効化します。とはいえOgreやGolemは高SPなので同時に編成できるモンスターが減りますし、数で攻められると弱い傾向にあります。またFalconに対して手が出せません。

どんな組み合わせであっても千日手になることはなく必ず決着がつきます。攻撃の順番がランダムなため、敵にDragonがいても、Skeletonの攻撃が先行すればDragonの攻撃前に倒し切ることも起こり得ます。

最強の編成を求める

さて最強の編成を求めるにはどうすればよいでしょうか？

人間が考える

まず考えられるのは人間が強そうだと思う編成を考えて、それらを戦わせあい、統計を取るというのはもっとも単純で実態に則した方法です。プレイヤーはコンピュータではなく人間であるからです。しかしここでの問題は、編成の絶対的な強さが人間の思考の範囲内に収まってしまうことです。人間が知恵と経験から「この編成が最強だ」と思っても、それを超える編成を機械的に簡単に見つけられるのであれば意味がありません。また、人間らしい編成のリストをどこかから取得しなければならず、現実的にそれを集めるのは難しい作業になるでしょう。

総当たりをする

編成パターン数が少ないという前提があれば、機械的に総当たりして一番強い編成を求められそうです。ちょうどSP10での編成パターンはたったの2160通りなので、総当たりですべてのケースを確かめて勝率の高い編成を抽出することができます。SPが10に満たない編成もできますが、利点がないため今回は考慮しません。ちなみにこの2160通りの編成パターンは木構造を使うと、特攻隊長を考慮した上で重複なしで簡単に求めることができます。総当たりでは人間が考えないであろうすべての編成を考慮することができますが、平均的には強いものの特定の編成にはまったく歯が立たないといった実践向きでない編成も抽出されることが考えられます。さらにこの方法では計算量が多くなり、結果が得られるまでにとても時間がかかることが難点です。

遺伝的アルゴリズム

そこで遺伝的アルゴリズムです。必ずしも正解を求められるわけではなく、局所解に陥りにくくするためのハイパーパラメータのチューニングが必要といえど、現実的な時間内でそこそこの結果を求められるため、こういった問題にうってつけです。シミュレーション環境が必要にはなりますが、アルゴリズム的にも複雑でない上、編成データも固定長なので遺伝的アルゴリズムの遺伝子データに変換しやすいところもこの問題に向いています。

評価方法も定量的にどのモンスターがどのように強いと計測するのではなく、実際に戦わせてみてその結果で強弱を判断するので、今回の場合は戦闘シミュレータが作成できれば遺伝的アルゴリズムを適用する準備はほぼ整ったといえます。

遺伝的アルゴリズムで最強の編成を求める

今回LoMR1を遺伝的アルゴリズムで解く上での流れは次のとおりです。

1. 1世代目の遺伝子をランダムにN個生成する
2. 遺伝子同士を使って戦闘シミュレータで戦わせる
3. 勝者とランダムに抽出した敗者の1/2から…
   • 1%でふたつの遺伝子を取り出して交叉させて次世代とする
   • 5%でひとつの遺伝子を取り出して突然変異させて次世代とする
   • 94%でひとつの遺伝子を取り出してそのまま次世代とする
4. N個の次世代を生成できたら現世代での遺伝子情報を表示
5. M世代経過していないなら2に戻る

3.で敗者からも遺伝子を選択するようにしています。これは一般的な遺伝的アルゴリズムからの変更点になりますが、ここではいわゆるアンチ編成を忘れないようにするためにこの処理を入れています。特定の編成が強いと判明すれば、その編成を攻略するための編成が作られることが容易に想像できるので、勝者の環境になりすぎないようにするための工夫です。

遺伝子の定義

各遺伝子には10個のスロットを持たせ、その中に0～9の値を持たせることにしました。0～8はモンスター番号に対応しており、9は空(編成の考慮にいれない)を意味しています。空を用意したのは10SPという縛りがある中で、後述する突然変異と交叉がうまく機能するようにです。

1世代目の遺伝子を作るときにはランダムで生成することにしました。10個のスロットの値をランダムに決定して、そこから生成される編成のSPが10以下なら生成成功です。この方法は多少効率が悪いように感じられますし、高SPのDragonを含む編成の生成確率が小さくなる心配もありましたが、実際動かして見ると問題にはなりませんでした。

(あとになって前述の2160通りのパターンから抽出して、特攻隊長以外の編成をシャッフルしてもいいと気づきました)

突然変異

ひとつの遺伝子を選択し、SPが10以下の結果が得られるまで、10個のスロットのうちランダムにひとつ選択して0～9の数値に変更した遺伝子を生成します。9(空)があるため異なるSPのモンスターにも変異しやすくなっています。

交叉

ふたつの遺伝子AとBを選択し、SPが10以下の結果が得られるまで、各スロットごと独立に1/2の確率でAまたはBのスロットの値を選択した新しい遺伝子を生成します(一様交叉)。

結果

次のようにパラメータを設定した遺伝的アルゴリズムを適用して、得られた結果の上位3位までの編成を記載します。結果は都度変わりますが大まかな傾向は掴めると思います。

公式のゲームが動作せず特攻隊長の被弾率とArmorの防御率が計測できなかったので、いくつか値を選び戦わせてみることにしました。

• 遺伝子数 = 3000
• 世代数 = 1000
• 特攻隊長の被弾率 = 1.0, 1.5, 2.0, 2.5, 3.0倍 (わからないため)
• Armorの防御率 = 0.7, 0.8, 0.9 (わからないため)

	防御率 0.7	防御率 8.0	防御率 9.0
被弾率 1.0	1. Falcon, Falcon, Dragon 2. Hellhound, Falcon, Dragon 3. Falcon, Elf, Dragon	1. Falcon, Falcon, Dragon 2. Hellhound, Falcon, Dragon 3. Falcon, Hellhound, Falcon, Elf x2	1. Falcon, Skeleton x4, Gnome x2, Elf 2. Falcon, Skeleton x5, Gnome, Elf 3. Falcon, Skeleton x3, Gnome x3, Elf
被弾率 1.5	1. Hellhound, Falcon, Dragon 2. Dragon, Hellhound, Falcon 3. Falcon, Falcon, Dragon	1. Falcon, Falcon, Dragon 2. Falcon, Hellhound, Falcon, Elf x2 3. Falcon, Hellhound, Elf x2, Elf	1. Hellhound, Falcon, Dragon 2. Falcon, Falcon, Dragon 3. Falcon, Skeleton, Gnome, Hellhound, Elf x2
被弾率 2.0	1. Falcon, Skeleton x4, Gnome x4 2. Falcon, Skeleton x3, Gnome x5 3. Lizardman, Skeleton x3, Gnome x5	1. Falcon, Falcon, Dragon 2. Hellhound, Falcon, Dragon 3. Dragon, Hellhound, Falcon	1. Falcon, Falcon, Dragon 2. Falcon, Hellhound, Falcon, Elf, Elf 3. Hellhound, Falcon, Dragon
被弾率 2.5	1. Falcon, Skeleton x4, Gnome x4 2. Falcon, Skeleton x3, Gnome x4 3. Lizardman, Skeleton x3, Gnome x5	1. Lizardman, Skeleton x3, Gnome x5 2. Lizardman, Skeleton x4, Gnome x4 3. Falcon, Skeleton x4, Gnome x4	1. Falcon, Falcon, Dragon, 2. Lizardman, Falcon, Dragon 3. Falcon, Skeleton x2, Dragon
被弾率 3.0	1. Falcon, Skeleton x3, Gnome x5 2. Falcon, Skeleton x3, Gnome x5 3. Lizardman, Skeleton x3, Gnome x5	1. Falcon, Skeleton x4, Gnome x4 2. Lizardman, Skeleton x4, Gnome x4 3. Falcon, Skeleton x5, Gnome x3	1. Lizardman, Skeleton x4, Gnome x4 2. Lizardman, Skeleton x3, Gnome x5 3. Falcon, Skeleton x4, Gnome x4

Armorの防御率が高く、特攻隊長への被弾率が低いとDragonが編成に加わり、特にFalcon x2かFalcon, Hellhoundが強いようです。Falcon, Hellhound, Dragonの編成はわかりやすい三すくみの関係になっています。そうでないときはSkeletonやGnomeで数で押す編成が有効なようです。Falconはどの場合でも有効であり、一撃で倒されることを防ぐために特攻隊長にするのが最良の配置という結果になりました。

Ogre, Golemの姿がまったく見えないのも特徴的です。このゲームにおいて編成のモンスター数が多いことは相手よりも先制攻撃の可能性が増え、それによって敵を減らせることを意味しているので、CrushによるArmor貫通でSPを3や4も使用することは割に合わないのでしょう。

ここでの編成の強さは連戦での強さを考慮していません。ですので、最強と思しきFalcon, Falcon, Dragonで編成したとしても、アンチ構成であるGnome x8, Hellhoundが現れたら敗北する確率は高くなるでしょう。