こんにちわ世界！ 今日はプログラミングの話をしよう。自分は技術屋ではないけれどプログラミングにはちょっとだけ興味と知識がある。お陰でごく短くて簡単なコードぐらいなら書くことが出来るぞ。エンジニアその他の諸兄らにはどうか寛大な心で読んで欲しい。

　そんな自分が最近になり少し背伸びをしてアルゴリズムを勉強してみたらいくつかの便利な手法を見かけたので使ってみたい。素晴らしいハンマーを手にして全てのモノが釘に見えるぞ。何か使ってみるのに手頃な題材はないか？  そう、ゲームだ。全ての道はゲームに通じている。

　さて、『ソルヴァーズ』はプレイしたかな？ 1人用TRPGと称されるこのゲームはヒーロー会社を経営し様々な事件を解決していくアナログゲームだ。つまり、ソリティアである。PCゲームのXCOMを小さく削り出して「選択と結果のランダム性」に独自の考えを入れたゲーム、と言うのが自分の理解だ。ゲームバランスの良さも見所だが、その価値の30％くらいは軽妙な内部テキストにある。読もう。

月刊スパ帝国Vol.22(ソルヴァーズ) | スパ帝国

　今回の記事はこいつを簡単なAIを書いて攻略しようという試みである。目指すのはワンマンアーミーによるクリアだ。ポンコツAIはソルヴァーズをクリア出来るだろうか？ 出来るとしたらどの程度の確率で？ 今のクラスタが注目しているのはソルヴァーズよりナショナルエコノミーなのでは？ 疑問は尽きない。検証しよう。

(補足情報)

　ソルヴァーズをプレイしたことがない人向けの補足情報。この記事で対象としているのは通常プレイと異なる「ワンマンアーミー」と呼ばれる縛りプレイの一種で、本来なら３人まで雇用可能なヒーローを１人しか雇用しないことで難易度を上げる。このワンマンアーミーでの攻略は自分の腕ではおよそ20-30%程度のクリア率、上手いプレイヤーでも50%を超えるかどうか疑問という難易度だ。

 Solve Solvers

 　では具体的にAIにどうやってソルヴァーズを攻略させるのかを説明していこう。ソルヴァーズは内政とミッションという二つのフェイズを繰り返していくゲームだ。内政フェイズで設備を追加したりヒーローを強化し、ミッションフェイズで強化されたヒーローが事件を解決して内政フェイズに使う資源を獲得してくる。この拡大再生産のループになっている。そこでAIもこの二つのフェイズで分割して取り組む。

ミッションフェイズ

 「ひとつ思いついた―では足りぬ。すべて思いつけ。」
《無限への突入/Enter the Infinite》

　そもそもミッションフェイズの流れはこうだ。
１.ヒーローの能力で決まる数のダイスを振る
２.各ミッション固有のアプローチに対してダイスを振り分ける
３.ダイスが使われたアプローチから得る達成度を合計して成否を判定する

　AIにやって欲しいのは最も良い結果を得られるようなダイス振り分けである。そこで最も愚直な方法として、振り分け可能な全ての組み合わせに対して達成度を計算させるという方法がある。振った３つのダイスが[1,5,6]でアプローチが3種類なら3P3=3!=6通りだ。おっと、ソルヴァーズでは「ダイスを使わず廃棄する」ことも可能なので、これも試行しなければならん。

　が、試行錯誤した末に「N個のダイスを使わない」組み合わせは前向き枝刈りすることにした。つまり試行せず無視する。１つ目の理由は試行数が膨大になるからだ。もう１つの理由はほとんどの場合でダイスを全て使う方が良い結果を得られるため。割に合わないのでレアケースを取りこぼそう。

　これで試行すべき組み合わせが得られた。しかしミッションで得られる資源は複数ある。「名声/悪名」「ヒーロー経験値」「研究」だ。単純に最大の名声が得られる組み合わせが最も良いのだろうか？ 最終ミッションをクリアするには研究を重視すべき場面もあるんじゃないか？ 悪名4と引き換えに経験値20を得るのは良い選択だろうか？

盤面評価

　今回作るAIを理解する上で重要なのが「盤面の評価」だ。ゲームの状態を評価して点数をつける。将棋で言えば自分の駒がどれくらい残っているか、オセロなら自分の色がどれくらい支配的か。実際にはもっと複雑だが、ともかくこれと同じことがソルヴァーズにも適用出来る。会社の持つ名声や研究、ヒーローの能力や経験値を総合的に評価して点数をつけてやれる。

　評価する際の基準だが今回はシンプルにそれぞれのパラメータに点数をつけて合計してみよう。名声1は10点、研究1は3点、ヒーローの経験値1は0.5点といった具合にだ。何なら階層分析法のようにきちんと重み付けしてもいいが最初は適当でいいだろう。雑にね。

　こうして盤面を点数付けしてやることでさっきの「悪名4と引き換えに経験値20を得るのは良い選択だろうか？」という疑問にも答えが出る。組み合わせを試行しミッションによる名声/悪名などを反映させ、反映後の盤面を評価して最も良い点数になる組み合わせを実際に選べば良い。

　多くのゲームプレイAIはこの盤面評価が最も脳漿を絞るべき重要な部分である。その次が試行すべき選択肢を絞り込む枝刈りの方法だ。人間でも強いプレイヤーは盤面を見て優勢かどうかを見極めるのが非常に上手い。そして重点的にどの選択肢を深く読んでいくべきかよく知っている。

内政フェイズ

　内政フェイズも似たようなやり方をしていく。施設や装備品に対しても同じように得点を設定しておき、盤面評価に組み込む。施設の評価得点というのは言わば大局観だ、即座には役に立たないが将来的には役立つという場合、将来の利益を考慮した得点付けをしておく。これをしないと近視眼的な決定になる、CIV4でAIが小屋に市民を配置しないように。

　今回のAIは固定された順番で決定木を作る。以下の順番にそれぞれ選択可能な行動について分岐し、それぞれに対して盤面評価を行う。得られた盤面評価が最良のものを選ぶのはミッションと同じだ。

１.「建て増しする」
２.「施設を追加する」
３.「装備品を購入する」
４.「レベルアップする」

　

　本来、ソルヴァーズのルールでは内政を好きな順番に行っても良い。しかし、組み合わせが増え複雑になるため、そしてこの順番でほとんど上手く行くので順番を固定した。ついでに一度の内政で複数の施設や装備品を購入するといったことも出来ない。更にAIは施設を左から順番に詰めて設置しなければならないという自主的な縛りを持っている。ポンコツ！

成果

　これでAIがソルヴァーズをプレイするための準備は全て整った。では、実際にプレイさせてみよう。なお、ビジネスパーソンについてはスキルの実装がややこしくなるという理由で除外した。どうせワンマンアーミーでは役に立たないので問題ない。

　およそ1分間に50ゲームくらいの速度で動く全自動ソルヴァープレイ機くん。試しにそれぞれの前職で100回ほどプレイさせてみよう。(検証の都合で前職を固定しダイスを4つ振る)

	1	2	3	4	5	6	7	8	9	10b	10c	win
兵士	0	1	0	2	3	11	75	0	0	0	8	0
警官	0	4	0	7	5	14	50	0	0	0	20	0
ロボット	0	0	0	2	8	10	69	0	0	0	11	0
エンジニア	0	4	1	9	8	6	63	0	0	0	9	0
科学者	0	6	3	20	19	10	35	0	0	0	6	1

 　データの見方は列が各ミッション終了時点にゲームオーバーとなったケース数。なんつうか酷い有様としか言い様がない。チンパンジーを座らせて延々とソルヴァーズをプレイさせているのか？  どいつもこいつもキルドーザーになぎ倒され過ぎなんだよ！ クリア者は500人中で科学者1人だけだ。ミュータントヒーローさえ獲得すれば何とかクリア可能なのだろう。

パラメーターの調整

　この結果を見て、盤面評価が最も重要なのだから評価に使う点数付けを改良すればもっとマシになるのでは？と考えた人もいるだろう。その通りだ。そもそも全ての前職に対して同じ得点表を使うのは間違っている。格納庫はロボット以外に役立たないし、科学者は全力で技能を上げるべきだ。それぞれの前職に適したより良い評価値を個別に設定しよう。

　しかし、この設定を自分でやるのは少々難しい。そもそも自分はゲームがそこまで上手くない。そこで、これもプログラミングによって解決しよう。こういった最も良い値の組合せを探索するトピックは最適化問題と言う名前で知られている。この評価関数は離散的(非連続的)で多峰性を持つので特に組合せ最適化とか呼ぶ。

　そもそも、ミッションや内政でやっている探索自体が最適化の１種だ(しらみつぶし探索)。ミッションの探索で盤面評価を参考により良い組合せを探したのと同じように、今度はAIのプレイ結果を参考により良い評価得点表の組合せを探すというわけ。

　ただし、今度は探索するのが数値の組合せなのでミッション探索のようにしらみ潰し探索を使うのは現実的でない。こういった実数型の組合せ最適化に使われる手法はいくつかある。疑似焼きなまし法、タブーサーチ、あるいは機械学習的にニューラルネットワークを利用する方法もある。それに今回使う遺伝的アルゴリズムだ。

遺伝的アルゴリズム

　遺伝的アルゴリズムはその名の通り生物の進化や遺伝子からのアナロジーで最適化する手法だ。求めたい数値の組合せを遺伝子として扱い評価関数の結果を得る。より良い評価を得られた遺伝子は優先的に残し、他の遺伝子と組み合わせ交叉させる。そして一定の確率で遺伝子に突然変異を加える。適応度が高い遺伝子を後世に伝えていくことで最適化する生物の進化と同じ仕組みなのである。使うのに数式が必要なく自然由来でオーガニックなので人に優しいアルゴリズムだ。

　この手法の良い点は最適な解が保証されない代わりに膨大な組合せから現実的な時間で比較的マシな近似解を得られるところ。局所解への収束も避けられる。今回の問題に向いている手法だ。こんな話ばかりしても通じにくいので実際に流れを追っていこう。

１.最初に遺伝子コードの集団をランダム生成する
　今回は１種類の点数を表現するのに３桁の数字を使う。実数型なので１桁を指数部にし、残り２桁を仮数部として扱う。例えば「213」というコードは13 * 10^2 =1300と読まれる(詳しくは浮動小数点数などで検索)。会社とヒーローのパラメータ、施設それぞれに得点をつけるので合計で23種類の点数が必要になる。
コード：3363371520052691…
得点表：名声1 => 36000点、悪名1 => 37000点、支出1 => 520点…

２.それぞれの遺伝子を評価する
　自然界における生存競争や性淘汰のようにより良い遺伝子を選ぶ。具体的には遺伝子コードから作られる得点表を元にAIがゲームを10回プレイする。このプレイ結果からどれくらいAIが優秀か評価づけする。ここでは倒産したミッション数と、最終ミッション時点の最高達成度を元に評価する。よりクリアに近い遺伝子が偉い世界なのだ。

３.優秀な遺伝子を取り出して交叉させる

　集団から評価が高い遺伝子を複数取り出してコードの一部を入れ替えて新しい子孫を作る。この選出方法や交叉方法には様々な種類があるが、ここでは選出方法にトーナメント選択、交叉方法に二点交叉を利用する。

　トーナメント選択というのはランダムにN個の遺伝子を集団から取り出して、その中から最も評価値(適応度)が高いものを使う選択方法だ。一度に取り出す数(トーナメントサイズ)を多くすればより優秀な遺伝子が残りやすくなり、少なくすれば遺伝子の多様性が保たれやすい。

　二点交叉というのはランダムに遺伝子コードの二点を決めて、それを境界に二つの遺伝子を交換する交叉方法だ。

<二点の決定>
親A：19|238415200|50673863
親B：31|926917518|22691691

<交叉>
子A：1992691751850673863
子B：3123841520022691691

４.一定確率で突然変異させる

　交叉だけでは色々な問題が生まれるため、低確率で遺伝子コードを変化させるのが突然変異だ。もっとも、必須のものではなく交叉だけで利用する人もまあまあいるらしい。今回の実装ではそれぞれの遺伝子に対して50％の確率で２点の遺伝子座を乱数の値に置き換える。遺伝子長が23*3=69なので遺伝子座あたり1.5％になる。これは一般的に推奨される確率の範囲内。

 

　こうして２−４の操作を延々と繰り返してより良い遺伝子コード、すなわち得点表を探索する。なんだか難しそうな入りだったが非常に簡単な仕組みだろう。自然は単純な操作で複雑なことをやってのける、ちょうクールだね。ところでアサガオはどうやって眼もないのに最も近くにある支柱を探し出して巻き付けるのだろうか？(答え)

　ちなみに、遺伝的アルゴリズムの表現型(遺伝子が表すデータ形式)は何らかの手順あるいはツリーなども突っ込めるので、例えばCIV4で最適な序盤の都市内政(生産キュー/市民配置)を探索することも出来る。

調整された得点表の成果

　それじゃあ試しに最もクリア可能性が高かった科学者だけをチューニングしてみよう。集団数100、トーナメントサイズ4でひたすら淘汰させる。

　しかし大変残念なことに22時間ほど計算させたにも関わらず僅かに30世代ほどしか進まなかった。200世代くらいは淘汰させる予定だったが仕方なく中断。何はともあれ、遺伝的アルゴリズムで調整された遺伝子を１つ取り出して科学者を1000回ほどプレイさせてみよう。

1	2	3	4	5	6	7	8	9	10b	10c	win
0	218	131	160	123	86	127	0	0	0	123	33

　クリア率が3.3％に向上したぞ。わーい。残念ながら劇的な向上は得られなかった。まぁチンパンジーにプレイさせるよりはマシだろう。途中の脱落率が高いがこれは評価の算出が最終的なクリアの成否に注目しているため。仮に「可能な限り長く生き残る」という価値で評価すれば95％ぐらいは最終戦に辿り着くようになる。

　おそらく、世代数をこれ以上に続けても劇的な向上は見込めないだろう。今回のようにシンプルなAIではこれぐらいは限界らしい。このやり方で出来ることは一通りやってしまったので今回はここまで。もしも次やる時はMGGやJGGなど他の選択モデルや機械学習や統計のアプローチを試してみたい。

まったく何の成果も生まなかった場合でも「間違った方法を１つ見つけた」としてここにカウントされる。
ソルヴァーズ - 「研究とは」