2017年5月、Unityの一大イベントであるUniteが開催されました。
Unity2017に関する魅力的な機能も色々発表され、期待に胸が膨らんじゃいます。

そういえば、今回のUniteには会社の後輩がボランティアスタッフとして参加しました。
「大変だったけどとっても楽しかった！」とのことですので、予定が確保できそうな方はぜひ次回のUniteに参加してみてください！（筆者も参加してみたい・・・！）

さてさて、今回はシミュレーションゲームのアルゴリズムを作ってみましょう。（賀好 昭仁）

## シミュレーションゲームというジャンルは広すぎました

改めて調べてみると、シミュレーションゲームには

・シミュレーションRPG
・恋愛シミュレーション
・フライトシミュレータ

など多種多様なゲームが含まれております。

ということで、今回はシミュレーションゲームの中でも特に歴史のある「マス目を使ったターン制戦略シミュレーションゲーム」のアルゴリズムを作ってみます。

※「マス目を使ったターン制戦略シミュレーションゲーム」ですとちょっと長いので、以降は「戦略シミュレーション」と称させていただきます。

＜余談＞
最近、ファイアーエムブレムヒーローズ（FEH）で久々にシミュレーションRPGをプレイしました。
筆者はこれまでシミュレーションRPGをいろいろプレイしてきましたが、すべて1マップに1時間前後かかるガッツリ系のゲームばかりでした。
FEHもその類かと思いきや、1マップ数分で終わるというスマホゲームらしいライトさ。
本格シミュレーションPRGでも工夫次第でここまでライトに作れるものなのか、と驚いたものです。（そして、ライトでも面白い・・・！）

## 戦略シミュレーションの要素を考えてみる

ゲームを作っていくにあたって、まずは戦略シミュレーションの要素を考えてみましょう。

戦略と名がつく通り、自軍のユニットを使って敵軍のユニットと戦うゲームですので、

・自軍ユニット
・敵軍ユニット

そして、戦うための舞台も必要です。
障害物の無い平原、うっそうとした森、山岳地帯など、さまざまなマップが登場すると楽しそうですね。

戦略シミュレーションに最低限必要な要素はこれくらいでしょうか。要素はとっても少ないですが、ユニットの種類・マップの種類・自軍と敵軍の戦力バランスや戦況・敵AIなどに変化をつければ、要素は少なくてもさまざまな楽しみ方ができます。

そういえば、将棋やチェスなどはユニットの種類が固定でマップも1種類しかありません。
それでも打ち手次第でさまざまな局面が楽しめることを考えますと、戦略シミュレーションの根本的な部分の奥深さが垣間見えますね。

## ユニットの動ける範囲を考えてみる

いざ戦略シミュレーションを作ろうとしたとき、まず頭を悩ませるのは「ユニットが動ける範囲をどう計算するか」だと思います。

将棋やチェスでは各コマの移動のルールがシンプルなため、動ける範囲を求めるのは簡単です。
ただ、戦略シミュレーションではユニットの移動力に応じて1回の行動で複数マス動けたり、同じ1マスでも平原と森で移動コストが変わったりと、さまざまな要素が絡んできます。

これらを解決するために、移動可能範囲を計算するためのアルゴリズムを実装する必要があります。

移動可能範囲は、簡単なアルゴリズムで求めることができます。まずはマップの各マス目の移動コストを列挙します。
移動不可のマス目は、どのユニットも移動不可能になるような大きな値を入れておけばOKです。
下の図では、移動コスト1の茶色のマスは平原、移動コスト2の緑色のマスは森、移動コスト9の灰色のマスは岩山（進入不可）と考えてください。

続いて、移動力の計算を行います。まずは動かしたいユニットが居るマスの座標に、そのユニットの移動力分の数値を入れておきます。下図は移動力4を持つユニットがマップ中央にいた場合の例です。

続いて、ユニットの居る上下左右のマスに、対象マスの移動コスト分を引いた値を入れます。
※対象マスに既に値が入っていた場合、上書きせずそのままにします。

下図では、ユニットの居る赤いマスを基準に、その四方のマス（黄色いマス）に値を入れています。
右側のマスは森（移動コスト2）なので、ここだけ数値が2になっています。

続いて、移動力の値を1減らしたマス、つまり値が「3」のマスを基準に同じ計算を行います。

あとは値を1ずつ減らしていき、0になるまで同じ処理を繰り返せば、移動可能範囲を導き出すことができます。
ちなみに、値がマイナスになったマスは移動力が足りず移動できないマスですので、最終的な移動可能範囲は下図の青いマスとなります。

特殊なマス（後述）がない限り、移動力や地系が変わっても同じ処理で移動範囲を求めることができます。

シミュレーションPRGや戦略シミュレーション全般で大活躍しそうなアルゴリズムですね！

ユニットを移動させる際にユニットが移動先にパッとワープしたり、移動不可マスを通って移動したりすると、プレイヤーは違和感を感じてしまいます。
違和感を感じさせないようにするためには、目的地までの移動経路を算出する必要があります。

移動経路は、先ほどの移動範囲の計算と逆の手順で導き出すことが可能です。

下図は赤いマスが移動先だった場合の例です。
まずは移動先マスの値（残りの移動力）に、そのマスの移動コストを足します。
四方にあるマスを見ると、上記の値に合致するマスが必ず1つ以上存在します。（図中の黄色いマス）
ユニットはこの黄色いマスを通って移動したことになります。
続いて黄色いマスを基点に同じ処理を繰り返すことで、徐々に移動経路が明らかになっていきます。

~~図 6 経路算出（移動先から2歩手前まで）~~

もし黄色いマスが複数存在する場合は「どちらからでも来られる」ことになります。

あとはユニットが元居た位置までこれを繰り返せば、移動経路が明らかになります。下図では、中央にある「4」のマスから「←↓←←」の経路と「↓←←←」の経路の2パターンが割り出せました。

## アルゴリズムの注意点と改良方法

今回は不要ですが、もしもマップに下記のようなマスが存在する場合は前述のアルゴリズムをそのまま使うことができません。

・移動力を消費しないマス
・通ると移動力が回復するマス

このようなマスに対応する場合、下記のような処理を加える必要があります。

・該当マスから周りのマスに対し、移動力の計算＆書き込みが終わったかどうかのフラグを設ける
・数字（残りの移動力）が埋まっているマスに対して、より大きい値が入れられる場合は値を上書き、上記フラグをクリアする処理
・ひと通りの計算が終わったのち、マス目上の最大移動力をベースに再度同じ計算を行う（この際、上記フラグが立っているマスは計算対象から除外）、全てのマスにフラグが立つまで何周も続ける

また、移動力回復マスにワープするマスを組み合わせると無限ループに陥る可能性もありますので、このようなマスを実装する場合は注意しましょう。

今回のサンプルプロジェクトはこちら。

https://github.com/akako/gamealgorithm-war-simulation/releases/tag/for_algorithm10

Unityで作ろう！ゲームアルゴリズム10 1

ユニットを選択して移動可能マスをハイライト、マスを選択して経路計算＋移動するところまでを作りました。
まだまだゲームとは言えませんが、これだけでも戦略シミュレーションの香りがプンプン漂ってきますね。

今回のアルゴリズムは、マス目を使った戦略シミュレーションであれば必ず活躍します。
HEX（6角形）のマス目でも同じアルゴリズムが適用できますので、ぜひ試してみてください！

【Unityで作ろう！ゲームアルゴリズム】シミュレーションゲームのアルゴリズムを作ってみる

筆者はずっとインドア派（というかゲーマー）だったのですが、最近は外出して体を動かすことにハマっています。

お散歩にジョギング、立ち寄った公園でお花の写真を撮るなど、楽しみ方はいろいろ。ちょっと歩くだけで、脳をビビっと刺激する変わった人や妙なモノに出会ったりするものです。アイデアが煮詰まったなら、ぜひ気晴らしに散歩に出てみましょう！

それでは早速ですが、今回はリバーシの対戦相手となるAIを作ってみましょう。（賀好 昭仁）

まずは用語の説明から入りましょう。
AIとは、Artificial Intelligence（人工知能）のことです。

世の中には様々なAIが溢れています。
そして、AIのほとんどは何らかの目的を達成するために作られています。
例えば、工業用の機械を制御して製品を作るための制御AIや、部屋中をくまなく掃除するための掃除機AIなど、その用途専用に最適化されたAIが沢山存在しています。
本記事で作成するAIも「リバーシの対戦相手を務める」という目的があります。

一方で、最近ディープラーニングと呼ばれる手法を利用した新しいタイプのAIが登場し始めています。

ディープラーニングとは、機械学習の手法のひとつです。
ざっくり説明しますと、まず「ニューラルネットワーク」という、人間の脳の仕組みを模した機能を備えるAIを準備します。
このAIにデータを与えると、AIはデータの特徴を分析し、学習していきます。
十分に学習が進むと、それまでの学習を元にして、与えられた情報がどのようなものであるかを判断することが出来るようになります。

ディープラーニングで出来上がったAIの例を挙げてみますと、2016年3月、Googleが「ネコを認識するAI」が出来たと発表し、話題となりました。

このAIがなぜスゴイかと言いますと、「人間がAIにネコとはどのようなものであるかを教えた」わけではなく、AIにYouTubeから取り出した1,000万枚の画像を与えてディープラーニングを進めた結果、「AIがネコの特徴を覚えた（ネコを判別させたかった訳ではないのに、勝手にネコを判別できるようになった）」という点です。

これは驚くべきことで、AIが置かれた状況に応じて臨機応変に（それこそ、まるで生き物のように）成長していける可能性を示唆しています。
いずれは「自ら言葉を覚え、人と自在に会話できるAI」なども誕生することでしょう。

いやはや、思い切り脱線してしまいました。

ディープラーニング用AIのプログラミングも記事にしたいところですが、筆者自身まだまだ理解が足りていませんので、いずれ機会があればということで。（笑

今回作成するAIは「リバーシができるAI」です。

一言で「リバーシができるAI」と言っても、実装の方向性はいくつか考えられます。

### １．ゲームの展開を予測するAI

今後のゲームの展開を予測し、最善と思われる手を打つAI

どういった手を打った結果どのような成果が得られたかを逐次収集し、どんどん強くなっていくAI

リバーシをプレイする上で「有利になる条件」「不利になる条件」を定義し、それに応じてプレイを進めるAI

リバーシの場合は打てる手が限られています。
ロジックが完璧に実装出来たとすると、1.のパターンが最強です。
AIに手を完全に予測されてしまうと、どう足掻いても勝ち目はありません。
その代わり、手を予測するために凄まじい処理能力が必要となります。

2.は対戦する度に強くなっていくAIで、実装するのがとても面白そうです。
ただ、仕組みがかなり複雑になってしまいます。

今回は一番シンプルな3.のパターンで実装を進めてみましょう。
（部分的に1.のパターンも使用します）

## リバーシのAIに必要なインターフェース

リバーシのAIが必要とする情報と、情報を与えられた時にどのようなレスポンスを返せばよいかを考えてみましょう。

まず、AIが次の手を打つために必要な最低限の情報は

・自分の石の色
・現在の盤面の状況

これらの情報から現在の状況がわかれば、次にどのような手を打てばよいかが計算出来るというわけです。

情報を受け取ったのち、AIが返すべきレスポンスは「次の手」です。
リバーシにおける「次の手」とは「どのマスに石を置くか」ということですので、マスの座標を返せばOKです。

## ランダムに石を置くAIを作ってみる

まずは適当なAIを作ってみましょう。
石が置けるマスからランダムで1マス選ぶAIです。

AIに必要な処理をまとめた基底クラスです。
盤面シミュレータのサブクラスを同梱し、簡単に盤面のシミュレーションが出来るようにしています。
AIはこのクラスを継承し、フィールド情報を受け取って次の手を返すGetNextMove()メソッドを実装すればOKです。

https://github.com/akako/gamealgorithm-reversi/blob/master/Assets/Scenes/Game/Scripts/AI/Game_AI_Base.cs

ランダムに石を置くAIです。
盤面シミュレータから石を置けるマスを取得し、その中からランダムで1つ選んで返すだけの処理となっています。

https://github.com/akako/gamealgorithm-reversi/blob/master/Assets/Scenes/Game/Scripts/AI/Game_AI_Random.cs

以下にAIを組み込んだプロジェクトを準備しましたので、試しにプレイしてみてください。

https://github.com/akako/gamealgorithm-reversi/releases/tag/for_algorithm3

今回のAIはシンプルで組み込みはとても簡単ですので、組み込みに関する解説は割愛させていただきます
（Game SceneController.cs・Game Field.cs・Game Cell.cs スクリプトの前回との差分をご確認ください）

## ちゃんと動くAIを作ってみる

Game AI RandomのAIと対戦してみると、ランダムに石を置くだけではとっても弱いことがお判りいただけるかと思います。
次はリバーシのセオリーに沿って次の手を打つAIを作ってみましょう。

まずはセオリーを書き出してみます。
Google先生にセオリーを教えてもらい、実装しやすそうなものをいくつかチョイスしました。

・角を取る
・角の斜め隣は出来るだけ打たない
・序盤は少なく取る
・取った石が相手の石に囲まれている場所を狙う（「中割り」と呼ぶそうです）
・終盤は石をたくさん返せる場所を狙う

余談ですが、筆者は今回の調査で「中割り」を初めて知りました。

## セオリーの重み付けをしてみる

盤面の状況は様々で一概には判断出来ないため、「どの状況がどの程度重要か」をAIに教えてあげます。

・角を取る
「50ポイント」の重要度

・終盤までは角の斜め隣は出来るだけ打たない
盤面の3分の2が埋まるまでは、該当マスは「-30ポイント」の重要度

・序盤は少なく取る
盤面の3分の1が埋まるまでは、「取れる石の数 ✕ -10ポイント」の重要度

・取った石が相手の石に囲まれている場所を狙う（「中割り」と呼ぶそうです）
「取った石の周囲にある相手の石の数 ✕ 2ポイント」の重要度

・終盤は石をたくさん返せる場所を狙う
盤面の3分の2が埋まっていれば、「返した石の数 ✕ 5ポイント」の重要度

上記の計算を実装し、どの手を打てば良いかを判断出来るようにしてみます。
（なお、各値は筆者の感覚で適当に設定しています

前述の処理を実装したAIです。
石を置けるマスのポイントを計算し、ポイントが一番高いマスを返すというわかりやすい処理になっています。

https://github.com/akako/gamealgorithm-reversi/blob/master/Assets/Scenes/Game/Scripts/AI/Game_AI_Theory.cs

に同梱しており、Game SceneController.cs 63〜64行目のコメントを付け外しして

//ais.Add(Game_Field.StoneColor.Black, new Game_AI_Random(Game_Field.StoneColor.Black));
ais.Add(Game_Field.StoneColor.White, new Game_AI_Theory(Game_Field.StoneColor.White));

にすれば、Game AI Theoryと対戦出来るようになります。
ちなみに、両方の行のコメントアウトを外せばGame AI RandomとGame AI fTheoryの対戦を見ることも出来ますよ！

## （オマケ）AIに性格を付けてみる

AIにも個性があった方が、より一層ゲームが盛り上がります。

・調子に乗るAI
盤面に自分の石が多いと調子に乗って適当に打つようになるAI

・欲に目がくらんでしまうAI
3つ以上石をひっくり返せるならば、それがどんな酷い手であっても打ってしまうAI

・スロースターターなAI
序盤は適当に打つが、終盤になると急に強くなるAI

などです。
リバーシのAIであれば、上記のいずれもGame AI Theoryを少しカスタムするだけで作れるかと思います。

ゲームに登場するキャラクターの性格を考えて、それに相応しいAIを作ってみると良いかもしれません。

ディープラーニングからAIの性格まで、ずいぶん話が広がってしまいました。
ゲームにおいてAIはゲームバランスに直結するため、プログラマとしては腕の見せどころです。
強すぎず弱すぎず、プレイヤーが「心地よい」と思えるような対戦相手を作ることを目指しましょう。（激ムズゲームも需要はありますけどね）

また、複雑で面白いAIが作れるならば、それ自体がゲームになることもあります。
少し昔のゲームですが、シーマンやワンダープロジェクトJなどは高度なAIが主役の興味深いゲームでした。

応用の幅は無限大ですので、本格的にAIに関して勉強してみるのも楽しそうですね。

【Unityで作ろう！ゲームアルゴリズム】リバーシのAIを作ってみよう

qnoteスマホアプリ開発チーム技術主任。PHP・Android・iOS・Unityなど複数のプラットフォームでの開発を行う。
しばしば7匹の先輩猫社員たちにイスを占領される。

賀好 昭仁の記事（1ページ目）

賀好昭仁の記事（1ページ目）