ヌメロン(数当てゲーム)のコンピュータをより強くする

# 1. はじめに
本記事でも主要な点は記載するが一応先週の記事↓
使用する言語はそのままC。

https://qiita.com/YuyMat/items/dc538bec86a9e5649a93

# 2. ヌメロンのルール
https://ameblo.jp/a-la-carte-1012/entry-11401369990.html

> まず、それぞれのプレイヤーが、0～9までの数字が書かれたカードのうち3つを使って、3桁の番号を作成する。0から始めても良い。ただし､｢550｣｢377｣といった同じ数字を2つ以上使用した番号は作れない。
これだけが、ゲーム前の準備。以下はゲームのルールである。
先攻のプレイヤーは相手が作成したと思われる番号をコールする。
相手はコールされた番号と自分の番号を見比べ、コールされた番号がどの程度合っているかを発表する。
数字と桁が合っていた場合は｢EAT｣、数字は合っているが桁は合っていない場合は｢BITE｣となる｡
例として、相手の番号が｢765｣で、コールされた番号が｢746｣であった場合は、3桁のうち｢7｣は桁の位置が合致しているためEAT、｢6｣は数字自体は合っているが桁の位置が違うためBITE。EATが1つ・BITEが1つなので､｢1EAT-1BITE｣となる｡
これを先攻･後攻が繰り返して行い､先に相手の番号を完全に当てきった(3桁なら3EATを相手に発表させた)プレイヤーの勝利となる｡

# 3. 結果
前回作成したコンピュータのVer1.0、そして今回作成したVer2.0でそれぞれ、プレイヤーの数字を当てるまでの平均ラウンド数(平均値)と中央ラウンド数(中央値)を比較した。今回はプレイヤーが"321"、"234"、"258"の3つの数字を持っていると仮定し、それぞれのコンピュータに15回ずつ当ててもらった。結果は以下の通りである

### 321
|| Ver1.0 | Ver2.0 |
|:-:|:-:|:-:|
| 平均ラウンド数 | 7.8 | 8.866... |
| 中央ラウンド数 | 8 | 9 |

### 234
|| Ver1.0 | Ver2.0 |
|:-:|:-:|:-:|
| 平均ラウンド数 | 13.666... | 11.8 |
| 中央ラウンド数 | 14 | 11 |

### 258
|| Ver1.0 | Ver2.0 |
|:-:|:-:|:-:|
| 平均ラウンド数 | 19.266... | 16.666... |
| 中央ラウンド数 | 18 | 17 |

***

- 321は後述するコンピュータのプログラムが影響し、当たるまでのラウンド数は完全にランダムになる。今回は15という少ない母数であったためにVer2.0が劣ってしまう結果となった

- 234では予想より大きな差がついた。平均値で2近くのラウンド数が減少しているのは大満足だ

- 258では平均ラウンド数の変化は満足のいく結果となったが、中央値で見る変化は1しかなかったため、当てるまでのラウンド数にかなり波があると考えられる

# Version 1.0までの動作
version1.0を土台としてversion2.0を作成しているため、基本的な動作はversion1.0が担ってくれている。

フローチャートは以下の通りである。（フローチャートだとだいぶわかりにくいかも）

```mermaid
graph TD
    A[開始] --> B[ラウンド1-3: 123, 456, 789を評価]
    B --> C{eat or biteが1以上?}
    C -->|はい| D[可能性のある数字リストに追加]
    C -->|いいえ| E[次のラウンドへ]
    D --> E
    E --> F{ラウンド3終了?}
    F -->|はい| G{可能性のある数字が9個未満?}
    G -->|はい| H[0をリストに追加]
    G -->|いいえ| I[次のステップへ]
    H --> I
    F -->|いいえ| B
    I --> J[ラウンド4以降: リストから3桁の数字を作成]
    J --> K[数字を評価]
    K --> L{eat=0 かつ bite=0?}
    L -->|はい| M[その数字をリストから除外]
    L -->|いいえ| N{eat+bite=3?}
    N -->|はい| O[その数字以外をリストから除外]
    N -->|いいえ| P[次のラウンドへ]
    M --> P
    O --> P
    P --> Q{正解?}
    Q -->|はい| R[終了]
    Q -->|いいえ| J
```

1. ラウンド1 = 123, ラウンド2 = 456, ラウンド3 = 789を評価する
2. それぞれeat, biteが1つでも出たら可能性のある数字リストに入れる
    
    ⇒ラウンド3終了時に可能性のある数字が9個ない場合、0をリストに入れる
    
3. ラウンド4からは可能性のある数字リストから適当な3桁の数字を作成
4. 評価をし、eat, biteが両方0の場合、可能性リストから除外
5. eat + biteが3の時、その数字以外のすべての数字を可能性リストから除外
6. 3に戻る

## 1. ラウンド1 = 123, ラウンド2 = 456, ラウンド3 = 789を評価する
最初の3ラウンドは相手の数字の情報を取るために"123", "456", "789"の3つの数字を聞くのが、自分の環境では定番の流れであった。これをコンピュータに持たせるべく、最初の3ラウンドの数字を固定している。

## 2. それぞれeat, biteが1つでも出たら可能性のある数字リストに入れる

グルーバル変数として`int num_array[10] = {0}`を宣言している。
そして、予想した数字が`eat > 0` or `bite > 0`であった場合、その数字を一桁ずつ分割し、`num_array[その数字] = 1`となるようにしている。

:::note info
e.g. コンピュータの予想数字が246で、その結果が1eat 0biteだった場合、num_arrayは{0, 0, 1, 0, 1, 0, 1, 0, 0, 0}となる。
:::
そして、3ラウンド終了時にこのnum_arrayの1が9個なかった場合、num_array[0]を1にするようにしている。

:::note info
e.g. もしプレイヤーの数字が270であった場合、ラウンド3終了時のnum_arrayは
{0, 1, 1, 1, 0, 0, 0, 1, 1, 1}
となり、プレイヤーの数字には0が含まれているのにも関わらず、num_arrayの0番目は0(false)になってしまう。
:::

## 3. ラウンド4からは可能性のある数字リストから適当な3桁の数字を作成
ラウンド4からはnum_arrayの1(true)になっている数字からランダムに3つ取り出し、3桁の数字を作成し、それをコンピュータの予想数字としている。

:::note info
e.g. num_array = {1, 1, 1, 1, 0, 0, 0, 1, 1, 1}
であった時、129や983などの数字を作成
:::

## 4. 評価をし、eat, biteが両方0の場合、可能性リストから除外
もし予想した数字が`eat == 0` and `bite == 0`であった場合、その予想した数字をnum_arrayから排除する。

:::note info
e.g. num_array = {1, 1, 1, 1, 0, 0, 0, 1, 1, 1}
手順3通りに、983という数字を予想。その結果0eat, obiteであった。そしたら、num_arrayを
{1, 1, 1, 0, 0, 0, 0, 1, 0, 0}　に更新する。
:::

## 5. eat + biteが3の時、その数字以外のすべての数字を可能性リストから除外
予想した数字のeatとbiteの合計が3であった場合、その数字の各桁の要素は合っているため、その数字以外の要素を0(false)にする。

:::note info
e.g. num_array = {1, 1, 1, 1, 0, 0, 0, 1, 1, 1}
手順3通りに、329という数字を予想。その結果3eat, 3biteであった。そしたら、num_arrayを
{0, 0, 1, 1, 0, 0, 0, 0, 0, 1}　に更新する。
:::

## 6. 3に戻る
手順3に戻り、予想数字を作成する。

# Version 2.0での追加点
まずversion1.0を作成して気づいたことをまとめた。

__問題点__
eat + bite == 3もしくは0の時にnum_arrayの変動はあるが、逆にそれ以外の時の変動がなくラウンドを無駄にしている。

__解決策__
1. eat + bite = 2の時、その数字を別の配列S_arrayへ格納
2. 予想した数字とS_arrayを比較することにより、数字を絞ることができる

と考えた。

__詳細__
S_arrayと絡むケースが4つある

### case 1 : eat + bite = 2, 被っている数字2個
S_arrayに入っている数字：1**23** (eat + bite = 2)
予想した数字：**23**4 --> eat + bite == 2であった。
> 1234全てに可能性があり絞り込めない。

### case 2 : eat + bite = 1, 被っている数字2個
S_arrayに入っている数字：1**23** (eat + bite = 2)
予想した数字：**23**4 --> eat + bite == 1であった。
> この場合、1は確定の数字、4は完全に排除

### case 3 : eat + bite = 0, 被っている数字1個
S_arrayに入っている数字：12**3** (eat + bite = 2)
予想した数字：**3**45 --> eat + bite == 0であった。
> この場合12は確定の数字

### case 4 : eat + bite = 1, 被っている数字1個
S_arrayに入っている数字：12**3** (eat + bite = 2)
予想した数字：**3**45 --> eat + bite == 1であった。
> 絞り込むことができない

***

これらのケースを踏まえて、
- case2, case3をプログラムに組み込む
- 確定した数字を入れる配列absolutely_arrayを作成する
- absolutely_arrayの要素数が2個になった時点で、その2個の数字と、num_arrayからランダムな1個の数字を取り出した3桁を作成する

:::note info
num_array = {0, 0, 0, 0, 1, 1, 1, 1, 1, 0}
absolutely_array = {0, 0, 0, 0, 0, 0, 0, 1, 1, 0}
であった場合、absolutely_arrayからの"7"と"8"、そしてnum_arrayからランダムに一つ取り出して、
**785**という数字を作成する
:::

- この方法で作成した数字はeat + bite != 3であった場合、num_arrayから取り出した数字を排除することができる

:::note info
上記例の785で考えるとこれがeat + bite != 3であった場合、"5"の可能性がなくなり、
num_array = {0, 0, 0, 0, 1, 0, 1, 1, 1, 0}　に更新される
:::

を計画立ててプログラムを組んだ。

# コード実装

- github:https://github.com/YuyMat/C-numeron
- version1.0との比較:https://github.com/YuyMat/C-numeron/compare/50d2266...3715e25

***

__目次__
1. [S_arrayに格納](#1-s_arrayに格納)
2. [被っている数字の個数を取得](#2-被っている数字の個数を取得)
3. [case2, case3の時の配列処理](#3-case2-case3の時の配列処理)
4. [確定した数字が2個 or 3個の時の処理](#4-確定した数字が2個-or-3個の時の処理)

***

## 1. S_arrayに格納
eatとbiteを判定する変数にこの処理を追加。
(今考えると、配列を操作する関数saveNumArrayに追加した方がメンテナンスしやすかったかもしれない)

```c
if (eat + bite == 2) {S_array[S_array_len++] = atoi(from_num);}
```


## 2. 被っている数字の個数を取得
まず、case2とcase3において、[S_array](#version-20での追加点)に入っている数字と、予想した数字で比較した際に、被っている数字がいくつあるかを判定する関数が必要であると考えた。
```c
int sameNumberCount(char *num, int S_array, char *S_different_num, char *guess_different_num, char *same_num) {
    char str_S_num[4];
    sprintf(str_S_num, "%d", S_array);
    int same_number_counter = 0;
    
    int index = 0;

    /* 予想した数字の各桁がS_arrayに格納されている数字の各桁と合致した場合、
    same_num_counterをインクリメント。
    そしてその合致した数字をsame_numに格納*/
    for (int j = 0; j < 3; j++) {
        for (int k = 0; k < 3; k++) {
            if (num[j] == str_S_num[k]) {
                same_number_counter++;
                same_num[index++] = num[j];
            }
        }
    }

    /* 予想した数字から、上で合致した数字を除いた数字を
    guess_different_numに格納*/
    index = 0;
    for (int i = 0; i < 3; i++) {
        if (strchr(same_num, num[i]) == NULL) {
            guess_different_num[index++] = num[i];
        }
    }

    /* S_arrayに格納されていた数字から、上で合致した数字を除いた数字を
    S_different_numに格納*/
    index = 0;
    for (int i = 0; i < 3; i++) {
        if (strchr(same_num, str_S_num[i]) == NULL) {
            S_different_num[index] = str_S_num[i];
            index++;
        }
    }

    return same_number_counter;
}
```

これで合致している数字の個数が取得できる。

## 3. case2, case3の時の配列処理
まず、予想した数字とS_arrayに格納されている数字を比較し、

- 合致した数字
- 予想した数字と合致した数字の差分
- S_arrayの数字と合致した数字の差分

の3つを入れる変数を定義した。
```c
char same_num[4];
char S_different_num[4];
char guess_different_num[4];
```

次に[case3](#case-3--eat--bite--0-被っている数字1個)の処理

```c
 if (eat + bite == 0 && sameNumberCount(num, S_array[i], S_different_num, guess_different_num, same_num) == 1) {
    // S_arrayの数字と合致した数字の差分の1桁目を1(true)に
    if (!absolutely_array[S_different_num[0] - '0']) {
        absolutely_array[(S_different_num[0] - '0')] = 1;
        absolutely_array_count++;    
    }

    // S_arrayの数字と合致した数字の差分の2桁目を1(true)に
    if (!absolutely_array[S_different_num[1] - '0']) {
        absolutely_array[(S_different_num[1] - '0')] = 1;
        absolutely_array_count++;    
    }
    break;
}
```

次に[case2](#case-2--eat--bite--1-被っている数字2個)の処理
```c
else if (eat + bite == 1 && sameNumberCount(num, S_array[i], S_different_num, guess_different_num, same_num) == 2) { //case 2
    // S_arrayの数字と合致した数字の差分の1桁目を1(true)に
    if (!absolutely_array[S_different_num[0] - '0']) {
        absolutely_array[(S_different_num[0] - '0')] = 1;
        absolutely_array_count++;
    }
    // 予想した数字と合致した数字の差分の1桁目を0(false)に
    if (absolutely_array[guess_different_num[0] - '0']) {num_array[(guess_different_num[0] - '0')] = 0;}
        break;
    }
```

## 4. 確定した数字が2個 or 3個の時の処理
- 確定した数字が2個(absolutely_arrayのtrueの数が2個)
```c
if (absolutely_array_count == 2) {
    bool f = true;
    while (f) {
        random_num1 = generateRandomNum(0, 0, array_count - 1, NULL);
        
        /* absolutely_array(確定数字)の2つの数字と、
        num_array(可能性数字)のランダムな1つの数字を繋ぎ合わせる */
        sprintf(return_tmp_num, "%s%c", str_tmp_absolutely_num, str_tmp_num[random_num1]);

        // ルール通りの数字であり、前に予想したことがない数字かチェック
        if (check_history(atoi(return_tmp_num)) && ruleNum(return_tmp_num)) {f = false;}
    }
    strcpy(computer_guess_num, return_tmp_num);
    guess_history[round_count] = atoi(computer_guess_num);
    
    // normalでいつも通りに3桁の数字を生成して上書きしないように制御
    normal = false;

    // one_randomはこの手法で数字を作成したことを伝える役割を持つ
    one_random = true;
}
```
そして、この手法で生成した数字が `eat + bite != 3`であった場合、guess_history(可能性数字)から取り出した数字を0(false)にする。
同様に`eat + bite == 3`であった場合、1(true)にし、absolutely_arrayの存在を消す。

:::note info
absolutely_arrayのtrueの数が3になった時点で、使っている数字は確定されたため、普通のnum_arrayだけを使用し、プレイヤーの数字を割り出す。
:::


```c
if (one_random && (eat + bite) == 2 && absolutely_array_count == 2) {
    num_array[num[2] - '0'] = 0;
} else if (absolutely_array_count == 2 && (eat + bite) == 3) {
    memset(num_array, 0, sizeof(num_array)); //num_array リセット
    for (int i = 0; i < 3; i++) {
        num_array[num[i] - '0'] = 1;
    }
    absolutely_array_count = 0;
} 
```

# version3.0へ向けて
version2.0のロジックを考える過程で、いくつか改善できそうな点を見つけたため、それを導入する。