Hatena::ブログ(Diary)

oupoの日記

2017-12-24

クリスマスイブなのでペラップにWe Wish a Merry Christmasを歌ってもらった

00:00

Pokémon RNG Advent Calendar 2017 24日目の記事です。

f:id:oupo:20171215195138p:image

D

ペラップ演奏会をしました。忙しい人はラスト30秒を見てください。

先人はこちら:

使ったseedとか (第5世代はMACアドレスによってseedが変わるので他の人は使えないが)

周波数=400Hz
seed=0x1612c3c5, iseed=610a0397, f=30
A4, A4, A4, B4flat, A4
  • ホワイト DSi(00-22-aa-38-54-68)
周波数=325Hz
2081/05/24 22:13:59 key=40(↑)
iseed=5c1d2d0cd37c0907 seed=37deba833913e966 f=97 (46)
F4, F4, G4, F4, E4, G4, G4, G4, F4, E4, G4, F4, G4, E4, F4
  • ブラック DS Lite (00-21-47-72-91-b3)
周波数=255Hz
2056/06/25 17:37:21 key=00
iseed=b1b95766f2f478a9 seed=627ba589ac411cb1 f=72 (24)
C4, D4, D4, D4, C4, C4, D4, C4, C4, D4

seed検索のソースコードは以下。おだんぽよさんのPokeRNGを利用しています。

#include <iostream>
#include <cstdio>
#include <cstdint>
#include <ctime>
#include <vector>
#include "PokeRNG/Calc5GenSeed.hpp"
#include "PokeRNG/CalcOffset.hpp"

using namespace std;

typedef uint32_t u32;
typedef uint64_t u64;
typedef int64_t s64;

struct AbstractRNG {
    virtual int rand(int n) = 0;
};

struct LCG64bit : AbstractRNG {
    u64 seed;

    LCG64bit(u64 s) : seed(s) {}

    int rand(int n) {
        seed = seed * 0x5D588B656C078965 + 0x269EC3;
        return (seed >> 32) * n >> 32;
    }
};

struct LCG32bit : AbstractRNG {
    u32 seed;

    LCG32bit(u32 s) : seed(s) {}

    int rand(int n) {
        seed = seed * 0x41c64e6d + 0x6073;
        return (seed >> 16) % n;
    }
};

bool valid_seed(AbstractRNG &rng, double baseFreq, vector<double> expectedFreqs, double allowRatio = 1.015) {
    for (double expected : expectedFreqs) {
        double got = ((rng.rand(8192)) / 8192.0 * 0.25 + 1) * baseFreq;
        double ratio;
        if (expected < got) {
                ratio = got / expected;
        } else {
            ratio = expected / got;
        }
        if (ratio >= allowRatio) {
            return false;
        }
    }
    return true;
}


u32 prev_seed(u32 seed) {
    return seed * 0xEEB9EB65 + 0x0A3561A1;
}

bool good_seed(u32 seed) {
    int i;
    for (i = 0; i < 10; i ++) seed = prev_seed(seed);
    for (; i < 40; i ++) {
        u32 upper = seed >> 24;
        u32 hour = (seed >> 16) & 0xff;
        u32 frame = seed & 0xffff;
        u32 second = (frame - 17) / 60 + 10;
        if (12 * 24 + second - 256 <= upper && upper <= 12 * 24 + second + 60 - 256
            && hour < 24 && 0x0270 <= frame && frame <= 0x0400) {
            return true;
        }
        seed = prev_seed(seed);
    }
    return false;
}

constexpr double C4 = 261.626;
constexpr double D4 = 293.665;
constexpr double E4 = 329.628;
constexpr double F4 = 349.228;
constexpr double G4 = 391.995;
constexpr double A4 = 440.000;
constexpr double B4flat = 466.164;

// 中音 (ホワイト1 + DSi)
int main1() {
    vector<double> expected = { F4, F4, G4, F4, E4, G4, G4, G4, F4, E4, G4, F4, G4, E4, F4 };
    double base = 325;

#pragma omp parallel for
    for (long i = 946652400; i < 4102412400; i ++) {
        PokeRNG::Parameters5Gen<PokeRNG::ROMType::W1JaDSi> param;
        PokeRNG::Calc5GenSeed calc_seed;
        PokeRNG::CalcOffset calc_offset;
        param.set_mac_addr(0x00, 0x22, 0xaa, 0x38, 0x54, 0x68);
        param.set_timer0(0x1233);
        time_t time = i;
        struct tm date;
        localtime_r(&time, &date);
        param.set_year(date.tm_year + 1900 - 2000);
        param.set_month(date.tm_mon + 1);
        param.set_day(date.tm_mday);
        param.set_hour(date.tm_hour);
        param.set_minute(date.tm_min);
        param.set_second(date.tm_sec);
        for (int key = 0; key < 0x100; key ++) {
            if ((key & 0x30) == 0x30 || (key & 0xc0) == 0xc0) continue;

            param.set_key(0x2fff ^ key);
            PokeRNG::u64 seed = calc_seed(param);
            calc_offset.bw1(seed, true, true);
            LCG64bit lcg(calc_offset.get_seed());
            int ofs = (int)calc_offset.get_offset();
            for (int i = 0; i < 100; i ++) {
                LCG64bit l = lcg;
                if (valid_seed(l, base, expected, 1.02))
#pragma omp critical
                {
                    printf("%04d/%02d/%02d %02d:%02d:%02d ", date.tm_year + 1900, date.tm_mon + 1, date.tm_mday, date.tm_hour, date.tm_min, date.tm_sec);
                    printf("key=%02x seed=%016lx %016lx f=%d (%d)\n", key, seed, lcg.seed, ofs + i, i);
                }
                lcg.rand(1);
            }
        }
    }

    return 0;
}

// 低音 (ブラック1 + DSLite)
int main2() {
    vector<double> expected = { C4, D4, D4, D4, C4, C4, D4, C4, C4, D4 };
    double base = 255;

#pragma omp parallel for
    for (long i = 946652400; i < 4102412400; i ++) {
        PokeRNG::Parameters5Gen<PokeRNG::ROMType::B1Ja> param;
        PokeRNG::Calc5GenSeed calc_seed;
        PokeRNG::CalcOffset calc_offset;
        param.set_mac_addr(0x00, 0x21, 0x47, 0x72, 0x91, 0xb3);
        time_t time = i;
        struct tm date;
        localtime_r(&time, &date);
        param.set_year(date.tm_year + 1900 - 2000);
        param.set_month(date.tm_mon + 1);
        param.set_day(date.tm_mday);
        param.set_hour(date.tm_hour);
        param.set_minute(date.tm_min);
        param.set_second(date.tm_sec);
        int key = 0;
        param.set_key(0x2fff ^ key);
        PokeRNG::u64 seed = calc_seed(param);
        calc_offset.bw1(seed, true, true);
        LCG64bit lcg(calc_offset.get_seed());
        int ofs = (int)calc_offset.get_offset();
        for (int i = 0; i < 30; i ++) {
            LCG64bit l = lcg;
            if (valid_seed(l, base, expected, 1.015))
#pragma omp critical
            {
                printf("%04d/%02d/%02d %02d:%02d:%02d ", date.tm_year + 1900, date.tm_mon + 1, date.tm_mday, date.tm_hour, date.tm_min, date.tm_sec);
                printf("key=%02x seed=%016lx %016lx f=%d (%d)\n", key, seed, lcg.seed, ofs + i, i);
            }
            lcg.rand(1);
        }
    }

    return 0;
}

// 高音 (Pt)
int main3() {
    vector<double> expected = { A4, A4, A4, B4flat, A4 };
    double base = 400;

#pragma omp parallel for
    for (s64 seed = 0; seed < 0x20000000; seed ++) {
        LCG32bit lcg(seed);
        if (valid_seed(lcg, base, expected, 1.008) && good_seed(seed)) {
#pragma omp critical
            printf("%08x\n", (u32)seed);
        }
    }

    return 0;
}

int main() {
    return main2();
}

2017-12-22

くじ番号から裏ID ローカル検索バージョン

17:33

f:id:oupo:20171222172850p:image

第4世代のポケモンにおいてくじ番号から裏IDを求めるプログラムです。

以前の記事

データベースを使わずにローカルで検索するバージョンを作ってみました。 (ただWeb Assemblyを試してみたかっただけという噂も)

スマートフォンでも遅いですが動きます。(未対応のブラウザもあるかも)

Q. ワーカー数とは?

A. 同時に並行に計算させる個数です。CPUプロセッサ数を指定すればいいです (デフォルトでそれが入力されているはず)

C++で書いたプログラムより14倍ぐらい遅くて残念。

2017-12-21

TinyMTにおいて状態から連続する127個の乱数の下位1bitの列を取り出す写像が全単射なこと

14:03

の件について。

たまたま全単射になるのではなく、必然なのではないかと考えてみたら実際そうだった。

体がF_2であることや次元がメルセンヌ指数であることも使わず証明できた。

f:id:oupo:20171221153850p:image

TeXソースは以下

参考文献

[1] 松本眞 (2004), 「有限体の擬似乱数への応用」 (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/TEACH/0407-2.pdf

2017-12-19

64bit LCGの検索

00:00

Pokémon RNG Advent Calendar 2017の19日の記事です。

第5世代のポケモンでは次の64bitのLCG(線形合同法)が使われています。

X_{n+1} = (X_n * 0x5d588b656c078965 + 0x269ec3) % 2^64

64bitとなると全seedをしらみつぶすということが現実的な時間では不可能です。

16bitの乱数値がわかる状況を考えます。この場合でも調べるseedの個数は2^48個あってやはり全探索は時間がかかりそうです。(2^32個の探索が1秒で済むと仮定しても18時間かかる)

しかし、実は16bitの乱数情報があればそれなりに速い時間で(たとえば私のパソコンではシングルスレッドでも19秒で)条件を満たすseedをすべて求められます。

正確には乱数値16bitとその10個先の乱数値16bitです。

すなわち

f(x) = (x * A + B) % 2^64
g(x, n) = ((x >> 32) * n) >> 32
where A = 0x5d588b656c078965, B = 0x269ec3

とおいたとき与えられたa, bに対して

g(x, 65536) = a
g(f^10(x), 65536) = b

を満たすxをすべて求められます。

仕組みはこうです。

xstep := 0x05114191

という定数を定義します。

この定数により次の式は

(xstep * A^10) % 2^64 = 0xbf4a64c9 =: ystep

という小さい値になります。 (そうなるようなxstepと10という定数を探したのです)

するとxをxstepずつ大きくしたときにy = f^10(x)はystepずつ大きくなることより、yの値が目標の値に到達するところまでスキップできることになります。

実際xをxstepずつ大きくすると以下のようになります。

i = 00, x = 0000000000000000, y = 67795501267f125a
i = 01, x = 0000000005114191, y = 67795501e5c97723
i = 02, x = 000000000a228322, y = 67795502a513dbec
i = 03, x = 000000000f33c4b3, y = 67795503645e40b5
i = 04, x = 0000000014450644, y = 6779550423a8a57e
i = 05, x = 00000000195647d5, y = 67795504e2f30a47
i = 06, x = 000000001e678966, y = 67795505a23d6f10
i = 07, x = 000000002378caf7, y = 677955066187d3d9
i = 08, x = 00000000288a0c88, y = 6779550720d238a2
i = 09, x = 000000002d9b4e19, y = 67795507e01c9d6b
i = 10, x = 0000000032ac8faa, y = 677955089f670234
i = 11, x = 0000000037bdd13b, y = 677955095eb166fd
i = 12, x = 000000003ccf12cc, y = 6779550a1dfbcbc6
i = 13, x = 0000000041e0545d, y = 6779550add46308f
i = 14, x = 0000000046f195ee, y = 6779550b9c909558
i = 15, x = 000000004c02d77f, y = 6779550c5bdafa21

yがちょっとずつしか進まないので目的の値の範囲にくるまでがばっとスキップできることがわかると思います。

このアイディアはno titleからいただきました。

さて、これを実装します。

0個先と10個先の乱数値だけだと全部出力するとかなりの個数(2^32くらい)になるので1個先と2個先の乱数値も条件に加えることにします。

#include <cstdio>
#include <cstdint>
#include <cmath>
#include <algorithm>
#include <chrono>
#include <random>

typedef int64_t s64;
typedef uint64_t u64;
typedef __int128 s128;

const u64 A = 0x5d588b656c078965ll;
const u64 B = 0x269ec3ll;
const s128 M = (s128)1 << 64;
const int BITS = 64;
const int P = 16;

class LCGOperator {
public:
    u64 a, b;
    LCGOperator(u64 aa, u64 bb) : a(aa), b(bb) {}

    LCGOperator o(LCGOperator y) {
        LCGOperator x = *this;
        LCGOperator res(x.a * y.a, x.a * y.b + x.b);
        return res;
    }

    LCGOperator pow(u64 n) {
        LCGOperator x = *this;
        if (n == 0) {
            return LCGOperator(1, 0);
        } else if (n % 2 == 1) {
            return x.o(x).pow(n / 2).o(x);
        } else {
            return x.o(x).pow(n / 2);
        }
    }

    u64 apply(u64 s) {
        return a * s + b;
    }
};

void search(u64 s0, u64 s1, u64 s2, u64 s10, bool check) {
    LCGOperator op0(A, B);
    LCGOperator op = op0.pow(10);
    const u64 xstep = 0x05114191;
    const u64 ystep = (xstep * op.a) % M;

    const s128 xstart = (s128)s0 << (BITS - P);
    const s128 xend = (s128)(s0 + 1) << (BITS - P);
    const s128 ystart = (s128)s10 << (BITS - P);
    const s128 yend = (s128)(s10 + 1) << (BITS - P);
    u64 found_count = 0;

    for (u64 i = 0; i < xstep; i ++) {
        s128 x = xstart + i;
        s128 y = op.apply(x);
        s128 s;

        while (x < xend) {
            while (ystart <= y && y < yend && x < xend) {
                if ((y % M) >> (BITS - P) == s10 && (!check || ((op0.apply(x) >> (BITS - P)) == s1 && (op0.pow(2).apply(x) >> (BITS - P)) == s2))) {
                    if (check) printf("found %016lx\n", (u64)x);
                    found_count ++;
                }
                x += xstep;
                y += ystep;
            }

            s128 ynext = (y >= ystart ? M : 0) + ystart - y;
            s = ynext / ystep + (ynext % ystep != 0 ? 1 : 0);

            y = (y + ystep * s) % M;
            x += xstep * s;
        }
    }
    printf("found_count=%ld\n", found_count);
}

int main() {
    std::mt19937 rnd;
    for (int i = 0; i < 10; i ++) {
        u64 seed = (u64)rnd() << 32 | rnd();
        printf("seed=%016lx\n", seed);
        LCGOperator op0(A, B);
        LCGOperator op = op0.pow(10);
        u64 s0 = seed >> (BITS - P);
        u64 s1 = op0.apply(seed) >> (BITS - P);
        u64 s2 = op0.pow(2).apply(seed) >> (BITS - P);
        u64 s10 = op.apply(seed) >> (BITS - P);
        auto start = std::chrono::system_clock::now();
        search(s0, s1, s2, s10, true);
        auto end = std::chrono::system_clock::now();
        printf("time=%ld\n", std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count());
    }
    return 0;
}

このプログラムは解の一つとなるべきseedを一つ乱数 (MT使用)で決めて、探索します。ちゃんと決めた解が探索によって見つかっていればいいわけです。

実行結果は次のようになります。

seed=d091bb5c22ae9ef6
found d091bb5c22ae9ef6
found d091de63e71f9f06
found d09117bbd62d8f67
found_count=3
seed=e7e1faeed5c31f79
found e7e1faeed5c31f79
found_count=1
seed=2082352cf807b7df
found 2082352cf807b7df
found_count=1
seed=e9d300053895afe1
found e9d3c6ad4987bf80
found e9d300053895afe1
found e9d3230cfd06aff1
found_count=3
seed=a1e24bba4ee4092b
found a1e24bba4ee4092b
found_count=1
...

ちゃんと見つかっていますね!

また、0個先と10個先の乱数値だけを条件にして探索して得られた個数がLattE (線形不等式を満たす整数点の個数を出力するソフトウェア)によって数えられた個数と一致することは何個かの具体例について確認済みです。

で、実際問題、第5世代のポケモンで0個先と10個先の乱数の16bit値が観測できる状況があるのかというとないです。PWT (ポケモンワールドトーナメント)でレンタルポケモンのトレーナーIDが乱数で決まっていればチャンスがあったのになという感じです。

16bitじゃなくて6bitか7bitくらいの乱数値からseedを現実的な時間で見つけるアルゴリズムを見つけられれば、ペラップの音程からseedを調べられますね。興味のある方、ぜひチャレンジしてみてください。

2017-12-12

DeSmuME用デバッガと霊界の布ときのみスクラッチ

00:00

Pokémon RNG Advent Calendar 2017の12日目の記事です。

DeSmuME用デバッガ

f:id:oupo:20171211224406p:image

DeSmuME用デバッガを作りました。

DeSmuMEはGDB Remote Stub Protocolを実装しています。これを使ってDeSmuMEとやり取りしデバッガの動作を行っています。

ARMとGDB StubであればDeSmuMEに限らずほかのエミュレータでも動くかもしれません。(未チェック)

というわけで、DS用ゲームを解析したい方、どうぞご利用ください。

TODOは以下の通り

と、これだけではRNGともPokémonとも関係ない記事になってしまうのでポケモン乱数の話をします。

霊界の布

ダイヤモンドパールで霊界の布をゲットする乱数調整を行いました。

D

きのみスクラッチ

f:id:oupo:20171212004151p:image

プラチナHGSSバトルフロンティアにおけるきのみスクラッチを解析しました。

どういう仕組みできのみが決まっているのか日本語で解説するのは面倒なのでseedを入力したらそのときの結果を出力するプログラムを貼ります。Rubyで書いています。

# Pt, HGSSでのフロンティアのきのみスクラッチ

class LCG
  def initialize(seed)
    @seed = seed
  end

  def clone
    LCG.new(@seed)
  end

  def rand()
    @seed = (@seed * 0x41c64e6d + 0x6073) % 2**32
    @seed >> 16
  end

  def rand_n(n)
    rand() % n
  end
end

ITEM_LIST = [0x00A9, 0x00AA, 0x00AB, 0x00AC, 0x00AD, 0x00AE, 0x00B8, 0x00B9, 0x00BA, 0x00BB, 0x00BC, 0x00BD, 0x00BE, 0x00BF, 0x00C0, 0x00C1, 0x00C2, 0x00C3, 0x00C4, 0x00C5, 0x00C6, 0x00C7, 0x00C8]

ITEM_NAMES = {
  0x005C => "きんのたま",
  0x00A9 => "ザロクのみ",
  0x00AA => "ネコブのみ",
  0x00AB => "タボルのみ",
  0x00AC => "ロメのみ",
  0x00AD => "ウブのみ",
  0x00AE => "マトマのみ",
  0x00B8 => "オッカのみ",
  0x00B9 => "イトケのみ",
  0x00BA => "ソクノのみ",
  0x00BB => "ソンドのみ",
  0x00BC => "ヤチェのみ",
  0x00BD => "ヨブのみ",
  0x00BE => "ビアーのみ",
  0x00BF => "シュカのみ",
  0x00C0 => "バコウのみ",
  0x00C1 => "ウタンのみ",
  0x00C2 => "タンガのみ",
  0x00C3 => "ヨロギのみ",
  0x00C4 => "カシブのみ",
  0x00C5 => "ハバンのみ",
  0x00C6 => "ナモのみ",
  0x00C7 => "リリバのみ",
  0x00C8 => "ホズのみ",
}

def make_scratch(lcg)
  # メタモンの位置決め
  arrange = Array.new(9, nil)
  2.times do |i|
    while true
      i = lcg.rand_n(9)
      if not arrange[i]
        arrange[i] = 4
        break
      end
    end
  end

  #きのみの配置を決定
  item = lcg.rand_n(4)
  count = 0
  9.times do |i|
    x = lcg.rand_n(9)
    if not arrange[x]
      count = 0
      arrange[x] = item
      if i == 2 or i == 4 or i == 6
        item = (item + 1) % 4
      end
    else
      count += 1
      redo if count < 30
      count = 0
      9.times do |j|
        next if arrange[j]
        arrange[j] = item
        if i == 2 or i == 4 or i == 6
          item = (item + 1) % 4
        end
        break
      end
    end
  end

  # アイテムを決定
  items = Array.new(4, nil)
  i0 = lcg.rand_n(4)
  4.times do |i|
    if i == i0
      items[i] = 0x5c
    else
      item = ITEM_LIST[lcg.rand_n(23)]
      redo if items.include?(item)
      items[i] = item
    end
  end
  
  [arrange, items.map{|x| ITEM_NAMES[x] }]
end

def main()
  print "seedを入力> 0x"
  seed = gets.to_i(16)
  print "最大消費数を入力> "
  max_f = gets.to_i
  lcg = LCG.new(seed)
  max_f.times do |f|
    puts "消費#{f}:"
    l = lcg.clone()
    3.times { p make_scratch(l) }
    lcg.rand()
  end
end

main() if $0 == __FILE__
Connection: close