重みつきランダム選択アルゴリズムの実装[JavaScript]

## 今回やりたいこと

トランプの神経衰弱ゲームをJavaScriptで実装しました。

[ゲームデモ画面](https://github.com/OnoYuta/app-memory-game)
![memory_game_play](https://user-images.githubusercontent.com/49770211/79117954-7bf77400-7dc7-11ea-9103-d6975390cc71.gif)

カードをランダムに選択するときに重みづけの方法を考えました。私が調べた限りでは、JavaScriptにそういった関数は用意されていないようでしたので、重みづけの参考になればと思っています。

プログラミング初心者なので、気になる点などありましたらご指摘いただけると非常にありがたいです。

### NPCの仕様

対戦相手（以下、NPC）は、次のような仕様を設定しました。

1. ゲーム開始時はカードの配置と数字を知らない
2. 表になったカードの配置と数字を記憶する 
3. 記憶できるカードの枚数には上限（以下、記憶容量）がある
4. 記憶容量を超えると覚えたカードからランダムに1枚を忘れる
5. `4.`の際に最近覚えたカードほど忘れにくいように重みをつける

古いものから順に忘れていく、というのは機械的すぎるので、ゲーム序盤で覚えたカードのほうが忘れやすい傾向にあるが、必ずしも覚えた順に忘れるわけではない、という仕様にしました。

どのカードを忘れるかランダムに選択する部分で、重みつきランダム選択アルゴリズムを使っています。正しくは重み付け乱択アルゴリズムというらしいです。

## 実装方針

記憶したカードは配列に格納し、配列の長さが記憶容量を超えたときに、カードをランダムに忘れる処理が実行される、というフローにしました。

### 記憶できる上限を設定する

NPCのクラスを作り、記憶容量（memoryCapacity）のプロパティを設けました。

```js
class Npc extends Player {
    constructor(name, label, strength) {
        super(name, label);
        this.memorizedCards = [];
        this.memoryCapacity = this.getMemoryCapacity(strength);
    }
```

今回はNPCの強さ（strength）をプレイヤが設定できるようにしたので、NPCの強さによって記憶容量が定まるようにしています。

### カードを記憶する

カードを記憶させるときは、表になったカードを配列（memorizedCards）に追加するだけですので、シンプルです。

```js
memoryCard(card) {
    this.memorizedCards.push(card);
}
```

### 上限を超えたときに忘れる

まずは重みづけなしでカードを忘れる処理を実装しました。

```js
function forgetMemorizedCards(memorizedCards, memoryCapacity) {

    // 覚えるべきカードが記憶容量を超えた場合に忘れる
    while (memorizedCards.length > memoryCapacity) {
        // どのカードを忘れるかを決定する
        let forgetMemorizedCardsIndex = getForgetMemorizedCardsIndex(memorizedCards);

        // 指定したindexの要素を削除する
        let forget = memorizedCards.splice(forgetMemorizedCardsIndex, 1);
    }

    return;
}

function getForgetMemorizedCardsIndex(memorizedCards) {
    // あとで重み付けを実装する
    return Math.floor(Math.random() * memorizedCards.length);
}
```

## 重みづけランダム選択の実装

次のような配列を例に考えます。

```js
hasOpened = [2, 5, 6, 9, 4];
```

配列の先頭に近いほど、記憶してから時間が経っている、という設定です。

この配列から普通にランダムに1つの要素を取り出そうとすると、取り出される確率はどの要素も等しくなるかと思います。

<img width="1127" alt="hasOpend_img.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/500854/411d5e34-7eb6-a58b-4f5e-391d012ca4b2.png">

今回は配列の先頭に近いほど取得されやすいという仕様にしたいので、この配列の各要素を(配列の長さ - その要素のindex)個ずつ格納した配列を新たに作りました。

```js
weightedHasOpened = [2, 2 , 2, 2, 2, 5, 5, 5, 5, 6, 6, 6, 9, 9, 4];
```

図にすると次のようなイメージです。

<img width="1129" alt="weightHasOpened_img.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/500854/fdf088dd-7ad4-bab6-50c1-cf002c0f26b3.png">

この中からランダムに要素を取り出せば、配列の先頭に近いほど取得されやすい、という条件を実現できそうです。

これをもとに、さきほどのgetForgetMemorizedCardsIndex()メソッドを修正しました。

```js
function getForgetMemorizedCardsIndex(memorizedCards) {

    let weightedMemorizedCards = [];

    for (let i = 0; i < memorizedCards.length; i++) {
        for (let j = memorizedCards.length - i; j > 0; j--) {
            weightedMemorizedCards.push(memorizedCards[i]);
        }
    }

    return weightedMemorizedCards[Math.floor(Math.random() * weightedMemorizedCards.length)];
}
```

ちゃんと意図した配列ができているかconsoleに出力して確認します。

```bash
2,5,1,3,6,8,9,4: memorizedCards
2,2,2,2,2,2,2,2,5,5,5,5,5,5,5,1,1,1,1,1,1,3,3,3,3,3,6,6,6,6,8,8,8,9,9,4: weightedMemorizedCards
```

挙動は問題なさそうでしたので、今回はこのアルゴリズムを採用しました。重みづけのところ（forループの`i < memorizedCards.length`のところ）を修正すれば、もう少し複雑な重みづけにも対応できそうです。