この記事はPortAdventCalendar2017の23日目となります。
はじめに
どうも、最近サーバーエンジニアからAndroidアプリエンジニアになったサイトウです。
websocketのリコネクションや非同期のハンドリングなどに頭を悩ませる苦痛（楽しい）な日々を送っています。
ところで皆さんはアズールレーンというゲームをプレイしたことがありますか？
このゲームは戦艦などをモチーフにしたキャラで癒されるゲームです(本当は違います)。
私はこのゲームをやりたくて毎朝６時半起きてたら、朝型エンジニアになりました(・ω・´ )
さて、今回の内容ですが
アズールレーンのパーティ(ゲーム中では艦隊という)をオススメしてくれるツールを作ろうと思います。
ある程度プレイしてるとたくさんキャラが育つと思いますが、このゲームのキャラは全員魅力的なのでプレイヤーとしてはどのキャラをパーティにして攻略や任務（クエストみたいなの）をこなすか迷うことが多々あるんですよね。そこで、こんなパーティはどうかな？って提案してくれるツールを作ろうと思いました。
仕様
今回作るものは強さと好き度の合計を基準にパーティを提案してくれるものです。
- 好き度とは、100が最大としたらこのキャラは87好きなんだ！みたいな数値で個人によってキャラの好き嫌いが分かれると思います。その好き嫌いを数値化したものを好き度と呼ぶことにします。
- 好き度合計とは、パーティに配属されているキャラの好き度を合計した数値です。
- 強さとは、パーティとしての強さを指します。パーティに含まれるキャラ個々の強さを合計すれば良いと考えるかもしれませんが、このゲームではとあるキャラがパーティ内にいる時強くなるという仕組みがあります（有名なのが赤城加賀の組み合わせです）。
- キャラには前衛、後衛の属性があり、パーティには前衛キャラと後衛キャラを必ず一隻以上配置しなければなりません。
- 前衛キャラは三隻、後衛キャラも三隻までしか配置は出来ません。したがってパーティは高々六隻までとなります。
好き度は個人で設定するようにします。最大値は100で最小値は0、デフォルトは０とします。
キャラの強さも今回は個人で設定するようにします。本当は装備や強化具合、基礎ステータスなどで定まるようにしたいのですが、時間の都合上やむなしです。
このゲームをプレイしている方は三笠など旗艦に置くと特定のキャラが強くなるシステムがあるのはご存知だと思いますが、今回は間に合いそうになかったので対応しないことにします。対応するのは赤城加賀のような組み合わせのみとします。
定式化
max\;\; F(x_1, ..., x_n) + L(x_1, ..., x_n) \\
s.t. \;\; 2 \leq \sum_{i=1}^n x_i \leq 6 \\
x_i \in \{0, 1\},\; n \in N(ただし、0を認めない)
目的関数のFとLは、それぞれ強さと好き度合計を意味します。
F(x_1, ..., x_n) = \phi_f (\sum_{i=1}^{n} f(x_i) + CF(x_1, ..., x_n)) \\
ただし, f(x_i)はキャラiの強さ \\
CF(x_i, ..., x_n)はとあるキャラ達の組み合わせによる強さとする. \\
\; \\
L(x_1, ..., x_n) = \phi_l (\sum_{i=1}^{n} l(x_i)) \\
ただし, l(x_i)はキャラiの好き度とする. \\
\; \\
\phi は正規化する写像とする. \\
これで十分かと思いますが、実はまだ足りていません。
選出された前衛艦が１から３隻かつ後衛艦隊が１から３隻を満たす。
この制約条件が必要となります。
好き度合計と強さを正規化する写像を自由に調整することにより、好き度を優先したりすることができる。
また、曖昧さを持たせたいときは目的関数に正の実数値をランダムに返すRを加えてあげると良い。これにより、毎回実行するたびに異なる値を取得できると思われる。
アルゴリズム
今回は遺伝的アルゴリズムを使ってこの問題を解くことにします。
もちろん枝狩りや動的計画法などでも出来ると思います。
単純に遺伝的アルゴリズムを使いたかったのが選んだ理由です。
また、今回は単純遺伝的アルゴリズムで戦いますが、これは単純遺伝的アルゴリズムでどこまで頑張れるのかが気になったからで、サービスなどで使うときは問題に適した交叉などを選んでください。
遺伝的アルゴリズムはネットや本で簡単に学べるアルゴリズムですのでこの記事では数学的な面を簡単に説明することにします。
遺伝的アルゴリズムはNPやNP困難に所属する問題を解くアルゴリズムとして期待されています。
ナップサック問題や巡回セールスマンのような組み合わせ最適化問題、sinなどの関数の最大値最小値、機械学習などかなり広い範囲で使えるアルゴリズムでもあります。
関数の最大値は山登り法とかでも解くことが可能ですが、その時問題になるのが局所最適解に収束するという点です。
この点などを踏まえていくつか解説しようと思います。
そもそもNPとNP困難ってなんぞや
NPの定義は「非決定性チューリングマシンで多項式時間内に解くことができる問題」です。
NP困難の定義は「NPに属する任意の問題と比べて、それ以上に難しい問題」です。
難しい言葉の定義ですが、次のように思っておくと良いかもしれません。
「我々のパソコンでは解くのにかなり時間がかかる問題」。
要するに高速に求めるには近似的に解くなどのようなに工夫しなければならない問題です。
これらの問題を近似的に解くことを期待されているのが遺伝的アルゴリズムです。
これは余談ですが、クラスNP=クラスPとなるのかならないのかという問題が有名なP=NP?予想です。
偉大な学者達がクラスNPの問題を多項式で解いた瞬間P=NPとなるまで証明してくれてるので頑張って多項式時間内に解けることを証明できたら、100万ドルを手に入れることができます。ビットコインなどに頭を悩ませている人たちはどうでしょうか？
局所最適解
とある関数の最大値を求める問題を考えてみることにします。
高校数学の記憶を思い出すと複雑な関数になるといくつかの山が出来、大体その山の頂点のどれかが最適解となる感覚があると思います。
y = -x^2を描くとx=0のとき山の頂点となる１つの山が出来ると思います。
山が一つの時はそこが最適解となりますが、複数の時は最大値にならないときがあります。その時の値を局所最適解と呼びます。
非凸計画問題などによく出てきて、我々をよく悩ませてくれるものです。
プログラミングしているときによく現れる症状としては、プログラムが１つの解に収束して結果が出てくるのだけど、本当に求めたい解ではないなど。
遺伝的アルゴリズムでは、この頭痛の種をつぶすことができます。それは突然変異というものです。
設計的な話
これは私の考えなのですが、遺伝的アルゴリズムを採用してどのように問題にアプローチする時に大事なのが数学的に考えることだと思います。
まずは落ち着いて問題をLP標準形などに定式化することが大事だと思います。
そして問題を定式化したら、分析します。
なぜ、このようなことをする必要があるかといいますと、実行不可能や非有界などが存在するときがあるからです。
これは仕様を見直したりしなければいくら頑張っても答えを得ることができません。
つまり、何も考えずに闇雲に遺伝的アルゴリズムを使ったところで答えが得られる保証がなく、ただコーディング時間を無駄にするだけです。
設計・実装
*** 選択、淘汰はCrossの中にいれています(少し設計ミスがあったのでその影響のためです。)
コードを貼るとすごい量になるのでここでは実装の仕方について解説します。今回はKotlinで実装してます。
GeneにObserverを張っている理由
各遺伝子には評価が存在します。ですが、交叉や突然変異などによって評価が変わってしまうので遺伝子情報が更新されたら評価も更新するためです。
一様交叉の実装方法
(0,1,1,0,1,1,1)のようなbit列をランダムに用意します。
0の時入れ替えない、1の時入れ替えるようにすれば簡単に実現できます。
キャラクター情報
AzurlaneGeneの中にenum classを引いて実装してます。
呼び出している部分（クライアント側のコード)
val algo = GeneticAlgorithm.build(AzurlaneFitness(), AzurlaneGene.createPop(100)){
operators = arrayListOf(OnePointCross(), AzurlaneMutate())
}
for (i in 1..50) {
algo.next()
}
val res = algo.result()
結果
android上に出力しているのでandroidの画面となります。
ヴァルファストになっていますが、正しくはベルファストですね。ごめんなさい＞＜
私は赤城加賀が好きなので赤城加賀がおすすめされるパターンが多いですね。
世帯ごとの世代を調べた結果、ヒッチハイキングが起こっているのと遺伝的アルゴリズムらしくない収束の仕方をしていたのでランダム探索に近いものになっていました。
とりあえずで一点交叉を採用しているのがネックとなっているみたいでした。
最後に
今回はゲームのパーティのおすすめを作るものでしたが、記事のおすすめなども作ることが出来ます。
その場合は記事に何らかの価値をもたせてルールを作ることで出来そうですね。
また、今回は遺伝的アルゴリズムからアプローチしましたが、アルゴリズムは１つではないのでその問題に適したアルゴリズムを選択すると良いでしょう。
次回記事を書く時があれば、交叉などを今回の問題に適した独自の方式に修正して、今回妥協した強さなどを機械的に算出するようにし、より優れたパーティレコメンドシステムをまとめられたらと思います。
もしくは、今回軽く触れた遺伝的アルゴリズムについてもう少し深く触れたものを書こうかなと思います。