Numer0nのAIを作った（アルゴリズム編）

<font color="#0080FF">***Numer0n***</font>というゲームを最近知った．
***道具をひとつも使わない***で遊べるにもかかわらずかなり面白かったので，AIを作ることにした．
（下のgifは秘密の数が`8725`の時の挙動．5回で当てられている．）
![Numern_AI.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264330/65797b2e-bbb3-7852-0658-395d1f69643b.gif)
成果物はこちら．`stdin.rs`は見ない方がいいです．
<a href="https://github.com/lenna-kun/Numer0n_AI"><img src="https://github-link-card.s3.ap-northeast-1.amazonaws.com/lenna-kun/Numer0n_AI.png" width="460px"></a>

#1. Numer0nについて

私が友人との間で行っていたのは，厳密には***Numer0n***ではなくて，ルールが少しカスタマイズされたものだったようなので，私が作ったAIはそっちのルールを採用してる．（個人的にはこっちの方が面白い）

##1-1. オリジナルルール

まずは普通の***Numer0n***のルールについて説明．
<font color="#0080FF">***1対1で行われるターン制のゲーム***</font>で，まず2人のプレイヤーは***3桁***の秘密の数(以降***SN_3***)をそれぞれ決める．
最終的な目的は，相手の***SN_3***を当てることである．
2人のプレイヤーは交互に***3桁***の数字を言い合う．
***ここで，SN_3，およびコールする数は各桁の数字が全て異なるような数字でなければならない(133などはNG)．***
ただこれだけでは，

$${_{10}P_3}=720$$

通りから1つ選んで***コール***しあうだけのゲームだが，***Numer0n***では，***コール***した数に対して，相手から***2つの情報(<font color="#0080FF">EAT</font>/<font color="#0080FF">BITE</font>)***が与えられる．

###1-1-1. EAT

***<font color="#0080FF">EAT</font>***について説明．
当てたい***SN_3***を仮に`123`とする．
***コール***された数を仮に`025`とする．
この時，この真ん中の`2`に注目してほしい．コールされた数は，***SN_3***とは違う数字であるが，真ん中の`2`に関しては，場所も数字も同じである．
これを***<font color="#0080FF">EAT</font>***という．
***つまり，相手より先に相手に<font color="#0080FF">3 EAT</font>を言わせれば勝ち．***
###1-1-2. BITE
***<font color="#0080FF">BITE</font>***について説明．
当てたい***SN_3***を仮に`123`とする．
***コール***された数を仮に`359`とする．
この時，`3`に注目してほしい．コールされた数は，***SN_3***とは違う数字であり，***<font color="#0080FF">EAT</font>***も発生していないが，2つの数字はどちらも`3`を含んでいる．
これを***<font color="#0080FF">BITE</font>***という．
###1-1-3. 例
***コール***された数を1桁ずつ見ていき，***<font color="#0080FF">EAT</font>***と***<font color="#0080FF">BITE</font>***の発生回数を数える．
***SN_3***=`123`のときの例を下の表に示す．

|CALL|EAT|BITE|
|:-:|:-:|:-:|
|495|0|0|
|150|1|0|
|273|1|1|
|132|1|2|
|321|1|2|
|312|0|3|
|123|3|0|

##1-2. カスタマイズされたルール

カスタマイズされたルールでは，より場合の数を増やすために***4桁***で行う．
これだけでも

$${_{10}P_4}=5040$$

通りだが，さらに各桁について同じ数を何度用いても良いこととする．
よって，カスタマイズされたルールでは，場合の数は

$${10^4}=10000$$

通り (単純に0000~9999と考えても良い) である．
また，***<font color="#0080FF">EAT</font>/<font color="#0080FF">BITE</font>***を以下のように定義する．
###1-2-1. EAT/BITE
カスタマイズされたルールでの***<font color="#0080FF">EAT</font>/<font color="#0080FF">BITE</font>***について説明．
当てたい***SN_3***を仮に`1223`とする．
***コール***された数を仮に`0253`とする．
***コール***された数の桁を順に見ていく．
1桁目の`3`は，言うまでもなく***<font color="#0080FF">EAT</font>***である．
3桁目の`2`は，***<font color="#0080FF">EAT</font>***と***<font color="#0080FF">BITE</font>***の両方が発生しているが，このようなとき，***<font color="#0080FF">BITE</font>***は無効であると考える．
よってこれは***<font color="#0080FF">2 EAT / 0 BITE</font>***である．

当てたい***SN_3***を仮に`1223`とする．
***コール***された数を仮に`2022`とする．
***コール***された数の桁を順に見ていく．
1桁目から順に，***<font color="#0080FF">BITE</font>***，***<font color="#0080FF">EAT</font>***，***<font color="#0080FF">何もない</font>***，***<font color="#0080FF">BITE</font>***であるから，これは***<font color="#0080FF">1 EAT / 2 BITE</font>***である．
###1-2-2. 例
***コール***された数を1桁ずつ見ていき，***<font color="#0080FF">EAT</font>***と***<font color="#0080FF">BITE</font>***の発生回数を数える．
***SN_3***=`1223`のときの例を下の表に示す．

|CALL|EAT|BITE|
|:-:|:-:|:-:|
|3789|0|1|
|3305|0|2|
|2731|0|3|
|1111|1|3|
|2222|2|2|
|1323|3|1|
|2312|0|4|
|2332|0|4|
|1223|4|0|

#2. AIをどう作るか

このゲームにおける最強戦略は存在するかという問題は非常に難しい問題である[^1]．
しかし，固定戦略で言えば，ある程度適切な戦略が存在する．
今回はその一つを実装した．
####とにかく場合の数を絞り込みたい
</br>
今回は，***どれだけ残る可能性を絞り込むことができるか***ということのみを評価基準として***コール***の評価を行った．

このゲームにおいて，ある***SN_3***に対してある***コール***がされたとき，それに対する***<font color="#0080FF">EAT</font>/<font color="#0080FF">BITE</font>***の組み合わせは***14種類***．

|EAT\BITE|0|1|2|3|4|
|:-:|:-:|:-:|:-:|:-:|:-:|
|**0**|0\0|0\1|0\2|0\3|0\4|
|**1**|1\0|1\1|1\2|1\3||
|**2**|2\0|2\1|2\2|||
|**3**|2\0|3\1||||
つまり，***SN_3***の候補が今$N$個あるとすると，***コール***によってそれらは***<font color="#0080FF">14グループに分割される</font>***わけだ．
各グループに属する候補の数をそれぞれ

$$a_1,\ a_2,\ \cdots\ a_{14} \hspace{20pt} (~\sum_{i=1}^{14} a_i = N~)$$

と表すと，この$a_i$が全体的に小さくなるような***コール***を選べば良いということがわかる．
そのような選び方を2種類説明する．

##2-1. α-β法 (Mini-Max法)

これは，ある***コール***を評価した値を

$$\max \\{\ a_i,\ i = 1,\ 2,\ \cdots,\ 14 \ \\}$$

として，この値が最も小さい***コール***を選ぶという手法である．
（普通はある程度の深さまで読むが，今回は***深さ1まで***とした．）
これにより，想定される***<font color="#0080FF">最大</font>***の損害が***<font color="#0080FF">最小</font>***になるような決断を行うことができる．

##2-2. エントロピーが最大となるコールを選ぶ方法

事象$X$が起こる確率を$P(X)$とすると、 事象$X$の発生により受け取る***<font color="#0080FF">選択情報量</font>***$I(X)$は

$$I(X) = \log \frac{1}{P(X = x)}=-\log P(X = x)$$

で表される．要するに，$\frac{1}{2^n}$の確率で起こる事象が発生すると，情報量$n$を得るということ．
これの***<font color="#0080FF">期待値</font>***$H(P)$

$$H(P) = \sum_{x \in \Omega} P(X = x)~(~-\log P(X = x)~)$$

が最大となるような***コール***を選ぶことで，より大きな情報量を得る決断を行うことができる．
今回のケースに当てはめると，

$$P(X = x) = \frac{a_x}{N}$$

となる．
今回はなんとなく少数を持ち込ませたくなかったので***<font color="#0080FF">Mini-Max法</font>***を採用した．

#3. 次回
次回は，実装上の工夫の話をします．
具体的には，EAT/BITEの数を高速に求める方法とか．

[^1]: https://www.tanaka.ecc.u-tokyo.ac.jp/ktanaka/papers/gpw96.pdf