LoginSignup
2
2

More than 5 years have passed since last update.

@YSRKEN

艦これの計算を高速化するTipsまとめ その1

Posted at

目次

  • 概要
  • 制空条件の判定
  • ステージ1撃墜
  • ステージ1触接

※「艦これの計算を高速化するTipsまとめ その2」では、攻撃順解決やダメージ計算などのTipsを掲載する予定です。ご期待下さい。

概要

  • 可読性が高いし結果が分かりやすいのでPythonを採用
  • 誰でも結果を確認できるようにWandboxを採用
  • Python3は人権なのでWandboxの中でもCPythonを選択
  • 時間の計測方法はtime.time()で2回取得して引き算するだけ
  • 各項目の見出しがWandboxへのリンクになっています

制空条件の判定

image.png
(出典：wikiwiki)

  • 「艦隊の制空値」と「敵艦隊の制空値」を入力すると、「制空権確保」～「制空権喪失」を返したい
  • ナイーブに実装すると、どうしてもif文の嵐になる。「予測分岐の失敗」まで頭をよぎりそう
  • 効率よく実装すると、あらかじめ配列(テーブル)に計算結果を入力してからそれを引く形になる
    • テーブル引きは(メモリに余裕がある際は)計算を端折れる、効率の良い常套手段
sample1.py
from time import time

def get_fighter_combat_result(fighter_power: int, enemy_fighter_power: int) -> int:
    """制空状態の判定(通常版)
    """
    if fighter_power >= 3 * enemy_fighter_power:
        return 0  # 制空権確保
    elif fighter_power * 2 >= 3 * enemy_fighter_power:
        return 1  # 航空優勢
    elif fighter_power * 3 > 2 * enemy_fighter_power:
        return 2  # 航空均衡
    elif fighter_power * 3 > enemy_fighter_power:
        return 3  # 航空劣勢
    else:
        return 4  # 制空権喪失

# 事前計算する
max_fighter_power: int = 1000  # 最大の制空値
result_list = [[0 for i in range(max_fighter_power)] for j in range(max_fighter_power)]  # キャッシュ
for i in range(0, max_fighter_power):
    for j in range(0, max_fighter_power):
        if i >= 3 * j:
            result_list[i][j] = 0  # 制空権確保
        elif i * 2 >= 3 * j:
            result_list[i][j] = 1  # 航空優勢
        elif i * 3 > 2 * j:
            result_list[i][j] = 2  # 航空均衡
        elif i * 3 > j:
            result_list[i][j] = 3  # 航空劣勢
        else:
            result_list[i][j] = 4  # 制空権喪失

def get_fighter_combat_result_fast(fighter_power: int, enemy_fighter_power: int) -> int:
    """制空状態の判定(高速)
    """
    return result_list[fighter_power][enemy_fighter_power]

print('制空状態の判定(簡単な書き方)')
fighter_power: int = 120  # 艦隊の制空値
enemy_fighter_power: int = 120    # 敵艦隊の制空値
loop_size: int = 10000000    # ループサイズ
# 測定ループ開始
start_time = time()
for _ in range(0, loop_size):
    result = get_fighter_combat_result(fighter_power, enemy_fighter_power)
elapsed_time = time() - start_time
# 測定ループ終了
print(f'経過時間：{elapsed_time}[s]')
print(f'処理時間：{elapsed_time / loop_size * 1000 * 1000}[us/回]')

print('制空状態の判定(高速な書き方)')
fighter_power: int = 120  # 艦隊の制空値
enemy_fighter_power: int = 120    # 敵艦隊の制空値
loop_size: int = 10000000    # ループサイズ
# 測定ループ開始
start_time = time()
for _ in range(0, loop_size):
    result = get_fighter_combat_result_fast(fighter_power, enemy_fighter_power)
elapsed_time = time() - start_time
# 測定ループ終了
print(f'経過時間：{elapsed_time}[s]')
print(f'処理時間：{elapsed_time / loop_size * 1000 * 1000}[us/回]')
result1.txt
制空状態の判定(簡単な書き方)
経過時間：5.383422374725342[s]
処理時間：0.5383422374725342[us/回]
制空状態の判定(高速な書き方)
経過時間：2.907625675201416[s]
処理時間：0.29076256752014157[us/回]

ステージ1撃墜

image.png
(出典：wikiwiki)

  • 制空状態によって、自艦隊および敵艦隊の艦載機が撃墜される(どちらもスロットごとに残搭載数から判定・切り捨て)
  • 自艦隊の撃墜割合は1/256刻みなので、例えば航空優勢だと26通りの可能性が一様分布でありうる
    • もっとも切り捨てなので、例えば10機スロで航空均衡の場合、1機撃墜が47.8％・2機撃墜が52.2％の確率で起きる
  • 敵艦隊の撃墜割合は1％刻み……ではない。カンペによると、2つの一様分布の混ぜ合わせらしい
    • 以下のサンプルでは、自艦隊の撃墜だけ考えることにする
  • ナイーブに実装すると、制空状態に合わせて撃墜数の一様乱数を振って計算することになる
  • 効率よく実装すると、撃墜数を事前計算することになる。なにげに「配列からランダムに1つ選択する」関数まであって草
sample2.py
from time import time
import random
import math

def calc_new_friend_slots(fighter_combat_result: int, slot: int) -> int:
    """St1撃墜処理(通常版)
    """
    if fighter_combat_result == 0:
        # 制空権確保
        return slot - math.floor(slot * random.randint(7, 15) / 256)
    elif fighter_combat_result == 1:
        # 航空優勢
        return slot - math.floor(slot * random.randint(20, 45) / 256)
    elif fighter_combat_result == 2:
        # 制空均衡
        return slot - math.floor(slot * random.randint(30, 75) / 256)
    elif fighter_combat_result == 3:
        # 航空劣勢
        return slot - math.floor(slot * random.randint(40, 105) / 256)
    else:
        # 制空権喪失
        return slot - math.floor(slot * random.randint(65, 150) / 256)

# 事前計算する
max_slot: int = 100  # 最大の搭載数
result_list = [[0 for i in range(max_slot)] for j in range(5)]
min_per = [7, 20, 30, 40, 65]
max_per = [15, 45, 75, 105, 150]
for i in range(0, 5):
    for j in range(0, max_slot):
        temp = list(map(lambda x: j - math.floor(j * x / 256), range(min_per[i], max_per[i] + 1)))
        result_list[i][j] = temp

def calc_new_friend_slots_fast(fighter_combat_result: int, slot: int) -> int:
    """St1撃墜処理(高速)
    """
    return random.choice(result_list[fighter_combat_result][slot])

print('St1撃墜処理(簡単な書き方)')
fighter_combat_result: int = 2  # 制空状態
friend_slot: int = 46     # 自艦隊のあるスロットの現搭載数
loop_size: int = 1000000  # ループサイズ
# 測定ループ開始
start_time = time()
for _ in range(0, loop_size):
    result = calc_new_friend_slots(fighter_combat_result, friend_slot)
elapsed_time = time() - start_time
# 測定ループ終了
print(f'経過時間：{elapsed_time}[s]')
print(f'処理時間：{elapsed_time / loop_size * 1000 * 1000}[us/回]')

print('St1撃墜処理(高速な書き方)')
fighter_combat_result: int = 2  # 制空状態
friend_slot: int = 46     # 自艦隊のあるスロットの現搭載数
loop_size: int = 1000000  # ループサイズ
# 測定ループ開始
start_time = time()
for _ in range(0, loop_size):
    result = calc_new_friend_slots_fast(fighter_combat_result, friend_slot)
elapsed_time = time() - start_time
# 測定ループ終了
print(f'経過時間：{elapsed_time}[s]')
print(f'処理時間：{elapsed_time / loop_size * 1000 * 1000}[us/回]')
result2.txt
St1撃墜処理(簡単な書き方)
経過時間：2.6160950660705566[s]
処理時間：2.616095066070556[us/回]
St1撃墜処理(高速な書き方)
経過時間：1.1893696784973145[s]
処理時間：1.1893696784973145[us/回]

ステージ1触接

image.png
image.png
image.png

(出典：wikiwiki)

  • いきなり面倒臭さが跳ね上がります。よくこんなの見つけ出したな感
  • ナイーブに実装すると、次のように計算するものと思われる
    • 制空状態が「制空権確保」「航空優勢」「航空劣勢」の場合のみ計算することに注意
    • 【フェーズ1計算】
    • ・艦娘の全スロットを調査し、水偵・艦偵・飛行艇について触接開始率を計算し、総和を求める
    • ・ただし航空優勢では開始率に0.6を掛ける(航空劣勢では何掛けするのかは不明。たぶん0.6か0.55)
    • ・触接開始率が100％未満なら乱数で、100％以上なら確実にフェーズ2に移行する
    • 【フェーズ2計算】
    • ・艦娘の全スロットを旗艦1スロ目～5スロ目・2番艦1スロ目～5スロ目……と走査する
    • ・その際、1機以上のスロにおける水偵・艦偵・艦攻・飛行艇について、索敵値と命中値のペアを配列に順に入れて記録する
    • ・その配列に対し、命中値で降順に安定ソートする
    • ・ソート後の配列を上から見ていき、触接選択率で乱数判定する
    • ・順に乱数判定して成功した時点で終了。命中値に応じた補正が掛かる
  • 効率よく実装すると……って、そもそも大部分が事前計算できるよなこれ
    • フェーズ1計算は出撃前に判断できる(100％を超えると乱数すら不要)
    • フェーズ2計算はソート後の結果を「触接選択率, 選択時の攻撃力補正」の配列で所持して、順番に見ていくだけ
    • もっと言えば、各々の選択確率は事前計算できるので、乱数を1回だけ使ってから「乱数は0.259だから2つ目の要素における攻撃力補正を使います」でおｋ

image.png

(出典：wikiwiki)

  • 例えばこの例の場合、事前に次のように計算できます。後は0～1の実数一様乱数を1回出して、「0.28未満なら九七友永(1つ目)、0.28以上0.482未満なら九七友永(2つ目)、……、0.97以上なら触接失敗」とすればよし
  • 計算量に差がありすぎるので、ナイーブな例と効率的な例の比較コードは出しません
calc1.txt
○対象となる艦載機の一覧を取得
[零観, 紫雲, 夜偵, 天山村田, 九七友永, 九七友永, 天山友永, 天山村田, 流星改]

○命中値で安定ソート
[零観(命中2), 紫雲(1), 夜偵(1), 天山村田(2), 九七友永(3), 九七友永(3), 天山友永(3), 天山村田(2), 流星改(0)]
↓
[九七友永(3), 九七友永(3), 天山友永(3), 零観(2), 天山村田(2), 天山村田(2), 紫雲(1), 夜偵(1), 流星改(0)]

○それぞれの触接選択率を計算
[九七友永(索敵4), 九七友永(4), 天山友永(5), 零観(6), 天山村田(4), 天山村田(4), 紫雲(8), 夜偵(3), 流星改(2)]
↓
[九七友永(28％), 九七友永(28％), 天山友永(35％), 零観(42％), 天山村田(28％), 天山村田(28％), 紫雲(56％), 夜偵(21％), 流星改(14％)]

○実際に選択される確率を求める。先頭から順に判定されることに注意
[九七友永(28％), 九七友永(20.2％), 天山友永(18.1％), 零観(14.2％), 天山村田(5.5％), 天山村田(3.9％), 紫雲(5.7％), 夜偵(0.9％), 流星改(0.5％)]
※どれも選択されず、触接に失敗する確率は3.0％
2
2
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
2
2