simplestarの技術ブログ

目的を書いて、思想と試行、結果と考察、そして具体的な手段を記録します。

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

ふと、前回書いたプログラム
simplestar-tech.hatenablog.com

について
デバッグ用に組み合わせ一覧を記録していましたが
ほしいのはカードごとの撃破率なので、計算結果が出たら
加算していけば答えを変えずに省メモリ化できることに気づきまして
下記の通り、省メモリ化を施しました。
若干の高速化もできています。

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

class SplitDamageCalculator
{
    public void CalculateP(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)
        {
            _ListCombinationProbability(ref cardDefeatRates, ref cardLives, probability, numCards, damageCount - 1);
        }
        else
        {
            for (int i = 0; i < numCards; i++)
                cardDefeatRates[i] = 0;
        }
    }

    private static void _ListCombinationProbability(ref float[] cardDefeatRates, ref int[] rootCombination, float rootProbability, int numCards, int damageCount)
    {
        if (0 > damageCount)
        {
            for (int k = 0; k < numCards; k++)
                if (0 == rootCombination[k])
                    cardDefeatRates[k] += rootProbability;
            return;
        }
        for (int i = 0; i < numCards; i++)
        {
            if (0 != rootCombination[i])
            {
                int numActiveCards = 0;
                for (int j = 0; j < numCards; j++)
                    if (0 != rootCombination[j])
                        ++numActiveCards;
                float probability = rootProbability * 1 / (float)numActiveCards;
                rootCombination[i]--;
                _ListCombinationProbability(ref cardDefeatRates, ref rootCombination, probability, numCards, damageCount - 1);
                rootCombination[i]++;
            }
        }
    }
}

また、とこかで大幅に高速化できる要素がひらめいたら追記します。

ひらめいたので書きました。
simplestar-tech.hatenablog.com