Hearthstone: ハースストーンのスプリットダメージの期待値プログラム高速化

およそ想定される最大計算量の 5^10 の分岐確率計算に 0.4 秒要するというのが前回の省メモリプログラムの速度でした。
これに対して
「秒という単位が出た時点で遅いです。」
という意見をもらいまして、さらなる高速化が求められている訳です。

高速化できる所を探してみました。

一つにアクティブなカード数を数えるループの部分があります。
分岐の親の場のカード数から変動があるかどうかは、親の処理で攻撃したときにライフ0になったかどうかを確認するだけで良いので
アクティブなカード枚数はその時に更新して子に渡せば良いというものです。

もう一つ高速化できるとしたら、場にカードが1枚残った場合
分岐は発生しないので、現在の確率を足して、早々に計算を切り上げるというものです。

さらにもう一つ、条件は限られますが攻撃回数より低いライフが一つもない場合は
計算せずにすべて 0 を返すと、意地悪な条件のもとで無駄な計算をせず済みます。

高速化前と高速化後のコードについて、計算時間をみてみましょう。

まず、高速化前のプログラムで
場に 4, 5, 6, 7, 8 というカードがある状態で
10回スプリットダメージを与えた時に、正しい答えを出すのに要した時間は 356 ms でした。
確率は次の通り
0.120805, 0.032919, 0.006379, 0.000864, 0.000078

第一案の現在のカード数を子に引き渡すように書いてみました。
すると同じ解答を得るのに 255 ms 要しました。
1.4 倍まで高速化できました。

コード見ていてひらめいたことに、確率計算のための割り算を無駄にループ内に入れていました。
この計算をループの外に置いて高速化をはかりましたが、ウェイトが低すぎて高速化は確認できませんでした。

次に

二つ目の案の最後の一枚が残ったら再帰処理を終了させるように書いてみました。
重要なのは、すべてのカードが撃破される場合はすでに除外しているので、最後の一枚が残ったら必ず生き残るということがわかります。
なので、場に一枚だけになった瞬間に分岐処理は終えても計算結果に影響は出ません。

246 ms 要してます。
ほんの少し高速化できました。

ここでさらに高速化できそうな処理を思いつきます。
例えば残りのダメージ回数が場に残っているカードの最低ライフに届かない場合
その残っているカードについてのみ撃破率の計算は不要です。
そんな時は、それまでに倒されているカードの確率を集計すれば良いのです。
という再帰処理を終了させる条件を加えてみました。

すると同じ解答を得るのに 128 ms を要しました。
前回の高速化よりさらに 1.92 倍も高速化できました。

さてさて、高速化のすごいところはここから
条件を変えてみましょう。
場に 7, 8, 9, 10, 11 というカードがある状態で
10回スプリットダメージを与えた時に、正しい答えを出すのに要した時間は
高速化前は 354 ms でした。
高速化後は 3 ms でした。
どちらも正解の
0.0008643, 0.0000779, 0.0000042, 0.0000001, 0.0000000 を計算しています。
なんと 118 倍も高速化しています。
というか 10 回もスプリットダメージを与えて全分岐をしらべると単純に
9765625 通りの可能性を一つずつ見ていかなければならないのに、正しい答えを出すのに 3 ms かよ。
という驚きがあります。

通常の計算量についても見てみます。
場に 4, 5, 6, 7, 8 というライフのカードがあったときに
8回スプリットダメージを与えて、それぞれのカードの撃破率を 0～1 で計算すると
0.0562765, 0.0104067, 0.0012314, 0.0000845, 0.0000026
となり、これに要する時間は 3 ms でした。

さて、今回の高速化版のコードがこちら

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class SplitDamageCalculator
{
    /// <summary>
    /// カードの撃破率を計算
    /// </summary>
    /// <param name="cardLives">カードのライフリスト</param>
    /// <param name="damageCount">スプリットダメージ回数</param>
    /// <param name="cardDefeatRates">カードごとの撃破率(0～1)</param>
    public static void CalculateDefeatRates(int[] cardLives, int damageCount, out float[] cardDefeatRates)
    {
        int numCards = cardLives.Length;
        cardDefeatRates = new float[numCards];
        float probability = 1;
        int totalLife = 0;
        for (int j = 0; j < numCards; j++)
            totalLife += cardLives[j];
        if (damageCount >= totalLife)
        {
            for (int i = 0; i < numCards; i++)
                cardDefeatRates[i] = 1;
        }
        else if (0 < damageCount)
        {
            int defeatTargetCount = 0;
            for (int i = 0; i < numCards; i++)
                if (damageCount >= cardLives[i])
                    ++defeatTargetCount;
            if (0 < defeatTargetCount)
            {
                _CalcuCombination(ref cardDefeatRates, ref cardLives, probability, numCards, numCards, damageCount);
            }
        }
    }

    /// <summary>
    /// 組み合わせの確率計算
    /// </summary>
    /// <param name="cardDefeatRates">確率計算結果格納先</param>
    /// <param name="rootCombination">分岐の根のライフの組み合わせ</param>
    /// <param name="rootProbability">分岐の根の分岐確率</param>
    /// <param name="numCards">初期の場のカード枚数</param>
    /// <param name="numActiveCards">分岐の根の場のカード枚数</param>
    /// <param name="damageCount">残っているダメージ回数</param>
    private static void _CalcuCombination(ref float[] cardDefeatRates, ref int[] rootCombination, float rootProbability, int numCards, int numActiveCards, int damageCount)
    {
        if (0 == damageCount)
        {
            for (int k = 0; k < numCards; k++)
                if (0 == rootCombination[k])
                    cardDefeatRates[k] += rootProbability;
            return;
        }
        int defeatTargetCount = 0;
        for (int i = 0; i < numCards; i++)
            if (damageCount >= rootCombination[i])
                ++defeatTargetCount;
        if (0 < defeatTargetCount)
        {
            float probability = rootProbability * 1 / (float)numActiveCards;
            for (int i = 0; i < numCards; i++)
            {
                if (0 != rootCombination[i])
                {
                    int localActive = numActiveCards;
                    if (0 == --rootCombination[i])
                        --localActive;
                    _CalcuCombination(ref cardDefeatRates, ref rootCombination, probability, numCards, localActive, damageCount - 1);
                    ++rootCombination[i];
                }
            }
        }
        else
        {
            for (int k = 0; k < numCards; k++)
                if (0 == rootCombination[k])
                    cardDefeatRates[k] += rootProbability;
        }
    }
}