ゲームボーイのポケモンの疑似乱数

疑似乱数アルゴリズム、「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…

線形合同法とp進整数と縮小写像

を素数,を正整数,を整数とする. を $$f(x) = a x + b$$ で定める. 命題1 がの倍数であると仮定する. このとき次が成立する. の不動点,すなわち $$f(x) = x$$ を満たすが存在する. の不動点は一意である. 任意のについて次で定義される数列: $$ x_n …

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

Pokémon RNG Advent Calendar 2017 24日目の記事です。ペラップ演奏会をしました。忙しい人はラスト30秒を見てください。先人はこちら: ペラップ乱数 - ろいしんぶろぐ 使ったseedとか (第5世代はMACアドレスによってseedが変わるので他の人は使えないが) プ…

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

第4世代のポケモンにおいてくじ番号から裏IDを求めるプログラムです。以前の記事 くじ番号から裏IDを検索するツールを作りました - oupoの日記 sid-searchを作り直してみた - oupoの日記 データベースを使わずにローカルで検索するバージョンを作ってみまし…

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

SM孵化乱数列を計算する : ただの雑記byさき 【TinyMT】なぜ乱数値の最下位bit列から元の内部状態を復元できるのか考えてみた。 | 夜綱のブログ の件について。たまたま全単射になるのではなく、必然なのではないかと考えてみたら実際そうだった。 体がF_2で…

64bit LCGの検索

Pokémon RNG Advent Calendar 2017の19日の記事です。第5世代のポケモンでは次の64bitのLCG(線形合同法)が使われています。 X_{n+1} = (X_n * 0x5d588b656c078965 + 0x269ec3) % 2^6464bitとなると全seedをしらみつぶすということが現実的な時間では不可能で…

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

Pokémon RNG Advent Calendar 2017の12日目の記事です。 DeSmuME用デバッガ https://github.com/oupo/desdebugger DeSmuME用デバッガを作りました。DeSmuMEはGDB Remote Stub Protocolを実装しています。これを使ってDeSmuMEとやり取りしデバッガの動作を行…

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

Pokémon RNG Advent Calendar 2017の11日目の記事です。バトルファクトリー 必勝(?)乱数調整 - oupoの日記の続きです。第4世代のポケモンのバトルファクトリーというレンタルポケモンを使って勝ち進める施設で乱数調整を行います。前回(なんと3年前!)は鉢巻…

乱数調整で遊ぼう 別解

ろいしんさんの乱数調整で遊ぼうを中身を見ながら解析します。 乱数調整で遊ぼう - ろいしんぶろぐ 乱数調整で遊ぼう解答 : ただの雑記byさき 1. 文字列を調べる 飛ばしてもよいです。バイナリエディタでは2バイトアラインされていないところの2バイト文字が…

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

Pokémon RNG Advent Calendar 2017の8日目の記事です。 https://chatot.netlify.com/ 作りました。oupoとmizdraさんの二人の共同作です。DSのポケモンにおいてペラップの鳴き声からseedを特定するためのツールです。要マイク。 使い方 1. ペラップの「おしゃ…

DSのROMのオーバーレイたちを展開するスクリプト

背景 DSはメインメモリが4MBしかなく、ゲームの全てのプログラムをメモリ上に載せることができません。そこで必要なときに必要なモジュールをメモリ上にロードしています(たとえば戦闘に入ったら戦闘用のプログラムモジュールをロードするなど)。 この各モジ…

DeSmuMEの3Dレンダラの行列をLuaからいじれるようにするhack

(2015年にやったものを発掘して記事にしているのでもう細部を忘れています)ゲーム内の処理とか一切触らずにこんな風に斜めから映したり、街の全体像を映したりできます。 (建物の一部が映ってなかったり、キャラクターの位置がずれているのはすでに修正済み…

計算結果をキャッシュする&コピーコストのかからないMT

背景 乱数調整のツールを作っていると次のようなコードを書きたくなります。 しかし、このコードはshow_ivs()を呼び出すたびにMTがコピーされるので遅いです。 struct MT { uint32_t table[624]; int index; }; void init_genrand(MT *mt, uint32_t seed); u…

63変数連立2次方程式が解ければTinyMTのstateは連続した64個の乱数値の下位2bitから得られる

Pokémon RNG Advent Calendar 2016 13日目の記事です。疑似乱数TinyMTにおいて得られた乱数値から乱数生成器の状態を逆算する話です。SM孵化乱数列を計算する : ただの雑記byさきによってTinyMTのstateは連続した127個の乱数値の下位1bitがあれば得られるこ…

出力関数が線形な場合のTinyMTにおいて連続する4つの乱数値からstateを得る

疑似乱数TinyMTの逆算について考えます。https://odanpoyo.github.io/2016/12/10/Tiny-Mersenne-twister%E3%81%AE%E9%80%86%E7%AE%97/の続きともいえるような内容です。 上の記事はstateから一つ前のstateを計算するという話でしたが、この記事では連続する4…

32bit LCGのseedを手計算で求めよう (半分ネタ)

で与えられる線形合同法疑似乱数において、その上位16bit が観測できるという状況を考えます。 そのとき $X_0$ の値を求めるにはどうすればよいでしょうか。$Y_0$ を $\alpha$ とおくとき $X_0$ は とかけます。よって $2^{16}$ 通りの $x$ すべてをしらみつ…

線形合同法の周期を一般に決定する方法

この記事ではKnuthの補題Pと(Z/mZ)*の構造定理の補題 - oupoの日記で与えた補題を利用する.

Knuthの補題Pと(Z/mZ)*の構造定理の補題

“The Art of Computer Programming”において線形合同法に関する定理を証明するのに使われる補題Pの証明を記す.また整数論の教科書で(Z/mZ)*の構造を決定するのに用いられる補題 (補題2と補題4)が補題Pから導かれることを見る.

線形合同法の周期が必ず法の値から定まる数の約数になること

線形合同法であるseedが0からいくつ進めたものかを得る その3 (法が2のべきとは限らない一般の場合)

線形合同法であるseedが0からいくつ進めたものかを得る - oupoの日記 線形合同法であるseedが0からいくつ進めたものかを得る その2 - oupoの日記 法が2のべきとは限らない一般の場合で求める方法ができた。法が素数pのべきの場合、{x_n}が法p^eで最大周期のL…

線形合同法数列が最大周期になる条件(ただし法が2のべきの場合) その2

線形合同法数列が最大周期になる条件(ただし法が2のべきの場合) - oupoの日記 線形合同法であるseedが0からいくつ進めたものかを得る その2 - oupoの日記の記事のアイディアを使ったら簡単な証明を得たので記す。 先の最大周期になる条件の証明はくどすぎた…

線形合同法であるseedが0からいくつ進めたものかを得る その2

前回の記事: 線形合同法である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の作者自身の講義…

ジョインアベニューの日替わりseedの周期

ポケモンBW2のジョインアベニューの日替わりseedで使われている漸化式がちょっとおもしろいです。 s[n+1] = ((s[n] * 0x5d583d6d6c078979 + 0x26a693) mod (2^64)) >> 32まず、0がこの漸化式の不動点になることがわかりますが、実際のゲーム中では0になった…

近況

乱数講座 乱数講座というものに参加しました。 (9月7日) LCG Ring LCG Ringというプログラムを書きました。 (9月24日) LCG Ring ポケモンの乱数調整ユーザーなら見ただけで何を意味しているかは分かるはず。 ジョインアベニューのくじの解析 ポケモンBW2のジ…

LCGにおけるseedの検索を離散幾何に帰着させる

LCG(線形合同法)でseedを検索することを離散幾何の問題に帰着させるということを考えてみました。まず線形合同法の漸化式で使われる関数を(Ax + B) mod Mとしておきます。 seedを1増やしたとき、その一つ先のseedというのはA増えるか、A-M増えるかのどちらか…

重複なしにランダムに選んだ後ある特定のseed値になるようなseed値を求める その2 - oupoの日記に追記をしておいた。誰も興味がないようなネタだろうけど…。

確率計算

過去に書いたプログラムが、投稿したwebサービスから消えていたのでブログに残しておく。(2011年11月に作成)ブラックシティとホワイトフォレストの最初に決まる13人の中にグレースがいる確率を求めるプログラム (だったと思う)。だだぢぢさんがTwitterで話題…

asm.jsを試す

Firefoxで実装されているというasm.jsを試しました。これはJavaScriptのプログラムのうち、一部を非常に制限されたルールにしたがって書いてそこに"use asm"というディレクティブをつければ、その部分が非常に高速化されるというしろものです。以前、「メル…