モンハンの護石ループバグ（痛風テーブル）はどうやって発生するか？

通称「痛風テーブル」と呼ばれるモンスターハンターライズの乱数ループバグの話です
これが心配で気持ちよく回せない！という人は多かったかもですが、[修正されるみたい](https://twitter.com/MH_Rise_JP/status/1385518669275353094)で良かったです

どうやったら発生するのか？どうやったら回避できるのかという話が身内Discordで盛り上がり、好きな話だったのでまとめました！

リバースエンジニアリングなしのあくまで「どうやったら発生するのか？」であり、発生する要因のひとつの予想として考えてください
でも結構やりがちなバグだと思うので参考になれば～

## 前提

モンハンでは護石という、ランダムにスキルがついた装備品があります
いらなくなった素材を一定数消費することで、１クエストごといくつか得ることができ、実質のハクスラ要素で、ゲームのエンドコンテンツです

この護石が、ある時から同じスキルのものが出てきてしまうユーザーが発生した、というのが今回のバグです
護石は同じスキルのものが２つあっても無駄ですし、そもそもこのループではあまり良い護石が出ないことからとても残念な状態になっちゃうわけですね

弱点特効（痛撃）・風圧軽減のスキルのついた護石が目印になることから痛風テーブルと呼ばれています
テーブルという言い方は正確じゃないんじゃないかな～と思ってるのですが、このあたりは過去作の経緯とか色々あるので省略します

攻略サイトの説明：https://altema.jp/mhrize/tufutable
公式の発表：https://www.capcom.co.jp/monsterhunter/rise/topics/notice/210408.html

## 護石はseedつき疑似乱数を使っている

今作モンハンではオートセーブ機能を切ることができるのですが、その状態で護石を確認してからリセットしてもう１度手に入れても、同じ護石が排出されます
何度もリセットするプレイをさせたくないという意図がありそうですね～

この実装をするのにはseedつき疑似乱数のアルゴリズムを使います
ゲーム業界で一番使われるのは[メルセンヌ・ツイスタ（MT）](https://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E3%83%BB%E3%83%84%E3%82%A4%E3%82%B9%E3%82%BF)だと思うので、ひとまずMTが使われると仮定して話を進めます

MTは非常に質の良い疑似乱数で、１度seedを与えて初期化した後は、とても周期の長い疑似乱数値を軽量に吐き出し続けてくれます
seedが同じなら、同じ順序の値が出てくるのでリセットにも強いです
![68747470733a2f2f692e696d6775722e636f6d2f557165736d45512e706e67.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1376552/5fca373f-e77e-7d65-3906-1329d6acb279.png)
最初のseedに使われているのは、ユーザーIDとセーブデータのユニークIDといったところ
時間とかも入れてるかもけど、何にしてもセーブデータごとにユニークなものだと思います

## MTをセーブする際に発生する問題

理屈上、最初のseedを保存しておけば、MTは同じ数字の順序を吐き出してくれます
でもこのままだと10回目の値が欲しければ10回、100回目なら100回、1000回目なら1000回処理する必要があるので「護石を何度も回していると、セーブデータ読み込み後に無茶苦茶重くなる」みたいなことになっちゃいます
サーバーみたいにずっと起動しておくというわけにもいかないし・・・

なので、MTの途中状態を保存することになります
ところがMTの内部メモリは624配列と大きくて、そのまま保存するにはちょっと躊躇しちゃいます
![68747470733a2f2f692e696d6775722e636f6d2f6a45744c5738482e706e67.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1376552/afb1378d-df1d-2b8a-6633-b1c684e80410.png)
そこで護石を作るたびにMT自体も作り直す方法を考えてみます
護石をつくったら、MTに次のMTのためのseedを吐き出してもらい、それを保存しておきます
![68747470733a2f2f692e696d6775722e636f6d2f6a3648436159532e706e67.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1376552/225e7450-541b-9821-14fc-6f69e94be8c6.png)
これなら保存しなければいけないのは１つのseed値なので大幅に節約できます
クエストごとに生成するのではなく護石ごとに生成することで乱数調節する余地も塞ぎましょう

初期化は毎回重いですが、許容範囲内ですし、後半無限に重くなるよりよほど良いはず

ひとまずこれで良いように思えます・・・が

## 内部メモリはループしないが、出力乱数は同じになることがある！

MTは非常に長い周期を持っていて、ゲーム中に２度同じ内部状態になることはありません
しかし出力される乱数は、当たり前ですがすべてのメモリを使うわけではないので同じ値が出てくることがあります
（出力時に落とした桁の数だけ確率が上がります）
![68747470733a2f2f692e696d6775722e636f6d2f656f6a6e5764622e706e67.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1376552/c84a8748-8163-785d-dbeb-fa65a135cfe2.png)
そして生成されていくMTの順序の中にこの２つが並んでしまうことがあります
![68747470733a2f2f692e696d6775722e636f6d2f6770637248596d2e706e67.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1376552/95c9f97e-fa65-9d5d-1e17-839cbc9a5e9b.png)
こうなると、自身を生成するseedを必ず作ってしまうので、同じ内部メモリのMTが作られ、このループから抜け出すことはできなくなります
どこかのMTが偶然にもこのseedを引いてしまえばこのループに入るので、理論的には護石を無限に回すと、すべてのユーザーがループにハマることになります

これが痛風テーブルの正体じゃないかと予想してます

## どうして何人もの人がループに陥ったの？

ループする仕組みはこれだとして、その特定のseedを何人も引き当てたのはどうしてでしょう？

桁を切り落としてしまっている、という説が僕の中で有力です
MTから出てくる数値自体はそれなりに桁があるのですが、仮に切り落とされてseedが32bitのuint値で保存されている場合、そのパターンは40億
一見余裕がありそうに見えるのけど、[誕生日パラドックス](https://ja.wikipedia.org/wiki/%E8%AA%95%E7%94%9F%E6%97%A5%E3%81%AE%E3%83%91%E3%83%A9%E3%83%89%E3%83%83%E3%82%AF%E3%82%B9)を考える必要があります
なんと40億のパターンでもだいたい6～7万くらいの試行で衝突してしまうのです！
モンハンの売上は11万本なので、衝突しそうな数字ですね～

もしくは、初期seedの生成方法があんまり良くなくて（ユーザーIDとセーブIDと時間を加算、とか）同じseedが実は排出されているかもです
同じような理由として、MTの初期化時の撹拌が弱い可能性もあります

これらに合わせてループする場所が運悪く発生しやすい数値だった可能性もあります
ループ間の距離が体感できるほど短いのはそれなりに運が作用してそうな気もします
過去作も同じアルゴリズムだったけど問題なかった、とかだったら今作のエンジニアは可愛そう・・・
そもそも護石廃人が排出する護石の数がすごいので・・・ループ範囲2652個って、よく気づいたなと思わざるを得ないです！

## どうやって脱出させるか？

[すでにこのバグの対策は済んでいる](https://twitter.com/MH_Rise_JP/status/1385518669275353094)みたいなのですが、自分たちならどう解決するか？というのも考えてみました！

まともに解決するなら、MTのメモリ空間をセーブデータに含めれば良いです
MTは、ひとつの乱数としてはそれなりに重いんですけど（たぶん2.5KB）図鑑とかに保存されている写真機能なんかに比べれは保存できないサイズではない、はず

これが重すぎる場合はMTの代わりに[Xorshift](https://ja.wikipedia.org/wiki/Xorshift)などの、比較的メモリが少ないアルゴリズムにしてしまうのも手です

・・・とはいえ、どちらも大きな変更を伴うので、バグ修正としては難しい場合があるかもしれません

Discordで提案されて、なるほど！と思ったのは、セーブseedに護石の生成インデックスを足してしまうという方法です
これならたまたまループseedを引いても（足した結果同じでも）、その次の護石では違う値に移動するので１人につき20億護石くらいはループ脱出してくれるはずになります
乱数としては品質が下がりますが、もともとMTの生成しなおしも乱数として品質下がっているのであまり変わらないと思います

もちろん新規実装のときは内部メモリを保存する方法のほうがおすすめです

## まとめ

* 乱数生成器を保存しなければならない場合は、できればそのメモリを保存すべき
* seedを保存するとしても十分な桁数を確保するべき
* 緊急避難的には、絶対にかぶらない数を足すことで脱出できる