第七世代TSV特定ツールを実装した話+@

この記事はPokémon Past Generation Advent Calendar 2022の2日目の記事です.

こんにちは. ニアトと申します.

今年もアドベントカレンダーの季節がやってまいりました.

本来は修論を書き連ねなければならない時期なのですが, 現実逃避もかねて どうにか時間を作って寄稿させていただくことになりました.

今回は表題にもあるとおり, 今年の夏頃に実装した第七世代TSV特定ツール関連の話を書くことにします.

Q. そもそもTSVとは

TSV = "Trainer Shiny Value"の頭字語

…という説明だけだといくらなんでも不足なのでもう少し説明すると, プレイヤーが持つROMごとに固有な値^[1]から計算できる値のことです.

第六世代, 第七世代において, 出現するポケモンが色違いになる条件は, 同様にポケモンが持つ個体ごとに固有な値^[2]から計算できる値である, PSV(="Pokemon Shiny Value")とTSVが一致することと同値です.

これらの世代における乱数調整ツールの多くは, TSVを参照して色違いの判定を行うため, いわゆる色乱数を行うにあたって重要な値となっています.

Q. なんで今さら第七世代のツールを?

TSVを特定するツールというのは, ポケモンSM/USUMの発売当初からろいしん氏によって公開されていました^[3].

諸事情により公開が停止された後も, ぼんじり氏がDiscordのポケモン乱数調整サーバー(いわゆる乱数鯖)にて同等の機能を有するBotを設置したことでその役割を引き継いでいます.

しかしながら, Discord上で運用されるBotである以上,

• Bot利用時にインターネット環境を要する
• Botがオフラインの場合（Botが稼働しているサーバーが停止している場合)も使えない
• そもそも乱数鯖に参加していないと使えない

といった懸念点があり, 一つ目の問題はまだしも, 二つ目三つ目の問題に関しては代替ツールが期待される強い動機になりうるだろうと考え, ローカル環境でも実行可能なTSV特定ツールの独自開発に着手することにしました.

特定アルゴリズムに関して

ツールのアルゴリズムはろいしん氏と同一のもの^[3:1]を用いています. ここでは, そのアルゴリズムを説明します.

TSV(の元となる値)^[4]の決定タイミングはトレーナー名の決定時で, トレーナーIDと共に決定します.

SMおよびUSUMでは, TSVの決定や個体値の決定といった事象を決定するための乱数生成アルゴリズムとしてSFMTが用いられています^[5]. 初期seedがゲーム起動時に決定された後は, ゲームの再起動以外でリセットされることはありません.

従って, 初回ゲーム起動時の初期seedさえ特定できれば, そこからTSVの逆算も可能となります.

初期seedの逆算にあたっては, g7tid(6ケタのトレーナーID), 受け取った御三家の個体値及び性格の情報が利用できます.

g7tid決定までの消費数がほぼ一定^[6]であることを利用し, g7tidが一致するような初期seedに対して, 受け取った御三家の個体値及び 性格の組み合わせが一定の消費範囲内に生成されるかを探索することで, 起動時の初期seedを得られます.

このとき, 探索にかかる計算ステップ数は

初期seed候補の探索(

$2^{32}$)

$+$ 初期seedの候補数(

$4.3\times {10}^3$)

$\times$消費数の探索範囲(~

${10}^5$)

$\approx {10}^9$(step)

程度と見積もることが出来, この程度であれば現実的な時間で計算可能です.

実装にあたって取り組んだこと

ツールの実装はC#によって行ったのですが, 実のところ私が独自に取り組んだことはあまり多くはありません.

先述の通り, アルゴリズム自体は既存のものを用いていますし, 乱数生成処理周りに関しても夜綱氏が非常に強力なライブラリを公開されているため, そちらを利用することでサクッと実装ができました.

しいて言えば, ツールのGUI化によって先駆者との差別化を図ってみたり, SFMTの実装をちゃんとSIMD-orientedにするためにライブラリのコードを弄ってみたりしたくらいです. そのあたりの話もきちんとまとめておきたいのですが時間的/体力的都合に割愛します. 折角なのでちょっとだけ書き記しておきます.

SFMTのお話

先ほど紹介した, SFMTという乱数生成アルゴリズムは, SIMD-oriented Fast Mersenne Twister の頭字語となっています.

名が体を表す通り, このアルゴリズムはSIMD^[7]によって内部状態の更新を高速化出来るように改良されたメルセンヌツイスタなのですが, ライブラリの実装がこれに対応していなかったため, 現著者の実装を見様見真似で移植してみることにしました.

元の実装

private void GenerateRandAll()
{
    uint[] p = this.stateVector;

    const int cMEXP = 19937;
    const int cPOS1 = 122;
    const uint cMSK1 = 0xdfffffefU;
    const uint cMSK2 = 0xddfecb7fU;
    const uint cMSK3 = 0xbffaffffU;
    const uint cMSK4 = 0xbffffff6U;
    const int cSL1 = 18;
    const int cSR1 = 11;
    const int cN = cMEXP / 128 + 1;
    const int cN32 = cN * 4;

    int a = 0;
    int b = cPOS1 * 4;
    int c = (cN - 2) * 4;
    int d = (cN - 1) * 4;
    do
    {
        p[a + 3] = p[a + 3] ^ (p[a + 3] << 8) ^ (p[a + 2] >> 24) ^ (p[c + 3] >> 8) ^ ((p[b + 3] >> cSR1) & cMSK4) ^ (p[d + 3] << cSL1);
        p[a + 2] = p[a + 2] ^ (p[a + 2] << 8) ^ (p[a + 1] >> 24) ^ (p[c + 3] << 24) ^ (p[c + 2] >> 8) ^ ((p[b + 2] >> cSR1) & cMSK3) ^ (p[d + 2] << cSL1);
        p[a + 1] = p[a + 1] ^ (p[a + 1] << 8) ^ (p[a + 0] >> 24) ^ (p[c + 2] << 24) ^ (p[c + 1] >> 8) ^ ((p[b + 1] >> cSR1) & cMSK2) ^ (p[d + 1] << cSL1);
        p[a + 0] = p[a + 0] ^ (p[a + 0] << 8) ^ (p[c + 1] << 24) ^ (p[c + 0] >> 8) ^ ((p[b + 0] >> cSR1) & cMSK1) ^ (p[d + 0] << cSL1);
        c = d; d = a; a += 4; b += 4;
        if (b >= cN32) b = 0;
    } while (a < cN32);
}

SIMD対応版

using static System.Runtime.Intrinsics.X86.Sse2;
using System.Runtime.Intrinsics;

private unsafe void GenerateRandAll()
{

    fixed (uint* pPtr = this.stateVector)
    {
        var r1 = LoadVector128(pPtr+4*(N-2));
        var r2 = LoadVector128(pPtr+4*(N-1));
        int i=0;
        for (; i < N - POS1; i++)
        {
            Store(pPtr + 4*i, mm_recursion(LoadVector128(pPtr + 4 * i), LoadVector128(pPtr + 4 * (i + POS1)), r1, r2));
            r1 = r2;
            r2 = LoadVector128(pPtr + 4*i);
        }
        for (; i < N; i++)
        {
            Store(pPtr + 4*i, mm_recursion(LoadVector128(pPtr + 4*i), LoadVector128(pPtr + 4*(i + POS1 - N)), r1, r2));
            r1 = r2;
            r2 = LoadVector128(pPtr + 4*i);
        }
    } ;
    ;

}

public readonly uint[] MSK = new uint[] { MSK1, MSK2, MSK3, MSK4 };
private unsafe Vector128<uint> mm_recursion(Vector128<uint> a, Vector128<uint> b, Vector128<uint> c, Vector128<uint> d)
{
    Vector128<uint> v, x, y, z, r;

    fixed (uint* pMSK = MSK)
    {
        var MASK = LoadVector128(pMSK);

        y = ShiftRightLogical(b, SR1);
        z = ShiftRightLogical128BitLane(c, SR2);
        v = ShiftLeftLogical(d, SL1);
        z = Xor(z, a);
        z = Xor(z, v);
        x = ShiftLeftLogical128BitLane(a, SL2);
        y = And(y, MASK);
        z = Xor(z, x);
        r = Xor(z, y);
    }
    return r;

}

(本当は移植にあたってC#で拡張命令を呼び出す方法とかを解説したかったのですが力尽きました)

過去の実行結果のスクショによれば, SIMDに対応したことによっておおよそ半分以下まで高速化できたようです.

(上:SIMD対応版/下:SIMD非対応版)

Q.で, 肝心のツールは?

こちらになります.

おわりに

と, いう訳で第七世代TSVツールを実装してみたよ, というお話でした.

他にも深堀り出来そうな話題(SIMD周りの話や, 初期seed候補検索apiを実装するためにAWSやRustと格闘した話など)はいくつかあるのですが, そこに至る前に力尽きてしまいました.

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

3日目はハンター氏による"USBGeckoノススメ"の記事となります. なんだかエキゾチックな香りがするタイトルですが, さてはて…?

---

1. いわゆる表ID, 裏IDのことを指します ↩︎

2. 性格値のことを指します ↩︎

3. 【USM対応】トレーナーIDからTSVを求めるツール ↩︎ ↩︎

4. くどいようですが, TSVという値が実際に保存されている訳ではありません. ここでいうTSVの決定タイミングはTIDSIDの決定タイミングを指しており, 実はトレーナーIDもTIDSIDの値をもとに決定されます. ↩︎

5. 実際はポケモンのタマゴの個体決定にTinyMTと呼ばれる別の乱数生成アルゴリズムも存在しますが, ここでは割愛します. ↩︎

6. 名前決定時にキャンセルをしていなければ, SMだと1012消費, USUMだと1132消費後の乱数によって決定されます. ↩︎

7. Single Instruction, Multiple Dataの頭字語. 一つの命令で複数のデータを同時に処理する演算手法のこと. ↩︎