# New スーパーマリオブラザーズ (NDS) の乱数調整に係る雑記

## はじめに
この記事は[Pokémon Past Generation Advent Calendar 2023](https://adventar.org/calendars/8746)の4日目の記事です.

こんにちは. [ニアト](https://twitter.com/21i10r29)と申します.

今年もAdvent Calendarの季節がやってまいりました. 寄稿させていただくのは今年で三年目なのですが, 今年の概要を見ると少し毛色が異なるようですね.

> 過去作及び最新世代(ただしここでの最新世代は3世代を指す)のポケモンについて記事を書くAdvent Calendarです.
Pokémon RNG Advent Calendar の後継を勝手に自称しており, **ポケモンに関係無い乱数調整の話題も含まれます.**

ということで(?), 今年はポケモンに関係ない乱数調整のお話をしようと思います.

肝心のゲームはというと... かの国民的アクションゲームこと, New スーパーマリオブラザーズです！

えっ, マリオ?

## New スーパーマリオブラザーズにおけるランダム要素
そもそもマリオに乱数調整が関わるようなランダム要素なんてあったっけ? と思われる方も多いでしょうが, ちゃんとあります.

分かりやすいところで言うと, 以下の二つ[^RTA]でしょうか?

| ||
|:--------------------------------------------------:|:--------------------------------------------------:
| 赤パタブロックから取得できるアイテム | キノピオハウスにおける配牌のシャッフル|

[^RTA]:余談ではありますが, new スーパーマリオブラザーズにおけるRTAでは, 赤パタブロックのアイテムを制御するための乱数調整が実用化されています. もし興味のある方はAndreMH氏らによる[解説](https://docs.google.com/document/d/1-KzdFI3CapkBX2GVNRXRtTUjwuqeSBCBNQPmH-yl03c/edit)をご覧ください.

上記以外だと, ミニゲームで遊べる幾つかのゲームにランダム要素があります. 私が小さい頃によく遊んでいた"ルイージのえあわせポーカー"もその一つです.


ゲーム内容はいたってシンプルで, 名前の通り同じ絵柄のカードを集めて役を作ることで勝負します. 勝てば掛けたコインとその役の強さに応じた倍率で掛け金が返ってきます.

役に関してはストレートとその関連役を除けば一般的なポーカーとほぼ同様です. 特に, 最上位の役である"5カード"は普通に遊んでいても中々出てきません.

**では, 普通ではない遊び方ではどうでしょうか?**

## 準備
普通ではない遊び方をするために幾つか準備を進めていきましょう.

乱数調整を行うためは, まず初めにゲームで利用されている乱数生成アルゴリズムについて知る必要があります.

重要なのは"乱数消費契機"と"乱数更新式"と"初期Seed生成方法"の3つです. 次節よりそれぞれ確認します.

### 乱数消費契機
プレイ中の乱数消費契機は次のようになっている.

||| | ||
|:--------:|:--------:|:--------:|:--------:|:--------:|
|ミニゲーム選択(初期Seed決定)| プレイモード選択(停止)| ミニゲーム一覧(60 [adv/s]) | あそびかた説明(停止) | ゲーム開始(ゲーム依存) |

タイトル画面で"ミニゲーム"を選択した時点で初期Seedが決定する. その後のミニゲーム一覧画面と実際のゲーム開始後を除くと乱数更新契機は存在しない.

### 乱数更新式
NSMBにおける乱数更新式はLCG(線形合同法)を改変したものになっている.

前回の出力結果に対して, 符号なし64bit整数としてLCGの漸化式計算を行った後, その上位32bitと下位32bitの和を符号なし32bit整数として出力する.

C# による実装例；

public static uint NextSeed(uint seed)
{
    ulong seed64 = seed;
    seed64 = seed64 * 0x19660DUL + 0x3C6EF35FUL;
    seed64 = ((seed64 >> 32) + seed64) & 0xFFFFFFFFUL;
    return (uint)seed64;
}

### 乱数更新式の脆弱性
実は, 先駆者の調査によって乱数の更新式には脆弱性が存在しており, `0x443B4723`が不動点となることが明らかになっています[^vulnerability].

Q. 不動点ってなあに?
A. 凄くざっくり説明すると何回同じ操作を繰り返しても同じ値に戻ってくるような値のことです.

`NextSeed(0x443B4723)`を実際に計算すると,

ulong seed64 = seed;
// -> 0x443B4723
seed64 = seed64 * 0x19660DUL + 0x3C6EF35FUL;
// -> 0x443B4723 * 0x19660D + 0x3C6EF35F = 0x6C4FD_44348226
seed64 = ((seed64 >> 32) + seed64) & 0xFFFFFFFFUL; 
// => (0x6C4FD + 0x44348226) & 0xFFFFFFFF = 0x443B4723
return (uint)seed64;

となり, 実際に`0x443B4723`に戻ってくることが分かります.

......サラッと書いていますがトンデモないことが起きていることにお気づきでしょうか. つまり, 上記の説明は乱数生成器がある値を出力するとそれ以降はずっと同じ値を出力すると述べているのです.

同じ乱数値が出力され続けるのであれば, "ルイージのえあわせポーカー"で配られるカードも同じ絵柄ばかりになりそうですね?

この脆弱性を突くために, 初期Seedの生成方法について詳しく見ていきましょう.

### 初期Seed生成方法
NSMBにおける初期Seedの決定にはDSの内部状態と暗号学的ハッシュ関数が用いられている.

具体的には, `OS_GetLowEntropyData` 関数によって取得される$4$byte $\times 8=32$byteからなるDSの内部状態に関するメッセージに対して, 暗号学的ハッシュ関数SHA-1を適用して$32$bit $\times5 = 160$bitのハッシュダイジェストを取得し, xorによる総和を取ったものを初期Seedとしている.

初期Seedの決定タイミングはゲーム起動時またはメニュー画面の"ミニゲーム"を選択した約$1$秒後.

C# による疑似コード;

public static uint GenerateInitSeed()
{
    SHA1 sha1 = SHA1.Create();
    uint[] data = OS_GetLowEntropyData();
    data[1] = data[1] ^ Mode; //Maingame:Mode=0x00000000, Minigame:Mode=0x00000001
    byte[] msg = MemoryMershal.Cast<uint,byte>(data.AsSpan()).ToArray();
    byte[] rawdigest = sha1.ComputeHash(msg);
    uint[] digest = MemoryMarshal.Cast<byte, uint>(rawdigest.AsSpan()).ToArray();
    uint initseed = digest[0] ^ digest[1] ^ digest[2] ^ digest[3] ^ digest[4];
}

public static uint[] OS_GetLowEntropyData()
{
    uint[] data = new uint[8];
    data[0] = Timer0 << 16 | VCount;
    data[1] = MAC&0xFFFF;
    data[2] = (MAC>>16) ^ GxStat ^ VFrame;
    data[3] = yy | (mm << 8) | (dd << 16) | (nn << 24);
    data[4] = hh | (mi << 8) | (ss << 16);
    data[5] = Microphone;
    data[6] = TouchPannel;
    data[7] = Input ^ 0x2FFF;
    
    return data;
}

:::spoiler 疑似コード内の各パラメータについて(折りたたみ)
- `Timer0` [@]
CPUタイマーの値を参照?
- `VCount` [@]
現在描画処理を行っている走査線の位置.
- `MAC`
DS本体のwifiモジュールのMACアドレス.
- `GxStat`
GPU関係のレジスタの値を参照? 常に一定の値(ミニゲームの場合は`0x86000000`)を取る.
- `VFrame` [@]
不明. ほぼ一定の値を取る.
- `yy`, `mm`, `dd`, `nn`
西暦下二桁, 月, 日, 曜日 をBCD表記に改めたもの.
- `hh`, `mi`, `ss`
時, 分, 秒 をBCD表記に改めたもの.[^hour]
- `Microphone`
マイク音声の値? 常に一定の値(`0x00000000`)を取る.
- `TouchPanel`
タッチパネルの検知位置? 常に一定の値(`0x00000000`)を取る.
- `Input`
現在入力中のキー状態をビットフラグ[^keyinput]で表したもの.
:::

:::spoiler ちょっとだけポケモン要素のある余談
`OS_GetLowEntropyData` 関数は, 実はポケモン第五世代における初期Seed決定にも用いられています.

但し,そのまま用いられているわけではなく, 新たに160bitの独自メッセージ(所謂`nazo`値)を先頭に付与したものをハッシュ計算用のメッセージとしているようです.

また, SHA-1計算後の処理も微妙に異なり, 得られたダイジェストの先頭64bitないし32bitを初期Seedとして利用しています.
:::

[^hour]: note: 初代/liteを用いていて且つ起動時刻が12時から23時の場合, `hh`に`0x40`を加算します. (BCD変換後)
[^keyinput]: note: ビットフラグの詳細はさき氏のブログ(https://xxsakixx.com/archives/53922673.html)にて解説されています.

### 初期Seed生成方法の脆弱性
初期Seed生成方法が分かったのは良いのですが, 幾つかのパラメータが明らかになっていません. 具体的な値が未知となっている`Timer0`, `VCount`, `VFrame`を逆算する必要があります.

実は, 初期Seedの決定方法はポケモン第五世代における初期Seed決定方法と非常に類似しており, 起動日時(`yy`, `mm`, `dd`, `nn`, `hh`, `mi`, `ss`)を固定すると同一のSeedが得られることが分かっています.

この性質を利用することでパラメータを逆算しましょう.

#### 初期Seedパラメータの特定
初期Seedパラメータを特定するためには, ゲームプレイ中のある時点でのSeedを特定する必要があります. Seedの特定にはミニゲーム "ルイージ・カルロ" が利用可能です.

(ゲーム内容はバッサリ割愛します)
| |
|:--------:|
| ルイージ・カルロ |

重要なのは, F:フラワー, K:スーパーキノコ, S:スター, C:クラウド, M:マリオ, L:ルイージの6種カードが6枚ずつの計36枚デッキが構成されること, ゲーム開始時にデッキが"ランダム"にシャッフルされたうえで上図のように配列されることです.

当然, このシャッフルを行う処理にも上述した乱数生成アルゴリズムが用いられています. 従って, 高々$2^{32}$通りの全探索を行うこと[^bruteforce]で, この配牌を出力しうるルイージカルロ開始時点のSeed(以後"生成Seed"と呼称します)が特定出来ます.

::: spoiler 参考: ルイージ・カルロにおけるデッキシャッフルアルゴリズム

ルイージ・カルロにおけるデッキシャッフルのエミュレートを行うコード(Python)を示す.

def emulate_carlo(rng:NSMBRandom):
    _rng = rng.deepcopy()
    F = ["F"]*6 #フラワー
    K = ["K"]*6 #スーパーキノコ
    S = ["S"]*6 #スター
    C = ["C"]*6 #クラウド
    M = ["M"]*6 #マリオ
    L = ["L"]*6 #ルイージ

    type2int = {}
    type2int["F"] = 0
    type2int["K"] = 1
    type2int["S"] = 2
    type2int["C"] = 3
    type2int["M"] = 4
    type2int["L"] = 5

    deck = F + K + S + C + M + L
    print(*deck,sep="")
    result = []
    result_int = []
    raw_rands = []
    for k in range(len(deck),0,-1):
        r = _rng.next_int(k)
        raw_rands.append(r)
        card = deck.pop(r)
        result.append(card)
        result_int.append(type2int[card])
    print(*result,sep="")
    print(raw_rands)
    print(result_int)

    for i in range(4):
        print(*result[5*i:5*(i+1)],sep="")
        
class NSMBRandom():
    def __init__(self, seed):
        self.seed = seed

    def next(self):
        r = self.seed
        r = r * 0x19660D + 0x3C6EF35F
        r = ((r >> 32) + r) & 0xFFFFFFFF
        self.seed = r
        return self.seed

    def next_int(self,n):
        r = self.next() >> 19
        t = (n * (r & 0xFFF)) >> 12
        return t

    def deepcopy(self):
        return NSMBRandom(self.seed)

:::
<p></p>

生成Seedの特定方法さえ明らかになれば, 後は以下の手順を踏むことで`Timer0`, `VCount`, `VFrame`の特定が可能となります.

1. タイミング(`yy`, `mm`, `dd`, `nn`, `hh`, `mi`, `ss`)を固定して"ミニゲーム"を選択する
2. "ミニゲーム"選択からルイージ・カルロの選択までを手早く操作し, ルイージ・カルロをプレイする
3. 得られた盤面から生成Seedを特定する
4. `Timer0`, `VCount`, `VFrame`の取りうる範囲を全探索して初期Seedを列挙する
5. 列挙した初期Seedの候補に対して, 特定した生成Seedに妥当な消費数で到達するものを抽出する
6. 1-5を複数回実施し, `Timer0`, `VCount`, `VFrame`の候補を絞り込む

なお, 筆者の環境(DSLite, ダブルスロットあり)における特定結果は以下の通りになりました.

| パラメータ | 値 |
|:----------:|:-------:|
| Timer0 | 0x00FE |
| VCount | 0x00D5 |
| VFrame | 0x0007 |

#### 不動点となるような初期Seedの全探索
初期Seedの生成に必要なパラメータさえ求められれば, 後は初期Seedが不動点(`0x443B4723`)となるような起動日時を全探索するだけです. [^datetime]

普通に計算する場合はSHA-1の計算部分が計算時間のボトルネックとなりますが, [1日目の記事](https://hackmd.io/@yatsuna827/r1K8v7ZEp)でも紹介されていたSIMDや並列計算による高速化アプローチが適用可能です.

[^datetime]:筆者の環境では, 2037年03月15日 19時20分38秒/2098年07月07日 11時58分01秒の2件がヒットしました.

## 実践
随分と長い長い遠回りをしていましたが, いよいよ普通ではない遊び方をするときがやってきました.

初期Seedが不動点となるような時刻でミニゲームを開始し, "ルイージのえあわせポーカー"を選択すると...

{%youtube bL1BnNhPY2E %}

最初に配られる自分の手札が`|L|F|F|F|F|`の4カードとなり`|L|`を交換することで`|F|F|F|F|F|`の5カードとなるゲームで固定されるようになります.

相手の手札は 交換しても5カードとはならず, `|L|L|L|L|M|`の4カードで固定されるため, ミニゲームを終了しない限り常に勝ち続けることになります.

やったね!

## まとめ
という訳で, 今回はNewスーパーマリオブラザーズの乱数生成アルゴリズムの脆弱性を利用した"ルイージのえあわせポーカー"の必勝法を紹介しました.

他にも深堀り出来そうな話題はいくつかあるのですが, やはり今年もそこに至る前に力尽きてしまいました...

とはいえ, アドベントカレンダー自体はまだまだ続きます. 引き続き色々な人の記事をお楽しみいただければ, 一参加者としても幸いです.

5日目はサイファー氏による"VC青ファイヤーの状況再現(色違い/めざ草/3FFF)"の記事となります. お楽しみに!!

## 謝辞
私がNSMBの乱数処理の調査に取り組むきっかけを与えてくださった [マジあり](https://twitter.com/maziari1105)氏には, 初期Seed決定処理や乱数調整手法の確立に当たって貴重なご意見を頂きました.

この場をお借りして御礼申し上げます.

[^vulnerability]:詳細は調査記事[(One Number Repeated Forever: RNG in NSMB)](https://roadrunnerwmc.github.io/blog/2020/05/08/nsmb-rng.html#fn:interesting_inputs)を参照してください.

[^bruteforce]:実際は乱数更新式の性質上, その1/5で済みます.