FGOで葛飾北斎より強いサーバントについてPrologに聞いてみる

# あらまし
FGOのサーバントについて、相関関係が難しいと思ったことはありませんか？
エクストラクラスが意味わかんなくて全部バーサーカーでいいや、って思ったことが何度もあります。
それでも、サーバントが何のクラスに属していて、どのクラスと有利不利の関係性を持っているのか知りたいことはありませんか？
そんなときはPrologの出番です。

## Prologってなんぞや？
パターンマッチに特化した論理型プログラミング言語です。

プログラミング言語のパラダイムは、手続き型、関数型、論理型と大まかに３つに分けられますが、そのうちの論理型に属します。
Prologはプログラミング言語の一種ですが、どちらかと言うと、SQLに超機能を搭載した、半分ぐらいデータベースのようなプログラミング言語です。

パターンマッチとは、入力から出力を推測する機能のことです。正規表現が代表的ですね。
正規表現は式を組み立てることで、式にマッチする文字列を抽出する考え方です（BrainF**kよりちょっと優しい）。
Prologはパターンマッチによる推論が行えるため、曖昧な質問にも、それにマッチする答えを列挙できます。

Prologは記述された事実をもとに論理を読み解いて答えを導き出すことが得意です。
例えば、AはBである、BはCである。ゆえにAはCである、という簡単な論理から、多少入り組んだ論理まで扱うことが得意です。
論理を扱えるので人工知能（AI）に使えるのではないかと期待されていましたが、
莫大な量のパラメータを無理やり近似させる手法のほうが伸びてしまいました。
プロンプトでPrologが書けるようになったらえらいぞ！

このエントリでは、Fate/Grand Orderのサーバントの有利・不利の関係を論理的に導き出します。

# Prologの基本的な書き方

まずは、完成形のソースコードを提示します。
https://gist.github.com/GRGSIBERIA/b31aa0d1c68c4e744282289a0445860a

日本語が文字列で囲ってない？　Prologは予約済みの文字列以外なら大抵の文字が扱えます。
日本語でPrologを書いている人もいるので怖がらないでください。

Prologの実行環境はWeb上にもあります。

https://swish.swi-prolog.org/

プログラムを記入する場所と、質問を投げる場所がそれぞれあります。
プログラムにGistsのコードを貼り付けて、以下のような質問を投げてみます。

```prolog
?- カテゴリ(三騎士, XXX)
XXX = セイバー
XXX = ランサー
XXX = アーチャー
```

Prologはカテゴリのカテゴリ名から、XXXにマッチする答えを返します。
プログラム本体と質問文は全く違う性質のものなので、大抵は行頭に質問文を明示するため`?-`という文字を入れます。

## 事実
本当に事実だけを書きます。例えば、キャスターとか、セイバーとか。

```prolog
クラス(セイバー).
クラス(アサシン).
クラス(ルーラー).
```

事実は言い換えれば、データベースに入っている初期値のようなものです。
Prologは事実をもとに推論を行います。

## 規則
規則とは、事実を縛るためのルールのことです。
一般的なプログラミング言語で言うところの関数宣言のようなものになります。

```prolog
カテゴリ(カテゴリ名, クラス名) :- クラス(クラス名).
カテゴリ(標準, アーチャー).
カテゴリ(三騎士, アーチャー).
```

この例では、カテゴリという事実の書き方を規則で縛っています。
カテゴリの事実を記入するには、カテゴリ名、クラス名の順番で渡す必要があり、クラス名はクラスの中の事実が必要になります。
例えば、存在しないクラス（ゲートキーパー）は、カテゴリの事実に反することになります。

有利の関係性を表した規則が以下のようになります。

```prolog
有利(攻撃, 守備) :- クラス(攻撃), クラス(守備).
有利(攻撃, 守備) :- カテゴリ(攻撃, _), カテゴリ(守備, _).
有利(攻撃, 守備) :- クラス(攻撃), カテゴリ(守備, _).
有利(攻撃, 守備) :- カテゴリ(攻撃, _), クラス(守備).
```

この規則では、攻撃と守備の変数は、それぞれクラスかカテゴリに属していることを規則で縛っています。

## 質問
Prologでは、記述された規則と事実から、論理的に導き出された答えを得ることができます。

既に規則がいくつか準備されているので、まずは簡単な質問を投げてみましょう。

```Prolog
?- 有利(アーチャー, XXX)
XXX = セイバー
```

おかしいですね、アーチャーはセイバーのほかに、バーサーカーに対しても有利なはずなのに。
これは、`クラス(アーチャー), クラス(XXX)`でマッチしたからです。
質問の範囲を広げてみましょう。

### アーチャーが攻撃側で有利なのは何のクラスか？

```prolog
有利(XXX, YYY), (カテゴリ(XXX, アーチャー); XXX = アーチャー)
```

この例ではまず最初に、`有利(XXX, YYY)`が評価されます。
コンマで区切るとAND文になり、セミコロンで区切るとOR文になります。
2つ目の項`()`が評価され、内側の`カテゴリ(XXX, アーチャー); XXX = アーチャー)`が評価されます。
内側はORで連結しているので、`カテゴリ(XXX, アーチャー)`か、`有利(アーチャー, YYY)`を満たすものからパターンマッチを行います。

`クラス(YYY)`か`カテゴリ(YYY, _)`のいずれかの条件に当てはまるのは何だろうかと、パターンマッチを行います。
様々な組み合わせのうち、質問文の条件を満たすのは、

```prolog
XXX = アーチャー,
YYY = セイバー
XXX = 標準,
YYY = バーサーカー
```

となりました。合ってますね。
バーサーカーは、`カテゴリ(標準, アーチャー)`でマッチしました。
同じクエリでプリテンダーについても質問してみましょう。

```prolog
?- 有利(XXX, YYY), (   カテゴリ(XXX, プリテンダー); XXX = プリテンダー)
XXX = プリテンダー,
YYY = アルターエゴ
XXX = エクストラ,
YYY = バーサーカー
XXX = プリテンダー,
YYY = 三騎士
XXX = プリテンダー,
YYY = バーサーカー
```

三騎士はアーチャー、ランサー、セイバーの3つのクラスのことを指します。
プリテンダーとアルターエゴは強弱関係が複雑ですね。

強弱関係が複雑だと正誤値表などを使って、各々の関係性をハードコーディングしたくなります。
しかしながら、FGOのようにカテゴリ単位での強弱関係、小グループでの強弱関係、あとから実装された強弱関係など、極めて複雑な状態になっています。
プリテンダーを言語的な仕様に落とし込むと「プリテンダーは、エクストラクラスに属していて、三騎士とアルターエゴに強い。しかし、バーサーカーについては他と同じ通りだ」となります。
このような仕様を`○✘－`のような記号で表現すると、コメント抜きでプリテンダーの動作を記述するのは困難でしょう。
少なくとも、なんで三騎士に強いのかコメントに残してくれないと混乱します。

一方で、Prologは日本語で表現できる部分が多く、予約された記号さえ踏まなければ、関係性を日本語で記述することができます。

# 良い質問を考える

Prologで重要なのは、良い質問とは何か、そのためにどのような規則があり、事実を配置するべきなのか。
これらをうまく考えられると、少ない手間ひまで、複雑で曖昧な目的でも、素直な質問で良い答えが得られることがあります。

## 質問を考える前の前置き

PrologはSQLと似た部分が多くあります。
SQLはいかにINSERT, UPDATE, DELETE, SELECTなどで良いクエリを書くかが問題になります。
Prologも良い質問は何か、質問に適した事実や規則は何かが重要になります。

<details><summary>Prologが難しいと言われる理由（読まなくてもいい）</summary>
例えば、2のべき乗を返すプログラムは以下のようになります。

```prolog
べき乗を返す(_, 0, 1).
べき乗を返す(B, N, Ans) :- 
    N > 0,
    NN is N - 1,
    べき乗を返す(B, NN, NAns),
    Ans is NAns * B.
?- べき乗を返す(2, 4, Ans)
Ans = 16
```

「うわ、再帰使ってる……」と思った人は正常です。

:::note warn
TODO: 一部がアルファベットになるのは、日本語を入れたら沼にハマったので、回避策がわかったら修正、先頭大文字を変数とみなす言語仕様が原因？）
:::

Prologは通常のプログラム言語のようなforループを簡単な形で書くことができません。
例えば、Pythonは与えられたリストから要素を取り出しながらforループで繰り返しができますが、Prologではループを書くためには規則で関数のようなものを作らなければなりません。その関数の中でループのような処理を実装する形になります。

恐らく、Prolog脱落者の多くは再帰定義とリストで諦めるのではないかと思います。
そんなことでPrologを諦めるなんてもったいない！
再帰とリストを使わずにPrologを使いましょう。
</details>

## 葛飾北斎よりクラス的に有利で、レア度が同等以上で最大攻撃力も高いサーバントの名前

SQLで考えたら頭が爆発しそうな目的です。
ハードコーディングでも、こんな複雑怪奇な割に、得られる答えがショボいのはどうなの？
開発の担当者に怒られそうです。
攻略Wikiでも苦虫を噛み潰したように、ユーザのために実装を考えるのではないでしょうか？

要するに、目的の条件を満たす質問を組み立てればいい、ただそれだけです。

```prolog
?- 
サーバント(SubR, SubC, SubName, _, SubATK),
SubName = "葛飾北斎" ->
	サーバント(TarR, TarC, TarName, _, TarATK),
	SubR @=< TarR, SubATK < TarATK,
	有利(TXX, SXX), (カテゴリ(TXX, TarC); TXX = TarC), (カテゴリ(SXX, SubC); SXX = SubC); !
```

### 1行目, 3行目
まずは、マッチしたいサーバントの変数名から考えましょう。
目的となるサーバントの変数名は`Sub`をつけることにしましょう。
一方で、答えとなるサーバントの変数名は`Tar`をつけることにしましょう。

比較したいのは、レア度、クラス、サーバント名、攻撃力です。
それぞれ`R, C, Name, ATK`と名付けることにします。
アンダーバーはパターンマッチするときに使わないことを明示しています。

### 2行目
2行目は、実はif文になっています。
`SubName = "葛飾北斎"`のマッチに成功したら、`->`演算子より先のマッチを試行します。
この行を消すと、`有利`の部分であらゆるパターンマッチを試みてしまい、アルターエゴ以外のクラスのサーバントが列挙されてしまいます。

### 4行目
値同士の比較を行います。

葛飾北斎より同等以上のレアリティは`SubR @=< TarR`になります。
比較演算子で、他のプログラミング言語で言うところの`<=`と意味は同じです。
`<=`を使うとSyntax Errorに引っかかるので、最初のうちは間違えます。

同様に葛飾北斎より攻撃力が大きい、という条件は`SubATK < TarATK`になります。

### 5行目
葛飾北斎より有利なサーバントを表示したいので、`有利(XXX, YYY)`のうち、XXXが答え、YYYが葛飾北斎になって欲しいです。
XXXとYYYでは取り違えが起きそうなので、葛飾北斎を`SXX`、葛飾北斎より有利を`TXX`という変数で使い分けましょう。
これも前述のプログラムの応用で、カテゴリか、もしくはクラスで一致するようなクエリを書きます。
やや長くなりますが、`有利(TXX, SXX), (カテゴリ(TXX, TarC); TXX = TarC), (カテゴリ(SXX, SubC); SXX = SubC)`で、いずれかにマッチさせます。

え？　片方はフォーリナーになるでしょ、常考、と思ったあなた。
あなたはガンダムです。

葛飾北斎のクラスは不明とすると、TXXとSXXでそれぞれでマッチするような書き方になります。
葛飾北斎が自明である場合は、質問の形が変わり、
`(有利(TXX, フォーリナー), (カテゴリ(TXX, TarC); TXX = TarC)); (有利(TXX, エクストラクラス), (カテゴリ(TXX, TarC); TXX = TarC))`
となります。
例えば、`カテゴリ(カテゴリ名, クラス名)`がより複雑になるほど、クエリが長くなります。
事実が曖昧で規則が複雑だと、機械的に質問を作ると長くなる傾向にあります。
曖昧な部分はうまいことパターンマッチで推測させましょう。
Prologの一番のウリはパターンマッチによる推論です。

### 5行目末尾
最後にある`!`は、2行目の`SubName = "葛飾北斎"`が失敗したときに、パターンマッチを終わらせることを指示しています。
`!`演算子はPrologではカットと呼びます。
Prologのif文は`A -> B; C`の形で評価されます。
今回の例では、`A -> B; !`の形になっていて、パターンマッチに失敗したら即座に終了（カット）します。

Prologは、葛飾北斎以外のパターンでも論理的に成立するか試行します。
このとき、2行目の`->`がないと、`SubName = "葛飾北斎"`以外で条件を満たすように試行を繰り返します。どのような原理で動いているのかと言うと、SubNameの葛飾北斎を改めて別の値に置き換えて試行します。葛飾北斎以外というのは、SubNameにマーリンとかマシュとかの別のサーバントに置き換えます。そうすると、論理的に破綻しない別の答えが得られることになります。

このような仕組みをバックトラックと呼ぶのですが、変えてもらっては困る！という場面では、カットを使ってそれ以降の試行を中断させます。論理的に破綻したことをPrologに伝える必要があるのは、他のプログラミング言語にない特徴だと思います。

### 得られた結果
```prolog
SXX = SubC, SubC = フォーリナー,
SubATK = 12100,
SubName = "葛飾北斎",
SubR = TarR, TarR = 5,
TXX = TarC, TarC = アルターエゴ,
TarATK = 12465,
TarName = "沖田総司〔オルタ〕"

SXX = SubC, SubC = フォーリナー,
SubATK = 12100,
SubName = "葛飾北斎",
SubR = TarR, TarR = 5,
TXX = TarC, TarC = アルターエゴ,
TarATK = 12835,
TarName = "キングプロテア"

SXX = SubC, SubC = フォーリナー,
SubATK = 12100,
SubName = "葛飾北斎",
SubR = TarR, TarR = 5,
TXX = TarC, TarC = アルターエゴ,
TarATK = 12252,
TarName = "蘆屋道満"

SXX = SubC, SubC = フォーリナー,
SubATK = 12100,
SubName = "葛飾北斎",
SubR = TarR, TarR = 5,
TXX = TarC, TarC = アルターエゴ,
TarATK = 12835,
TarName = "マナナン・マク・リール〔バゼット〕"
```

沖田総司〔オルタ〕、キングプロテア、蘆屋道満、マナナン・マク・リール〔バゼット〕が、
レアリティ、クラス、攻撃力の観点で、葛飾北斎より優れていることが示されました。
いずれもクラスはアルターエゴで、フォーリナーより有利なクラスはアルターエゴしかありません。
結果として恐らく満足できるはず（同じテストを他のプログラミング言語でもう一度書くのはしんどい）。

# まとめ
Prologでは、パターンマッチを使った推論がとても強力なプログラミング言語です。
もちろん、将棋や囲碁などで最適解を探索するのにも強く、他のプログラミング言語と比べて実装が簡潔で明瞭になる場面もあります。
Prologに慣れると、ゲームの中での最適解を探すのにも重宝します。

ぜひ冒頭あたりに置いたコードを使いながら、Prologに色々な質問を試してみましょう。最初は質問を思い浮かべるところからです。ぜひ試してみてください。