simplestarの技術ブログ

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

Hearthstone: ハースストーンのスプリットダメージの期待値（検算プログラム）

Game

スプリットダメージの期待値の計算について書いてきましたが
やっと期待値計算を行うためのプログラムの形が見えてきました。
（正確にはカードごとに撃破される確率を出すプログラムです。）

ということで、私が見たものを書いてみます。

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

class SplitDamageCalculator
{
    public struct CombinationProbability
    {
        public int[] combination;
        public float probability;
    }

    public void CalculateP(int[] cardLives, int damageCount, out float[] cardDefeatRates)
    {
        int numCards = cardLives.Length;
        cardDefeatRates = new float[numCards];
        CombinationProbability cp = new CombinationProbability { combination = new int[numCards], probability = 1 };
        for (int j = 0; j < numCards; j++)
        {
            int life = cardLives[j];
            cp.combination[j] = life;
        }
        List<List<CombinationProbability>> layers = new List<List<CombinationProbability>>();
        for (int i = 0; i < damageCount; i++)
        {
            layers.Add(new List<CombinationProbability>());
        }
        _ListCombinationProbability(ref layers, ref cp, numCards, damageCount - 1);
        foreach (CombinationProbability resultCp in layers[0])
        {
            for (int i = 0; i < numCards; i++)
            {
                if (0 == resultCp.combination[i])
                {
                    cardDefeatRates[i] += resultCp.probability;
                }
            }
        }
    }

    private static void _ListCombinationProbability(ref List<List<CombinationProbability>> layers, ref CombinationProbability rootCp, int numCards, int damageCount)
    {
        if (0 > damageCount)
        {
            return;
        }
        List<CombinationProbability> layer = layers[damageCount];
        for (int i = 0; i < numCards; i++)
        {
            CombinationProbability cp = new CombinationProbability() { combination = new int[numCards], probability = 0 };
            int numActiveCards = 0;
            bool isLeaf = false;
            for (int j = 0; j < numCards; j++)
            {
                int life = rootCp.combination[j];
                cp.combination[j] = life;
                if (0 == life)
                {
                    if (j == i)
                    {
                        isLeaf = true;
                        break;
                    }
                }
                else
                {
                    if (j == i)
                    {
                        cp.combination[j] = life - 1;
                    }
                    ++numActiveCards;
                }
            }
            if (!isLeaf)
            {
                cp.probability = rootCp.probability * 1 / (float)numActiveCards;
                layer.Add(cp);

                _ListCombinationProbability(ref layers, ref cp, numCards, damageCount - 1);
            }
        }
    }
}

正しく動作するかみてみましょう。

使い方は次の通り

            int [] cardLives = new int[3] { 1, 2, 3 };
            float[] defeatRates = null;
            SplitDamageCalculator c = new SplitDamageCalculator();
            c.CalculateP(cardLives, 3, out defeatRates);

結果はこちら

defeatRates
		[0]	0.7222222	float
		[1]	0.3240741	float
		[2]	0.0370370373	float

前回に全事象を書き出して、求めた値と一致していますね。
では、さらに難しくなるダメージ回数4の場合の撃破率を列挙してみます。

defeatRates
		[0]	0.842592537	float
		[1]	0.537037	float
		[2]	0.162037045	float

さらにさらに難しくなるダメージ回数5の場合の撃破率を列挙してみます。

defeatRates
		[0]	0.9212965	float
		[1]	0.715277851	float
		[2]	0.363425851	float

ある意味簡単ですが、まじめに計算すると難しくなるダメージ回数6の場合の撃破率を列挙してみます。

defeatRates
		[0]	1.00000024	float
		[1]	1.00000024	float
		[2]	1.00000024	float

興味本位でダメージ回数7の場合は？

defeatRates
		[0]	0.0	float
		[1]	0.0	float
		[2]	0.0	float

ライフ合計が総合ダメージ以下なら計算せず 1 だけ返すように書き換えます。
では、ダメージ回数が 2 の場合は

defeatRates
		[0]	0.5555556	float
		[1]	0.111111112	float
		[2]	0.0	float

前々回に手計算で求めた結果と、簡易的に作ったプログラムの結果とも一致していますね。

ダメージ回数が1の場合は

defeatRates
		[0]	0.333333343	float
		[1]	0.0	float
		[2]	0.0	float

これはひと目でわかります。
正しいですね。

これまた興味本位でダメージ回数が0の場合は、クラッシュしました。
ダメージ回数が0以下の場合は計算せず 0 だけ返すように書き換えます。

完成版がこちら！

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

class SplitDamageCalculator
{
    public struct CombinationProbability
    {
        public int[] combination;
        public float probability;
    }

    public void CalculateP(int[] cardLives, int damageCount, out float[] cardDefeatRates)
    {
        int numCards = cardLives.Length;
        cardDefeatRates = new float[numCards];
        CombinationProbability cp = new CombinationProbability { combination = new int[numCards], probability = 1 };
        int totalLife = 0;
        for (int j = 0; j < numCards; j++)
        {
            int life = cardLives[j];
            cp.combination[j] = life;
            totalLife += life;
        }
        if (damageCount >= totalLife)
        {
            for (int i = 0; i < numCards; i++)
            {
                cardDefeatRates[i] = 1;
            }
        }
        else if (0 < damageCount)
        {
            List<List<CombinationProbability>> layers = new List<List<CombinationProbability>>();
            for (int i = 0; i < damageCount; i++)
            {
                layers.Add(new List<CombinationProbability>());
            }
            _ListCombinationProbability(ref layers, ref cp, numCards, damageCount - 1);
            foreach (CombinationProbability resultCp in layers[0])
            {
                for (int i = 0; i < numCards; i++)
                {
                    if (0 == resultCp.combination[i])
                    {
                        cardDefeatRates[i] += resultCp.probability;
                    }
                }
            }
        }
        else
        {
            for (int i = 0; i < numCards; i++)
            {
                cardDefeatRates[i] = 0;
            }
        }
    }

    private static void _ListCombinationProbability(ref List<List<CombinationProbability>> layers, ref CombinationProbability rootCp, int numCards, int damageCount)
    {
        if (0 > damageCount)
        {
            return;
        }
        List<CombinationProbability> layer = layers[damageCount];
        for (int i = 0; i < numCards; i++)
        {
            CombinationProbability cp = new CombinationProbability() { combination = new int[numCards], probability = 0 };
            int numActiveCards = 0;
            bool isLeaf = false;
            for (int j = 0; j < numCards; j++)
            {
                int life = rootCp.combination[j];
                cp.combination[j] = life;
                if (0 == life)
                {
                    if (j == i)
                    {
                        isLeaf = true;
                        break;
                    }
                }
                else
                {
                    if (j == i)
                    {
                        cp.combination[j] = life - 1;
                    }
                    ++numActiveCards;
                }
            }
            if (!isLeaf)
            {
                cp.probability = rootCp.probability * 1 / (float)numActiveCards;
                layer.Add(cp);

                _ListCombinationProbability(ref layers, ref cp, numCards, damageCount - 1);
            }
        }
    }
}

■問題1
場にライフ3,4,5のカード3枚がある場合に、スプリットダメージ回数4を実行したとき
それぞれのカードについて撃破される確率を計算しなさい。
★答え1
上記プログラムの結果は次の通り

		[0]	0.111111112	float
		[1]	0.0123456791	float
		[2]	0.0	float

ライフ4のカードについては 1/3 * 1/3 * 1/3 * 1/3 の 0.0123456790123457 になるはずなので、あってますね。
ライフ3のカードについて、ダメージ回数4の時に、以下の組み合わせ一覧が考えられ、それぞれの確率を併記すると次の通り
0, 3, 5 probability 0.0185185187 float
0, 4, 4 probability 0.0185185187 float
0, 3, 5 probability 0.0123456791 float
0, 4, 4 probability 0.0123456791 float
0, 3, 5 probability 0.0123456791 float
0, 4, 4 probability 0.0123456791 float
0, 3, 5 probability 0.0123456791 float
0, 4, 4 probability 0.0123456791 float
合計が 0.111111112 ということで、これもあっていますね。

これがスプリットダメージにおける、カードごとの撃破率を求めるプログラムです。

プロジェクト一式はこちら
http://file.blenderbluelog.anime-movie.net/SplitDamage.zip

成果物のアプリだけ欲しい人はこちら
http://file.blenderbluelog.anime-movie.net/SplitDamage.exe
★実行できない人へ
別PCで作られたプログラムを実行するには、セキュリティを解除する必要があります。
下図を参考にしてください。
f:id:simplestar_tech:20160111105846p:plain

simplestar_tech 読者になる

コメントを書く