クイズゲームの出題テーブル
問題提示に関する問題提示
以前、クイズゲームを作った時のこと。
クイズゲームは問題を大量に溜めておいて、それを順番に提示していく仕組みを持っている。
この時、提示順にはどのような条件が必要か。
- ユーザーからはランダムに見えること（擬似乱数）
- 一度提示された問題は、他に提示できる問題がなくなるまで提示されない。
と、このようになる。
以前作った場合は、長い長い配列を用意して、そこに問題番号を全て格納し、ランダムに並べ替えたものを使った。つまりは出題テーブルである。使い切ったらもう一度作り直すだけだ。そのため、速度も重視したシャッフルプログラムを考えたりして、wikipediaに既に書いているような車輪の再生産などをしたりもした。
ただしこの方法は弱点もある。
- 問題数が可変（増やしていく計画があった）ので、配列だといずれ限界が来る。
- 単純に全部の順番を保持しているのだから、メモリーを食う。
そういう不安を抱えながらの実装であった。
線形合同法とポロロッカ問題
しばらくしてカルドセプトサーガのサイコロ問題が発生した折に、擬似乱数のことを調べまくり、少なくとも線形合同法については使い方は理解した。
そして線形合同法の性質が、この出題テーブルに似ていると気付いたのだ。
線形合同法は、初期値ないし前回出した数値を元に次の数値を計算する漸化式で、A・B・Mの三つの定数を持ち、それらが互いにいくつかの条件を満たした時、最大周期、つまり0からM-1までの数値が一回ずつ出てくるようになる。（そして最初に戻って同じテーブルが繰り返される）
これを使えば、初期値や一周のフラグなどの情報を追加することで、ほんのわずかなメモリー領域で長大な配列の順番を制御できることになる。
ただし、出題テーブルに線形合同法を採用すると、注意しないとポロロッカ問題（命名・俺。参考：ポロロッカといえば思い出す:地獄変00）が発生する可能性がある。
選択肢の表示順はランダムに入れ替えるので、問題を見なくても正解がクリックされていくようなことにはならないが、さすがに常に同じ順番で問題が提示されるのはまずい。
これの対処法は、A・B・Mの三つの定数を調整することだ。
特に問題数がオンラインによって常に増加していくならば、Mの値は常に変化し続けることになる。これならばあまり問題にはなるまい。
ただ、問題総数が増加しなくなった（サポートが終わったor飽きた）などの状況を考えると、AとBでも調整できるようにしなければならない。この時、Mに対しAとBが一意に決定されるとポロロッカへ一直線である。なので、AとBの決定に関しては他の乱数の手助けが必要になる。
AとBとMの関係
ここで必要になるのは、Mを与えると最大周期を実現するAとBが出てくるような関数であり、しかもこれには引数に乱数を与えるか、内部的に乱数を使うかどうかしなければならない。ここは真乱数でも使いたいところだが。
そこはクリアーしたとして、では最大周期を持つA・B・Mを割り出そうとすると、また別の数学的障壁が顔を出してくるのである。
Xn+1 = ( A * Xn + B ) mod M
M>A、M>B、A>0、B>0の時、
- BとMが互いに素である。
- A-1が、Mの持つ全ての素因数で割りきれる。
- Mが4の倍数である場合は、A-1も4の倍数である。
- MはXnよりも大きい。
条件4はどうでもいい（与える初期値に気をつければいいだけの話だし、仮に与える初期値がM以上だったとしても、式に含まれるmodによって別の正しい数値に収斂して問題にはならない。その初期値に戻らないだけ）が、他の3条件が問題だ。
そう、素因数分解である。素数を使うのである。ああ、なんと言う難関。その分かりにくさを以ってRSAとか暗号とかの基礎をなすあの素数なのである。
素因数分解、その前に素数。
与えられたMをまず素因数分解しなければならない。そのためには、素因数表記できるフォーマットを用意して、Mをその方式で記述しなければならない。
素数は数学的にはまだまだ未開の部分の多い分野で、ある数値が素数かどうかを調べることですら様々な方法や、それらに付随する諸々の問題点がある。
しかし私は数学者ではないので、それらの厳密な適用などは専門外だし興味もない（あることはあるが、新聞記事程度にしかない）。現実的な方法を模索する。
素因数分解をするには、2以上、元の値の平方根までの範囲にある素数で順番に割っていくことが基本的なアルゴリズムだ。逆に言えば、Mの値の大雑把な限界がわかっていればその平方根までの素数を用意すればこと足りると言うことになる。
現在、クイズマジックアカデミーは6万問とか言うのがググッたら概略で出てきたので、大雑把に10万問まで対応できれば、将来的な拡張にもなんとか対応できると言うことになる。ちなみに10万の平方根は316.22776601683793319988935444327...なので、2から316までの間の素数がわかれば、素因数分解するには充分と言うことに。
ちなみに、316以下の素数は、以下の通り65個ある。※エラトステネスの篩で計算した。
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313
これだけならば、もうソースにベタ書きしてもいいくらいだろう。
これで準備は整った。実際にMからAとBを計算してみる。
- Mを素因数分解する。
- 先にA-1を決める。A-1はMの素因数を1乗ずつ掛け合わせたものとする。
- Mが素因数2を2乗以上持つならば、A-1にもさらに2を掛ける。
- ここで、ランダムにAにMの持つ素因数を掛けてもよい。Mを超えないように注意。
- 1を足してAを確定させるが、もしAがM以上になってしまったら（Mが素数の1乗のみで構成されている場合そうなる。素因数2については少々例外があるが）、Mを1増やして1に戻る。
- Bを決める。BとMは互いに素なので、BはMが使っていない素因数をランダムに選んで構成される。この時、BがM以上にならないように気をつけるか、決めなおす。
これで、ABMが決定する。場合によってはMが最初に指定した値よりも増えていることがあるが、そこは問題選択ルーチンの方で、存在しない問題番号を指定されたらスルーして次の問題を取得するような柔軟さを与えて対処したい。
