# XDのseed検索DBがめちゃくちゃ軽くなった話
この記事は[Pokémon RNG Advent Calendar 2020](https://adventar.org/calendars/5311) 4日目の記事です。
3日目と同様に、以前書いてあった記事に加筆したものです。
カレンダーに空きがあれば遠慮なく過去記事で埋めてしまうつもりなので、カレンダーに記事を投稿したい方はとりあえず枠を確保しちゃってください。

## 概要
### XDのseed検索って主人公のケツを眺めるんじゃないんですか？
XD乱数を開拓･整備してくださった偉大なるギンザルさんの方法では、XDにおけるseedの検索は『起動時刻を固定したうえで、不定消費の無いマップで主人公のモーションを眺めて全探索する』というものでした。
しかし近年、かけら(sina_poke)さんによって、コロシアムと同様に『いますぐバトル』からseed検索をすることが可能になりました。崇めましょう。

### 自作DBが必要になった経緯
- 先に『COReader』という『PC画面に移したGCのキャプチャ画面を読み取って画像認識でseed検索を半自動化するツール』を公開していた。
- XDでもキャプチャした画面からseed検索ができたら楽だと思った。
- そのためにはseed検索用DBを自作する必要があった。
- いつも通り16GBのファイルを生成してもいいが(あんまり良くない)、かけらさんのツールのDBは非常に軽量。なにか容量削減の工夫ができるらしい。それを目標に処理を考えてみた。
- いくつかの工夫を施したところ、かけらさんのオリジナルDBよりもずっと容量が抑えられ、結果としてツールに組み込むことが可能になった。

### 完成品(?)がこちらです
COReaderのように独立したツールではなく、[XDSearch](https://www.dropbox.com/sh/shx4y8v3lovo4dj/AAAkCARDF_np2qQUHoRn8Nh1a?dl=0)のseed検索機能に組み込みました。ただし大きな問題があり、自分の環境以外ではキャプチャの読込がズレてしまい、ちゃんと動かないっぽいです(おい)

## XDとにかくバトルの処理
COのとにかくバトルとの違いは以下の通り.
- プレイヤーとCOMでパーティが異なる。プレイヤー用のパーティ、COM用のパーティはそれぞれ5種類ずつ。
- パーティは2匹。
- 個体に性別指定･性格指定は無い。
- 努力値がランダムに生成される。

また、処理の違いでは無いが、
- 見せあい画面で4匹分のHP実数値を見ることができる。

のはXDとにかくバトルの大きな特徴である。

Coの『とにかくバトル』

XDの『いますぐバトル』

『いますぐバトル』の処理の流れは以下の通り.

- 1消費
- プレイヤーのパーティ決定(GetRand() % 5)
- COMのパーティ決定(GetRand() % 5)

- 1消費
- COMのTSV決定(GetRand() ^ GetRand())
- COMのパーティ 1匹目生成
- 1匹目の努力値決定
- COMのパーティ 2匹目生成
- 2匹目の努力値決定

- 1消費
- プレイヤーのTSV決定(GetRand() ^ GetRand())
- プレイヤーのパーティ 1匹目生成
- 1匹目の努力値決定
- プレイヤーのパーティ 2匹目生成
- 2匹目の努力値決定

ポケモンの生成処理はこんな感じ(GCで共通のポケモン生成処理)

- ダミーHID生成(生成されるだけで実際は使われない)
- ダミーLID生成(生成されるだけで実際は使われない)
- 個体値生成(HAB)
- 個体値生成(SCD)
- 特性決定
- HID決定
- LID決定
PIDは先に生成されたTSVを参照し、色違いになるときに再計算.

努力値決定処理は以下の通り(疑似コード)

var EVs = new uint[6];
for (int i = 0; i < 101; i++)
{
  for (int j = 0; j < 6; j++)
    EVs[j] = (EVs[j] + seed.GetRand(0x100)) & 0xFF;

  var sumEV = EVs.Sum();
  if (sumEV == 510) return EVs; // 合計が510ちょうどなら終了
  if (sumEV <= 490) continue; // 合計が490以下なら持ち越し
  if (sumEV < 530) break; // 合計が491 ~ 529なら微調整に入る
  if (i != 100) EVs.Fill(0); // 合計が530以上ならリセット
}

var k = 0;
while (sumEV != 510)
{
  // 合計が510未満なら, 255未満の箇所をHから順に1ずつ加算していく.
  if (sumEV < 510 && EVs[k] < 255) { EVs[k]++; sumEV++; }
  // 合計が510超なら, 0でない箇所をHから順に1ずつ減算していく.
  if (sumEV > 510 && EVs[k] != 0) { EVs[k]--; sumEV--; }
  k = (k + 1) % 6;
}
return EVs;

## DB作成の考察
　まずは普通に(seed,key)の対を$2^{32}$通り予め計算しておいて、検索時にkeyを二分探索するナイーブな方針を取ることを考え、そのために必要なkeyの生成方法を考える。COではこのkeyはプレイヤーの名前(3通り)$\times$プレイヤーのパーティ(8通り)を7回分並べたものになっている($24^7$ ＞ $2^{32}$)。COReaderのDBでは容量の削減のために2回分をコード化してファイル名で分割している(7回分をコード化してkeyにすると32bitに収まらない)。
XDのとにかくバトルで観測できるのは両者のパーティ(5通り$\times$ 5通り)と、4匹分のHP実数値である。パーティの情報だけでseedを検索しようとすると、COとほぼ同じ構成のDBができる($25^7$ > $2^{32}$)。
しかしせっかくHP実数値が観測できるのだから、これを利用しない手は無い。HP実数値から得られる情報は、対象の種族に依らず、個体値(0 ~ 31)と努力値/4(0 ~ 63)の和(0~94)である。なんと1回で$5^2 \times 95^4$の情報量があり、これならとにかくバトルの観測2回で十分な情報量が得られることになるのである！

#### 果たしてそうでしょうか？ (冷静HCヌオー)
上の考察、とても重要なことを忘れています。それは「LCGの下位 $n$ bitは周期$2^n$で巡回する」というLCGの~~欠点~~性質です。
上記の生成処理を見返すと、HP個体値と各努力値は、ともに乱数値の下位8bitしか使っていないことがわかります(HP個体値はr&0x1Fで決定します)。つまり、<u> PIDの再計算が起こらない限り </u>、HP実数値は計算開始seedの下位24bitのみにしか依存しない(上位8bitは影響しない)のです。しかしながら、幸いなことに、パーティ決定は%5で決定しています。この情報を使えば上位8bitの特定は可能($5^4 > 2^8$)なので、心配は杞憂に終わりました。

#### 杞憂どころか
この考察がDBの軽量化に大きく役立つことになった。すなわち、HPの情報から得られるのがseedの下位24bitまでなので、ファイルに保持すべきseedの情報は下位24bitで十分なのである。残り上位8bit分は実行時に総当たりすれば十分間に合う計算量。これだけでDBの容量は1/256まで抑えることができた。

#### もっと容量を削減したい ―― 「情報を捨てる」という選択肢
とにかくバトルの生成処理を見ると、努力値決定に再計算処理がある。これを利用することで、DBの容量をもっと削減する方法がある。「生成処理を1回分無視する」のである。再計算処理があるということは、異なるseedから計算を開始して、計算終了時のseedが同じになる組があるということである。つまり、候補とすべきseedを減らせるのである。もともと2回の観測で情報量は十分なので、1回観測を増やす手間(A,Bボタンを押す回数が1回ずつ増える)を考慮しても、十分リターンがある可能性が高い。…ということで、実行してみたところ、
キロバイト……？
大幅な容量の削減に成功してしまった。まさかここまでとは予想もしていなかった。
計算結果は、容量削減のために24bitを上位8bitと下位16bitに分け、上位8bitでファイル分けを行い下位16bitのみを格納したのだが、興味深い傾向が見られた。
上位8bitが大きいseedのほうが明らかに少ないのである。
原因は努力値の生成処理を読めばわかる。例えば終了時のseedがxxFFxxxxになっているということは、生成された6か所の努力値のうち素早さの努力値に255が加算された回に再計算が終了したということである。対して終了時のseedがxx00xxxxなら、素早さの努力値に加算された値は0であり、再計算条件に該当してしまう確率は前者のほうがずっと大きいのである。

#### 何か忘れてませんか？
下線部を忘れてはいけません。色違い回避が発生した場合、観測されるHPとseedの関係性が変わってしまいます。色違い回避によるPID再計算が発生した場合のseedとHPの組も追加する必要があります。

## 実際の構成と検索処理
以上をすべて踏まえたうえで、以下のようにファイルを生成した。
1. $2^{32}$通りのseedすべてに対して「とにかくバトル」の生成処理を1回行い、終了時のseedの下位24bitをファイルに書き出す.
2. 1.で書き出したファイルから重複しているseedを取り除く.
3. 2.で残ったseed(24bit)の全てについて、上位8bitを補って32bitに戻し、「とにかくバトル」の生成処理を1回行って、HP実数値(最低値からの増加分, 0~94)を取得･32bitコード化(以下keyと呼称)する処理を行い、得られたkeyの重複を取り除いたうえで、再度24bit seedと組みにしてファイルに書き込み(この処理を行うことでPID再計算の発生にも対応できる).
4. keyでソート.

容量は以下の通り. 

また、検索処理は以下の通り行う.
1. 検索のために1回分のHP情報(4体分)と、2回分のパーティ情報を入力. HP情報からkeyを生成.
2. 二分探索でkeyに一致するindexを取得し, seed候補(24bit)を得る. 一致するkeyは複数存在する可能性があるので, 前後のindexも調べる.
3. 2.で得たseed候補のすべてに対して上位8bitを総当たりし、2回分の「とにかくバトル」生成処理を行い、1回目のHP及び2回分のパーティ情報が一致するものを出力する.

コードは公開しています → https://github.com/yatsuna827/XDDatabase