おかえりちびロボ!乱数生成アルゴリズムに関して

みなさんこんにちは ゲストCもちです。ついにおかえりちびロボ!での乱数を格納しているアドレスが判明したので、英語漬けの時と同様に解析をかけて生成アルゴリズムまで判明をさせましたので、報告をさせていただきます。最後にC言語での生成を試みたものがありますが、パソコンでは正しく出力されなかったので、プログラマーの皆様プルリクお待ちしております。


1.Abstract

おかえりちびロボ!ではRTAは2011年から始まったが、メモリ値に関する系統的な調査・研究は過去に事例がなくゲストCもちによる解析しか行われていない。2018年から研究が始まったものの、研究技術不足で今まで乱数に関しての知見が無かった。2020年に逆アセンブラによる研究が可能になったのを境に研究が大きく進んでいる。今回はRTAに対しても有用な知識になるであろう乱数に関しての研究を行った。
DeSmuMe_0.9.11_x86のRAMサーチ機能を使い、乱数の格納メモリが0x02230C6C,0x02230C70に格納されていることが分かった。
その後NO$GBA.EXEを使い、メモリブレイクでブレイクポイントを仕掛け該当ルーチンを割り出すことに成功した。
該当ルーチンのアセンブリ言語を読み日本語化した後、C言語に書き換えを行った。その結果、線形合同法であることが分かり、以下のことが分かった。
①RNG1 = (((RNG1×0x6C078965) << 32) / 0xFFFFFFFF ) + 0x269EC3
②RNG2 = 0x5D588B65×RNG1 + 0x6C078965×RNG2 + ((RNG1×0x6C078965) >> 32)
③C言語で乱数予想ソフトを作った。パソコンでコンパイルしたものはRNG2で0しか吐かなかったが、iOSのMobile C[C/C++ Compiler]ではエミュレーターの値と一致した


2.Introduction

この項ではおかえりちびロボ!に関する系統的な研究、及び乱数に関して記載する。おかえりちびロボ!のSpeedrunに関わる研究は2011年にグレイ氏により始まった。彼はこの時点である程度のチャートを構築している。またこの時点ではカジノポイントは買った方が早いとの結論が付けられた。また同氏彼は2011年5月8日にRTAを通しており、記録は6時間45分03秒となっている。そこでは各おもちゃとの会話の進み具合による知見やローンに関する知見が得られている。さらに同氏は2011年5月11日にもRTAを通しており、記録は6時間15分19秒となっている。この走りによりカジノポイントは買うよりも稼いだ方が利点が多いとの結論が付けられた。しかし彼はこの投稿を最後にこの研究から姿を消すこととなった。2018年にゲストCもちによりTASが制作され始める。これを機にメモリ値に関連した系統的な研究が始まった。同氏はクリアまでに必要なリッチーポイントから、計算的に176 Pもしくは171 Pを4490マネもしくは4390マネ稼いで買い取るのが一番早いということを結論付けた。また、カジノでの乱数決定タイミングに関しても調査を行い報告をしている。しかし、乱数の格納アドレス・生成アルゴリズムや使用のされ方、各種確率が報告された例はない。そこで私は乱数生成アルゴリズムを判明させることが本稿の目的として調査を行った。


3.Analysis section

使用ソフト
・DeSmuMe_0.9.11_x86
・NO$GBA.EXE
・Visual Studio Code

あまり詳細な方法を書くと訴えられる可能性があるので、ざっくりと記す。まずメモリ値の格納アドレスを特定する必要があるので、DeSmuMe_0.9.11_x86のRAMサーチ機能を使用した。その調査により乱数格納アドレスは0xx02230C6C,0x02230C70に格納されていることが分かった。その後NO$GBA.EXEでこのアドレスでブレイクポイントを仕掛け乱数生成ルーチンを特定した。アセンブリ言語で書かれた、この生成アルゴリズムは以下のようになっていた。
①ldr r1,=Lxx_2330C68h 
②ldr r3,[r1,0Ch] 
③ldr r2,[r1,4h] 
④ldr r0,[r1,8h]
⑤umull r14,r12,r3,r2  
⑥mla r12,r3,r0,r12 
⑦ldr r0,[r1,10h] 
⑧ldr r5,[r1,14h] 
⑨mla r12,r0,r2,r12 
⑩ldr r3,[r1,18h] 
⑪adds r5,r5,r14 
⑫adc r0,r3,r12 
⑬str r5,[r1,4h] 
⑭str r0,[r1,8h] 
これの解読の詳細は次節で議論する。この結果を元にC言語をVisual Stdio Codeで組み立て、コンパイルを行った。


Result and discussion

前接では乱数生成ルーチンをアセンブリ言語で抜きだすことができた。この節では、これを翻訳しC言語に直して検証することが目的である。前節の①~⑭に対応して翻訳する。なおアセンブリ言語の知識は乏しく、翻訳が間違っている可能性もある
① r1レジスタに0x2330C68を代入する。
② r3レジスタに0x2330C68+0x0Cのアドレスにある値を代入する(4byte) ここの値は0x6C078965で固定されていることが分かっている。
③ r2レジスタに0x2330C68+0x4のアドレスにある値を代入する(4byte) ここのアドレスは0x02230C6C i.e.RNG1に値する。
④ r0レジスタに0x2330C68+0x8のアドレスにある値を代入する(4byte) ここのアドレスは0x02230C70 i.e.RNG2に値する。
⑤ r14レジスタとr12レジスタに、r3レジスタとr2レジスタの乗算値(64bit 8ytes)を代入する。(r14レジスタ(下位),r12レジスタ(上位)) ただし符号なしとみなす。r3には0x6C078965が、r2にはRNG1が格納されているので、RNG1×0x6C078965の積の上位32bitがr12へ、下位32bitがr14へ代入される。
⑥ r12レジスタにr3レジスタとr0レジスタの積とr12レジスタの和を書き込む。i.e. r12 = 0x6C078965×RNG2+r12 ということである。 
⑦ r0レジスタに0x2330C68+0x10のアドレスにある値を代入する(4byte) ここの値は0x5D588B65で固定されていることが分かっている。
⑧ r5レジスタに0x2330C68+0x14のアドレスにある値を代入する(4byte) ここの値は0x00269EC3で固定されていることが分かっている。
⑨ r12レジスタにr0レジスタとr2レジスタの積とr12レジスタの和を書き込む。 i.e. r12 = 0x5D588B65×RNG1+r12
⑩ r3レジスタに0x2330C68+0x18の値を代入する(4byte) ここの値は0で固定されていた。正直なぜこの処理をするのかは理解できていはいない。
⑪ r5レジスタにr5レジスタとr14レジスタの和を代入する。 i.e. r5 = 0x00269EC3 + r14(乗算値下位32bit)
⑫ r0レジスタにr3レジスタとr12レジスタの和を桁上がりを考慮して代入する。 i.e. r0 = 0 + r12
⑬ 0x2330C68+0x4にr5の値を代入する。 i.e. r5の値がRNG1となる。
⑭ 0x2330C68+0x8にr0の値を代入する。 i.e. r0の値がRNG2となる。

この翻訳をもとに私は以下のようにC言語で乱数予想ツールをVisual Stdio Codeで組んだ。
#include<stdio.h>
voidmain () {
unsignedlonglong RNG1;
unsignedlonglong RNG2;
int highorder;
int loworder;

printf("これはおかえりちびロボ用の乱数生成・予想ツールです。");
printf("RNG1(0x02230C6C)の値を16進数で入力してください。");
scanf("%x",&RNG1);
printf("RNG2(0x02230C70)の値を16進数で入力してください。");
scanf("%x",&RNG2);

    highorder = (RNG1*0x6C078965) >> 32;
    loworder = (RNG1*0x6C078965 << 32)/0xFFFFFFFF;
    highorder = 0x6C078965*RNG2+highorder;
    RNG2 = 0x5D588B65*RNG1 + highorder;
    RNG1 = loworder + 0x269EC3;

printf("次の乱数は\nRNG1:%x\nRNG2:%x",RNG1,RNG2);

}

これを同ツールでコンパイルを試みた。.exeのコンパイル自体は成功したものの、RNG2では0を出力をしてしまった。そこで、iOSにあるMobile C[C/C++ Compiler]で試したところ、以下のツイートのようにメモリ値が一致することが確認できた




Conclusion

本調査では逆アセンブラという手法を使い、乱数生成アルゴリズムを確定することを試みた。少し不完全ではあるが、C言語という高水準言語で乱数予想ツールを作成することができた。これにより更に研究が進むことが期待できる


Associated content



Author information

ゲストCもち
Speedrun.com:gestoC_moti




この記事へのコメント

2021年01月
               1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31