キャリー付き乗算

TUSBではキャリー付き乗算(multiply-with-carry, MWC)を用いて乱数の取得を行っている。

キャリー付き乗算 (英: multiply-with-carry, MWC) は、George Marsagliaにより開発された整数疑似乱数生成用の手法である。乱数種には2〜数千の値を必要とする。MWC の主な長所は、単純な整数演算からなっており非常に高速に動作するという点と、\(2^{60\dots 2000000}\) という非常に長周期であるという点である。
(キャリー付き乗算-Wikipediaより引用)

細かい理論については置いておき、TUSB内でどのように計算が行われているかというと、以下の式を繰り返し計算して乱数列を得ている。

\[x_n = \begin{cases} (ax_{n-1}+c_{n-1})\mod b & (n>1)\\ GameTime\mod b & (n=1) \end{cases}\\ c_n = \begin{cases} \lfloor \frac{ax_{n-1}+c_{n-1}}{b}\rfloor & (n>1)\\ GameTime\mod b & (n=1) \end{cases}\]

\(x_n\)が乱数列で、\(c_n\)がキャリーとなっている。
但し、

\[a = 31743\\ b = 65536\\ GameTime=(\text{#GameTimeのGlobal})\]

である。\(x_n\)を特定の値との剰余を求める事により、ある範囲の乱数を得る。

例えば0 ~ 9までの乱数\(R\)を得たいとき、\(x_{n-1},c_{n-1}\)から\(x_n\)を計算し、\(R=x_n\mod 10\)とすることで値\(R\)を取得する。

初項\(x_1,c_1\)

初項\(x_1,c_1\)はどちらも\(x_1,c_1 = GameTime\mod b\)である。

#GameTimeのGlobal(以降、#GameTime)はプレイヤーが初めてTUSBにログインしたとき(具体的にはチームに属していないプレイヤーが存在するとき)、その時のワールドが作られてからの時間を記録する。ソロプレイであれば、その時一回限りの更新であり、マルチプレイであれば、新しいプレイヤーがログインするたびに#GameTimeは更新される。

乱数の更新

乱数の更新は以下の2つの条件に該当するとき、行われる。

  1. プレイヤーが初めてTUSBにログインしたとき
  2. UpdateRandomが付与されたプレイヤーが存在するとき

乱数の使い方

TUSBの二次創作等で乱数を使用する方法について記す。

  1. プレイヤーのRndMWC(これが\(x_n\))の値をRandom等の一時変数に代入
  2. プレイヤーにUpdateRandomを付与
  3. 取得したい値の範囲(0 ~ 9など)に対応した値(0 ~ 9であれば10)でRandomとの剰余を計算する

乱数の特定について

ここでは、乱数が特定することが可能であるか考える。
まずTUSBでは前述したように乱数の更新のほとんどは、UpdateRandomによって行われる。これは数はあるが特定は容易である。次に、プレイヤーが初めてTUSBにログインしたときの#GameTimeの特定だが、ソロプレイでは可能であるかもしれない。しかし、マルチプレイでは2人目以降のプレイヤーの初ログイン時間の特定はコマンドを使わない限り不可能である。

結論としては、ソロプレイならば#GameTimeが一意に定まり、UpdateRandomを付与されるタイミングをすべて把握することができるのなら乱数の特定が可能となり、マルチプレイでははぼ不可能と考えられる。
まぁ、できても人力TAS?に近い状態なので現実的ではないだろう。

UpdateRandomが付与されるタイミング一覧

後々、書きます。

Tags: 解説