目次
はじめに
先日 jpoke というシングル対戦のシミュレータを公開しました。jpoke ではターン進行や効果の連鎖を表現するためにイベント駆動というアーキテクチャを採用しています。
ところで、jpoke では致死率、すなわち『相手を技で倒すのに何発必要で、何%で倒せるか』を計算する補助機能も提供しています。致死率を正確に計算するには、すべてのダメージとHPの分岐を網羅する必要があります。一方で、対戦シミュレータは乱数で選ばれた単一状態を追い続けるため、そもそも致死率計算とは相性が良くありません。
致死率計算を実装するにあたり、対戦シミュレータからはダメージ計算式だけを拝借し、分布計算などのパーツはすべて外付けすることにしました。この外付けコードの実装や気づいたことについて紹介したいと思います。
致死率計算 = 畳み込み
ダメージ乱数の16分岐をそのまま配列にして計算してしまうと、n回攻撃したときの計算量が 16n に膨れ上がります。そこで、1本の配列を『状態』と『場合の数』に分離すると、計算量を n_hp * n_damage まで抑えることができます。
具体例として、無振りガブが無振りガブにじしんを撃った場合 (確3)、ダメージは75,76,78,79,81,82,84,85,87,88の10通りなので、以下のような計算になります。
1回目の攻撃
計算量: n_hp(1) * n_damage(10) = 10
攻撃後のHP: 95,96,98,99,101,102,104,105,107,108 (10通り)
2回目の攻撃
計算量: n_hp(10) * n_damage(10) = 100
攻撃後のHP: 7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33 (27通り)
3回目の攻撃
計算量: n_hp(27) * n_damage(10) = 270
攻撃後のHP: 0 (1通り)
ほとんどのケースでは同じ HP に到達する組が大量に発生するので、HP分布は計算量よりも小さくなります。
3回目の攻撃での計算量は 270 で、配列のまま計算した場合 (163=4096) の 1/10 以下で済みました。
致死率を計算するには HP とその場合の数をセットで計算する必要があるので、{hp: freq}, {damage: damage_freq} のような辞書で表現すれば、{hp_after: freq_after} = {hp_before-damage: hp_freq*damage_freq} のように計算できます。
HPだけでは状態を表現しきれない
防御側がオボンの実を持っている場合を考えます。
分布を {hp: freq} で表現しただけでは、オボンの実をまだ消費していないのか、消費した結果その HP まで回復したのか区別できません。区別するにはキーに道具の有効状態を記録する必要があります。そこで、キーを不変 (frozen) データクラスに拡張しました。
@dataclass(frozen=True)
class State:
value: int
item_enabled: bool = True
def __add__(self, other: State) -> State:
return State(
value=self.value + other.value,
item_enabled=self.item_enabled and other.item_enabled,
)
アイテムを消費した枝と未消費の枝は、同じHPでも別のキーとして扱われます。また __add__ で加算を定義することで、HPの畳み込みと item_enabled の AND 合成を自然に統合できました。
同様に、特性ばけのかわの有効判定も ability_enabled フラグを導入すれば解決できます。
分布計算の途中に効果を差し込む
今度は防御側がたべのこしを持っている場合を考えます。たべのこしは毎ターン終了時に発動するので、ダメージ計算のあとに if で効果を差し込めば正しく計算できます。
hp_dist = {State(value=defender.hp): 1}
for i in range(n_attack):
hp_dist = hp_dist - damage_dist
if defender.item == "たべのこし":
hp_dist = hp_dist + defender.max_hp // 16
しかし、致死率計算に影響する要素(アイテム・状態異常・天候など)が増えるたびに if を継ぎ足していくとループがどんどん肥大化していきます。
そこで、ループ進行と効果処理を分離することにしました。まず、ループ側は「ダメージを適用してイベントを発火する」ことだけを担当します。
hp_dist = {State(value=defender.hp): 1}
for i in range(n_attack):
hp_dist = hp_dist - damage_dist
hp_dist = emit(Event.ON_TURN_END, ctx, hp_dist)
効果側では、イベントと効果処理を紐づけて登録しておきます。
def heal_1_16(ctx, hp_dist):
return hp_dist + ctx.defender.max_hp // 16
handlers = {
"たべのこし": {
Event.ON_TURN_END: heal_1_16
}
}
こうしておけば、対応する効果が増えてもループ本体は汚染されません。新しい特性やアイテムに対応するときは handlers に1行足すだけで済みます。ここでは紹介していませんが、実際にはイベントを発火してからハンドラが呼ばれるまでの間に、呼ぶべきハンドラをかき集める処理が必要です。このようにイベントとハンドラで制御する構造をイベント駆動と呼びます。jpoke 本体の対戦シミュレータも基本的に同じ仕組みです。
まとめ
ここまで読んでいただきありがとうございました。簡単ですが jpoke の致死率計算の実装について紹介しました。この文章がダメージ計算ツールを開発されている方の役に立てば幸いです。
jpoke は GitHub で公開しています。興味を持っていただけたらぜひ覗いてみてください。
https://github.com/tmwork1/jpoke
