くじ番号から裏ID ローカル検索バージョン
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は以下の通り
と、これだけでは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で逆アセンブルする
右下に文字列一覧があります。
試しに「当たりだ! もう一本」をクリックしましょう
「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までの値を設定できます
鳴き声を取りこぼしてしまった場合は入力に「?」の行を入れておいてください。その行は任意の周波数にマッチするものとして処理されます。
開発
プルリクエスト、イシュー投稿歓迎です。また、MITライセンスで公開しているのでご自由に。