はじめに
この記事は、対戦ゲームにおいて勝利を目指すゲームAIの戦略を考えるための記事です。エンタメとして人間を楽しませるAIには触れていません。また体系的な知識の紹介ではなく、私個人の考え方を書きだしたものになります。生暖かい気持ちで読むことをお勧めします。
この記事のターゲット
プログラミングは多少出来るけど、ゲームAIは何をすればいいのかよく分からないという方。AtCoderで言えば茶色か緑～、コドゲで言えば未経験～Silverリーグくらい？
早速の寄り道
ここでは取り扱いませんが、ゲーム理論で調べると色々出てくると思います。一部だけでも役立つので、見れる範囲で見てみましょう。
記事中で扱う用語
リソース
ゲーム内における、ライフ、お金などの資源です。見方次第では、計算時間などもリソースと言えます。
アドバンテージ
対戦相手と比較して、あるリソースで有利な状態を指します。リソースAではアドバンテージがあるけどリソースBではディスアドバンテージ（不利）がある、というケースもあります。
ステージ
ゲームによりますが、いくつかの段階（ステージ）に分けることが出来ます。これはゲーム側でステージが明確に分かれているというわけではなく、そういう考え方が出来るということです。ゲーム中に「そろそろ終盤だな」と思ったりしないでしょうか。そんな感じのやつです。
基本的な考え方
ゲームの進行とは、アドバンテージの取捨選択、あるいは対戦相手とのアドバンテージの交換です。ゲームには複数のリソースがあり、通常は何か１つのリソースだけを伸ばせば勝てるようには出来ていません。*1 何かを取るために何かを諦める選択の連続です。
では、何のアドバンテージをどれくらい得るように動くべきなのか？それこそがゲームAIの性能や個性を決める重要なポイントです。*2 ゲーム全体の構造を元に、ステージ毎の戦略を考えてみましょう。
ステージ毎の戦略
例として、少し複雑ではありますが、Age of Empires、シヴィライゼーション、League of Legendsのような戦略ゲームを考えてみましょう。*3
序盤戦は、リソースを稼ぐステージです。自軍をパワーアップさせ、索敵を行い、自陣を広く堅牢にし、より有利な状態で相手と接敵できるようにします。ユニットや建築物というリソースの獲得、情報というリソースの獲得ですね。これらのリソースが敵軍を上回れば、そのままアドバンテージになります。
中盤戦は、互いのリソースを削り合い、より多くのアドバンテージを生むステージです。有利なユニットをぶつけて、自分の槍兵５体と相手の騎兵１０体を相打ちさせたりします。*4 この例では互いにリソースは消費しますが、相手の方が多くのリソースを失うため、アドバンテージを得ることになります。また、上手く情報アドバンテージを活かせば、無防備な敵拠点を被害なしで殲滅することも出来るでしょう。戦略ゲームが好きな人間からすると、この辺りが一番楽しいのではないでしょうか。
終盤戦は、それまでに得たアドバンテージを活かしてゲームの終結を目指すステージです。最終的にゲームに勝つことができるなら、それまでに得たリソースやアドバンテージをいくらでも投入できます。相手を詰ませることが出来るのか？失敗してアドバンテージを失い、逆転を許すことにならないか？自分が不利側なら、逆転の手は無いか？という緻密な計算を行うことになるでしょう。そういった詰み狙いと詰み回避を行いながら、合間にアドバンテージの獲得を狙っていきます。
このように、ステージ毎に戦略を分けることで人間が考える際に行動の指針を立てやすくなります。
ゲームAIへの戦略の組み込み方
人間である実装者が戦略を考えられるようになったところで、次にゲームAIにそれを実装する方法を考えましょう。
ルールベース*5の場合、終盤で取るべき行動ほど優先順位を上げて何の行動をするか決めればそれっぽくなるのではないでしょうか。『詰みチェック＞アドバンテージの取得＞リソース稼ぎ』のような感じですね。ただコドゲの下位リーグに関して言えば、終盤ステージを意識せずにアドバンテージの取得まで、あるいはリソースを稼ぐだけでもリーグ突破できるものが多い気がします。*6 終盤や中盤の動作は序盤の動作が前提になるという意味でも、実装は序盤に行うリソース稼ぎからすると良いでしょうね。
評価関数を用いたゲーム木探索の場合は、リソースまたはアドバンテージを評価に組み込みます。どのリソースを稼ぐべきか、どのリソースでアドバンテージを得るべきかを、値の大小により優先順位を付けてAIに教えてあげる感じですね。何のリソースの優先度を上げればいいの？ということについては一概に言えないので、そこは各々工夫してみましょう。ここについては後で別の記事としてコツを書くかもしれないし、書かないかもしれません。
TronBattleでの例
簡単な具体例として、コドゲ定番のTronBattleで実装することを考えてみましょう。上下左右いずれかの未踏マスに移動して、最後まで脱落せずに生き残った人が勝ちになるゲームです。リソースの種類（≒ゲームの奥深さ）は少ないゲームですが、その分ゲームAIの入門にはうってつけです。
初級（序盤戦略）：残りの移動可能なマス数を、残りライフというリソースとして考えます。４方向それぞれに移動した場合の残りライフを計算し、残りライフが最大になる方向に移動しましょう。これはルールベースでもゲーム木探索でも出来ますが、DFSあるいはBFSによる数え上げが必要です。リソースを稼ぐというよりはすり減らしていますが、こういう例も稀によくあります。
中級（中盤戦略）：対戦相手との移動可能なマス数（残りライフ）の差を、アドバンテージとして考えます。４方向それぞれに移動した場合のアドバンテージを計算し、アドバンテージが最大になる方向に移動しましょう。これ単体では初級との差が『相手より広い場所にいるときに細い道を閉じる』だけになりイマイチかもしれませんが、数手読みや、ボロノイ図等による見込み計算を加えると更に強力になります。*7 *8
上級（終盤戦略）：『自分の移動可能マス数＞相手の移動可能マス数』の盤面にできれば勝ち確定です。そんな盤面にできる手が見つかったらやりましょう。*9 逆に、『自分の移動可能マス数＜相手の移動可能マス数』になる場所には移動してはいけません。 この挙動自体は中級の動きができれば既に出来ている可能性が高いですが、出来ていなければやりましょう。また、１位が無理なときに２位を確定させるなどで期待順位を高めることが出来ます。
おわりに
長々と書いてはみましたが、特に目新しいことでもなく、おそらくは無意識でやっている人も多いのではないかと思います。また無理にこの枠に当てはめようとしても上手く行かないケースもあるかと思うので、こういう考え方の人もいるんだなという程度に参考にしていただければ幸いです。
自分はこういう考え方をしてるよ！というご意見があれば是非コメントかTwitterで教えてください。
*1:優れたゲームとはそういうものだからです。分かれ道があって右か左かでうんうん悩むのが難しく、また楽しいものなのです。
*2:余談ですが、それを考えずに手を探索できる構造もあります。MCTSとか。
*3:実はLoLはプレイしたことありませんし、他２つもにわかなので、変な事を言っていたらエアプ乙と笑ってください。
*4:とりあえずコストや盤面は無視して、多く討ち取れたからヨシ！ということにしましょう。
*5:if文連打マン。
*6:リソースの取得がそのまま点になり、勝敗判定に使われるパターン。
*7:中盤戦略と言いつつ最序盤から行える戦略なので、例として適切なのか分かりませんね…。
*8:2人対戦を想定しています。3人以上の対戦が解放されているなら、誰と比較して何位を狙うかは好きにやりましょう。
*9:ターン順による誤差はあえて無視しているので、実装する際は自力で計算してみましょう。
