More than 1 year has passed since last update.

唐突にダイスの期待値を計算するツールが欲しくなったから1週間で作ってリリースした part3

Posted at 2022-08-16

この記事はpart3です！！part1の内容が前提になってるのでpart1を読んでからの方が楽しめると思います🥰

▼ part1 ▼

※プロダクト開発っぽいタイトルですが、この記事の内容はかなりアルゴリズムっぽいです。若干エッセーっぽいのは許して。

完成品どーん (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]}`);
}