# 🙏 不慮の事故に備えてコンパイルする前に祈る 🙏
$ g++ AbuseMaxChainDrUtsugi.cpp -o AbuseMaxChainDrUtsugi.exe -lm -std=c++11
$ ./AbuseMaxChainDrUtsugi.exe
    r[n] % 3   max chain        S[n]
           0          20  0X97024D60
           1          19   0X15A9302
           2          19  0XD62B4730

結果から「ポケモンのしんかというのは～」は最大20連続, 「カントーにはまだぼくの〜」「ポケルスがくっついた～」は最大19連続であることがわかります.

初期Seedを求める

乱数からそれを狙うことができる初期Seedを求めましょう. これも前回のプログラムを再利用してサクッと書き上げます *1.

gist.github.com

frameは800 ~ 10000F(約3分)に収まるようにしました.

# 🙏🙏🙏 祈る 🙏🙏🙏
$ g++ CalcInitialSeed.cpp -o CalcInitialSeed.exe -lm -std=c++11
$ ./CalcInitialSeed.exe
    n        S[n]        S[0]
   27  0X97024D60  0X961424C7
  184   0X15A9302  0XC60C148A
   88  0XD62B4730  0X4C1514D8

結果

結果を表にまとめます.

r[n] % 3	メッセージ	max chain	n	S[n]	S[0]
0	ポケモンのしんかというのは～	20	27	0x97024D60	0x961424C7
1	カントーにはまだぼくの〜	19	184	0x15A9302	0xC60C148A
2	ポケルスがくっついた～	19	88	0xD62B4730	0x4C1514D8

r[n] % 3 == 0 で最大20連続. ちなみに初期Seedは乱数逆算ツールを使うと自動で求めることが出来ます. 便利〜.

ツールの使い方は以下を参考に.

http://d.hatena.ne.jp/milk4724/20140804/1407121138d.hatena.ne.jp

乱数調整する際の問題点

今回の問題点は消費数が多すぎるものがあることです (184消費とか). 一般的に使われる消費法で消費数が多いものは「連れ歩いている眠り状態のポケモンに話しかける(消費数: 4)」ですが, この消費法を用いても40回以上は眠り状態のポケモンに話しかけなければなりません. しんどいですね.

そこで, オーキドはかせのポケモンこうざを用いた消費法をお勧めします. この消費法であれば毎秒30消費以上を実現することができます *2. 便利〜.

こちらもツールの使い方は以下の外部サイトを参考に. ameblo.jp

ちなみに僕はウツギ博士に電話をするのに飽きたので乱数調整はしません *3. 誰か代わりにやって動画を上げてくれると @mizdra が喜びます.

おわり.

最後に

Pokémon RNG Advent Calendar 2016が全日埋まりそうでで嬉しさと驚きを感じています. 非常にマイナーな分野でそれに関わる人も少ないので全日埋まるとは全く想像もしていなかった…

それとつい先程, 最新作のSMの孵化乱数調整が実機で可能になったようです. めでたい 🎉🎉🎉

セーブデータの解析を行わずにSM孵化用乱数列のseedを特定することに成功しました
— さき@隠居 (@water_blow) 2016年12月11日

これに関する詳細な記事は後ほど公開されることでしょう. 楽しみですね.

明日は oupo さん担当の「TinyMTの逆算」です.

*1:任意の乱数から初期Seedを求めるライブラリ無かったので手書きする羽目になった. 誰か作ってくれ.

*2:ちなみにこれは自分の図鑑のコンプ状況をツールに入力しなければならないのでそこだけは面倒です. 一度ツールに入力してしまえば後はそれを再利用することが可能なのでやっておくと良いと思います.

*3:電話掛けてる時よりプログラム書いてる時のほうが5000兆倍楽しい

2016-12-01

乱数調整入門

ポケモン programming 第四世代

はじめに

この記事はPokémon RNG Advent Calendar 2016 一日目の記事です🎉🎉🎉

www.adventar.org

この記事では主にコンピュータゲームで話題になっている乱数調整について, ポケモンを例に説明します. 以下の方々を対象にした入門的な記事になっています.

乱数調整という言葉を初めて聞いた人
乱数調整という言葉を聞いたことはあるが, その意味や具体的な手順を知らない人
乱数調整をやってみたいと思っているが, 手を出せずにいる人

ポケモンのゲームシステム, 16進数表記, ビット演算を知っている/理解できる前提で書いています. ご了承下さい.

わかりやすさを優先して一部現実と異なる事が書かれている場合があります. 誤字や重大な間違いを発見した場合は修正しますのでこの記事のコメントもしくはTwitterのリプライにてお気軽にご連絡下さい.

「乱数調整」とは

記事のタイトルを見て, 「乱数調整って何だろう?」と疑問に思った方もいるでしょう. 本記事では「乱数調整」の仕組みを理解し, 実際に乱数調整を行ってみることを想定したものとなっています. 「乱数調整」について説明する前に「乱数」について軽く学習しましょう.

「乱数」とは

「乱数」とはサイコロの出目のように規則性がなく予測不能な数のことです. サイコロを例にとって考えてみます. サイコロを数回振ると, 1, 3, 4, 3, 2, 6, 1, ... というように1~6の出目を得ることができます. 一般に, サイコロの出目には規則性が無く, 得られる値はでたらめに並んでいます. このように, でたらめに並んだ数列を「乱数列」と言い, その数列の元を「乱数」と言います*1. 乱数列はそれ以前の数から次の数を予測することが出来ないという特徴があります.

1回目	2回目	3回目	4回目	5回目	6回目
2	4	6	4	4	1

7回目	8回目	9回目	10回目	11回目	12回目
3	4	5	5	6	?

※ サイコロを11回振った時の出目を表にしました*2. 1 ~ 11回目の出目に規則性が無く, 12回目の出目を予測することは出来ません.

乱数の種類

ここで, コンピュータで乱数を扱う方法を紹介します. 詳しい説明は省きますが *3, コンピュータは確定的な計算を用いてしか乱数を生成することが出来ません. 以下にコンピュータ上での具体的な乱数の計算例を示します.

S[0] = 0
S[n+1] = (3 * S[n] + 5) % 7
S = { 5, 6, 2, 4, 3, 0, 5, 6, 2, 4, 3, 0, 5, 6, 2, 4, 3, 0, 5, 6, ... }

この乱数生成法は「線形合同法(LCG)」と呼ばれ, 漸化式を用いた簡易的な乱数生成法の1つです*4.

線形合同法は適当な初期値からスタートして、次の漸化式で乱数を生成します。

X[i] = (A * X[i-1] + C) mod M

これで 0 以上 M 未満の値を生成することができます。A, C, M の選び方は参考文献 [2] より引用します。

M が 2 の累乗なら A mod 8 を 5 または 3 とし（5 の方が安全）、定数項 C を奇数とする。このとき、周期はちょうど M となり、その 1 周期分には 0 から M - 1 までの整数が 1 個ずつ現れる。

高速にするには C = 0 とし、初期値 X0 を奇数にする。ただし、周期は M / 4 になる。

サービス終了のお知らせ

S[0] は乱数列の初項で, 初期Seed, もしくはSeedと呼ばれます. 乱数列は初期Seedと漸化式を用いて逐次的に求められます. このように確定的な計算によって得た乱数を擬似乱数*5, 対してサイコロのような確定的な計算以外で得た乱数を自然乱数と区別して呼びます. 擬似乱数生成法には漸化式以外を用いたものもありますが, 漸化式を用いた擬似乱数生成法には以下のようなメリットがあり, コンピュータと相性が良いのでこの方法が主流です.

漸化式と初期Seedを記録しておけば、誰でも同じ数列を再現できる (注: ある乱数列を再現するために全ての項を記録しておく必要がない)

(コンピュータ上での計算が)高速で低コスト

あなたの使っている乱数、大丈夫？-危ない標準乱数と、メルセンヌ・ツイスター開発秘話-

初期Seedは乱数列を決定する重要な要素の1つで, 出来るだけ乱雑な値になるように設定されます. 通常は乱数生成器を起動した時刻などを元に設定されます.

擬似乱数列は確定的な計算によって生成されているので, それを構成する各乱数の値を算定することが可能です. 事前に擬似乱数列を構成する個々の乱数を求めることができれば, それらを基に決定される事象を予測し, 狙った事象を発生させることも可能となります.

改めて「乱数調整」とは

乱数を軽く理解できたところで改めて乱数調整の意味について説明します. 乱数調整とは「 次に得られる乱数を予測し, 狙った乱数を得ること 」を指します. 先程のサイコロの例で考えるならば, 何かしらの手法で12回目のサイコロの出目を事前に予測し, 実際に予測した出目を得ること, これが乱数調整です.

実際にはサイコロの出目のような自然乱数を予測することは神でもない限り出来ないので, 算定可能な擬似乱数を対象に乱数調整が行われます.

乱数調整は「 事象を予測し, 狙った事象を発生させること 」といったようにもっと広義的に捉えられる場合もあります*6. これは調整する対象を乱数から事象(将来発生する事象)に拡張しただけです. これは調整する対象をミクロな見方をするか/マクロな見方をするかの違いです. この記事ではポケモンにおける乱数調整で一般に利用されている後者の意味で乱数調整を捉えます.

ポケモンで使用される乱数生成法

乱数調整の言葉の理解が深まったところでポケモンでどのように乱数が扱われているかを見ていきましょう!

使用するハードウェア, ソフトごとに乱数生成法が異なりますが, 今回は DS Lite + ポケットモンスターハートゴールド(HG)を使用します. ポケモンシリーズで使用される乱数生成法の多くはネットのえらい人たちが既に調べてくれているのでわざわざ自分で調査する必要はありません. えらい人たちに感謝 🙏

HGでは以下で定義される線形合同法によって乱数が生成されています.

frame  := フレーム (0 ＜ frame)
year   := 年 (2000 ≦ year ≦ 2099)
month  := 月 (1 ≦ month ≦ 12)
day    :=  日 (1 ≦ day ≦ 31)
hour   := 時間 (0 ≦ hour ≦ 23)
minute := 分 (0 ≦ minute ≦ 59)
second := 秒 (0 ≦ second ≦ 59)

S[0]   = (((month * day + minute + second) * 0x1000000)
         + (hour * 0x10000)
         + (frame + year - 2000)) % 0x100000000

S[n+1] = (0x41C64E6D * S[n] + 0x6073) % 0x100000000

年, 月, 時間, 分などの日時はゲームで「つづきからはじめる」を押した瞬間のハードに設定されている日時が用いられ, frame はDSを起動してソフトを選択し, ゲームが起動した瞬間から「つづきからはじめる」を押した瞬間までの時間をフレーム*7(単位の記号はF, 1秒≒60F)という単位に換算したものです. ただし実際には, DSのメニューからソフトを選択し, 起動するまでに350F(約5.8秒)のラグが発生 *8 しており, その時間は frame に含まれないことに注意して下さい. また, ゲームの仕様によりフレームは2ずつしか増加しません.

f:id:mizdra:20161206214959j:plain

例えば, 僕が今この文章を書いている2016年11月26日3時10分10秒*9にDSのメニューからゲームを選択し, 2016年11月26日3時10分40秒に「つづきからはじめる」を押したとすると, 初期Seedは以下のようになります .

frame  = (40s - 10s) * 60F - 350F = 1450
year   = 2016
month  = 11
day    = 26
hour   = 3
minute = 10
second = 40

S_0    = (((month * day + minute + second) * 0x1000000)
         + (hour * 0x10000)
         + (frame + year - 2000)) % 0x100000000
       = 0x500305BA

実擬似乱数列

LCGで生成される乱数にはとても不思議な特徴があります. ここでLCGの漸化式を見てみましょう.

S[n+1] = (0x41C64E6D * S[n] + 0x6073) % 0x100000000

0x41C64E6D, 0x6073 は両方とも奇数であることに注目して下さい.

奇数*偶数+奇数 は奇数
奇数*奇数+奇数 は偶数

より, なんとこの擬似乱数列は 偶数, 奇数, 偶数, 奇数, ... を繰り返してしまいます! 不思議ですね! これはよく知られたLCGの欠点の1つで, 最下位bitが 0, 1 を繰り返すというものです.

UNIX の /usr/ucb/cc を解析した結果、 rand( ) は以下の動作をすることがわかった。

static long x=1;

void srand(long s) { x=s; }

long rand() { x=x*1103515245+12345; return x&2147483647; }

これは、非常にシンプルな線形合同法である。この乱数の最下位ビットは0と1の繰り返しになる。すなわち、偶数と奇数が交互に生成される。このことから、この乱数で下位ビットを乱数として使うのは危険であることがわかる。また、ある乱数が得られたら、次に現れる乱数が１種類しかないという欠点も持つ。

良い乱数・悪い乱数

これを知らずにLCGで生成された生の乱数を使用すると大きな偏りが生じてしまうので *10 , ポケモンでは S[n] >>> 16 (>>> は0 埋め右シフト) を擬似乱数として使用しています. 本記事では説明のために実擬似乱数列 r[n] = S[n] >>> 16 と定義しておきます (様々な乱数調整関連の記事で r[n] という式自体は出てきますが, それに名前が付いてなくて不便なので勝手に僕が名付けました).

乱数の消費

ポケモンでは新しい乱数が生成されたとき, 「乱数が消費された」と言い, 乱数生成器で乱数が生成される度に乱数が消費されていきます. 乱数が2度生成された場合は2回乱数が消費され, 「乱数が2消費された」「2F消費された*11」といった表現が使われます.

以下に乱数を消費する事象の代表的な例を示します.

消費数	事象
1	ウツギ博士に電話を掛ける(通話内容の決定で乱数が消費される)
1	NPCが振り向く/移動する*12 (NPCが振り向く向き, 静止時間の決定)
1	録音した音声を鳴き声として設定したペラップの鳴き声を聞く(鳴き声を聞く度に音の高さが変わる, 音の高さの決定で乱数が消費される)
2	たんパンこぞうゴロウに電話を掛ける(電話内容自体に疑似ランダムな要素はありませんが, 内部で乱数生成器によって2F消費されています)
4	連れ歩いている眠り状態のポケモンに話しかける(上と同じく疑似ランダムな要素はありませんが, 内部で乱数生成器によって4F消費されています)
`徘徊ポケモンの数` 以上	「つづきからはじめる」を押してゲームを再開する(徘徊ポケモン*13の出現ポイント決定に乱数が消費される, ゲーム再開前後で徘徊ポケモンの出現ポイントが同じになったとき出現ポイントの再決定が行われる, ゲーム再開時に自動的に消費が行われるので強制消費と呼ばれます)
手持ちポケモンの数	128歩歩く(128毎歩くたびに行われる手持ちポケモンのなつき度判定で乱数が消費される)
12以上	ラジオのチャンネルをオーキドはかせのポケモンこうざに切り替える(詳細: オーキドはかせのポケモンこうざ - oupoの日記)

これらの乱数消費法を用いることで, 自分の好きな回数だけ乱数を消費できます.

ウツギ博士との電話で乱数調整

「消費」という概念, 上の説明だけでは分かりにくいですね... 実際にウツギ博士に電話を掛けて消費がどんな操作であるのかを確認しましょう.

準備

ウツギ博士が電話で話す内容はストーリーの進行具合によって変わってくるのですが, 今回は以下の条件の元でやってみます.

殿堂入り前にウツギ博士にトゲピーを見せ, 変わらずの石を貰っている
殿堂入りをしている
ポケルスに感染した個体、もしくは感染した後完治した個体をポケモンセンターで回復させたことがある

この条件下では, ウツギ博士が電話で話す内容が3種類に固定され, 電話をする度に r[n] % 3 で対応するメッセージが決定されるようになります.

`r[n] % 3`	メッセージ(先頭のみ)
0	ポケモンのしんかというのは～
1	カントーにはまだぼくの〜
2	ポケルスがくっついた～

今回は先程計算した初期Seed 0x500305BA で乱数調整を行います. 初期Seed 0x500305BA での n = 20 までの乱数列は以下のようになります.

n	`S[n]`	`r[n]`	`r[n] % 3`	メッセージ(先頭のみ)
0	0x500305BA	0x5003	2	ポケルスがくっついた～
1	0xA4E47CA5	0xA4E4	2	ポケルスがくっついた～
2	0x1FE1B8B4	0x1FE1	1	カントーにはまだぼくの〜
3	0xE89ADD17	0xE89A	2	ポケルスがくっついた～
4	0x1017853E	0x1017	0	ポケモンのしんかというのは～
5	0xD090FFD9	0xD090	1	カントーにはまだぼくの〜
6	0xF6876DD8	0xF687	0	ポケモンのしんかというのは～
7	0x0831F56B	0x0831	0	ポケモンのしんかというのは～
8	0xB1CE7902	0xB1CE	2	ポケルスがくっついた～
9	0xB754824D	0xB754	0	ポケモンのしんかというのは～
10	0x233D513C	0x233D	0	ポケモンのしんかというのは～
11	0xC0443EFF	0xC044	2	ポケルスがくっついた～
12	0x207AE506	0x207A	1	カントーにはまだぼくの〜
13	0xEEBFB801	0xEEBF	0	ポケモンのしんかというのは～
14	0xA37806E0	0xA378	1	カントーにはまだぼくの〜
15	0x5D738DD3	0x5D73	1	カントーにはまだぼくの〜
16	0x439C0D4A	0x439C	1	カントーにはまだぼくの〜
17	0x66BA94F5	0x66BA	0	ポケモンのしんかというのは～
18	0x015272C4	0x0152	2	ポケルスがくっついた～
19	0x36AAF5E7	0x36AA	2	ポケルスがくっついた～
20	0x356175CE	0x3561	0	ポケモンのしんかというのは～

ポケモンでは S[0] は疑似ランダムな事象を決定するためには用いられず, S[1] 以降が用いられます. つまり, ゲームを再開して初めて生成される乱数は S[1] となります. また, 僕が乱数調整を行うHGは徘徊ポケモンが3匹いるので, ゲーム再開時に自動的に3~6F消費されます. よって初めにウツギ博士に電話を掛けるときに使われる乱数は S[4], S[5], S[6] のどれかです.

乱数調整する際は出来るだけ不定NPC (先程の消費の例で挙げた乱数を消費するNPCのこと) がいない所でやると良いでしょう. 自分が消費している最中にNPCに勝手に消費されてしまっても困りますからね. 不定NPCがいない所であればどこでも良いです. 僕は主人公の部屋でやることにしました. ここで一度セーブしてハードの電源を切りましょう.

f:id:mizdra:20161204182703j:plain

トロフィーコンプしてないことがバレてしまう…

初期Seedを合わせる

初期Seed 0x5003048F に合わせるには2016年11月26日3時10分10秒にDSのメニューからゲームを選択し, 2016年11月26日3時10分40秒に「つづきからはじめる」を押す, でしたね. 以下の手順で初期Seedを合わせましょう.

エメタイマーで30秒間のタイマーをセットする
ハードの電源を入れ, 本体設定パネル > 日付&時刻パネル > 日付パネル 及び 本体設定パネル > 日付&時刻パネル > 時刻パネル からハードの日時・時刻を2016年11月26日3時10分0秒に設定する
直ぐにハードを再起動し, 上画面の時計の針が10秒を指した直後にHGを選択する. 同時にエメタイマーを起動する.
「つづきからはじめる」ボタンの画面で待機し, エメタイマーのカウントが0になったらボタンを押す
ゲームが再開したらポケギアのマップを開き, 徘徊ポケモンの位置から初期Seedを特定する
初期Seedが目標のものと異なっていたらずれを確認し, タイマーにずれを反映させて 2 に戻る. 一致すればそこで終了.

「エメタイマー」, 「徘徊ポケモンの位置」のあたりを解説します.

1. エメタイマーで30秒間のタイマーをセットする

ポケモンでは frame を合わせるためにエメタイマーと呼ばれるタイマーをよく使います *14. これは乱数調整用に開発されたタイマーでフレーム⇛秒変換機能など乱数調整を補助する様々な機能が付いています.

ポケモンの館エメループ

使い方はサイトの下部にある説明を読めばわかります. 今回は30秒間待機したいので「時間」欄に「30」と入力しました.

f:id:mizdra:20161204190438p:plain

5. ゲームが再開したらポケギアのマップを開き, 徘徊ポケモンの位置から初期Seedを特定する

「乱数の消費」の項でも取り上げましたが, 徘徊ポケモンの位置の決定には S[1] 以降の任意の個数の乱数が使われます (徘徊ポケモンが3匹の場合). これを利用して徘徊ポケモンの位置からどの初期Seedを引いたのかある程度絞ることが出来ます. 「HGSS徘徊初期seed確認」というツールを使ってみましょう.

HGSS徘徊初期seed確認

セーブ直前の位置

セーブした直前での徘徊ポケモンの位置を <ライコウの位置>,<エンテイの位置>,<ラティアスの位置> の形式で入力します. 位置は 29ばんどうろ だったら 29, 21ばんすいどう だったら 21 といったように数値で指定します. 今回は 32ばんどうろ,29ばんどうろ,5ばんどうろ だったので 32,29,5 と入力しました.

ロード後の位置

ソフトを再開したときの徘徊ポケモンの位置を入力します. 形式は「セーブ直前の位置」欄と同じです.

目標初期seed

合わせたい初期Seedを入力します. 今回は 0x500305BA と入力しました.

下4桁の範囲

徘徊ポケモンの位置を検索するの初期Seedの範囲を, 初期Seedの下4桁の範囲で決めます. 「つづきからはじめる」を押した日時・時刻が固定であれば初期Seedの上位4桁は固定なので, 基本的に下4桁のみが変動します. 今回は 0x500 ~ 0x5D0 と入力しました.

実際にこの手順でやると, ゲーム再開後の徘徊ポケモンの位置は 29,45,3 となりました. これを先程の「ロード後の位置」に入力して「計算」ボタンを押すと以下の出力が得られました.

f:id:mizdra:20161204203327p:plain

これより, 目標の初期Seed 0x500305BA に対して 0x500305A0 を引いていたことがわかります. 下4桁の差を取ると 0x05BA - 0x05A0 = 26 となり, 待機時間が 26F 短かったことになります. ちなみに括弧の中に表示されている数はその初期Seedでの強制消費数を表しています. つまり, 目標の初期Seed 0x500305BA での強制消費数は3F, 初めにウツギ博士に電話を掛けるときに使われる乱数は S[4] となります.

次に待機時間のずれをタイマー側にも反映させましょう. 30秒間の待機時間を 26F だけ延長したいので 30s * 60 + 26F = 1826F で 1826F を待機時間として設定すれば良いことになります.

f:id:mizdra:20161204204323p:plain

この設定でもう一度 2~5 の操作をやってみたところ, 見事徘徊ポケモンの位置が 33,30,22 となり, 初期Seedを 0x500305BA に合わせることに成功しました!

めでたい! 🎉🎉🎉

f:id:mizdra:20161204210441j:plain

今回は2回目のチャレンジで初期Seedを合わせることに成功しましたが, 1/60秒間隔での操作が要求されるので割りとシビアです. いつかは成功するのでめげずに何度も挑戦してみましょう.

ここまでの操作をおさらいします.

エメタイマーで30秒間のタイマーをセットする
ハードの電源を入れ, 本体設定パネル > 日付&時刻パネル > 日付パネル 及び 本体設定パネル > 日付&時刻パネル > 時刻パネル からハードの日時・時刻を2016年11月26日3時10分0秒に設定する
直ぐにハードを再起動し, 上画面の時計の針が10秒を指した直後にHGを選択する. 同時にエメタイマーを起動する.
「つづきからはじめる」ボタンの画面で待機し, エメタイマーのカウントが0になったらボタンを押す
ゲームが再開したらポケギアのマップを開き, 徘徊ポケモンの位置から初期Seedを特定する
初期Seedが目標のものと異なっていたらずれを確認し, タイマーにずれを反映させて 2 に戻る. 一致すればそこで終了.

乱数を消費する

初期Seedを合わせ終わったので後は乱数を消費するだけです. 17回電話を掛けた場合 *15, 上で計算した乱数列から次の順番でメッセージが流れるはずです.

n	`S[n]`	`r[n]`	`r[n] % 3`	メッセージ(先頭のみ)
4	0x1017853E	0x1017	0	ポケモンのしんかというのは～
5	0xD090FFD9	0xD090	1	カントーにはまだぼくの〜
6	0xF6876DD8	0xF687	0	ポケモンのしんかというのは～
7	0x0831F56B	0x0831	0	ポケモンのしんかというのは～
8	0xB1CE7902	0xB1CE	2	ポケルスがくっついた～
9	0xB754824D	0xB754	0	ポケモンのしんかというのは～
10	0x233D513C	0x233D	0	ポケモンのしんかというのは～
11	0xC0443EFF	0xC044	2	ポケルスがくっついた～
12	0x207AE506	0x207A	1	カントーにはまだぼくの〜
13	0xEEBFB801	0xEEBF	0	ポケモンのしんかというのは～
14	0xA37806E0	0xA378	1	カントーにはまだぼくの〜
15	0x5D738DD3	0x5D73	1	カントーにはまだぼくの〜
16	0x439C0D4A	0x439C	1	カントーにはまだぼくの〜
17	0x66BA94F5	0x66BA	0	ポケモンのしんかというのは～
18	0x015272C4	0x0152	2	ポケルスがくっついた～
19	0x36AAF5E7	0x36AA	2	ポケルスがくっついた～
20	0x356175CE	0x3561	0	ポケモンのしんかというのは～

動画を取りました.

ウツギ博士乱数

確かに上の表の通りにメッセージが流れています. 乱数調整成功です. 👏👏

ウツギ博士との電話で乱数調整その2

ただ予想通りにメッセージが流れただけではつまらないのでもう少し高度なことをしてみましょう. 今度は,

ウツギ博士が「ポケモンのしんかというのは～」というメッセージを15回以上連続で話す

ことを乱数調整してみます. ウツギ博士に進化について熱く語ってもらいましょう.

乱数と初期Seedの計算

まず目的のメッセージを15回以上連続で話す乱数 S[n], 及びその初期Seedを計算しなければなりませんね. 本来であれば既存のツールを使って計算…といきたいところですかこんなどうでもいい乱数調整のためのツールなんかあるはずがありません. ではどうするか. 無いなら作ってしまいば良いのですよ. ✨😉☝️

という訳でサクッとC++で目的の乱数と初期Seed, 必要な消費数を出力するプログラムを書きました. ﾌﾟﾛｸﾞﾗﾐﾝｸﾞﾁｮｯﾄﾃﾞｷﾙな皆さんなら当然書けますよね???

ウツギ博士にポケモンの進化について熱く語ってもらう.

# ソースコードをclone
$ git clone https://gist.github.com/faf3c48f67d999fc8072795e6c67a901.git abuse-dr-utsugi

# コンパイル
$ cd abuse-dr-utsugi
$ g++ AbuseDrUtsugi.cpp -o AbuseDrUtsugi.exe -std=c++11

# 実行
$ ./AbuseDrUtsugi.exe
  n        S[n]        S[0]
 10  0X23E5E254  0XD2160812
  5  0X2A991401  0X89070502
  9  0X3B4F3C64  0X96010A6D
  4  0X72038E62  0X4114049E
  5  0X7B215E11  0XE8040852
  6  0X810C32E0  0X89070502
  5  0XA2B1DC2D  0X4114049E

いくつか初期Seedの候補か出力されましたが, ここでは初期Seed 0x89070502 を狙います. 先程と同様に手計算で起動時刻を求めました.

DSメニューからゲームを選択: 2099年5月20日7時2分10秒
待機時間: 1533F
「つづきからはじめる」を選択: 2099年5月20日7時2分35秒

初期Seedを合わせる

エメタイマーは以下のように設定しておきます.

f:id:mizdra:20161205191833p:plain

僕の場合はセーブ直前での徘徊ポケモンの位置が 32,29,5 だったので「HGSS徘徊初期seed確認」には以下のように設定しました.

f:id:mizdra:20161205193404p:plain

1回目

徘徊ポケモンの位置は 30,31,12 でした.

f:id:mizdra:20161205194342p:plain

0x502 - 0x4ee = 20 より, 待機時間を 20F 延長し, エメタイマーに 1553F を設定しました.

f:id:mizdra:20161205193712p:plain

2回目

徘徊ポケモンの位置は 30,32,9 でした.

f:id:mizdra:20161205194006p:plain

おや…? 徘徊ポケモンの位置を正しく入力したのに初期Seed候補が出力されませんね. ここで左下にある「秒のずれを許容」にチェックを入れて秒や分のずれを考慮した初期Seed候補検索をしてみましょう.

f:id:mizdra:20161205194559p:plain

初期Seed候補 0x8a070500 が出力されました. ここで, 0x8a - 0x89 = 1 より, 「つづきからはじめる」を押した時刻が1秒遅れたと推測されます. エメタイマーの設定はそのままにして, DSメニューからゲームを選択する時刻を1秒早めて(2099年5月20日7時2分9秒)みます.

3回目

徘徊ポケモンの位置は 29,35,2 でした. 成功です 👍

乱数を消費する

強制消費数は3Fなので, 初めにウツギ博士に電話を掛けるときに使われる乱数は S[4] となります. 乱数列を計算すると, 以下のようになっています.

n	`S[n]`	`r[n]`	`r[n] % 3`	メッセージ(先頭のみ)
0	0x89070502	0x8907	0	ポケモンのしんかというのは～
1	0xDD101E4D	0xDD10	0	ポケモンのしんかというのは～
2	0x05A6BD3C	0x05A6	0	ポケモンのしんかというのは～
3	0xCE0F3AFF	0xCE0F	2	ポケルスがくっついた～
4	0xC0B03106	0xC0B0	2	ポケルスがくっついた～
5	0x2A991401	0x2A99	0	ポケモンのしんかというのは～
6	0x810C32E0	0x810C	0	ポケモンのしんかというのは～
7	0xE2F249D3	0xE2F2	0	ポケモンのしんかというのは～
8	0x1FDA194A	0x1FDA	0	ポケモンのしんかというのは～
9	0x5CCDB0F5	0x5CCD	0	ポケモンのしんかというのは～
10	0x41FD5EC4	0x41FD	0	ポケモンのしんかというのは～
11	0x5B5971E7	0x5B59	0	ポケモンのしんかというのは～
12	0xE57441CE	0xE574	0	ポケモンのしんかというのは～
13	0x51E12929	0x51E1	0	ポケモンのしんかというのは～
14	0xB61F64E8	0xB61F	0	ポケモンのしんかというのは～
15	0x0F8D073B	0x0F8D	0	ポケモンのしんかというのは～
16	0x29E26E92	0x29E2	0	ポケモンのしんかというのは～
17	0x6A05F09D	0x6A05	0	ポケモンのしんかというのは～
18	0xEA45A94C	0xEA45	0	ポケモンのしんかというのは～
19	0x36069DCF	0x3606	0	ポケモンのしんかというのは～
20	0xA200A396	0xA200	0	ポケモンのしんかというのは～
21	0xC821BB51	0xC821	2	ポケルスがくっついた～

よって16連続でウツギ博士がポケモンの進化についての話をしてくれます. 熱いですね.

動画を取りました.

ウツギ博士乱数 (16連続同一メッセージ)

確かに16連続で熱い話をしてくれていますね. 乱数調整成功です 👏👏

この記事で行う乱数調整はこれで終わりです *16. 乱数列を意識しながら乱数調整を行ったので, 疑似ランダムな事象の裏ではどんな計算が行われているのかということをイメージする力が付いたのではないでしょうか. 以下で他にどんなことに対して乱数調整できるのか軽くリストアップしたので是非ご覧になって下さい (色乱数や高個体値ポケモンの乱数はありきたりすぎるのでカットで 👋).

他にどんなことが乱数調整できるの?

自販機乱数のお話 - ろいしんぶろぐ
- ゲーム内に設置されている当たり付き自販機で当たりを出す話(BW1)
ペラップ乱数 - ろいしんぶろぐ
- ペラップ(録音した好きな音声をその鳴き声として設定出来る, 鳴き声を発する度に音の高さが変わる)というポケモンの鳴き声の音の高さを調整して素敵な音を奏でる話(BW1)
いかにして乱数調整を成功させるか: IDくじでマスボ回収の効率化
- IDくじ(引いたIDが持っているポケモンのIDに一致していれば景品がもらえる)で特等の景品を当てる(BW1)
バトルサブウェイ乱数補助ツール : ただの雑記byさき
メロメロボディを利用した野生乱数 : ただの雑記byさき

面倒になってきたので雑にいきます.

ミツルくん、色ラルトスを捕まえるの巻 pic.twitter.com/U63jJg1Esu
— 夜綱 (@sub_827) 2014年11月15日

「せっかく3世代乱数できるようになったのに…」とお嘆きのあなた！これを機に3世代乱数沼に嵌ってみませんか！？ pic.twitter.com/3QXh3ObVmS
— 夜綱 (@sub_827) 2015年11月10日

d.hatena.ne.jp

僕がパッと思いついたのはこれくらいですが, これは入れるべきというものがあれば教えてください 🙏

乱数調整の勉強する際に参考になるサイト

BW乱数調整まとめ - ふちのgdgd日記
- 第五世代の乱数調整について一通りまとまっています
no pain,no gain
- 第三世代 ~ 第五世代, XDなど様々な世代の乱数調整に関する記事があります.
http://tellu.wpblog.jp
- XDの乱数調整について非常に詳しい記事があります
- なんとXDの乱数調整記事は英語版のものもあります
- 第三世代やXDの乱数生成の仕組みについての記事も
さびたコイルのページ
- 乱数調整用のツールや解析情報が置いてあります
218番道路で高個体値メタモンを探すスレまとめWiki - アットウィキ
- 第三世代の乱数調査スレのアーカイブ
ポケットモンスター情報センター 2号館1階(ロビー)
- 第三世代の乱数調査に関する情報があります
- 一部のブラウザでは表示が崩れてまともに見れないのが難点
ゴン’ｚキッチン！
XD乱数調整のやり方
BW乱数調整まとめ - ふちのgdgd日記

上に同じく, これは入れるべきというものがあれば教えてください 🙏🙏🙏

おわりに

以上が Pokémon RNG Advent Calendar 2016 1日目「乱数調整入門」となります. ここまで読んでくださった方々, ありがとうございます! お疲れ様でした! 😃

期限までに書ききることができなかったのは残念 *17 ですが, Pokémon RNG Advent Calendar 2016 では興味深い記事が次々と投稿されてきています. 残りの日も Pokémon RNG Advent Calendar 2016 で楽しんでいきましょう!

www.adventar.org

2日目は @sub_827 さんの担当です!

*1:つまり, 「乱数」とは規則性がなく予測不能な数のことです.

*2:家からサイコロ探し出して1人で転がしてました

*3:僕はこのあたりのことについて詳しくないので何も言えません

*4:他にもメルセンヌ・ツイスタ法やカオス乱数などがあります. (参考: http://www.nt-s.ne.jp/product/campain/knowledge/missing-number.html)

*5:後ほど述べますが, 擬似乱数は算定可能なので予測不能な数では無い, 乱数ではないとも言われています

*6:調整するのは「乱数」であり「事象」ではないので厳密には間違っています

*7:Frameの原意は動画を構成する一枚一枚の静止画（コマ）のことで, ポケモンにおける乱数調整では経過時間を表す単位として用いられます

*8:参考: 雪の舞う夜に。 : 【乱数調整】空白時間の測定【HGSS・DPPt】

*9:何でこんな時間に記事を書いているんでしょうね...

*10:うっかり「乱数ではない乱数のようなもの」を使わないよう, 乱数を扱うときはその乱数生成法の利点と欠点についてよく調べておきましょう

*11:描画処理1Fにつき乱数が1消費されることから、消費される乱数の個数を数える際にFを単位として用いる慣習があります

*12:一定時間ごとに決まった向きに振り向くなど周期的な動作をするNPCは乱数を消費しません

*13:"徘徊系ポケモン（はいかいけい－）とは、出現ポイントがある条件によってマップ上を移動する伝説のポケモンのこと。" http://wiki.xn--rckteqa2e.com/wiki/%E5%BE%98%E5%BE%8A%E7%B3%BB%E3%83%9D%E3%82%B1%E3%83%A2%E3%83%B3

*14:Flash製のツールです. 時代を感じますね…

*15:17回も連続で電話をかけるだなんて主人公も迷惑な野郎ですね

*16:撮影しながらの乱数調整しんどかった…

*17:今日 (記事公開日) は12/6 です. 大遅刻してしまって本当に申し訳ありません 🙇

2016-09-12

巻き爪の治療

たまには技術以外のテーマの記事を。

長年悩まされていた巻き爪が治りつつある。

巻き爪については以下のサイトで簡単に把握できる。爪の端が内側に巻く症状で、皮膚に食い込んで痛みを伴ったりする。

dr-nail.jp

僕の場合は巻き爪の中でも陥入爪に当たるもので、(記憶が定かではないが)3年以上前に左足の親指に発症した。当時授業で行っていたサッカーで負荷を掛け過ぎたり、(運悪く)よく足をモノにぶつけたりして患部が腫れ、そこに爪が食い込んだのが原因だと思う。

歩いたり走ったりする分には痛みはないが、親指に体重を乗せたり、患部をモノにぶつけたりするとガラスの破片で刺されたような痛みが伴う。特に体育なんかは最悪で、親指に異常なくらい負荷が掛かるので毎回痛みに怯えながらやってる。サッカーとかまともに出来ない。というか情報系の学部なのに何で体育あるんだ。わけわからん。

発症した当初は放っておけば治るだろうという安直な考えでいたが、次第に悪化していったので発症から一年経過した頃に病院で診てもらった。そこでは毎日テープで爪が食い込んでいる皮膚を爪から引き離し、開いた隙間に薬を塗るよう指導された。この治療を数ヶ月間継続した結果、少々腫れてはいたものの痛みが殆ど無いレベルまで落ち着いた。

が、当時の僕はそこで満足して以降通院をやめてしまった。これが失敗だった。通院をやめてからというものの少しずつ腫れが酷くなり、数カ月後には元に戻るどころか以前より強い痛みを伴う状態になってしまった(今から半年前の話)。これではマズいと思った僕は再び病院で診てもらい、再びテープによる治療を再開した。この時、応急処置として患部に食い込んでいた爪の端を切ってもらった*1。痛みの強さも頻度も低下してすごく楽になった。以降テープによる治療を継続し、今に至る。

現状、患部に触れても痛みが無い程度まで回復することができた。実を言うとテープを貼る作業を結構サボっていたので毎日きちんとやっていれば治療に3年なんかも掛かってなかったと思う。サボり癖って言うのかな。改善していきたい。

怪我とか病気とかって放置すると時間も金もその他諸々消費するし、ろくな事無いなって改めて思った。この調子で今度こそ完治させるぞ。

「痛いけど我慢できる、いつか自然に治るだろう」という自己判断をするのは危険です。放置したことによって更に悪化する場合は決して少なくはありません。 http://dr-nail.jp/treatment/makidume

別の話になるけど巻き爪と同じく3年前くらいに発症したアレルギーが原因で林檎、梨、桃、柿、枇杷、生海老を食べると喉が痒くなる症状があったが、梨であれば食べても痒くなっていたことが数週間前に判明した*2。梨は大好物だったので本当に嬉しい。これが徳を積んだ結果か。:pray:

*1:切断に使ったハサミが「力こそパワー💪」みたいなやつでちょっと怖かった

*2:梨以外も今度試したい

2016-08-21

夏のCLI commandsものまね大会 ~ls編~

「そこは〇〇では?」、「ここはこうしたほうがいいんじゃない?」等の優しいマサカリ🔪は大歓迎です。よろしくお願いします。

仕様

ls <dir>を真似る
オプションは-a, -Fに対応する
複合オプション-aFに対応する

リポジトリ

github.com

使い方

$ npm install -g mizdra/node-ls
$ node-ls --help

  Usage: node-ls [options] <dir>

  Options:

    -h, --help      output usage information
    -V, --version   output the version number
    -a, --all       include hidden files and directories
    -F, --classify  classify files and directories

$ node-ls -aF sample-dir
./
../
.hidden-dir
.hidden-file
fifo|
sock=
sock-symlink@
visible-dir/
visible-dir-symlink@
visible-file
visible-file-symlink@
x-666-file
x-677-file*
x-767-file*
x-776-file*
x-777-file*
x-777-file-symlink@

感想

lsの挙動についてちょっとだけ詳しくなった
- -Fオプションはただディレクトリの名前の末尾に/を付けてくれるだけだと思ってた
  - 実際にはディレクトリに/, シンボリックリンクに@, 実行可能ファイルに*, UNIX ドメインソケットに=, FIFO(名前付きパイプ)に|が付く (環境依存)
Unixのファイルシステムについてちょっとだけ詳しくなった
- UNIX ドメインソケットとかFIFOとか初めて知った…
tj/commanderjsがとにかく便利
- オプションとか引数を良い感じにパースしてくれる
- しかしAPI documentationがあまりにも不親切
  - 引数の型が書いてないAPIがある
  - descriptionが分かりにくい
  - サンプルコードがないAPIがある
  - 酷いものに至っては、分かりにくいdescriptionとそのAPIを実装するメソッドのソースコードが貼られただけ
  - 仕様がきちんと決まってないとある挙動がバグなのか判別することすらできないと思うんだけど、どうしてこうなってるんだろう…
  - 散々愚痴を書いてますがtj/commanderjsそのものは素晴らしいライブラリだと思ってます!
Array#{filter,map}を使ったら良い感じに書けた
- 複合オプション-aFにも対応できた
- Arrayすごい
  - こういうのってStreamって言うんだっけ
コマンドのパースをbin/command.js(このプロジェクトではbin/node-ls.js)に集約してみた
- lib配下はCLI非依存の処理、bin配下はCLI依存の処理に分けたら綺麗そうだなと思ってやってみた
- 個人的には割りと綺麗にみえる
- 他のプロジェクトを参考にしつつbin/command.jsの設計についてもう少し考えてみたい
- 参考になりそうなプロジェクト: babel-cli, webpack/webpack, gulpjs/gulp, mysticatea/npm-run-all, mochajs/mocha, etc.
エラーを処理してない(面倒だった)
- 次回以降はちゃんとエラー処理したい
テストを書いてない(面倒だった)
同期メソッド(fs.*Sync)を使って書くと楽だった
- 最初は非同期メソッドを使って書いていた
- 1ファイルごとに1つの非同期メソッドを呼び出す === 複数の処理が並列で実行される
- 制御が難しくなってきた
- デバッグも難しくなってきた
- つらくなってきた
- だいぶ書いてから気づいたけどArray#{filter, map}に上手く非同期メソッドを埋め込めない
  - [..].filter(file => asyncFunc(file)).map(..)できない
  - async/awaitがあれば綺麗に書けそう…な気がする (今回はNode.js v6.4.0を使用しているのでトランスパイラ等を使わない限りasync/await使えません!)
    - イメージ: [..].filter(file => await asyncFunc(file)).map(..)
    - でもこれArray#filterがパラレルじゃないからawaitで1ファイルについて処理している時に他のファイルが待たされることになる。つまり駄目
- 非同期って難しい…
- 他のライブラリを組み合わせて上手くできたりしないかな。要調査
  - node-ls-parallelの機運
- 結果: 非同期メソッドやめた
良い感じにモジュール化できた(個人の感想)
- ES6 Modulesスタイルで書いたことはあったけどCommonJSスタイルはまだだった
- ES6 Modulesスタイルと殆ど変わらなかった
- 綺麗にモジュール化できると気持ちいい
  - 久々にちゃんとしたコードを書いた気がする
- 正直モジュール化とかあまり詳しくなくてオレオレで書いているのでちゃんと勉強したい
インストールのチェックはnpm pack, npm install ./*.tgzでやった
- C90で頒布された部誌「百萬石 2016年夏号」の「npmを使う際の傾向と対策」で得た知識
- 悲しい現実です → https://twitter.com/whywaita/status/766589357306159104

終わりに

コーディング途中の僕のツイートです。

簡単そうと言いながらlsコマンドを真似るコードを書きはじめたけど想像以上に時間掛かってる(現在進行形で作業中)
— mizdra (@mizdra) August 18, 2016

次回は多分catをやります。(難易度的にcatを一番最初にやるべきだった気がする)

2016-08-21

夏のCLI commandsものまね大会

「夏のCLI commandsものまね大会」、やります。

概要

ザックリ言うとCLI commandsをNode.jsで実装します。例えば、lsコマンドのようにNode.jsで特定のディレクトリに格納されているファイル一覧を出力するCLI commandを作るといった感じです。

方針

制作していくにあたって方針を立てておきます。

任意のCLI commandsをNode.jsで実装する。
実装は満足する範囲内で行うものとし、全ての機能を実装したり1つの機能を完璧に実装する必要はない。
使用する言語はNode.js(version: 6.4.0)とする。
ES 2015+で書く。
babelやtscなどのトランスパイラを用いても、最終的にNode.jsで実行可能であれば良しとする。
コードは綺麗に時間を掛けて書く。
可能な限りライブラリを使用する。
コードを書き終えたらコーディング中に思ったことや感想などを記事にする。

リンク

夏のCLI commandsものまね大会 ~ls編~ - mizdra's blog

あとがき

頑張ります。

2016-06-18

管理者権限無しでCentOS 6.5上にC++開発環境を作成した時のメモ

大学の講義てC++を書いていて、大学のPC上でもシンタックスハイライトとか補完とかを効かせながらC++コーディングしたいなと思っていた。以下はvimで良い感じのC++開発環境を構築したときのメモ。

目標 & 方針

clangの導入
vimでC++開発
- 補完はvim-clang
- シンタックスハイライトはcolor_coded
sudo権限がなく、yumなどの付属のパッケージマネージャを利用することができないので、自前でビルドし、porgでインストールする
- バイナリは~/localフォルダにインストールする
- ただし、vim プラグインはneobundle.vimを使って.vim/bundleにインストールする

環境

CentOS(x86_64) 6.5
sudo権限を持たないユーザで作業
シェルはtcsh
インストールされているvimでluaが有効になっていない

(大学のサーバなのでセキュリティ上あまり詳しいことは書けない…)

準備

~/localディレクトリを作成し、~/local/binにPATHを通しておく
neobundle.vimを導入しておく

インストールしたもの一覧

欲しいものはllvm, vim-clang, color_codedのみだが、依存パッケージのインストールされていたバージョンが低かったり、そもそもインストールされていなかったりしていたので、合計10個のパッケージを新規インストールすることになった。

porg 0.8 (パッケージ管理に使用)
gcc 6.1.0
python 2.7.11
cmake 3.5.2
llvm 3.8.0 (python 2.7+, gcc 4.7.0+に依存、build時にcmake 3.4.3+が必要)
lua 5.3.2
vim 7.4 (luaに依存)
vim-clang (clang, vimに依存)
glibc 2.17
color_coded (clang, vim 7.4p330+, lua 5.1+, gcc 4.9+, glibc 2.15+に依存)

1から順にインストールしていく。

1. porgのインストール

参考: linuxでソースからインストールしたソフトウェアを管理 - Qiita

$ tar xzvf porg-0.8.tar.gz
$ cd porg-0.8
$ ./configure --disable-grop --prefix=$HOME/local
$ make
$ make install
$ make logme

2. gccのインストール

参考: CentOS6.xでGCC5.2をOS標準の4.4.7と共存できるようにソースビルドした - Qiita

# `ftp.tsukuba.wide.ad.jp/software/gcc/releases/`から最新版のgccをDLする
$ wget http://ftp.tsukuba.wide.ad.jp/software/gcc/releases/gcc-6.1.0/gcc-6.1.0.tar.gz
$ tar xf gcc-6.1.0.tar.gz
$ cd gcc-6.1.0

# 必要なパッケージのDL
$ contrib/download_prerequisites

# ビルド用ディレクトリ作成
$ mkdir ../build
$ cd ../build

# configure
$ ../configure --disable-multilib --enable-languages=c,c++ --host=x86_64-redhat-linux --build=x86_64-redhat-linux --target=x86_64-redhat-linux --disable-libgcj --with-system-zlib --enable-checking=release --prefix=$HOME/local --with-local-prefix=$HOME/local

# ビルド(時間掛かる)
$ make -k -j8 STAGE1_CFLAGS='-march=core2 -O3' BOOT_CFLAGS='-march=native -Os' >& /dev/null && echo "GCCビルド成功" || echo "GCビルド失敗"
$ porg -lp gcc-6.1.0 "make install"

3. pythonのインストール

参考: CentOS6.7にClangをビルド&インストール - Qiita

$ wget https://www.python.org/ftp/python/2.7.11/Python-2.7.11.tar.xz
$ tar xf Python-2.7.11.tar.xz
$ cd Python-2.7.11
$ ./configure --host=x86_64-redhat-linux --build=x86_64-redhat-linux --target=x86_64-redhat-linux --prefix=$HOME/local CFLAGS="-march=core2 -O3"
$ make -j8
$ porg -lp python-2.7.11 "make install"

4. cmakeのインストール

参考: CentOS6.7にClangをビルド&インストール - Qiita

$ wget https://cmake.org/files/v3.5/cmake-3.5.2.tar.gz
$ tar xf cmake-3.5.2.tar.gz
$ cd cmake-3.5.2
$ ./configure --prefix=$HOME/local
$ make -j8
$ porg -lp cmake-3.5.2 "make install -j8"

5. llvmのインストール

参考: CentOS6.7にClangをビルド&インストール - Qiita

# llvmのDL
svn co http://llvm.org/svn/llvm-project/llvm/tags/RELEASE_380/final llvm

# clangのDL
cd llvm/tools
svn co http://llvm.org/svn/llvm-project/cfe/tags/RELEASE_380/final clang
cd ../...

# compiler-rtのDL
cd llvm/tools/clang/tools
svn co http://llvm.org/svn/llvm-project/clang-tools-extra/tags/RELEASE_370/final extra
cd ../../../..

# ビルド用ディレクトリ作成
$ mkdir build
$ cd build
$ cmake -G "Unix Makefiles" -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++ -DCMAKE_ASM_COMPILER=gcc -DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX=$HOME/local -DGCC_INSTALL_PREFIX="${HOME}/local" -DLLVM_PARALLEL_COMPILE_JOBS=8 -DLLVM_PARALLEL_LINK_JOBS=8 -DLLVM_TARGETS_TO_BUILD="X86" ../

# ビルド(すごく時間掛かる)
$ make -j8

$ porg -lp llvm-3.8.0 "make install"

6. luaのインストール

参考: lua-users wiki: Building Lua

$ wget http://www.lua.org/ftp/lua-5.3.2.tar.gz
$ tar zxvf lua-5.3.2
$ cd lua-5.3.2
$ make linux
$ porg -lp lua-5.3.2 "make install INSTALL_TOP=$HOME/local"

# 確認
$ lua -v
Lua 5.3.2  Copyright (C) 1994-2015 Lua.org, PUC-Rio

7. vimのインストール

参考: enable-luaなvim7.4をインストール - Qiita

$ wget https://github.com/vim/vim/archive/master.zip
$ unzip -d vim master.zip
$ cd vim/src
$ ./configure --enable-multibyte --enable-xim --enable-fontset --enable-luainterp --with-features=huge --disable-selinux --prefix=$HOME/local --enable-luainterp=yes --with-lua-prefix=$HOME/local --enable-rubyinterp=yes --enable-pythoninterp=yes --with-python-config-dir=$HOME/local/lib/python2.7/config
$ make -j8
$ porg -lp vim-7.4 "make install"

# 確認
$ ./vim --version | grep +lua
+dialog_con_gui  +lua             +rightleft       +windows

8. vim-clangのインストール

vimのプラグインマネージャを利用すれば簡単にインストールできるので省略。

9. glibcのインストール

参考: CentOS6系にanrdoid-ndk-10eをインストール(ビルドは未検証) - Qiita

$ wget http://ftp.gnu.org/gnu/glibc/glibc-2.17.tar.gz
$ tar zxvf glibc-2.17.tar.gz
$ mkdir glibc-2.17/build
$ cd glibc-2.17/build

# パスが通ってるディレクトリに入れると既存のglibcと競合して不具合が発生するので、ここでは``$HOME/local/glibc-2.17``に入れた
$ ../configure --prefix=$HOME/local/glibc-2.17 --enable-shared --disable-profile --disable-debug

$ make

# 以下を実行するとエラーが発生する。恐らくバグ。今のところ無視しても問題なく動作している。
# $ make check

$ porg -lp glibc-2.17 "make install"

10. color_codedのインストール

vimのプラグインマネージャを利用すれば簡単にインストールできるので、詳細は省略。
ただし、color_codedは使用する前にビルドしておく必要があるが、その際にglib 1.15+へのパスを教えてあげなければ正しくビルドが行えない。
自分はneoBundle.vimを使っていたので以下のように設定した。

NeoBundleLazy 'jeaye/color_coded', {
  \ 'build': {
  \   'unix': 'cmake -DCUSTOM_CLANG=1 -DLLVM_ROOT_PATH=$HOME/local/glibc-2.17 . && make && make install',
  \ },
  \ 'autoload': { 'filetypes' : ['c', 'cpp', 'objc', 'objcpp'] },
  \ 'build_commands' : ['cmake', 'make'],
  \ 'external_commands' : ['clang']
\}

動作確認

適当に.vimrc書いてcppファイルを開いてみた。 f:id:mizdra:20160618170226p:plain ちゃんと動いた。めでたしめでたし。

2016-04-02

LCGでMath.imulのベンチマーク

ES2015にてjs高速化の一環としてMath.imul関数が実装された。本記事では実装されたMath.imulとそのPolyfillのベンチマークをLCG(線形合同法)で取る。

前提

LCGでベンチマークを取っているのでMath.imulの演算処理のみに焦点を当てたベンチマーク結果は取れません。そうした純粋な結果のみを知りたい方はリポジトリをクローンして自分でカスタマイズして下さい。

環境

MacBook Air (Early 2015) 2.2GHzデュアルコア Intel Core i7
Chrome 49.0.2623.110
Firefox 45.0.1
Safari 9.1 (11601.5.17.1)

ベンチマーク詳細

function imul(a, b) {
  var ah  = (a >>> 16) & 0xffff;
  var al = a & 0xffff;
  var bh  = (b >>> 16) & 0xffff;
  var bl = b & 0xffff;
  return ((al * bl) + (((ah * bl + al * bh) << 16) >>> 0)|0);
}

// Polyfill
(function() {
    console.time('mul1');
    calc();
    console.timeEnd('mul1');
    
    function calc() {
        var seed = 0x00000000;
        var max = MAX_FRAME;
        for(var i = 0; i < max; i++)
            seed = u32(imul(0x41C64E6D, seed) + 0x6073);
    }
    
    function u32(x) {
        return x >>> 0;
    }
})();

// Math.imul
(function() {
    console.time('mul2');
    calc();
    console.timeEnd('mul2');
    
    function calc() {
        var seed = 0x00000000;
        var max = MAX_FRAME;
        for(var i = 0; i < max; i++)
            seed = u32(Math.imul(0x41C64E6D, seed) + 0x6073);
    }
    
    function u32(x) {
        return x >>> 0;
    }
})();

32bitのseedをmax回LCGで回すベンチマーク。今回はmax = 10000000とした。

結果

LCGを回し終わるまでの時間を計測する。単位はms。

	Polyfill	Math.imul
Chrome	361.045	493.741
Firefox	108.52	58.36
Safari	542.977	260.964

Firefox, Safariの結果は予想通りMath.imulのほうが速かった。 Chromeのみが何故かPolyfillのほうが速かったが、今後のV8エンジンの改善によって解決すると思われる。 Math.imulの中身はネイティブ実装だろうし、Polyfill使うくらいだったらMath.imulを使ったほうがいいんじゃないかな。

ソースコード

github.com

概要

乱数を求める

実行

初期Seedを求める

結果

乱数調整する際の問題点

最後に

はじめに

「乱数調整」とは

「乱数」とは

乱数の種類

改めて「乱数調整」とは

ポケモンで使用される乱数生成法

実擬似乱数列

乱数の消費

ウツギ博士との電話で乱数調整

準備

初期Seedを合わせる

1. エメタイマーで30秒間のタイマーをセットする

5. ゲームが再開したらポケギアのマップを開き, 徘徊ポケモンの位置から初期Seedを特定する

セーブ直前の位置

ロード後の位置

目標初期seed

下4桁の範囲

乱数を消費する

ウツギ博士との電話で乱数調整 その2

乱数と初期Seedの計算

初期Seedを合わせる

1回目

2回目

3回目

乱数を消費する

他にどんなことが乱数調整できるの?

乱数調整の勉強する際に参考になるサイト

おわりに

仕様

使い方

感想

終わりに

概要

方針

リンク

あとがき

目標 & 方針

環境

準備

インストールしたもの一覧

1. porgのインストール

2. gccのインストール

3. pythonのインストール

4. cmakeのインストール

5. llvmのインストール

6. luaのインストール

7. vimのインストール

8. vim-clangのインストール

9. glibcのインストール

10. color_codedのインストール

動作確認

前提

環境

ベンチマーク詳細

結果

参考

ウツギ博士との電話で乱数調整その2