完成品どーん (3回目)

part1のあらすじ

ダイスの期待値などを計算してくれるサービスを作った
しかしダイスの期待値に正規分布の近似を使ってるから精度が微妙

今回は精度を改善していくお話です

そもそも、元々どのぐらいの精度だったん？

正規分布というのは超ざっくり説明すると下の図のような分布のことです。それに対してダイスの出目というのは多項分布というものなので、強引に正規分布に近似すると精度が落ちちゃいます。

出典：http://ryo-kida.blog.jp/archives/54884972.html

じゃあどのくらい落ちるのかと言われると難しいのですが、例えば2d100の分布は次のような形をしています。

似ていると言われれば似てるけど、ちょっと無理があるなぁってぐらいの精度ですね。

なので正規分布に近似せずにダイスの期待値を求めてみようというお話です。

どうやって求めるのさ

「それは私にもわからん」

というのは半分冗談ですが、私には思いつかなかったのでTwitterで聞いてみました。

誰も答えてくれませんでした。世間は非情だね。

しょうがないので友達に聞いたら答えてくれました。持つべきものは友ってそれ一番(ry

友達から貰ったのがこのコード

const generate2DArray = (m: number, n: number, val = 0): number[][] => {
  return [...Array(m)].map((_) => Array(n).fill(val));
};

const dp = generate2DArray(n, m * m, 0.0);

for (let i = 0; i < m; i++) {
  dp[0][i] = 1.0 / m;
}
for (let i = 1; i < n; i++) {
  let sum = 0.0;
  for (let j = 0; j < n * m; j++) {
    if (j < m) {
      sum += dp[i - 1][j];
    } else {
      sum = sum - dp[i - 1][j - m] + dp[i - 1][j];
    }
    dp[i][j] += sum / m;
  }
}

for (let i = 0; i < ; i++) {
  console.log(`${n + i} : ${dp[n - 1][i]}`);
}

まずn×n*mの大きさの2次元配列を定義して、そこに値を埋めていく方式で計算していることがわかります。なので表を使って値が埋まる過程を追ってみましょう。

例として3D6 (n=3, m=6) の場合を考えます。この時二次元配列の大きさは3×18になります。

ループの外で値が少しいじられているので最初の配列は次の図のようになります。この表がどのように変化していくのか見ていきましょう。

1ループ目

5列目まで（赤色の部分）は上のものを足してコピーという風に動いていましたが、6列目から（青色の部分）は6個前のものを引くという動作が加わるのでだんだん小さくなって11以降は0になっています。

2ループ目

2ループ目もやることは変わらず、5列目までと6列目以降にわけて処理を行っていきます。

するとあら不思議、3D6の確率分布が得られているではありませんか！

グラフにするとこんな感じ。

このプログラムが何をしているのかをまとめると

最初にm面ダイスの確率分布を作る
ループごとにダイスを増やしていく
n-1回ループするとn個ダイスを振った確率分布が得られる

という感じです。さっきの具体例に当てはめてみるとこんな感じ。

最初に1d6の確率分布を作る
1ループ目では2d6、2ループ目では3d6の確率分布を作る
3d6の確率分布をGETだぜ！

計算量は $ O(n^2m) $ なので微妙に大きいですが、1000Dのような馬鹿でかい値を入れなければあまり問題にならないです。

精度が上がると何が嬉しいの？

精度が上がって一番嬉しいのは

めっちゃきれいな確率分布のグラフ(下図)が書ける！！！！！！！！

濃くなってる部分が信頼区間です。これがやりたかったんだよこれが、、、

さいごに

確率分布のグラフを見るぐらいの価値はあるはずなので覗いてやってください。