2005/03/09 (水)
■ ドラクエ8：カジノのビンゴゲーム当たる確率計算(前編) 
誰か既に計算しているだろうけど、暇潰しに計算していたので一応アップ。
前提
- 5x5の25マス中にボールを10個までランダムで入れ、縦横斜め5個一直線に並べばビンゴ(当たり)。
- 中央部の一つは最初から選択されているものと見なす。実際に使用されるマスは24個。
- ゲーム中のマスの番号はランダムだが、確率を求める際には番号は影響しない。
総組み合わせ数
24個マスがあり、x個ボールを選択してセットした際、その「置き方」の総数を求める。
数学で順列・組み合わせを学んだのはいつだろうか。この場合、どのような順番でマスを埋めるかは重要ではなく、置き方の総数を求めたいので、「組み合わせ」を使って求める。「nCr」(n=総数、r=抜き取り数)で、公式はn!/(r!×(n-r)!)だが、まぁ表計算ソフトか何かを使った方が早いだろう。EXCELだとCOMBINワークシート関数を使用する。
- 24個の空きエリアに、 1個入れる置き方→24C1 = 24パターン。
- 24個の空きエリアに、 2個入れる置き方→24C2 = 276パターン。
- 24個の空きエリアに、 3個入れる置き方→24C3 = 2024パターン。
- 24個の空きエリアに、 4個入れる置き方→24C4 = 10626パターン。
- 24個の空きエリアに、 5個入れる置き方→24C5 = 42504パターン。
- 24個の空きエリアに、 6個入れる置き方→24C6 = 134596パターン。
- 24個の空きエリアに、 7個入れる置き方→24C7 = 346104パターン。
- 24個の空きエリアに、 8個入れる置き方→24C8 = 735471パターン。
- 24個の空きエリアに、 9個入れる置き方→24C9 = 1307504パターン。
- 24個の空きエリアに、10個入れる置き方→24C10= 1961256パターン。
当たり総数
ここで当たりの総数を求めれば、「x個置いたとき当たるパターン数/x個の置き方のパターン数」で割合が算出できる。
- 1～3個置いた場合は当たらないため、条件を除外する。
- 4個置いた場合、当たる可能性のある置き方は、「(1)3段目横一段並んだ場合」「(2)3列目縦一列並んだ場合」「(3)左上から右下まで斜めに並んだ場合」「(4)右上から左下まで斜めに並んだ場合」の4通りとなる。当たる確率は4/10626→0.0037%程度、となる。
- 5個置いた場合、当たる可能性のある置き方は、横に並んだ場合5パターン、縦に並んだ場合5パターン、斜めに並んだ場合2パターンの、計12パターンである。……と書いたら信じるだろうか。これはパターン数ではなく当たる可能性のあるラインの数であって、12は間違い。下記の通り、計88パターン存在する。
当たる確率は 88/42504 →0.21%程度となる。また、この「5個置いた場合」は5個を順不同に置くため、4個目で当たっている場合でも5個目を置いた、と言う想定になる。「4個目か5個目を置いた時点で当たる可能性が0.21%」になる。
当たるパターンの数式化
6個以上置いた場合、そのパターン数は莫大になり、パターンを想定して数える事は無理に近い。何らかの数式に置き換え計算する必要が出てくる。
- 6個ボールを置いた際、想定できることは
と考えることができる。元に戻って5個の場合、また6・7個の場合もそれぞれ考えを整理してみると
- 5個置いた場合
- 5個で当たるライン×8 × 余り0個を19箇所の内0箇所に
- 4個で当たるライン×4 × 余り1個を20箇所の内1箇所に
- 6個置いた場合
- 5個で当たるライン×8 × 余り1個を19箇所の内1箇所に
- 4個で当たるライン×4 × 余り2個を20箇所の内2箇所に
- 7個置いた場合
- 5個で当たるライン×8 × 余り2個を19箇所の内2箇所に
- 4個で当たるライン×4 × 余り3個を20箇所の内3箇所に
となる。
n個置いた場合、当たりパターン数は[19C(n-5)×8 + 20C(n-4)×4] となる。(厳密には8個以上置くと2ライン当たるパターンが出てきて、ケースとしては被るので誤差が発生する。とりあえずは無視)
計算結果(誤差あり)
| 置いた数 | 総パターン数 | 当たりパターン | 割合 | ||
|---|---|---|---|---|---|
| 19C(n-5)×8 | 20C(n-4)×4 | 当たりパターン数計 | 当たりパターン/総パターン | ||
| 4 | 10626 | - | 4 | 4 | 0.000376435 |
| 5 | 42504 | 8 | 80 | 88 | 0.002070393 |
| 6 | 134596 | 152 | 760 | 912 | 0.006775833 |
| 7 | 346104 | 1368 | 4560 | 5928 | 0.0171278 |
| 8 | 735471 | 7752 | 19380 | 27132 | 0.036890646 |
| 9 | 1307504 | 31008 | 62016 | 93024 | 0.071146245 |
| 10 | 1961256 | 93024 | 155040 | 248064 | 0.126482213 |
■ ドラクエ8：カジノのビンゴゲーム当たる確率計算(後編)
プログラムを使って総当たりしてみる
今時のCPUは早いので、総当たりしてもそこそこの時間で結果が出せる。すべてのパターンについてチェックさせ、割合が正しいか確認してみる。前提
- 24個のマスを埋めるため、24ビット以上のデータ型でビットをフラグとして扱う。
- 当たりの結果を算出するのは大変なので、12ライン分の当たるパターンはマスクパターンを用意し、そのパターンに合うように結果がセットされているか判定する。
| 1 | 6 | 11 | 15 | 20 |
| 2 | 7 | 12 | 16 | 21 |
| 3 | 8 | x | 17 | 22 |
| 4 | 9 | 13 | 18 | 23 |
| 5 | 10 | 14 | 19 | 24 |
- 1,2,3,4,5
- 6,7,8,9,10
- 11,12,13,14
- 15,16,17,18,19
- 20,21,22,23,24
- 1,6,11,15,20
- 2,7,12,16,21
- 3,8,17,22
- 4,9,13,18,23
- 5,10,14,19,24
- 1,7,18,24
- 5,9,16,20
| ライン | ビットパターン | 16進数 | |||||
|---|---|---|---|---|---|---|---|
| 1 | 0000 | 0000 | 0000 | 0000 | 0001 | 1111 | 0x00001F |
| 2 | 0000 | 0000 | 0000 | 0011 | 1110 | 0000 | 0x0003E0 |
| 3 | 0000 | 0000 | 0011 | 1100 | 0000 | 0000 | 0x003C00 |
| 4 | 0000 | 0111 | 1100 | 0000 | 0000 | 0000 | 0x07C000 |
| 5 | 1111 | 1000 | 0000 | 0000 | 0000 | 0000 | 0xF80000 |
| 6 | 0000 | 1000 | 0100 | 0100 | 0010 | 0001 | 0x084421 |
| 7 | 0001 | 0000 | 1000 | 1000 | 0100 | 0010 | 0x108842 |
| 8 | 0010 | 0001 | 0000 | 0000 | 1000 | 0100 | 0x210084 |
| 9 | 0100 | 0010 | 0001 | 0001 | 0000 | 1000 | 0x421108 |
| 10 | 1000 | 0100 | 0010 | 0010 | 0001 | 0000 | 0x842210 |
| 11 | 1000 | 0010 | 0000 | 0000 | 0100 | 0001 | 0x820041 |
| 12 | 0000 | 1000 | 1000 | 0001 | 0001 | 0000 | 0x088110 |
処理概要
- 4～10個置いたとき、それぞれの置くパターン数・当たるパターン数・割合を求める
- n個置いた場合の、置くパターン数を求める。2^24中の数字からn個フラグが立っている数字をピックアップするれば、置くパターン数が求まる。
- ピックアップした数字が、当たりラインのビットパターンを含むかどうか調べる。含んでいれば、当たりのパターン数としてカウントする。
プログラム(Java)
メソッド名は悩んだが適当に付けてしまった。Javaプログラムだが、C++/C#のプログラマでも読めるとは思う。内容はいい加減。ビット操作があるので、そういったことをやったこと無い人は難しいかもしれない。public class Bingo { static final int SIZE=24; //マスのサイズ static final int MAX_NUM = (int)Math.pow(2,SIZE); // 24ビットのパターン数 //当たりラインのビットパターン static final int[] LINE_LIST = new int[12]; static { LINE_LIST[ 0] =0x00001F; // 1,2,3,4,5 LINE_LIST[ 1] =0x0003E0; // 6,7,8,9,10 LINE_LIST[ 2] =0x003C00; // 11,12,13,14 LINE_LIST[ 3] =0x07C000; // 15,16,17,18,19 LINE_LIST[ 4] =0xF80000; // 20,21,22,23,24 LINE_LIST[ 5] =0x084421; // 1,6,11,15,20 LINE_LIST[ 6] =0x108842; // 2,7,12,16,21 LINE_LIST[ 7] =0x210084; // 3,8,17,22 LINE_LIST[ 8] =0x421108; // 4,9,13,18,23 LINE_LIST[ 9] =0x842210; // 5,10,14,19,24 LINE_LIST[10] =0x820041; // 1,7,18,24 LINE_LIST[11] =0x088110; // 5,9,16,20 } public static void main(String[] args) { System.out.println("ボール数, 置き方パターン数, 当たりパターン数, 割合%"); int select; // ボールを置く個数 for(select=4; select<=10; select++) { findSelection(select); //該当個数置いた場合のパターン数を検索 } } public static void findSelection(int select) { int count1=0; // 組み合わせ数 int count2=0; // 当たり数 for (int i=0; i<MAX_NUM; i++) { if (isCombin(i,select)) {//組み合わせのパターンか調べる count1++; /* 必要であればビットパターンを表示可能なように編集 String s = "000000000000000000000000" +Integer.toBinaryString(i); s = s.substring(s.length()-SIZE); */ //当たりラインのビットパターンに一致する部分があるか調べる for(int j=0;j<LINE_LIST.length; j++) { if((i&LINE_LIST[j]) == LINE_LIST[j]) { count2++; /* 必要であればビットパターンを以下略 s = s+",bingo!"; */ break; /*breakをコメントにすると計算結果(誤差あり)と同じになる*/ } } /* 必要であればビットパターンを出力する →ログにでも s を出力するなりなんなり */ } } double per= count2 * 100.0 / count1; System.out.println(select + ", " + count1 + ", " + count2 + ", " + per); } // 数値内のビット数がn個であるか調べる // n個であれば置くパターンの内の一つと考えられる public static boolean isCombin(int num,int n) { int cnt=0; for(int i=0; i<SIZE; i++) { cnt = cnt + (num & 1); num>>=1; } return (cnt==n); } }
実行結果
c:\>javac Bingo.java c:\>java Bingo ボール数, 置き方パターン数, 当たりパターン数, 割合% 4, 10626, 4, 0.03764351590438547 5, 42504, 88, 0.2070393374741201 6, 134596, 912, 0.6775832862789385 7, 346104, 5928, 1.7127799736495388 8, 735471, 27102, 3.684985539878527 9, 1307504, 92520, 7.076077778729549 10, 1961256, 244092, 12.445698062873994前編でも述べたとおり、8個以上置いた場合の当たりパターン数が異なってくる。それでも結果はさほど変わらず、12%程度は当たる、と言う結果に落ち着く。
トラックバック - http://dorakue.g.hatena.ne.jp/toinami/20050309
2005/02/19 (土)
トラックバック - http://dorakue.g.hatena.ne.jp/toinami/20050219