ポケモン界における最強タイプを遺伝的アルゴリズムで求めてみた

## はじめに

みなさんポケモンは好きでしょうか。

ポケモンには、現在18種類のタイプが存在しますが、中には弱点が多くて不利なタイプがありますよね。例えば、草タイプや氷タイプは弱点が多く、一方で鋼タイプや電気タイプは耐性が多くて有利に見えます。

そこで、もし実際にこれらのタイプのポケモンが同じ環境で共生していたら、何百世代か後には、**弱点が多いタイプは自然淘汰され、耐性が多いタイプが優勢になるのでは？？という疑問が湧きました。**

![natural_selection.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3705454/30561fe4-8562-6266-6341-241fae8f3349.jpeg)

今回は遺伝的アルゴリズムを用いて、異なるタイプのポケモンが共存する環境をシミュレーションします。能力が全く同じであると仮定した場合、どのタイプのポケモンが生き残るのか、またどのタイプが生存戦略として有利なのかを探求してみたいと思います。

![img_01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3705454/1cb99a5a-0050-2d4c-74bc-9d29f23163a9.png)
(https://www.pokemon.co.jp/ex/sun_moon/fight/161215_01.html) より


## 実験設定
繰り返す世代数は1000、全18単タイプ各1000匹のポケモンをはじめに用意します。
合計は18000匹となり、この値を世代内の基準の個体数とします。

遺伝的アルゴリズムを用い、タイプの交叉をします。また、今回突然変異は起こらないものとします。**本来のポケモンの設定ではあり得ませんが、今回は子孫が親のタイプを引き継ぐとします。**

注: この記事で「世代」という言葉はポケモンの世代(第〇世代)ではなく、遺伝的アルゴリズムとしての世代として使用します。

```python
class Pokemon(object):
    def __init__(self, style1, style2=None):
        if style2 == None:
            self.style1 = self.style2 = style1
        else:
            self.style1 = min(style1, style2)
            self.style2 = max(style1, style2)

    @property
    def is_single(self):
        return self.style1 == self.style2
```


### 評価
タイプの評価として、世代内でランダムな相手とそれぞれバトルさせます。バトルといっても、タイプ情報のみを使ったジャンケンのようなもので、種族値平均やサブウェポンなどは一切考慮していません。(ドラゴンタイプは種族値が比較的高い、水タイプは氷タイプのサブウェポンを持ちやすいなど)

各タイプのポケモンが世代を生き残るには、上記のバトルにおいて同世代のポケモン1匹と戦い、そのポケモンに勝つ必要があります。勝利確率を計算する式は以下の図に示します。**バトルによって求まった確率に応じて、そのポケモンの生死が決まります。**

### 勝利確率の計算方法
| タイプ相性 | 攻撃側スコア | 防御側スコア |
| ---- | ---- | ---- |
| 効果なし | +0% | +50% |
| いまひとつ1/4倍 | +10% | +40% |
| いまひとつ1/2倍 | +20% | +30% |
| 等倍 | +30% | +20% |
| 抜群2倍 | +40% | +10% |
| 抜群4倍 | +50% | +0% |

この上の表に従って計算します。**(攻撃側スコア+防御側スコア)によって求まった値**がそのまま勝利確率です。また、複合タイプの場合は、お互いに一番有利なタイプの技を使って攻撃しあうとします。


具体例を用いて説明します。例えば、はがね・ゴーストタイプvs炎・格闘タイプなら、こちらのはがね・ゴーストタイプからはゴーストタイプ(等倍)で攻撃し、相手からは炎タイプ(抜群2倍)で攻撃されます。よって攻撃側スコア30%と防御側スコア10%を合計して勝利確率40%となり、対して炎・格闘側の勝利確率は60%となります。

![attacker_score.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3705454/c8cddb62-4524-972f-36b6-447ec81d9e6c.jpeg)

![defender_score.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3705454/f83dca12-1003-2730-33dc-1cdadb01d531.jpeg)

この評価の過程により、世代内でバトルに勝利した個体半分が生き残り、子孫を残すことができます。

```python
class Pokemon(object):
    '''
    省略
    '''
    def evaluate_battle(self, other):
        def get_attacker_score(attacker, defender):
            def calculate_score(moves):
                if moves[0] == 0:
                    return 0
                elif len(moves) == 1:
                    return sum(moves) + 10
                elif len(moves) == 2:
                    return sum(moves) - 10

            # タイプ1の技で攻撃
            moves = []
            moves.append(compatibility_table[attacker.style1][defender.style1] * 10)
            if not defender.is_single:
                moves.append(compatibility_table[attacker.style1][defender.style2] * 10)
            moves.sort()
            attacker_score = calculate_score(moves)

            if not attacker.is_single:
                # タイプ2の技で攻撃
                moves = []
                moves.append(compatibility_table[attacker.style2][defender.style1] * 10)
                if not defender.is_single:
                    moves.append(compatibility_table[attacker.style2][defender.style2] * 10)
                moves.sort()
                # より相性がいい技を採用
                return max(attacker_score, calculate(moves))
            else:
                return attacker_score

        attacker_score = get_attacker_score(self, other)
        defender_score = 50 - get_attacker_score(other, self)

        return (attacker_score + defender_score)

    
```

### 交叉
世代の中で生き残っているポケモンを選び交叉させます。生き残ってる全ポケモンが子孫を残せるようにペアを組みます。

![crossover.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3705454/87a57b8a-a201-a2c2-94bd-540e334199b0.jpeg)


また、交叉は上の画像のように進んでいきます。親のタイプが草・毒タイプ、水・飛行タイプのとき、草・水タイプ、草・飛行タイプ、毒・水タイプ、毒・飛行タイプの4種類のタイプが生まれる可能性があります。
もし、親が単タイプの場合は血液型のようにそのタイプが2つあるように考えて遺伝をさせます。隔世遺伝などはせず、親のタイプのみを引き継ぎます。

```python
class Pokemon(object):
    '''
    省略
    '''
    def crossover(self, other):
        style1 = self.style1 if random.randint(0, 1) == 0 else self.style2
        style2 = other.style1 if random.randint(0, 1) == 0 else other.style2

        return Pokemon(style1, style2)
```

## 実験結果

実験結果です。一つ目のグラフはそのタイプを含んでいるポケモンが第1000世代目に何匹いるかを表した棒グラフで、二つ目のグラフは実際に第1000世代目にいるタイプの個体数を上位15タイプまで抜き出した棒グラフ、三つ目のグラフは第1000世代までのタイプの推移グラフです(18タイプ全てが載っているので見づらいですがご了承ください)。一つ目のグラフについて、複合タイプはそれぞれのタイプで一匹とカウントするので、グラフの合計値は18000以上になります。

![type.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3705454/b3c31d03-72ea-6229-28e5-346f0b1e2dc4.png)

![complex_type.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3705454/cd6053dc-33fb-5690-7900-4acf62dd9cd1.png)

![simulation.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3705454/04ff1a54-4230-91a6-eb44-924c60090f3a.png)

結果として、**水タイプ**が群を抜いて最強ということがわかりました！
最初の世代からずっと高い位置についていて、途中からは首位をキープし誰が見ても最強です。
**18000匹いるうちの約5400匹**を占めていて、第1000世代内の3割は水タイプのポケモンということになります。実際に第1000世代に蔓延るポケモンのタイプを見ても水タイプを複合したポケモンが圧倒的に多いことがわかります。

そして、かなり意外なことに**草タイプ**がかなり上位についています。絶滅寸前のところまで行くと思っていたので驚いてます。どうやら、環境上位に位置している**水・電気・地面タイプ全てに耐性を持っているタイプ**ということが鍵のようです。推移グラフを見るに、大きく数を減らしている世代もあるので、今回上位に位置したのは環境のおかげも大きそうです。

反対に、鋼タイプは水・電気タイプ両方にいまひとつで受け切られてしまい、上位のタイプで抜群以上を取れるタイプがほとんどないため、真ん中の位置にいます。今回は第1000世代の結果を見ているので今後の変動はありそうですが、弱いと思っていた氷タイプより下位にいることに驚きました。

## 考察

### 最強タイプについて
水タイプが強い理由について考察します。
水タイプの技は水・草・ドラゴンタイプには半減で受け切られますが、今回の生存競争では水タイプ同士で戦った際にどちらが勝っても水タイプの遺伝子を残せるので影響がなく、攻撃側として不利なタイプが二つだけで技範囲がかなり広いです。そしてその不利な草タイプは弱点が多いので複合タイプで補うことも容易いです。

また、水タイプは複合タイプもかなり強く、例えば水・電気タイプは弱点タイプが二つに対し耐性タイプが五つあり、水・地面タイプも弱点タイプが一つに対し耐性タイプが五つあります。
こういった**技範囲の広さ、複合タイプの優秀さ**から首位に君臨しているのだと予想されます。

### 絶滅したタイプについて
そして、残念ながら今回絶滅してしまったタイプについても考察します。
一番最初に絶滅してしまったのは**岩タイプ**です。これに関しては、環境上位に水・草・地面タイプといった弱点タイプが多いせいだと考えられます。約80世代とかなり早い段階で絶滅しているので、やはり環境に逆らうのは大変なことがわかりますね。

また、他に絶滅してしまったタイプを見てみると、共通点として**上位のタイプに対して抜群を取りづらい**ということが分かります。ノーマルタイプはもちろん他のタイプも総じて抜群を取りづらく、反対に上位のタイプを見てみるとお互いに弱点を突きながら生き残っています。

水タイプを中心に環境が回り、それに弱点を付ける電気・草タイプが増え、そしてそのタイプに弱点を付ける地面・炎タイプ...といった感じです。


## まとめ
今回は遺伝的アルゴリズムを用いてポケモンのタイプのシミュレーションを行い、結果として水タイプが一番強いということが分かりました。しかし、第1000世代で止めたのでこの結果が出たのであって、ここからまた世代数を重ねるごとに環境が変わり結果は変わってきそうです。

そして、今回はポケモンの種類や種族値平均などのタイプに関係ない要素は全て除外しています。
これらの要素を追加して、初期設定を変えたり、評価方法を変えることで全く違った結果も出ると思います。

今回、コードも全て公開しているので、興味がある人はぜひ設定を変えてやってみてください！


https://github.com/nope0124/pokemon-genetic-algorithm

## 追記
記事を一通り書いた後に気づいたんですが、この方も同様のことをグラフ理論を用いて行っていたようです。

https://qiita.com/masaka_programming/items/503eaa2c1fa776dfdb19

こちらの方の結果では草タイプが最弱になっていましたが、水タイプ(特に水・地面タイプ)は同様最強になっていて、手法が違っても似た結果に辿り着いていて面白いなあと思いました。

## 追追記

第25回進化計算学会研究会にてこの記事に関するポスター発表を行いました。

https://www.jpnsec.org/symposium202401.html