『ソフィーのアトリエ』の調合をグラフ理論で考察してみる

#はじめに
アトリエシリーズとは、コーエーテクモゲームスのガストブランド（旧・株式会社ガスト）から発売されている「錬金術」を題材としたRPGシリーズです。
ほとんどの作品のタイトルが『＜主人公の名前＞のアトリエ』で構成されているため、アトリエシリーズと呼ばれています。

今回はこのアトリエシリーズのうち、近日（2022/2/24・25）に発売する『[ソフィーのアトリエ2](https://www.gamecity.ne.jp/atelier/sophie2/)』に乗っかって、その時系列上の前作にあたる『[ソフィーのアトリエ](https://social.gust.co.jp/sophie/)』の調合システムを、グラフ理論を使って考察してみます。

#アトリエシリーズにおける「錬金術」
錬金術とは科学の元となった試みであり、卑金属から貴金属（特に金）を精錬することを目標としている......(by wikipedia)
これではないです。

とはいえこれに影響を受けて作られたゲームであることは間違いないため、錬金術における終着点であった「賢者の石」、すなわち卑金属を貴金属へ変え、人間を不老不死の存在へと変えることができる究極の物質もゲームに登場します。
大抵どの作品でも錬金術士（アトリエシリーズでは錬金術"師"ではなく錬金術"士"なんですよね）として大成するための一つの目標として、作中で登場しているイメージですね。

アトリエシリーズはファンタジーよりの世界観ではありますが、賢者の石によって金を作ったり不老不死になったりという設定は採用されていないです。
どの作品でも最終盤に出てくるやりこみのお供、もとい優秀な中間素材という印象ですね。

ゲームシステムとしては、素材をフィールドから収集し、その素材を材料に錬金を行い、新たな物質を調合するというシステムです。
この記事では、この調合システムに着目しています。

では実際のゲーム画面を使って説明していきましょうか。
以降のスクリーンショットはSteam版の「ソフィーのアトリエDX」で撮影したものです。

![20220220121905_1.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/373452/0a23e51f-23a3-5219-f662-fbfff8c0db8d.jpeg)

この「アプコール」というアイテムを調合するときの手順を例として説明します。
材料に書かれているものが、「アプコール」を調合する時に必要な材料です。

「きまぐれいちご　×2」の部分は文字通り「きまぐれいちご」というアイテムを2つ使って調合するということです。

さて、次の材料は（植物類）や（水）という表記になっています。
こういった（）がついたものをゲーム中ではカテゴリ、と呼んでいます。

各アイテムは必ずカテゴリを持っており、材料としてカテゴリが指定された場合は、そのカテゴリを持つアイテム全てを材料として使うことができます。
とりあえず材料にカテゴリを指定している調合品は、材料として使えるアイテムが多く、応用の幅が広くて使いやすいというイメージを持ってもらえればよいです。

![20220220121932_1.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/373452/acdfe761-94a8-e48d-4af9-822109a8a369.jpeg)

このように、（植物類）のカテゴリを持っていればどんなアイテムでも構わないので、ここには「魔法の草」や「コバルト草」、「五日ヅル」といったアイテムを使用することができます。

このように、名指しで指定されているアイテムと、カテゴリを指定されているアイテムを組み合わせて新たなアイテムを調合していく、というのがこのゲームの主な楽しみです。
まあRPGなのでその調合したアイテムを使って敵と戦う、というのも面白いシステムなんですが、今回の考察には関係してこないのでカットです。

#グラフで表す
さて、ここからが本題です。
素材や調合品を頂点、調合によるアイテムの変化を、素材と調合品を結ぶ辺とした有向グラフで管理することにより、どのアイテムが一番多くの調合に活用できるのか、などを考察することが可能なのではないでしょうか？

なお、素材や調合品の一覧、レシピなどの情報は複数の攻略サイト
(https://omoteura.com/atelier_sophie/
https://wikiwiki.jp/sophie-a17/
https://ds-can.com/sophie/)
のものを組み合わせて収集し、最終的に実機で目視で確かめました。
正直検証のためのプログラム作成なんかよりこちらのほうがよっぽど大変で時間がかかりました......
とはいえ攻略サイトを作ってくださった方々のおかげでだいぶ時短できたので感謝しかありません。
~~いくつかミスがあったので手動で修正しましたが~~

![Figure_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/373452/7d3e88f7-3c6c-0f29-ffb3-4cd7db70a02c.png)


お試しで1レシピだけ抜粋してグラフを出力させてみました。
水色の頂点は素材もしくは調合品です。
各有向辺は調合によるアイテムの変化を表し、今回抜粋したレシピは「山師の薬」のレシピです。

このアイテムは

* 魔法の草　×2
* （動物素材）　×1
* （水）　×1

で作られます。
そのため、「魔法の草」と、カテゴリ（動物素材）もしくは（水）を持つ素材及び調合品から「山師の薬」への辺が張られるというわけですね。
ここでは、カテゴリを素材とするレシピがあった場合、そのカテゴリに属する素材及び調合品すべてから、完成品への辺を張るという風に実装をしています。

さて、すべての素材・調合品、レシピを追加してみましょう。
先程の図では素材と調合品の点の色が一緒で分かりづらかったと思いますので、素材の点は水色、調合品の点は青色の点で表すように修正をし、描画させてみます。

![sophie_relation.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/373452/bfe61feb-b01f-0c4d-ab06-a883cf3e42ad.png)


うーんこれはひどい。
pythonのグラフを扱うためのライブラリであるnetworkxを使って管理・描画させているのですが、文字の被りとかを解消しきれず、ひどいことになってしまいました。
頂点数は223、辺の数は4415なので、まあきれいには描画されないですよね。

networkxのspring_layout()という力学モデルを利用した点の配置アルゴリズムで定めたのですが（[そちらについて詳しくはこちら](https://qiita.com/odanny/items/7c550010f5915ae4acdc)）、装飾品や爆弾といった、調合した完成品を再び材料にして調合ができないものが外側に、カテゴリ（水）を持つなど、調合した完成品を材料として調合を行いやすいものが内側に集まっているようなのは面白い点ですね。

とはいえ、この辺の数では考察しようにも見にくくてしょうがないので、改善を図ります。

具体的には、カテゴリを点として追加し、素材・調合品は自身の属するカテゴリへと辺を張ります。
そして、材料にカテゴリを持つレシピに対しては、先程と違い各素材から完成品へ辺を張るのではなく、**カテゴリから**完成品へと辺を張ります。
これにより、大幅に辺を減らすことが可能でしょう。
そのように改善したバージョンがこちらです。

![sophie_relation_with_category.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/373452/6d9b6c73-0d5e-d793-df20-7aedeb0666a4.png)

先程よりきれいになりましたかね。
今回の図では頂点数は251、辺の数は949でした。
改善によって辺の数を約1/4まで減らすことができました。

カテゴリは薄緑の点で表されています。
先ほどと似た傾向で、そのカテゴリを持つアイテムが多い、もしくはそのカテゴリを材料に要求するレシピが多いカテゴリが内側に集まり、完成品を材料にしないものが外側に集まっているようですね。

#"優秀"な素材・カテゴリ
さて、上述のグラフを活用して、もともとの目標であったどの素材や調合品、カテゴリが優秀であるかを考察していきましょう。
ゲームシステム的に"優秀である"調合品・カテゴリとは、

* 多くの素材から到達できる
* そのアイテムの属するカテゴリを材料に持つレシピが多い

と言えるかと思います。
なぜなら、基本的にアトリエの調合をやり込んでいくと、アイテムや装備に優秀な特性をつけることが目標になってきます。
攻撃アイテムにはダメージを上昇させる特性を付与したく、装備にはステータスを上昇させる特性を付与したいです。

特性は素材にランダムでついており、完成品に欲しい特性を、その材料になっているカテゴリのアイテムまで移してゆくという作業を繰り返すことになります。
また、似たような特性を組み合わせることで上位の特性にする、合成特性というシステムがあるので、いくつかのレシピを経由することでループできる調合ルートも、"優秀である"と言えることができるでしょう。

ループできる調合ルートの例として、

* ピュアウォーター→ピュアウォーター
* ゼッテル→ラーメル麦粉→中和剤・赤→ゼッテル
* アプコール→ミネラルエキス→ピュアウォーター→アプコール

などがあります。

グラフ理論的にはこのループ調合は閉路を検出できればよいのですが、すべての閉路を検出する関数がいつまで経っても返事をしない（頂点数や辺の数が多すぎ）ので、今回はこのループ調合の話は一旦置いておきます。

この"優秀さ"については、グラフ理論における[PageRank](https://ja.wikipedia.org/wiki/%E3%83%9A%E3%83%BC%E3%82%B8%E3%83%A9%E3%83%B3%E3%82%AF)のアルゴリズムを使うことでうまく考察できそうです。
PageRankの発想は、引用に基づく学術論文の評価に似ていて、

* 重要な論文は多くの人から引用される
* 被引用数が多い論文から引用されている論文の重要度も高い
* ただし、リンク集のような乱発されたリンクの価値は低い

のようになっています。(概ねwikiそのまま)

今回作成したグラフに対しても、

* 重要な素材は、それを材料とするレシピが多い
* 重要な調合品は重要な素材を材料とする

と言えるでしょう。

networkxにはPageRankを求める関数もあるので、それを活用して、調べてみましょう。

```PageRank上位の10頂点を抜粋.txt
('失敗作の灰', 0.10539604880006007)
('(魔法の道具)', 0.06270881636914954)
('(重要)', 0.040330167096745945)
('(エリキシル)', 0.03648828772469065)
('(装飾品)', 0.0344808437154083)
('賢者の石', 0.027285465558607724)
('(薬品)', 0.02688764740681478)
('(爆弾)', 0.023194467995822584)
('(金属)', 0.01904992737626737)
('妖精の錬金釜', 0.017443149385683577)
```

見ての通り「失敗作の灰」が最も重要度が高い素材であることがわかりました。



……さて、ソフィーのアトリエをやり込んだ方はこの結論、全く意味がないということがわかるかと思います。
それはなぜか。

このアイテムは、錬金レベルが足りていない難しいアイテムを作ろうとしたり、時間制限の設けられた錬金釜を利用して錬金をし、時間制限を破ってしまった場合に手に入れることができるアイテムだからです。

つまり、すべてのレシピの完成品が「失敗作の灰」でもあるというわけですね。（確かストーリー進行に必須のアイテムの調合は失敗しなかったと思うので、厳密にはこのグラフは間違っているはずですが……結論は変わりませんね）

そこで、「失敗作の灰」を除いたPageRank上位10個の頂点をもう少し詳しく見てみましょう。
グラフ理論的には、派生元が有向グラフ上の親にあたる点群、使いみちが有向グラフ上の子にあたる点群を表しています。

```
(魔法の道具) :
派生元: ['敬虔な信者用お札', '魔力を秘めたページ', '破れた魔道書', '失敗作の灰', 'マナフェザー', '勝者のお守り', '魔除けの護符', '妖精の道標', '小悪魔のいたずら', '万物の写本', 'メルクリウスの瞳', '鍛錬のお守り', 'クリアドロップ', 'ヘクセ・アウリス', '天使のささやき', '緊急退避バッグ', '魔法使いの笛', '原初の種火', '神の落し物', '生きてる荷車', '天界の大掃除', '死霊使いの笛', '終末の種火', '封じの白本']
使いみち: ['マナフェザー', '失敗作の灰', '妖精の錬金釜', '古代の錬金釜', 'アトリエテント']

(重要) :
派生元: ['朧草の花弁', '久遠の竜鱗', '魂結いの石', 'うるおい草', 'おばあちゃんの錬金釜', '練習用の錬金釜', '達人の錬金釜', '魂盟の針', '幽世の羅針盤', '同調の錬金釜', '妖精の錬金釜', '古代の錬金釜', '真理の鍵', '試作型栄養剤', '聡者の標', 'アトリエテント']
使いみち: []

(エリキシル) :
派生元: ['常世の仙花', 'ドンケルハイト', '精霊結晶', '竜のウロコ', '竜の血晶', '星の粉', '太陽の粉', 'ペンデグリュン', '竜核', '出来損ないの欠片', '焦げた欠片', '臭う欠片', '綺麗な欠片', '失敗作の灰', '錬金粘土', '賢者の石', '神秘の霊薬', '深紅の石']
使いみち: ['生命の蜜', '失敗作の灰', '賢者の石', '神秘の霊薬', '深紅の石', '英雄降ろしの丸薬', 'ヴェルベティス', '万薬のもと', '試作型栄養剤', '聡者の標']

(装飾品) :
派生元: ['マイスターミトン', '友愛のペルソナ', 'モノクログラス', '深緑の羽飾り', 'エンゼルリボン', 'ハッスルベルト', 'グナーデリング', 'エアリスブローチ', '物霊のイヤリング', '白熱はちまき', '心眼のモノクル', 'クロニクルマーク', '生命のバングル', '時操りの砂時計', 'アンブロシアの花冠', 'エレメントガード']
使いみち: []

賢者の石 :
派生元: ['深紅の石', '失敗作の灰', '(エリキシル)', '(宝石)']
使いみち: ['(金属)', '(薬の材料)', '(エリキシル)', '(神秘の力)']

(薬品) :
派生元: ['山師の薬', 'リフュールボトル', '不幸の瓶詰め', '万能促進剤', '生命の蜜', '万能厄除け香', 'ハニーシロップ', '火竜の気付け薬', '神秘の霊薬', 'そよ風のアロマ', '英雄降ろしの丸薬']
使いみち: ['ハニーシロップ', '失敗作の灰']

(爆弾) :
派生元: ['うに袋', 'フラム', 'レヘルン', 'ドナーストーン', 'クラフト', 'プニプニ弾', 'オリフラム', 'シュタルレヘルン', 'ドナークリスタル', '原初の種火', '神の落し物', '天界の大掃除', '終末の種火']
使いみち: ['原初の種火', '失敗作の灰', '神の落し物', '天界の大掃除', '終末の種火']

(金属) :
派生元: ['ソウルストン', 'くすぶる鍛石', '銀いも', '忘れ去られた部品', 'インゴット', '束ねた金糸', 'シュタルメタル', 'シルヴァリア', 'ミネラルエキス', 'ルビリウム', 'ブリッツライト', '雪花水晶', 'ヘクセ・アウリス', '精密な部品', 'ハートペンダント', 'ガイストアイゼン', 'ゴルトアイゼン', '賢者の石', 'ハルモニウム']
使いみち: ['束ねた金糸', '失敗作の灰', 'モノクログラス', 'クラフト', '妖精の道標', '小悪魔のいたずら', '達人の錬金釜', 'メルクリウスの瞳', '旅人の靴', 'ハッスルベルト', '同調の錬金釜', 'グナーデリング', '天使のささやき', 'ハートペンダント', '物霊のイヤリング', 'ドナークリスタル', '心眼のモノクル', '妖精の錬金釜', 'クロニクルマーク', '生命のバングル', '神の落し物', '生きてる荷車', '時操りの砂時計', '古代の錬金釜', '天界の大掃除', 'アンブロシアの花冠', 'エレメントガード']

妖精の錬金釜 :
派生元: ['妖精の錬金釜', '錬金粘土', '(金属)', '(魔法の道具)']
使いみち: ['(重要)', '妖精の錬金釜', '失敗作の灰']

古代の錬金釜 :
派生元: ['古代の錬金釜', '錬金粘土', '(金属)', '(魔法の道具)']
使いみち: ['(重要)', '古代の錬金釜', '失敗作の灰']
```

カテゴリを頂点として追加していなければ派生元は本当に派生元になっていたのですが、カテゴリが頂点として存在しているので、カテゴリが重要な頂点だと判断された場合は、派生元の部分はそのカテゴリに属しているアイテムの集合になってしまっています。
頂点名がアイテムならば、派生元は材料を表しています。

使いみちは、頂点名がカテゴリならば、そのカテゴリを材料として使うアイテムを。アイテム名ならそのアイテムの属するカテゴリを表します。

PageRankで考察してみると、調合の完成品を材料とするレシピが多いかどうかは意外と関係がなさそうに思えます。
というのも、カテゴリ（魔法の道具）は使いみちが限られているにも関わらず、PageRank的には2位になっています。
そのカテゴリに属するアイテム数で比較すると、カテゴリ（魔法の道具）は全体2位なので（一位はカテゴリ（神秘の力）です）、それが影響しているのかもしれません。

また、「失敗作の灰」を除いたアイテムの中では「賢者の石」が一番重要度が高いというのも面白い点ですね。
重要度の高いカテゴリ（エリキシル）,（金属）,（薬の材料）,（神秘の力）を持っており、何より「失敗作の灰」を材料にする、という点が大きく重要度に影響を与えているのではないかと思います。

やはり錬金術たるもの最重要アイテムは「賢者の石」でないと、ということでしょうか。

#最後に
正直1週間前くらいに思い立って作業を始め、ソフィー2の発売までに間に合わせることを目標に執筆したので記事のクオリティの低さや考察の浅さが出てしまっているかもしれません。
今回利用したデータやプログラムはhttps://github.com/hiiragi-kaede/Atelier_Relation_Research
にてまとめてあります。
他のシリーズ作品についても活用できるかと思うので、興味があれば見ていってください。
あとコードの指摘などがあればお待ちしています。

最後にはなりますが、アトリエシリーズはこういった調合の考察などを楽しめる人なら向いてると思います。
個人的には初心者には「ソフィーのアトリエ」をおすすめしていますが、最新作の「ソフィーのアトリエ2」も初心者でも楽しめるかと思いますので、興味があればプレイしてみてください！

ここまで読んでくださりありがとうございました。

最後に今回使用したPythonコードを折りたたんで掲載しておきます。
<details>
<summary>今回使用したPythonコード</summary><div>

```relation.py
import matplotlib.pyplot as plt
import networkx as nx

#素材情報を取得
material_fname="sophie_materials.txt"
materials,category=[],[]
data=[]
material_info={}
with open(material_fname) as f:
    tmp=[i.split(":") for i in f.readlines()]
    materials=[i[0] for i in tmp]
    category=[i[1][:-2].split(",") for i in tmp]
    material_info={materials[i]:category[i] for i in range(len(materials))}

#調合品情報を取得
recipe_fname="sophie_recipes.txt"
synthesis_info={}
with open(recipe_fname) as f:
    while True:
        name=f.readline()[:-2]
        if name=="": break
        
        components=f.readline().split("[")[1][:-2].split(",")
        components=[i.replace("'","").strip() for i in components]
        category=f.readline().split("[")[1][:-2].split(",")
        category=[i.replace("'","").strip() for i in category]
        synthesis_info[name]={"components":components,
                            "category":category}

#素材・調合品のカテゴリを取得し、setで重複を取り除くことで、カテゴリ集合を取得
all_categories=set()
for k,v in material_info.items():
    for ele in v:
        all_categories.add(ele)
for k,v in synthesis_info.items():
    for ele in v["category"]:
        all_categories.add(ele)

all_categories=sorted(list(all_categories))

#そのカテゴリに属するアイテム一覧を作成
category_items={i:[] for i in all_categories}
for k,v in material_info.items():
    for ele in v:
        category_items[ele].append(k)
for k,v in synthesis_info.items():
    for ele in v["category"]:
        category_items[ele].append(k)


def research1():
    """
        カテゴリを要求する素材をすべて各素材からの辺に変換、すなわち各レシピに使える素材全てから調合品への辺を張る方式。
    """    
    G=nx.DiGraph()

    #素材アイテムをグラフに追加(cyanの点)
    for i in range(len(materials)):
        G.add_node(materials[i],color="c")

    #調合アイテムをグラフに追加(blueの点)
    for k in synthesis_info.keys():
        G.add_node(k,color="b")

    #レシピのエッジをグラフに追加    
    for name in synthesis_info.keys():
        recipe=synthesis_info[name]["components"]
        for material in recipe:
            if "(" in material:
                for cate_item in category_items[material]:
                    G.add_edge(cate_item,name,info="錬金:"+name)
                    G.add_edge(cate_item,"失敗作の灰",info="失敗:"+name)
            else:
                G.add_edge(material,name,info="錬金:"+name)
                G.add_edge(material,"失敗作の灰",info="失敗:"+name)

    print("node size:",len(G.nodes()))
    print("edge size:",len(G.edges()))
    pos=nx.spring_layout(G,k=0.8)
    
    #ページランクを求め、重要度順にソート
    pr=nx.pagerank(G)
    pr=sorted(pr.items(),key=lambda x:x[1],reverse=True)

    plt.figure(figsize=(24,16))
    node_colors=[node["color"] for node in G.nodes.values()]

    nx.draw_networkx_nodes(G,pos,node_color=node_colors,alpha=0.6)
    nx.draw_networkx_labels(G,pos,font_size=6,font_family='Yu Gothic',font_weight="bold")
    nx.draw_networkx_edges(G,pos,edge_color="#377eb8",alpha=0.5)

    plt.axis('off')
    plt.savefig("sophie_relation.png")

    fname="sophie_pagerank.txt"
    with open(fname,"w") as f:
        for ele in pr:
            print(ele,file=f)

    cate_item_key=sorted(category_items.items(),key=lambda x:len(x[1]),reverse=True)
    fname="sophie_category_size.txt"
    with open(fname,"w") as f:
        for k,v in cate_item_key:
            print(str(k)+"  size:"+str(len(v)),file=f)

    


def research2():
    """
        カテゴリを点として追加し、各素材やアイテムのカテゴリもその点への辺として管理する方式。
    """    
    #ループ調合などを探すためのグラフの作成
    G=nx.DiGraph()

    #素材アイテムをグラフに追加(cyanの点)
    for i in range(len(materials)):
        G.add_node(materials[i],color="c")

    #調合アイテムをグラフに追加(blueの点)
    for k in synthesis_info.keys():
        G.add_node(k,color="b")

    #カテゴリをグラフに追加(palegreenの点)
    for k in category_items:
        G.add_node(k,color="palegreen")
    
    #各アイテムのカテゴリ情報を辺として追加
    for k in material_info.keys():
        for category in material_info[k]:
            G.add_edge(k,category,info="素材カテゴリ")
    for k in synthesis_info.keys():
        for category in synthesis_info[k]["category"]:
            G.add_edge(k,category,info="調合品カテゴリ")
    
    #レシピを辺として追加
    for name in synthesis_info.keys():
        recipe=synthesis_info[name]["components"]
        for item in recipe:
            G.add_edge(item,name,info="錬金:"+name)
            G.add_edge(item,"失敗作の灰",info="失敗:"+name)
    
    print("node size:",len(G.nodes()))
    print("edge size:",len(G.edges()))
    pos=nx.spring_layout(G,k=0.7)

    plt.figure(figsize=(24,16))
    node_colors=[node["color"] for node in G.nodes.values()]

    nx.draw_networkx_nodes(G,pos,node_color=node_colors,alpha=0.6)
    
    nx.draw_networkx_labels(G,pos,font_size=6,font_family='Yu Gothic',font_weight="bold")
    nx.draw_networkx_edges(G,pos,edge_color="#377eb8",alpha=0.5)

    plt.axis('off')
    plt.savefig("sophie_relation_with_category.png")
    
    pr=nx.pagerank(G)
    pr=sorted(pr.items(),key=lambda x:x[1],reverse=True)
    fname="sophie_pagerank_with_category.txt"
    with open(fname,"w") as f:
        for ele in pr:
            print(ele,file=f)
    
    fname="sophie_important_items.txt"
    with open(fname,"w") as f:
        for ele in pr:
            print(ele[0],":",file=f)
            print("派生元:",list(G.predecessors(ele[0])),file=f)
            print("使いみち:",list(G.successors(ele[0])),file=f)
            print(file=f)

if __name__=="__main__":
    type=int(input("""\
1->カテゴリを点で管理しない
2->カテゴリを点で管理
グラフのタイプを入力:"""))
    if type==1:
        research1()
    elif type==2:
        research2()
```

</div></details>