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

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

以前の記事

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

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

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

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

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

の件について。

たまたま全単射になるのではなく、必然なのではないかと考えてみたら実際そうだった。
体がF_2であることや次元がメルセンヌ指数であることも使わず証明できた。

TeXソースは以下

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

64bit LCGの検索

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がちょっとずつしか進まないので目的の値の範囲にくるまでがばっとスキップできることがわかると思います。

このアイディアはCracking Pseudorandom Sequences Generators in Java Applicationsからいただきました。

さて、これを実装します。
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を調べられますね。興味のある方、ぜひチャレンジしてみてください。

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

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

DeSmuME用デバッガ


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

DeSmuMEはGDB Remote Stub Protocolを実装しています。これを使ってDeSmuMEとやり取りしデバッガの動作を行っています。
ARMとGDB StubであればDeSmuMEに限らずほかのエミュレータでも動くかもしれません。(未チェック)

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

TODOは以下の通り

  • メモリビュー
  • アセンブルリストにコメントをつけられるように
  • Follow Jump / Undo Follow
  • Jump命令に関して矢印をつける
  • Read, Writeのブレークポイント

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

霊界の布

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


きのみスクラッチ

プラチナ、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__

バトルファクトリー Lv50 1周目〜5周目 乱数調整

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

バトルファクトリー 必勝(?)乱数調整 - oupoの日記の続きです。

第4世代のポケモンのバトルファクトリーというレンタルポケモンを使って勝ち進める施設で乱数調整を行います。

前回(なんと3年前!)は鉢巻きムクホークと襷道連れムウマージでオープンレベル4周目を必勝するseedを探して乱数調整しました。
今回はLv50 1周目〜5周目で乱数調整します。前回のように必勝までは難しくて実現できていません。

1周目

seedは0x532b6a85

勝ち筋:クチートヌケニン

ヌケニンで完封できるやつが1匹以上いてそれ以外のポケモンもだいたいクチートに弱い的なseedを探した。

だいたいクチートに弱い、の判定がかなりザル。

2周目に備えて全交換

2周目

seedは0xb50a44ff

勝ち筋:オオスバメ

一応必勝判定関数を全試合で使用

オオスバメの根性どくどく玉からげんきの火力は目を見張るものがあるが、守るを覚えておらず1回相手の攻撃を耐える必要があるのが難点。

交換なし

3周目

seedは0x004ce889

勝ち筋:キングドラオオスバメ

7戦目にだけ必勝判定関数使用 (そうでないと全然seedが見つからなかった)

キングドラが出ているとき素早さが負けていたら雨を降らせるような戦略をプログラムにしたのだが、実はミスがあってその部分が動いていなかった
7戦目、ヌオーに波乗りを打つミスをした。

交換3回。

4周目

seedは0x01686087

勝ち筋: ハピナス

敵トレーナーがランク3の場合必勝判定をさぼる (やはりそうしないとseedが見つからなかった)

肝心のハピナスを活躍させられなかった。ゴウカザルがずっと活躍。
6戦目、カメールが瓦割りを覚えていることを知らなくてハピナスに交換するミスをした。

交換1回。

5周目

seedは0x4ab4b12e

勝ち筋: スカーフトリックポリゴンZりゅうのまいギャラドス

敵AIの技決定がランダムではなくなったので、逆にスカーフトリックなどではめれる。

キノガッサをスカーフトリックでうまくいく相手にしていたのはよくなかった。

所感

  • seedを見つける条件がザルい周多め。運が悪いと負ける可能性あるよなー
  • モンテカルロ法で対戦シミュレーションとかして勝率の高いseedを見つけようとしたものの、敵AIの解析とかもしないといけないのが大変で実現できなかった
  • 5周目の戦略は気に入っている

使ったツールは以下

検索に使ったコードは以下

乱数調整で遊ぼう 別解

ろいしんさんの乱数調整で遊ぼうを中身を見ながら解析します。

1. 文字列を調べる

飛ばしてもよいです。バイナリエディタでは2バイトアラインされていないところの2バイト文字が見れなかったりするので念のため。
以下のRubyスクリプトで文字列を出力します

fname = ARGV[0]
File.binread(fname).scan(/(?:[\x81-\x9f\xe0-\xfc][\x40-\x7e\x80-\xfc]|[\x20-\x7e]){4,}/n).each do |matched|
  puts matched.encode("utf-8", "cp932", undef: :replace)
end

結果

おいしいみず
サイコソーダ
ミックスオレ
何をしますか?
おかね:%d円
しらべる -> 0
ポケモン -> 1
かいもの -> 2
________
| || ⊂⊃⊂⊃ ||
| || [][][][] ||
| ||
| || [][][][] ||
| || poke
 Θ ||
| || 口口口口 ||
|| ==== ||
    ̄ ̄ ̄ ̄ ̄ ̄
自動販売機が ある!
ほしい 飲み物は....
1. おいしいみず 200円
2. サイコソーダ 350円
3. ミックスオレ 400円
0. やめる
 おかね:%d円
...やっぱり やめた
YOU LOSE...
ペラップを しばいた!
もう一度遊びますか?
はい -> 1
いいえ -> 0
おかねが 足りない....
ガコン!
%sが でてきた!
当たりだ! もう一本
%sが でてきた!
YOU WIN!!
ベトベター
オニドリル
マグマッグ
ベトベトン
がんばりや
さみしがり
ゆうかん 
いじっぱり
やんちゃ 
ずぶとい 
すなお  
のんき  
わんぱく 
のうてんき
おくびょう
せっかち 
まじめ  
ようき  
むじゃき 
ひかえめ 
おっとり 
れいせい 
てれや  
うっかりや
おだやか 
おとなしい
なまいき 
しんちょう
きまぐれ 
するどいくちばし
きんのたま
モンスターボールを 買いました
おかね:%d円
野生の%sを つかまえた!
%s Lv.%d
性格:%s
個体値:%d-%d-%d-%d-%d-%d
なんと!
つかまえた%sが %sをもっていた!
%sを 売って
%d円 手に入れた
おかね:%d円
YOU LOSE...

2. とりあえず普通に遊ぶ

遊びます

3. IDAで逆アセンブルする

IDAで逆アセンブルします。

右下に文字列一覧があります。
試しに「当たりだ! もう一本」をクリックしましょう

「DATA XREF DATA XREF: sub_4011D0+9F↑o」というのがありますね。
これを使うと、この文字列を参照しているコードに移動できます。大変べんり。

無事、乱数を使ってあたりが出るかどうか判定しているところが見れました。
疑似乱数はx_{n+1} = (x_n * 41C64E6Dh + 6073h) % 2^32のようで、seedはdword_404374に格納されているようです。

初期seed決定も調べておきましょう。
dword_404374を選んで「Jump to xref to operand」を押すと、seedを読み書きしている部分が表示されます。

見つかりました。
これを見るとtime64()の戻り値 (1970年1月1日 00:00:00からの経過秒数)の下32bitを使っているようです。

ゲームの12/8からのバージョンではペラップが実際に音を鳴らすようになりました。
これを調べてみます。
Beepという文字列があるのでBeep() APIを使って音を鳴らしているのだと推定されます。呼んでいるところを見てみましょう。

(((seed >> 16) * 8192) >> 16) * 110 / 8192 + 440

によって周波数を定めているようです。

4. seed書き込みをトレースしながら実行

seed書き込みがあったらそのことを出力しながら実行してみます。

メニュー > Debugger > Breakpoints > Breakpoint listを開きます。

このように設定します。

そしてメニュー > Debugger > Start Processを押してみましょう。プログラムが実行されます。

このとき遊んでみると、seedが更新されるたびにTrace Windowにそのことが出力されます。

初期seedは0x5a2b5249であることがわかります。Rubyで確認してみると

irb(main):026:0> (Time.utc(1970,1,1) + 0x5a2b5249).getlocal
=> 2017-12-09 12:02:33 +0900

となって確かに起動時刻が使われています。

ペラップを鳴かせると1消費したり野生のポケモンを捕まえるといくつか消費したり、といったこともトレースされます。

長くなってきたのでこの辺りで。
これ以外の情報が気になる方はぜひ自分で解析してみてください。

ペラップの鳴き声からseedを特定するツールを作った

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

作りました。oupoとmizdraさんの二人の共同作です。

DSのポケモンにおいてペラップの鳴き声からseedを特定するためのツールです。要マイク。

使い方

1. ペラップの「おしゃべり」機能で880hzのサイン波を録音しておく (youtubeで880hzと検索すれば出ます)
2. このツールを開いた状態で、ペラップの鳴き声を鳴らす。するとツールの入力ボックスに自動的に入力される
3.検索したいモードなどを設定して検索を実行する
4. seed または消費数が見つかる

注意

マイクが遠くてペラップの鳴き声が拾われない、あるいは逆にペラップ以外のBGMの音も拾ってしまうという場合。このときはページ下部のmaxDecibelsを調整してください。-99から-1までの値を設定できます
鳴き声を取りこぼしてしまった場合は入力に「?」の行を入れておいてください。その行は任意の周波数にマッチするものとして処理されます。

開発

githubリポジトリを置いています。

プルリクエスト、イシュー投稿歓迎です。また、MITライセンスで公開しているのでご自由に。

今後の課題

  • Reactを全然使っていないのをリファクタリング
  • ペラップの音を拾う部分をもっと精度よく
  • 第5世代のパラメータを複数保存できるようにする
  • 第5世代のseed検索でキー入力に対応する
筆者: oupo (連絡先: oupo.nejiki@gmail.com)