【UE4】Utility Based AI（プロジェクト付）

#はじめに
ユーティリティベースのAIをよく知らなかったので勉強ついでにサンプルプロジェクトも作ってみました。
今回はサンプルプロジェクトの解説に加え、勉強する際に参考にしたWebサイトや書籍を紹介します。

#Utility Based AI

##Utilityってなに？
Utilityと聞くとプログラマの方ならば「便利な何か」というイメージが湧くと思います。プログラムではしばしば「Utilityクラス」という**「何かをするのに便利な関数群」**が定義されている事があります。しかしUtility Based AIで使われるUtilityという言葉とは意味が異なります。

Utility Based AIにおける「Utility」は**経済学で用いられるUtility**を指し、日本語で**「効用」**と訳されます。意味は

>各消費者が，自己の消費する財から受ける満足の度合いを数量的に表現したもの。[コトバンクより](https://kotobank.jp/word/効用-63294)

となり、まとめてしまえば**「満足度」**とも言えます。

Utility Based AIはこの**満足度**を指標として**「より高い満足度を得られる」**ように意思決定をします。

###例え話
手元に２０万円あります。その２０万円で何をしますか？
ある方は２０万円相当のダイヤモンドやアクセサリーを買うかもしれません。ある方は２０万円相当の洋服を買うかもしれません。ある方は２０万円分の旅行をするかもしれません。
自分なら２０万円相当のゲーミングPCを買います！

アクセサリーを買った方は同価値の洋服やPCよりも**アクセサリーを購入し装着（または飾る）**することに**大きな満足感**を得られたのかも知れません。

>**ある行動（行動A)をする事**が他の行動（行動B)をするよりも**大きな満足感を得られる**事を行動Aは行動Bよりも**大きな（もしくは高い）効用を持つ**と言います。

旅行を選んだ方も旅行することで得られる開放感や見知らぬ土地を歩くワクワク感という形には表せないものですが、それに高い効用を持っています。

２０万円という**お金の価値は不変**ですが、その使い道は多岐に渡ります。その使い道を決める**価値とはまた別**の重要な要素がUtility（効用）です。


#プロジェクトの解説
Utility Based AIについて気合を入れて書くつもりでしたが、いざ書いてみるとそんなに書くことも無かったので早速プロジェクトの解説に移ります。
**中学数学も怪しい程の数学力**しか持ち合わせていませんが、頑張って書いてみます。

プロジェクトはいつも通りOneDriveにアップしています。
[プロジェクトはこちら！](https://1drv.ms/u/s!Au-8FqgREBKZhTFeJ1aND_XsMmW9)

このプロジェクトは[Game AI Pro 1](http://www.gameaipro.com)の[Chapter 9: An Introduction to Utility Theory](http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter09_An_Introduction_to_Utility_Theory.pdf)に付属するサンプルコードをほぼUE4に移植したものです。
変更点としては「コマンド選択UIの追加」「バトルログの追加」「ユーティリティスコアの可視化」等です。

Utility Based AIの仕組みについては**BP_BasicUtilityAI**や**BP_BasicUtilityAI_WithCurve**に全てを実装しています。今回の記事ではこの２つを解説し、それ以外のアセットについては特に解説はしません。

##BP_BasicUtilityAI

###関数ChooseNextAction
この関数では①**相手の脅威度**を表す「Threat」を求め、②数学関数（１次関数や２次関数、指数関数とか）で各アクションに対する**ユーティリティスコア**を求めます。
求められたユーティリティスコアを基に③**重み付けランダム**もしくは**最も良いスコア**を持つアクションを返します。

![2018-03-18_16h04_50.png](https://qiita-image-store.s3.amazonaws.com/0/104467/76d27c5a-5007-0a26-6148-afd42556fb14.png)

変数Threatは相手が与え得る最大ダメージと自身の体力の比で表され、自身の体力が低いほど**相手に一撃で倒されてしまう可能性**が高まります。この値は脅威度とされ、脅威度を引数に取る「Score Run」や「Score Heal」のスコアをスケーリングします。（脅威度が低ければScore RunやScore Healのスコアは小さくなり選ばれる可能性が低くなります。）

###関数ScoreAttack
ScoreAttackは相手のHPに応じて線形状に変化し、1.0～Base Attack Scoreまでの値を取ります。グラフは以下のようになります。

![chart (1).png](https://qiita-image-store.s3.amazonaws.com/0/104467/1d90cabf-3fa3-2941-28dc-c04ea6157296.png)

横軸の値は相手のHP（Opponent Health）を表し、縦軸はユーティリティスコアです。
横軸の25からスコアが上昇し始めます。25という数値は**AIが与え得る最大ダメージから由来**しており、相手のHPが低いほど「運が良ければ一撃で相手（プレイヤー）を倒せる」可能性が高まります。その可能性に応じる形でスコアも上昇していきます。
相手のHPが10になるとスコアは最大の1で固定されます。この10という数字はAIが必ず与えられるダメージ量である**最小ダメージ値に由来**しています。相手のHPがAIが与えることが出来る最小ダメージ以下になれば「相手を**絶対**に倒せる」事になりユーティリティスコアは最大の1が出力されます。

###関数ScoreRun
ScoreRunでは自身のHPの割合と所持する回復薬（Potion）の数に応じてスコアが求められます。ここで出力されるスコアは2次関数と同様になります。

![chart (2).png](https://qiita-image-store.s3.amazonaws.com/0/104467/e3b2d364-c9a3-ef10-27b4-93df2796998a.png)

回復薬を所持している場合は体力が低下したとしてもスコアは低い状態を維持し（体力が下がれば回復すれば良いだけです）、回復薬の所持数が0になればスコアを跳ね上げます。（回復の手段が無いため逃げるしかありません）

このようなグラフを生む鍵はローカル変数Exponent（指数）にあります。
2次関数の指数が**0 < X < 1**の場合、**0に近いほど曲線は狭まり、1に近いほど広がり**ます。（回復薬が0個＝指数が0.25、回復薬が最大個＝指数が0.00390625）
この関数では求めた累乗を**1から引く**事でグラフの**曲線を反転**しています。よって**0に近いほど広がり、1に近いほど狭まる**曲線となります。

##関数ScoreHeal
この関数が出力する値は**ロジスティック関数**と呼ばれる有名なS字曲線になります。（ロジスティック関数は機械学習を少し齧った方なら聞いた覚えもあるかと思います）

>個人的に**「e」**や**ネイピア数**もしくは**自然対数の底（もしくは2.71828）**という文字が見えたら「あ！ロジスティック関数だ！」と考えています。

![chart (3).png](https://qiita-image-store.s3.amazonaws.com/0/104467/c6b600b9-87fa-d559-53df-5cefb71852ef.png)

ここではネイピア数（2.71828）の他に2つの定数が出てきますので、それについて説明したいと思います。

変数HealScoreLogisticSteepnessはS字曲線のキツさ？急さ？を制御する定数です。上の画像では3つの曲線があり、それぞれでHealScoreLogisticSteepnessの値を変化させています。
青色の曲線はプロジェクトを作る上で参考にしたサンプルプロジェクトで使われていた数値です。ネイピア数をそのまま使用した赤色の曲線と比べるとずいぶん緩やかな曲線を描いています。
今回配布しているプロジェクトではネイピア数をそのまま使用するために1.0がデフォルト値として入っています。

変数HealScoreLogisticRangeには**6.0**という数値が入っています。
通常のロジスティック関数というのは**Xが0の時、Yは0.5を通る**グラフになり、**約-6あたりでYが0**になり**約＋6あたりでYが1**になります。（今回は**1-(1/1+e^-x)**という形なので結果は反転しています。）そのままでは不便なグラフになるため**X=0の時、Y=0**となるようにグラフを**正方向シフト**させます。（**1-(1/1+e^-x+c)**という形になる）
そのための値がHealScoreLogisticRangeにある**6.0**という数値になります。


##BP_BasicUtilityAI_With_Curve
中学数学が怪しいレベルの自分ではこれまで説明したような数学関数を「あぁ、なるほど？」となるまでにはとてつもなく時間がかかります。（今回のプロジェクトでは1週間ほど）ましてや**自分が望むグラフ**を数式で表現することも非常に時間がかかってしまいます。
UnrealEngineでは幸いなことに自分のような数式でグラフを描くのが大変苦手な方向けの機能があります。

それは**「Curve アセット」**です。

Curveアセットにはいくつかの種類がありますが、今回のようなプロジェクトの場合は**Curve Float**が有用です。

BP_BasicUtilityAI_With_Curveは名前にあるようにユーティリティスコアの算出をCurve Floatで実現しています。
Curveアセットを使うことによりスコアデータをコードに埋め込まずに外に出すため**データドリブン**となり、数学に強い方で無くとも**容易にAIの振る舞いを変化**させることが出来ます。

###関数ScoreAttack
上記で説明した関数ScoreAttackよりもずいぶんとスッキリしたコードになっています。
仕組みは単純で攻撃用スコアカーブアセットに引数から渡される**相手の体力**を渡し、対応する値をスコアとして返します。

![2018-03-19_00h52_56.png](https://qiita-image-store.s3.amazonaws.com/0/104467/0ccc1a0a-592f-7057-bf88-4c0b17d02863.png)

攻撃用スコアカーブは上のようになっています。横軸を相手の体力とし0～100までの値を取ります。縦軸はユーティリティスコアとなっており1～0の値を取ります。
今回のプロジェクトで用意したカーブアセットは数式から求められるグラフと同様の形としています。

###関数ScoreRun
数式版では所持する回復薬数に応じてグラフの値が大きく変化していましたが、Float Curveの場合作成できる曲線は1つだけです。なので今回は**所持する回復薬が0個の場合**のみカーブアセットの値を取るようにしています。回復薬をいくつか所持している場合は0.0を返し、逃走アクションはピックアップされないようにしています。

![2018-03-19_01h11_41.png](https://qiita-image-store.s3.amazonaws.com/0/104467/04f3c659-815b-2111-9b9c-523f85e0dcbf.png)

逃走用スコアカーブは上のようにしており、縦軸は攻撃用スコアカーブと同様にユーティリティスコアを表しています。
攻撃用スコアカーブでは横軸を相手の体力としていましたが、逃走用スコアカーブでは横軸を**自身の体力**としています。
横軸が0に近いほど（体力が0に近いほど）逃走ユーティリティスコアは徐々に上昇していきます。


#まとめ
Utility Based AIは非常に数学的ですが上手く数式を組み立てられれば**AIに個性を持たせる**事が簡単に出来、カーブアセットのようなエディタがあれば数学にあまり強い方でなくとも容易にAIの振る舞いを変化させることが出来る強力な意思決定方法だと思います。

#参考資料
[An Introduction to Utility Theory](http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter09_An_Introduction_to_Utility_Theory.pdf)
[デジタルゲームにおける人工知能技術の応用の現在](https://jsai.ixsq.nii.ac.jp/ej/index.php?active_action=repository_view_main_item_snippet&page_id=13&block_id=23&all=デジタルゲームにおける人工知能技術の応用の現在&pn=1&st=1)
[At-a-glance functions for modelling utility-based game AI](https://alastaira.wordpress.com/2013/01/25/at-a-glance-functions-for-modelling-utility-based-game-ai/)
[ゲームプログラミングのための行動AI数学](https://www.borndigital.co.jp/book/610.html)
[ゲームAI – 基礎編(2) – 『はじめてのエージェントベースアーキテクチャ』](http://tech.cygames.co.jp/archives/2364/)
[Utility Based AI - kurihara-nの日記](http://kurihara-n.hatenablog.com/entry/2016/09/25/001838)