次世代ガチャの実装

# 1. 次世代ガチャとは何か
「艦これ」や「ドールズフロントライン」で実装されているガチャは、単なるくじ引きではない。これらのガチャを次世代ガチャと呼び、実装を試みる。

従来型のガチャの特徴は、入力として 1単位 のコインを投入すると、出力として 予め決められた提供確率に従ってランダムに 1つのアイテムが得られるものだ。一方、次世代ガチャの特徴は、**入力をユーザが柔軟に指定でき、それによってガチャの提供確率を変化させることができる**というものだ。

多くの場合、ユーザが指定する入力は N 個の非負整数の組で表される。例えば、`(力の種: 10個, 魔法の種: 15個, 俊敏の種: 5個, 賢さの種: 20個)`を入力とすると、「勇者タイプ」のキャラクターが出やすいガチャになる。魔法の種の割合を増やせば、「魔法使いタイプ」のキャラクターが出やすくなる。といった具合だ。

# 2. 用語整理
その他の用語は適宜定義する:

- **資材**: ガチャの入力。N 種類ある。
    - **レシピ**: N種の資材をいくつずつ混ぜるかの N個組。例: `(100, 100, 40, 40)`
- **キャラ**: ガチャの出力。キャラクターの略。
    - **レア度**: キャラクターの属性。高レアであるほどガチャから排出されにくい
    - **タイプ**: キャラクターの属性。勇者や戦士、魔法使いなど。
- **ガチャ**: 1つのレシピを入力として1つのキャラを排出する機能
    - **テーブル**: キャラクタごとの排出確率を保持する構造。レシピの関数。

# 3. 仕様整理

## 仕様 1: 入力制限
各資材の投入量に最小値と最大値を設ける。典型的には最小値として 10, 最大値を 99 などとする。

## 仕様 2: レア度アップ
資材投入の総量に応じて、高レアなキャラをあたりやすくする。`(10, 10, 10, 10)` のレシピよりも、`(99, 99, 99, 99)`のレシピの方を回すインセンティブを提供する。

## 仕様 3: タイプフィルター
レシピによって 特定のタイプを出さないようにする。例えば、「魔法使いタイプ」のキャラは、魔法の種が 30 以下の場合には絶対に出ない、「戦士タイプ」のキャラは総資源量が 50 を超えると絶対に出ない。この機能によりユーザは欲しいキャラを狙いやすくなる。

## 仕様 4: タイプ別排出確率
タイプごとに排出確率を決める。例えば、勇者タイプは戦士タイプよりも3倍排出されにくい。なお、タイプ別の排出確率の相対的な比率は総資材量には依存しないものとする（そのため、タイプフィルターは本機能の一部とみなすことはできない）。

## 仕様 5: キャラ別排出確率
同タイプ・同レアリティであってもキャラごとに当選確率を変える。「最高レアリティの中でもさらに出にくい超超レアキャラがいるよ！」

## 仕様 6: キャラ別当選確率アップボーナス
特定のキャラを当てるためのレシピが存在する。その特定レシピに近いレシピにすると、そのキャラが当たりやすくなると。この機能は補助的なもので、ほんの多少当選確率がアップするぐらいのおまじない・ゲン担ぎとして利用される。

特定レシピは全てのキャラに存在するのではなく、一部の目玉キャラのみに実装する。すなわち、特定レシピが存在しない場合もある（し、それが普通）。

## 仕様 7: 当選確率の考え方
特定のキャラが選出される手続きは以下。同等の結果が得られればよいため、必ずしもこのような順の手続きでの実装である必要はない

- Step0: (ユーザがレシピを入力とする)
- Step1: タイプフィルターで排出可能なキャラの集合が定まる
- Step2: レシピの資材量からレアリティ別の確率一覧が定まる
- Step3: (タイプ, レアリティ)で指定されるキー別の当選確率が定まる
- Step4: キャラごとの当選確率、すなわち、テーブルが定まる
- Step5: 特定レシピによる味付けで、テーブルを微調整する
- Step6: 乱数を生成し、テーブルに従って排出キャラを定める。

# 4. 実装

## 4-0. 当選確率の考え方
キャラの当選確率を以下のように考える:

>
当選確率 ∝ (レア係数) × (タイプ係数) × (キャラ係数) × (レシピ補正)

レア係数は、キャラのレア度によって振り分けられる値で、例えば★3 で 20, ★4 で 4、★5 で 1 というように定める。タイプ係数は、キャラのタイプによって振り分けられる値で、戦士なら 10,　魔法使いなら5, 勇者なら 1 などとする。キャラ係数は、同タイプ・同レアリティであるキャラ間の相対的な当たり具合によって振り分けられる値で、★5勇者の中でも、伝説の勇者には 1を振り分け、その他の勇者には 10を割り振る。

このように、ガチャの排出テーブルを各係数を求めることに帰着させる。

## 4-1. レアリティ周りの実装
レア係数は総資材の関数である。レアリティが高いものの相対頻度を上げればよい。今回の実装では、レアリティの期待値が平均よりも高いものの頻度を一律に割合で上げているが、もう少し工夫してもよい。ゲームデザインとの兼ね合いであるので「10倍資材を投入するなら、当選確率を10倍にするべきだ」としてもよいし、「いやいや、せめて 5倍でしょう」とか、「当選確率を上げるのは最高レアだけでいいんじゃない？」とか色々な意見が出るだろう。重要なのは、それらの仕様の幅を、この関数の実装で吸収できるということだ:

```js
const [INPUTMIN, INPUTMAX] = [10, 99];
const RARITY = [
  { id: 5, coef: 1 },
  { id: 4, coef: 4 },
  { id: 3, coef: 20 },
];
const sum = xs => xs.reduce((a, x) => a + x, 0);

function rarityTable (xs, rArr) {
  // calc bonus
  const [min, max] = [INPUTMIN, INPUTMAX].map(x => x * xs.length);
  const volume = (sum(xs) - min) / (max - min); // 0 - 1.0
  const bonus = 1.0 + volume * INPUTMAX / INPUTMIN;
  // get new coefficents modified by given bonus
  const av = sum(rArr.map(r => r.coef)) / rArr.length;
  const isTarget = r => r.coef < av;
  const newCoef = rArr.map(r => isTarget(r) ? r.coef * bonus : r.coef);
  return rArr.map((obj, i) => ({ ...obj, coef: newCoef[i] }));
}
```

総資材量を大きくすると、高レアの頻度が大きくなるのがわかる:

```js
console.log(rarityTable([10, 10, 10, 10], RARITY));
console.log(rarityTable([20, 20, 20, 20], RARITY));
console.log(rarityTable([99, 99, 99, 99], RARITY));
/* output
[ { id: 5, coef: 1 }, { id: 4, coef: 4 }, { id: 3, coef: 20 } ]
[ { id: 5, coef: 2.11 }, { id: 4, coef: 8.45 },  { id: 3, coef: 20 } ]
[ { id: 5, coef: 10.9 }, { id: 4, coef: 43.6 }, { id: 3, coef: 20 } ]
*/
```


## 4-2. タイプとレアリティ周りの実装
続いて、タイプに関する実装。以下のようにデータを定義:

```js
const TYPES = [
  { id: 'typeA', coef: 10, pred: xs => true },
  { id: 'typeB', coef: 10, pred: xs => sum(xs) < 100 },
  { id: 'typeC', coef: 3, pred: xs => xs[0] > 19 && xs[1] > 39 },
  { id: 'typeD', coef: 1, pred: xs => sum(xs) > 149 && xs.every(x => x > 29) },
];
```

`coef`は前述の係数を表す。typeD が一番排出されにくく、typeA, typeB が一番よく排出される。`pred` はタイプフィルターの実装である。typeA は常に真なので、どんなレシピでも排出される可能性があるのに対し、typeD は総資材量が 150 以上かつ、各資材が30以上でないと排出されないことが示されている。

タイプフィルターの実装は簡単で、`pred`でフィルタリングしてあげればよい。前述のように、キャラの排出確率を決める要因の一つが `レア度＋タイプ` で決められる係数である。そこで、レア度とタイプを指定すると一意に決まるID を **kind** と名前を付けよう。kind ごとの係数を一覧化したものを kindテーブルと呼び、それを作成する関数を実装する:

```js
function kindTable (xs, tArr, rArr) {
  const rTable = rarityTable(xs, rArr);
  const tTable = tArr.filter(t => t.pred(xs));
  const result = [];
  for (const t of tTable) {
    for (const r of rTable) {
      result[`${t.id}-${r.id}`] = t.coef * r.coef;
    }
  }
  return result;
};
```
レシピを変化させると、タイプフィルターと、レア度アップ機能によって、kind テーブルが仕様通りの動作をすることが見て取れよう:

```js
console.log(kindTable([10, 10, 10, 10], TYPES, RARITY));
console.log(kindTable([50, 50, 50, 50], TYPES, RARITY));

/* output
[ 'typeA-5': 10,
  'typeA-4': 40,
  'typeA-3': 200,
  'typeB-5': 10,
  'typeB-4': 40,
  'typeB-3': 200 ]
[ 'typeA-5': 54.49438202247191,
  'typeA-4': 217.97752808988764,
  'typeA-3': 200,
  'typeC-5': 16.348314606741575,
  'typeC-4': 65.3932584269663,
  'typeC-3': 60,
  'typeD-5': 5.449438202247191,
  'typeD-4': 21.797752808988765,
  'typeD-3': 20 ]
*/
```

## 4-3. キャラ周りの実装
データ構造をまず示そう:

```js
const CHARACTERS = [
  { id: 'A51', type: 'typeA', rarity: 5, coef: 10 },
  { id: 'A52', type: 'typeA', rarity: 5, coef: 10 },
  { id: 'A41', type: 'typeA', rarity: 4, coef: 10 },
  { id: 'A42', type: 'typeA', rarity: 4, coef: 10 },
  { id: 'A31', type: 'typeA', rarity: 3, coef: 10 },
  { id: 'A32', type: 'typeA', rarity: 3, coef: 10 },
  { id: 'B51', type: 'typeB', rarity: 5, coef: 10 },
  { id: 'B52', type: 'typeB', rarity: 5, coef: 10 },
  { id: 'B41', type: 'typeB', rarity: 4, coef: 10 },
  { id: 'B42', type: 'typeB', rarity: 4, coef: 10 },
  { id: 'B31', type: 'typeB', rarity: 3, coef: 10 },
  { id: 'B32', type: 'typeB', rarity: 3, coef: 10 },
  { id: 'C51', type: 'typeC', rarity: 5, coef: 10 },
  { id: 'C52', type: 'typeC', rarity: 5, coef: 10 },
  { id: 'C41', type: 'typeC', rarity: 4, coef: 10 },
  { id: 'C42', type: 'typeC', rarity: 4, coef: 10 },
  { id: 'C31', type: 'typeC', rarity: 3, coef: 10 },
  { id: 'C32', type: 'typeC', rarity: 3, coef: 10 },
  { id: 'D51', type: 'typeD', rarity: 5, coef: 10 },
  { id: 'D52', type: 'typeD', rarity: 5, coef: 1 },
  { id: 'D41', type: 'typeD', rarity: 4, coef: 10 },
  { id: 'D42', type: 'typeD', rarity: 4, coef: 5 },
  { id: 'D31', type: 'typeD', rarity: 3, coef: 10 },
  { id: 'D32', type: 'typeD', rarity: 3, coef: 10 },
];
```

さて、キャラ係数を決めるロジックは、レア係数・タイプ係数の導出ロジックとは、**異なる**。イメージ的には、kind で与えられた頻度を、同kind のキャラで**分配する**。例えば、typeA, ★5 のキャラが2体いて、キャラ係数が 1: 2 だったとすると、kind係数 300 を 100 と 200 に分配する、というイメージ。これによりテーブルを作成することができる:

```js
function totalCoef (cArr) {
  const result = {};
  for (const { type, rarity } of cArr) {
    const key = `${type}-${rarity}`;
    if (result[key]) {
      continue;
    }
    result[key] = sum(cArr.filter(c => c.type === type && c.rarity === rarity).map(c => c.coef));
  }
  return result;
}

function tableOf (xs, cArr, tArr, rArr) {
  const kTable = kindTable(xs, tArr, rArr);
  const kCoef = totalCoef(cArr);

  const result = [];
  for (const c of cArr) {
    const kind = `${c.type}-${c.rarity}`;
    if (kTable[kind] && kCoef[kind]) {
      result.push({ ...c, coef: c.coef * kTable[kind] / kCoef[kind] });
    }
  }
  return result;
}
```

以下のようになる:

```js
console.log(tableOf([10, 10, 10, 10], CHARACTERS, TYPES, RARITY))
console.log(tableOf([50, 50, 50, 50], CHARACTERS, TYPES, RARITY))
/* output
[ { id: 'A51', type: 'typeA', rarity: 5, coef: 5 },
  { id: 'A52', type: 'typeA', rarity: 5, coef: 5 },
  { id: 'A41', type: 'typeA', rarity: 4, coef: 20 },
  { id: 'A42', type: 'typeA', rarity: 4, coef: 20 },
  { id: 'A31', type: 'typeA', rarity: 3, coef: 100 },
  { id: 'A32', type: 'typeA', rarity: 3, coef: 100 },
  { id: 'B51', type: 'typeB', rarity: 5, coef: 5 },
  { id: 'B52', type: 'typeB', rarity: 5, coef: 5 },
  { id: 'B41', type: 'typeB', rarity: 4, coef: 20 },
  { id: 'B42', type: 'typeB', rarity: 4, coef: 20 },
  { id: 'B31', type: 'typeB', rarity: 3, coef: 100 },
  { id: 'B32', type: 'typeB', rarity: 3, coef: 100 } ]
[ { id: 'A51', type: 'typeA', rarity: 5, coef: 27.24719101123595 },
  { id: 'A52', type: 'typeA', rarity: 5, coef: 27.24719101123595 },
  { id: 'A41', type: 'typeA', rarity: 4, coef: 108.9887640449438 },
  { id: 'A42', type: 'typeA', rarity: 4, coef: 108.9887640449438 },
  { id: 'A31', type: 'typeA', rarity: 3, coef: 100 },
  { id: 'A32', type: 'typeA', rarity: 3, coef: 100 },
  { id: 'C51', type: 'typeC', rarity: 5, coef: 8.174157303370787 },
  { id: 'C52', type: 'typeC', rarity: 5, coef: 8.174157303370787 },
  { id: 'C41', type: 'typeC', rarity: 4, coef: 32.69662921348315 },
  { id: 'C42', type: 'typeC', rarity: 4, coef: 32.69662921348315 },
  { id: 'C31', type: 'typeC', rarity: 3, coef: 30 },
  { id: 'C32', type: 'typeC', rarity: 3, coef: 30 },
  { id: 'D51', type: 'typeD', rarity: 5, coef: 4.954034729315628 },
  { id: 'D52', type: 'typeD', rarity: 5, coef: 0.49540347293156284 },
  { id: 'D41', type: 'typeD', rarity: 4, coef: 14.53183520599251 },
  { id: 'D42', type: 'typeD', rarity: 4, coef: 7.265917602996255 },
  { id: 'D31', type: 'typeD', rarity: 3, coef: 10 },
  { id: 'D32', type: 'typeD', rarity: 3, coef: 10 } ]
*/
```

## 4-4. 特定レシピによるテーブル微調整
特に言うことはない。Nつの資材があるので、N次元における距離を定義して、カットオフ内にあれば、係数を少し大きくしてあげる。これも減衰をどのようにするのかは、議論の余地があるだろうが、この関数で仕様の幅を吸収できるのがポイント。

```js
const RECIPES = [
  { id: 'D52', value: [50, 50, 50, 50] },
];

function modifyTable (xs, table, recipes) {
  const cutoff = 2;
  const result = [...table]; // copy
  for (const recipe of recipes) {
    const found = table.find(x => x.id === recipe.id);
    if (!found) {
      continue;
    }
    const distance = sum(xs.map((x, i) => Math.abs(x - recipe.value[i])));
    console.log(found, distance);
    if (distance > cutoff) {
      continue;
    }
    found.coef *= 1.2;
  }
  return result;
}
```

## 4-5. ガチャの実装
テーブルが与えられれば、ガチャを実装するのは簡単。係数を確率に変換するために、1で正規化。乱数と内部の累積関数の大小関係で、当てるキャラを指定（このへんの話は、昔書いた[ガチャプログラムの実装（中級者向け）](https://qiita.com/41semicolon/items/9d4d200c14b09cb28fd9)あたりを見るといいかも）:

```js
function gacha (table, rval) {
  let acc = 0;
  const total = sum(table.map(x => x.coef));
  for (const entry of table) {
    acc += entry.coef / total; // probability = coef / total
    if (acc >= rval) {
      return { ...entry };
    }
  }
  return [...table[table.length - 1]]; // just for safety.
}
```

軽く動作確認:

```js
const t1 = tableOf([10, 10, 10, 10], CHARACTERS, TYPES, RARITY);
const t1m = modifyTable([10, 10, 10, 10], t1, RECIPES);
simulation(10000, t1m);
const t2 = tableOf([50, 50, 50, 50], CHARACTERS, TYPES, RARITY);
const t2m = modifyTable([50, 50, 50, 50], t2, RECIPES);
simulation(10000, t2m);
/* output
{ '3': 8080, '4': 1553, '5': 367 } { typeA: 4935, typeB: 5065 } { D51: 0, D52: 0 }
{ '3': 4216, '4': 4578, '5': 1206 } { typeA: 7165, typeD: 688, typeC: 2147 } { D51: 76, D52: 13 }
*/
```

タイプフィルターも効いているし、資材量を増やすとレア度が当たる頻度も増えている。同kind 内での係数違いに起因する排出確率の変化も確認できた。

# 5. ソースコード
Node v11. で確認。バグなどあれば、コメントください

```js
const [INPUTMIN, INPUTMAX] = [10, 99];

const RARITY = [
  { id: 5, coef: 1 },
  { id: 4, coef: 4 },
  { id: 3, coef: 20 },
];

const TYPES = [
  { id: 'typeA', coef: 10, pred: xs => true },
  { id: 'typeB', coef: 10, pred: xs => sum(xs) < 100 },
  { id: 'typeC', coef: 3, pred: xs => xs[0] > 19 && xs[1] > 39 },
  { id: 'typeD', coef: 1, pred: xs => sum(xs) > 149 && xs.every(x => x > 29) },
];

const CHARACTERS = [
  { id: 'A51', type: 'typeA', rarity: 5, coef: 10 },
  { id: 'A52', type: 'typeA', rarity: 5, coef: 10 },
  { id: 'A41', type: 'typeA', rarity: 4, coef: 10 },
  { id: 'A42', type: 'typeA', rarity: 4, coef: 10 },
  { id: 'A31', type: 'typeA', rarity: 3, coef: 10 },
  { id: 'A32', type: 'typeA', rarity: 3, coef: 10 },
  { id: 'B51', type: 'typeB', rarity: 5, coef: 10 },
  { id: 'B52', type: 'typeB', rarity: 5, coef: 10 },
  { id: 'B41', type: 'typeB', rarity: 4, coef: 10 },
  { id: 'B42', type: 'typeB', rarity: 4, coef: 10 },
  { id: 'B31', type: 'typeB', rarity: 3, coef: 10 },
  { id: 'B32', type: 'typeB', rarity: 3, coef: 10 },
  { id: 'C51', type: 'typeC', rarity: 5, coef: 10 },
  { id: 'C52', type: 'typeC', rarity: 5, coef: 10 },
  { id: 'C41', type: 'typeC', rarity: 4, coef: 10 },
  { id: 'C42', type: 'typeC', rarity: 4, coef: 10 },
  { id: 'C31', type: 'typeC', rarity: 3, coef: 10 },
  { id: 'C32', type: 'typeC', rarity: 3, coef: 10 },
  { id: 'D51', type: 'typeD', rarity: 5, coef: 10 },
  { id: 'D52', type: 'typeD', rarity: 5, coef: 1 },
  { id: 'D41', type: 'typeD', rarity: 4, coef: 10 },
  { id: 'D42', type: 'typeD', rarity: 4, coef: 5 },
  { id: 'D31', type: 'typeD', rarity: 3, coef: 10 },
  { id: 'D32', type: 'typeD', rarity: 3, coef: 10 },
];

const RECIPES = [
  { id: 'D52', value: [50, 50, 50, 50] },
];

const sum = xs => xs.reduce((a, x) => a + x, 0);

function rarityTable (xs, rArr) {
  // calc bonus
  const [min, max] = [INPUTMIN, INPUTMAX].map(x => x * xs.length);
  const volume = (sum(xs) - min) / (max - min); // 0 - 1.0
  const bonus = 1.0 + volume * INPUTMAX / INPUTMIN; // maybe adequate this to log
  // get new coefficents modified by given bonus
  const av = sum(rArr.map(r => r.coef)) / rArr.length;
  const isTarget = r => r.coef < av;
  const newCoef = rArr.map(r => isTarget(r) ? r.coef * bonus : r.coef);
  return rArr.map((obj, i) => ({ ...obj, coef: newCoef[i] }));
}

function kindTable (xs, tArr, rArr) {
  const rTable = rarityTable(xs, rArr);
  const tTable = tArr.filter(t => t.pred(xs));
  const result = [];
  for (const t of tTable) {
    for (const r of rTable) {
      result[`${t.id}-${r.id}`] = t.coef * r.coef;
    }
  }
  return result;
};

function totalCoef (cArr) {
  const result = {};
  for (const { type, rarity } of cArr) {
    const key = `${type}-${rarity}`;
    if (result[key]) {
      continue;
    }
    result[key] = sum(cArr.filter(c => c.type === type && c.rarity === rarity).map(c => c.coef));
  }
  return result;
}

function tableOf (xs, cArr, tArr, rArr) {
  const kTable = kindTable(xs, tArr, rArr);
  const kCoef = totalCoef(cArr);

  const result = [];
  for (const c of cArr) {
    const kind = `${c.type}-${c.rarity}`;
    if (kTable[kind] && kCoef[kind]) {
      result.push({ ...c, coef: c.coef * kTable[kind] / kCoef[kind] });
    }
  }
  return result;
}

function modifyTable (xs, table, recipes) {
  const cutoff = 2;
  const result = [...table]; // copy
  for (const recipe of recipes) {
    const found = table.find(x => x.id === recipe.id);
    if (!found) {
      continue;
    }
    const distance = sum(xs.map((x, i) => Math.abs(x - recipe.value[i])));
    console.log(found, distance);
    if (distance > cutoff) {
      continue;
    }
    found.coef *= 1.2;
  }
  return result;
}

function gacha (table, rval) {
  let acc = 0;
  const total = sum(table.map(x => x.coef));
  for (const entry of table) {
    acc += entry.coef / total; // probability = coef / total
    if (acc >= rval) {
      return { ...entry };
    }
  }
  return [...table[table.length - 1]]; // just for safety.
}

/*
console.log(rarityTable([10, 10, 10, 10], RARITY));
console.log(rarityTable([20, 20, 20, 20], RARITY));
console.log(rarityTable([99, 99, 99, 99], RARITY));
*/

/*
console.log(kindTable([10, 10, 10, 10], TYPES, RARITY));
console.log(kindTable([50, 50, 50, 50], TYPES, RARITY));
*/

/*
console.log(tableOf([10, 10, 10, 10], CHARACTERS, TYPES, RARITY))
console.log(tableOf([50, 50, 50, 50], CHARACTERS, TYPES, RARITY))
*/

function simulation (nSample, table) {
  const statR = {};
  const statT = {};
  const statID = {};
  for (let i = 0; i < nSample; i++) {
    const result = gacha(table, Math.random());
    statR[result.rarity] = (statR[result.rarity] || 0) + 1;
    statT[result.type] = (statT[result.type] || 0) + 1;
    statID[result.id] = (statID[result.id] || 0) + 1;
  }
  console.log(statR, statT, { D51: statID.D51 || 0, D52: statID.D52 || 0 });
}

const t1 = tableOf([10, 10, 10, 10], CHARACTERS, TYPES, RARITY);
const t1m = modifyTable([10, 10, 10, 10], t1, RECIPES);
simulation(10000, t1m);
const t2 = tableOf([50, 50, 50, 50], CHARACTERS, TYPES, RARITY);
const t2m = modifyTable([50, 50, 50, 50], t2, RECIPES);
simulation(10000, t2m);
```