1
0

More than 1 year has passed since last update.

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

Posted at

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

▼ part1 ▼

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

完成品どーん (3回目)

part1のあらすじ

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

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

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

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

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

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

chart.png

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

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

どうやって求めるのさ

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

というのは半分冗談ですが、私には思いつかなかったので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になります。

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

image.png

1ループ目

image.png

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

2ループ目

image.png

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

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

chart.png

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

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

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

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

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

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

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

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

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

image.png

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

さいごに

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

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0