現在巷では遺伝的アルゴリズムで最高にエッチな画像を生成するページが話題ですね。それにあやかって少し前に作成した遺伝的アルゴリズムによるポケモンPTの生成プログラムの解説を投稿したいと思います。
前置き
私は大学のポケモンサークルに所属しており、サークル内大会に参加することにしました。そのサークル内大会では、
- 種族値合計330以下縛り
- 見せ合い6-3のシングルバトル
- Lv50合わせ
- ポケモン"ヨワシ"、及び持ち物"でんきだま"使用禁止
という条件が課せられることになりました。
(種族値とはなんぞや？という方はこちら。簡単に言うとポケモンそれ自身がもっているステータスの強さ。)
もちろん種族値縛りなんて対戦は行ったこともなければ、前例も数えるほどしかありません。その少ない前例も進化前縛りでガチ対戦に潜るというものや、縛る数値が異なるもの、そもそも対戦に用いるソフトが異なるものばかりで、環境が全く同じものはありません。基本的にポケモンのパーティを組む際には
- 強そうなポケモンを1~2匹選ぶ
- そのポケモンが苦手とするポケモンに対抗出来るポケモンを選ぶ
という流れで組むのが一般的ですが、そもそも
- 強いポケモンが分からない
- それに対抗できるポケモンも分からない
という状況に陥ってしまうわけです。そもそもパーティを作ったとしても試運転する場所がない。そこで環境がなければ作ればいいと思い、プログラム上で仮想的に対戦させるシステムを構築。ついでにポケモンも自動で生成するようにしてパーティを構築したわけです。
設計
PTに用いるポケモンの生成は、今回の主題となっている__遺伝的アルゴリズム__によって行いました。遺伝的アルゴリズムとは
- 個体の作成
- 評価値の作成
という2STEPが存在します。詳しくはこのページが分かりやすいと思います。
つまり、個体生成と評価値の作成を行うプログラムを書く必要があります。個体の作成にはポケモンの諸データが必要になりますが、評価値を作成するために使用しますので、評価値を作成できる形式で作成する必要があります。つまり、プログラムは評価値の作成をどう行うか、という点から着手し始めたほうが良さそうです。
ポケモンの強さを評価するには、ポケモンバトルをエミュレーションしてしまうのが最も適しています。かと言って、ポケモンの対戦シミュレートを0から自作するのはまず無理でしょう。ポケモン対戦はあまりにも要素が多く、それを作るだけでおそらくサークル内大会には間に合わないと予測できます。ポケモン剣盾のバトルシミュレーターを自作した人のブログを見ると、2ヶ月掛けて5000行書いたらしいです。恐ろしいですね。もちろんこの人に対して直接アポイントを取ることも考えたのですが、結局はそこから対戦シミュレートのためのプログラムを書かないといけないわけです。面倒ですね。いろいろ探してみましたが、結局Pokemon Showdown!を利用するのがてっとり早いと思いまして、それを利用することになりました。
実はShowdownってオープンソースでして、GitHubにソースコードが上がっています。また自動対戦についてはShowdown用AIが開発されていたため、それをローカルに移植して用いました。自分のPCでShowdownサーバーを立てて行っても良かったのですが、通信によるオーバーヘッドが気になるのと、そもそもAI同士で戦わせる方法が分からなかったので気合で実装しました。（ここが一番辛かったです。）
ポケモンの対戦シミュレートが行えれば、複数のポケモンを生成しその中で総当たり戦を行えばどのポケモンが強いのかを導くことが出来ます。また、ポケモン対戦シミュレートをShowdownで行うことが決まったので、ポケモンはそれにインポート出来る形式で生成すれば良いことまで決まりました。showdownのディレクトリにデータ自体は存在したので、json形式に書き直してPythonにimport出来るようにしました。拡張子が.jsonのものがポケモンのデータです。.txtはルール上使用可能なポケモンやアイテムをまとめたものです。
また、ポケモンは対戦シミュレータを使用する関係上、以下の形式で表します。詳細はこちら
NICKNAME|SPECIES|ITEM|ABILITY|MOVES|NATURE|EVS|GENDER|IVS|SHINY|LEVEL|HAPPINESS,POKEBALL,HIDDENPOWERTYPE
※EVSが努力値、IVSが個体値です。
プログラミング
ポケモンの生成
ポケモンの初期値生成は、ポケモンの種族を固定し、そのポケモンの覚える技、特性、技、ステータスなどをランダムに生成しました。専用の持ち物に関しては、専用の持ち物があるポケモンに対して例外的な持ち物を持たせる(可能性を与える)例外的処理を行いました。
ステータスの生成は以下のコードで行いました。（一部抽出）本当はフローチャートとかで表したかったけれど長いので諦めました
import random
import numpy as np
import json
from copy import copy
natures = json.load(open('./data/natures.json')) #性格のリストの読み込み
stasList = ['HP', 'Atk', 'Def', 'SpA', 'SpD', 'Spe']
natureWeight = []
for key, item in natures.items():
if item['minus'] == 'Atk' or item['minus'] == 'SpA':
natureWeight.append(3)
elif item['minus'] == 'Spe':
natureWeight.append(2)
else:
natureWeight.append(1)
def pChoice(epsilon):
if epsilon > random.random():
return True
else:
return False
def choicePoint(nature, count):
if nature['name'] == 'Serious':
points = np.random.choice(stasList, size=count, replace=False)
elif count == 3:
prob = np.array([0.125]*6)
prob[stasList.index(nature['plus'])] = 0.5
prob[stasList.index(nature['minus'])] = 0
points = np.random.choice(stasList, size=3, replace=False, p=prob)
elif count == 5:
points = copy(stasList)
points.remove(nature['minus'])
return points
def EVcalc(pokemon, nature, count):
w = [0] * 6
points = choicePoint(nature, count)
for i in points:
w[stasList.index(i)] = 1
pokemon['EVs'][i] = 4
if nature['plus'] in points:
w[stasList.index(nature['plus'])] += 1
roopCount = 62 if count == 3 else 61
for i in range(roopCount):
incrementPoint = random.choices(stasList, weights=w)[0]
pokemon['EVs'][incrementPoint] += 8
if pokemon['EVs'][incrementPoint] == 252:
w[stasList.index(incrementPoint)] = 0
else:
w[stasList.index(incrementPoint)] += 1
return pokemon
def generate():
pokemon = {'EVs':{'HP':0, 'Atk':0, 'Def':0, 'SpA':0, 'SpD':0, 'Spe':0}, 'IVs':{'HP':31, 'Atk':31, 'Def':31, 'SpA':31, 'SpD':31, 'Spe':31}}
nature = random.choices(list(natures.keys()),weights=natureWeight)[0]
nature = natures[nature]
pokemon.update(nature)
if nature['minus'] == 'Atk' or nature['minus'] == 'Spe':
pokemon['IVs'][nature['minus']] = 0 if random.randrange(3) else 31
if pChoice(0.7):
if nature['plus'] == 'Spe':
pokemon['EVs']['Spe'] = 252
weight = [10, 92, 3, 92, 3, 0]
weight[stasList.index(nature['minus'])] = 0
tmp = random.choices(stasList, weights=weight)[0]
pokemon['EVs'][tmp] = 252
if pokemon['EVs']['HP'] == 0:
pokemon['EVs']['HP'] = 4
elif nature['minus'] != 'SpD':
pokemon['EVs']['SpD'] = 4
else:
pokemon['EVs']['Def'] = 4
elif nature['plus'] == 'Atk' or nature['plus'] == 'SpA':
pokemon['EVs'][nature['plus']] = 252
weight = [49, 0, 1, 0, 1, 49]
weight[stasList.index(nature['minus'])] = 0
tmp = random.choices(stasList, weights=weight)[0]
pokemon['EVs'][tmp] = 252
if pokemon['EVs']['Spe'] == 0 and nature['minus'] == 'Spe':
pokemon['EVs']['Spe'] = 4
elif pokemon['EVs']['HP'] == 0:
pokemon['EVs']['HP'] = 4
else:
pokemon['EVs']['SpD'] = 4
else:
points = choicePoint(nature, 3)
for i in points[:2]:
pokemon['EVs'][i] = 252
pokemon['EVs'][points[-1]] = 4
else:
count = 3 if pChoice(0.7) else 5
pokemon = EVcalc(pokemon, nature, count)
pass
return pokemon
if __name__ == '__main__':
print(generate())
>> {
>> "EVs": {
>> "HP": 4,
>> "Atk": 0,
>> "Def": 0,
>> "SpA": 252,
>> "SpD": 0,
>> "Spe": 252
>> },
>> "IVs": {
>> "HP": 31,
>> "Atk": 0,
>> "Def": 31,
>> "SpA": 31,
>> "SpD": 31,
>> "Spe": 31
>> },
>> "name": "Modest",
>> "plus": "SpA",
>> "minus": "Atk"
>> } #返ってくるデータの例
性格のリストは辞書型になっており、["plus"], ["minus"]にそれぞれ上昇補正箇所・下方修正箇所が納められています。無補正は"None"を返します。
ポケモン対戦において無補正の性格は基本的に用いられないため、通常5つある性格ですがそのうち1つのみを選ぶようにしています。またnatureWeightで性格の出る確率に傾斜をつけたりしています。努力値はそれぞれの性格に基づいた確率で振っていきます。この確率の根拠は？（綾波レイ）女の勘よ♡（葛城ミサト）何たるアバウト！（式波アスカ）詳細はコードをご覧ください。
ポケモンの遺伝交配は、以下の手順で行いました。
- 親となるポケモンを同一種族から2匹抽出する。
- アイテムを両親から60%の確率で遺伝(それぞれ30%)、残りの40%はランダムで選択する。
- 特性を両親から80%の確率で遺伝(それぞれ40%)、残りの20%はランダムで選択する。
- ステータスを両親から60%の確率で遺伝(それぞれ30%)、残りの40%はランダムで選択する。
- 両親の覚えている技の中から3~4つ遺伝させる。50%の確率で1つ技をランダム選択。両親ともに覚えている技は選択されやすくする。
アイテム・特性・ステータス・技をそれぞれ独立試行で遺伝させたので、それらを上手く連携させたポケモンが生まれるか不安だったのですが、襷カウンターゾロアなど、コンボと思われる組み合わせのポケモンも存在したので安心しました。"カウンター"とは相手から受けた物理攻撃のダメージを倍にして返すという技で、"きあいのタスキ"という持ち物を持たせることにより、確実に相手から受けた攻撃を倒されずに反射することが出来る、という組み合わせです。（おそらく偶然産まれた存在が、技と持ち物を同時に遺伝し続けたものだと思われます。）このような偶然の産物が遺伝しなかった、という事故を防ぐために、評価値の高かったポケモンほど多くの子孫を残すようなプログラムを書きました。その成果が表れたものだと思われます。コードは以下の通りです。
import os
import random
import math
import re
from collections import Counter
from .modules import item
from .modules import ability
from .modules import move
from .modules import stats
def pChoice(epsilon):
if epsilon > random.random():
return True
else:
return False
def heredity(dna1, dna2, elem, prob):
if pChoice(prob):
return dna1[elem] if random.randrange(2) else dna2[elem]
else:
return False
def randomChoice(population, weights, ignore='False'):
if ignore != 'False':
weights[ignore] = 0
if sum(weights) > 0:
return random.choices(population, weights=weights)[0]
else:
return False
def heredityMove(dna1, dna2, species):
moves = dna1.split(',')
moves.extend(dna2.split(','))
if len(moves) < 4:
return ','.join(moves)
moves = Counter(moves)
moves, weight = [i for i in moves.keys()], [i for i in moves.values()]
childMoves = []
ignore = 'False'
for i in range(3):
selectmove = randomChoice(moves, weight, ignore)
if selectmove:
childMoves.append(selectmove)
ignore = moves.index(selectmove)
else:
return ','.join(childMoves)
if pChoice(0.5):
childMoves.append(randomChoice(moves, weight, ignore))
else:
randomMove = move.selectMove(species).split(',')
for i in randomMove:
if not i in childMoves:
childMoves.append(i)
break
return ','.join(childMoves)
def cross(parent1, parent2):
dna1 = parent1.split('|')
dna2 = parent2.split('|')
species = dna1[1]
child = ['']*12
child[1] = species
child[10] = '50'
child[2] = i if (i:=heredity(dna1, dna2, 2, 0.6)) else item.selectItem(species)
child[3] = i if (i:=heredity(dna1, dna2, 3, 0.8)) else ability.selectability(species)
if pChoice(0.6):
if random.randrange(2):
child[5:9] = dna1[5:9]
else:
child[5:9] = dna2[5:9]
else:
child[5:9] = stats.showdownpt().split('|')
child[4] = heredityMove(dna1[4], dna2[4], species)
return '|'.join(child)
def ga(parents, parentCnt=25):
generateCnt = len(parents)
parents = parents[:parentCnt]
parents = [re.sub('\d+\.*\d* \|', '|', i, 1) for i in parents]
children = []
for i in range(generateCnt // parentCnt):
weight = [math.sqrt(parentCnt-i) for i in range(parentCnt)]
parent1 = parents[i]
for j in range(parentCnt):
parent2 = randomChoice(parents, weight, i)
children.append(cross(parent1, parent2))
return children
from .modulesでインポートしているファイル群はそれぞれアイテム、特性、技、ステータスをランダムで生成するプログラムです。突然変異に用います。親世代のポケモンのうち、上位からparentCntの数だけの親を残し、さらにその中から上位ほど親として選んで交配させます。ポケモンのシステムにある預け屋さんのシステムとは全く異なるので混同しないようにしてください。
ポケモンの評価
評価値を作成するためにポケモン同士で対戦を行います。遺伝的アルゴリズムを成立させるためには、十分な数の親世代とそれらの適切評価が必要です。しかしながら、188種類も存在する種族値330以下のポケモン全てに対してそれぞれに十分の親世代を用意し、総当たりで対戦することは計算量的に避けたいです。そこで、以下の手順でポケモンを絞り込むことにしました。
- 188匹をランダムで5匹づつに分ける。（余りの3匹は適当に選択する）
- 5匹づつに分けた中で遺伝的アルゴリズムを用い、ポケモン種族毎の評価値を算出。
- 前の評価値から上位72匹を選出。
- 上位72匹+余りの3匹の75匹を、さらにランダムに5匹づつに分け、種族毎の評価値を算出。
- 75匹のうち上位20匹を選び、遺伝的アルゴリズムを用いる。
遺伝的アルゴリズムを用いた評価値の作成は、
- 各種族毎に20匹づつランダムに生成。（20*5で100匹のポケモンが生成される）
- 100匹の中でランダムに対戦を行う。
- 対戦結果を踏まえ、評価値を算出。
- 種族ごとに評価値の高かったポケモンを親世代に、次世代を作成。
というように行います。そして、最終的に評価値を種族ごとに合計し、合計値が高いものを選出します。
対戦を踏まえた評価値の作成はTrueSkillを用います。分かりやすく言うとゲームのレーティングです。Microsoftが開発したレーティングアルゴリズムで、Eloレーティングなどの既存のレーティングアルゴリズムより収束が早いなどと言った利点があるようです。詳細はこちら。対戦シミュレートは並列化を行っても重く、できるだけ対戦回数を減らしたいという目的からこれを採用しました。~~はっきりいって仕組みはてんで分かりません。~~ありがたいことにPythonパッケージとして配布されているので有り難く利用させて頂きます。Microsoft最高！！
また、最後20匹で遺伝的アルゴリズムを回す際は、上位15種類は次世代に残し、残り5種類を最終段階に残ったポケモンの中からランダムに入れ替えるようにしました。局所解に陥ることを防ぐ目的です。この学習を時間の限り行いました。
パーティの生成
ポケモンのパーティを自動生成するためには、かなり多くの数のポケモンの組み合わせから遺伝的アルゴリズムを組まなければなりません。またその場合は選出も行わなければならないわけですが、現時点では選出を最適で行うアルゴリズムを組む時間もありません。（この時点で大会まで12時間程度しか時間がありませんでした。）しかしながら、この場合求められている解は最適解である必要はなく、近似解でも十分に目的を達成することが出来ます。そこで動的計画法により近似解を求めることにしました。（実際にこのプログラムの実装が正しい自信がありません。）手順は以下の通りです。
- あるポケモンがある種族のポケモンに対してどれだけ役割を遂行出来るかを計算した対面相性表を作成する。
- 対面相性表を元に、出来る限り多くのポケモンに対して役割を持てるような組み合わせを動的計画法により探索する
動的計画法により探索する方法は以下のとおりです。
- パーティが1匹で構成されている場合の評価値を、全てのポケモンについて計算する
- パーティにもう1匹ポケモンを加える場合、手順1で計算されたポケモンのうちどれに加えれば最も評価値が高いのか計算する
- 手順1,2をパーティが6匹になるまで繰り返す
また、パーティの評価値は以下のように計算しています。
- あるポケモンを別の種族のポケモン5匹（遺伝的アルゴリズムにより生成された上位5匹）と戦わせ、その勝ち数をnとする。
- 0.8/(1+10**(3.5-n))を計算し、mとする。
- PTがある種族に対する対策度合いをpとし、1-Π(1-m)で表す。（Πは総乗記号）
- Σpをパーティの評価値とする。
あるポケモンに対してn=5,4であるポケモンを出来るだけ包括的に取れるようなパーティに出来るようにプログラムを組んだつもりです。ここらへんは上手く言語化出来た自信が無いので、気になった方は直接聞きに来てください。手順2で使用した曲線はシグモイド曲線という名前があるそうです。
そうして出来たパーティがこちらになります。
調整
このままだと持ち物が被ってしまっていたり、覚えていても意味の薄い技を覚えていたりしたので以下の変更を行いました。
- ウデッポウの持ち物をしんかのきせき->こだわりスカーフに
- チョンチーの持ち物をヨプのみ->とつげきチョッキに
- ウデッポウの技をクラブハンマー->はどうだんに
- ウデッポウの技をじたばた->とんぼがえりに
- ゾロアの技をつめとぎ->ふいうちに
- ゾロアの技をにほんばれ->シャドーボールに
- テッシードの技をたいあたり->はたきおとすに
- テッシードの技をエナジーボール->タネばくだんに
- ヤトウモリの技をわるだくみ->りゅうのはどうに
- ヤトウモリの技をベノムトラップ->ヘドロウェーブに
- ヤトウモリの技をねっぷう->かえんほうしゃに
- デスマスの技をシャドーボール->たたりめに
- デスマスの技をてっぺき->おにびに
- デスマスの技をあまごい->みちづれに
- デスマスの技をりんしょう->シャドーボールに
- チョンチーの技をなみのり->ねっとうに
- チョンチーの技をバブルこうせん->れいとうビームに
- チョンチーの技をワイルドボルト->ボルトチェンジに
- チョンチーの技をハイドロポンプ->10まんボルトに
技に関しては、最終的な結果からかなり変えました。このアルゴリズム（と学習量）で算出された技のデータセットは完璧ではなく、（人の目で見ても）欠陥があるものでしたので、技の選択アルゴリズムは改善の余地があると思われます。
最終的に作成したパーティは以下の通りになりました。
感想
実際の大会は優勝こそしたものの、自分自身のプレイングミスが目立つ結果となりました。しかしながら勝てたのは、テッシードくんが炎技を尽く避けてくれたおかげです。
遺伝的アルゴリズムでパーティを作成する過程では、人間には思いつかない奇妙なコンボなどが生成されたりしないかなぁなどと期待していましたが、流石にそんなことはありませんでした。しかし、ウデッポウ・ゾロア・ヤトウモリなど、自分しか使用者がいないポケモンを用いてパーティを作成することが出来たという点だけで私的には満足しています。
今後の目標としては、人の手で修正せずともまともであるパーティを生成することが挙げられます。今回は技をガッツリ修正したので、それを行わなくてもいい感じに技を覚えていてほしいです。また、このアルゴリズムだとどうしても対面構築になってしまいがちという欠点もあります。また挑戦するだけの時間があれば、そういった点を踏まえてリベンジしたいと考えています。
ソースコード
開発を期限ギリギリまで行っていた（言い訳）影響で、ファイル類がとても見るに堪えないくらい散らかっていますが、それでも良ければこちらに公開しています。現在ドキュメントを整理したり体裁を整えたりしていますので、温かい目で見守っていただければ幸いです。