概要 Mathematica (or Wolfram Cloud)を使ったら、ペラップの鳴き声だけから64bit LCGのseedを特定できた。 これは64bit LCGの上位5bitの連続した値を13個観測してseedを十分現実的な時間で復元したことになる。 内容 第5世代のポケモンでは64bitの線形合同…
Walkie-Talkieをビルドします。 古いdevkitProが必要です。 linuxバージョンはここから落とせるようです。 dslibris - Browse /tool/devkitpro/r23b at SourceForge.net この場合32bitのlinuxで動きますから、それを用意します。私はVirtualBoxの上でCentOS …
GBAのROMを二次元コードを使ってダンプするNDSプログラムとそれを読み取るwebプログラムを書きました。 GitHub - oupo/gbatoqr gbatoqr experiment このNDSプログラムは2.25KBずつブロックに分けて2次元コード化し表示を繰り返します。 4MBのROMのダンプにだ…
pattirudon氏のアルゴリズムについて - oupoの日記 このアルゴリズムのオーダーを調べます。 つまり、線形な遷移で決まっている疑似乱数で、状態から乱数は足し算で決まっているものとする。 このとき乱数値からseedを復元するアルゴリズムを考える。 ただし…
背景 ポケモンソード・シールドのレイドバトルと呼ばれるイベントではxoroshiro128+という疑似乱数を使ってモンスターを生成している。 これについて、セーブデータを抽出せず、ゲームのプレイから得られる情報からxoroshiro128+の乱数の種を復元できないか…
疑似乱数アルゴリズム、「pokemon rng ffd3」で検索したら出てきた。 http://tasvideos.org/GameResources/GBx/PokemonGen1.html http://wiki.pokemonspeedruns.com/index.php/Pokémon_Red/Blue/Yellow_DSum_Manipulation 乱数生成のたびにIOレジスタの一つ0…
を素数，を正整数，を整数とする． を $$f(x) = a x + b$$ で定める． 命題1 がの倍数であると仮定する． このとき次が成立する． の不動点，すなわち $$f(x) = x$$ を満たすが存在する． の不動点は一意である． 任意のについて次で定義される数列: $$ x_n …
Pokémon RNG Advent Calendar 2017 24日目の記事です。ペラップ演奏会をしました。忙しい人はラスト30秒を見てください。先人はこちら: ペラップ乱数 - ろいしんぶろぐ 使ったseedとか (第5世代はMACアドレスによってseedが変わるので他の人は使えないが) プ…
第4世代のポケモンにおいてくじ番号から裏IDを求めるプログラムです。以前の記事 くじ番号から裏IDを検索するツールを作りました - oupoの日記 sid-searchを作り直してみた - oupoの日記 データベースを使わずにローカルで検索するバージョンを作ってみまし…
SM孵化乱数列を計算する : ただの雑記byさき 【TinyMT】なぜ乱数値の最下位bit列から元の内部状態を復元できるのか考えてみた。 | 夜綱のブログ の件について。たまたま全単射になるのではなく、必然なのではないかと考えてみたら実際そうだった。 体がF_2で…
Pokémon RNG Advent Calendar 2017の19日の記事です。第5世代のポケモンでは次の64bitのLCG(線形合同法)が使われています。 X_{n+1} = (X_n * 0x5d588b656c078965 + 0x269ec3) % 2^6464bitとなると全seedをしらみつぶすということが現実的な時間では不可能で…
Pokémon RNG Advent Calendar 2017の12日目の記事です。 DeSmuME用デバッガ https://github.com/oupo/desdebugger DeSmuME用デバッガを作りました。DeSmuMEはGDB Remote Stub Protocolを実装しています。これを使ってDeSmuMEとやり取りしデバッガの動作を行…
Pokémon RNG Advent Calendar 2017の11日目の記事です。バトルファクトリー 必勝(?)乱数調整 - oupoの日記の続きです。第4世代のポケモンのバトルファクトリーというレンタルポケモンを使って勝ち進める施設で乱数調整を行います。前回(なんと3年前！)は鉢巻…
ろいしんさんの乱数調整で遊ぼうを中身を見ながら解析します。 乱数調整で遊ぼう - ろいしんぶろぐ 乱数調整で遊ぼう解答 : ただの雑記byさき 1. 文字列を調べる 飛ばしてもよいです。バイナリエディタでは2バイトアラインされていないところの2バイト文字が…
Pokémon RNG Advent Calendar 2017の8日目の記事です。 https://chatot.netlify.com/ 作りました。oupoとmizdraさんの二人の共同作です。DSのポケモンにおいてペラップの鳴き声からseedを特定するためのツールです。要マイク。 使い方 1. ペラップの「おしゃ…
背景 DSはメインメモリが4MBしかなく、ゲームの全てのプログラムをメモリ上に載せることができません。そこで必要なときに必要なモジュールをメモリ上にロードしています(たとえば戦闘に入ったら戦闘用のプログラムモジュールをロードするなど)。 この各モジ…
(2015年にやったものを発掘して記事にしているのでもう細部を忘れています)ゲーム内の処理とか一切触らずにこんな風に斜めから映したり、街の全体像を映したりできます。 (建物の一部が映ってなかったり、キャラクターの位置がずれているのはすでに修正済み…
背景 乱数調整のツールを作っていると次のようなコードを書きたくなります。 しかし、このコードはshow_ivs()を呼び出すたびにMTがコピーされるので遅いです。 struct MT { uint32_t table[624]; int index; }; void init_genrand(MT *mt, uint32_t seed); u…
Pokémon RNG Advent Calendar 2016 13日目の記事です。疑似乱数TinyMTにおいて得られた乱数値から乱数生成器の状態を逆算する話です。SM孵化乱数列を計算する : ただの雑記byさきによってTinyMTのstateは連続した127個の乱数値の下位1bitがあれば得られるこ…
疑似乱数TinyMTの逆算について考えます。https://odanpoyo.github.io/2016/12/10/Tiny-Mersenne-twister%E3%81%AE%E9%80%86%E7%AE%97/の続きともいえるような内容です。 上の記事はstateから一つ前のstateを計算するという話でしたが、この記事では連続する4…
で与えられる線形合同法疑似乱数において、その上位16bit が観測できるという状況を考えます。 そのとき $X_0$ の値を求めるにはどうすればよいでしょうか。$Y_0$ を $\alpha$ とおくとき $X_0$ は とかけます。よって $2^{16}$ 通りの $x$ すべてをしらみつ…
この記事ではKnuthの補題Pと(Z/mZ)*の構造定理の補題 - oupoの日記で与えた補題を利用する．
“The Art of Computer Programming”において線形合同法に関する定理を証明するのに使われる補題Pの証明を記す．また整数論の教科書で(Z/mZ)*の構造を決定するのに用いられる補題 (補題2と補題4)が補題Pから導かれることを見る．
線形合同法であるseedが0からいくつ進めたものかを得る - oupoの日記 線形合同法であるseedが0からいくつ進めたものかを得る その2 - oupoの日記 法が2のべきとは限らない一般の場合で求める方法ができた。法が素数pのべきの場合、{x_n}が法p^eで最大周期のL…
線形合同法数列が最大周期になる条件(ただし法が2のべきの場合) - oupoの日記 線形合同法であるseedが0からいくつ進めたものかを得る その2 - oupoの日記の記事のアイディアを使ったら簡単な証明を得たので記す。 先の最大周期になる条件の証明はくどすぎた…
前回の記事: 線形合同法であるseedが0からいくつ進めたものかを得る - oupoの日記 続きの記事: 線形合同法であるseedが0からいくつ進めたものかを得る その3 (法が2のべきとは限らない一般の場合) - oupoの日記 周期2^k, 初項0のLCG数列{x_n}に対して、{x_{2…
ポケモンHGSSにおけるバトルファクトリーの必勝(?)乱数調整の動画を撮影しました。作った(or 使った)ツールは以下 http://oupo.github.io/factory-npc/ https://github.com/oupo/factory-search (UIなし) オーキドはかせのポケモンこうざで乱数消費補助ツー…
擬似乱数生成器メルセンヌツイスタ(MT)には以下のような調律(tempering)と呼ばれる関数が登場します。 u32 tempering(u32 x) { x ^= (x >> 11); x ^= (x << 7) & 0x9d2c5680; x ^= (x << 15) & 0xefc60000; x ^= (x >> 18); return x; } MTの作者自身の講義…
ポケモンBW2のジョインアベニューの日替わりseedで使われている漸化式がちょっとおもしろいです。 s[n+1] = ((s[n] * 0x5d583d6d6c078979 + 0x26a693) mod (2^64)) >> 32まず、0がこの漸化式の不動点になることがわかりますが、実際のゲーム中では0になった…
