はじめに
minecraftでサバイバルをすることになりました．
さて，生き残るためにすべきことは？作成すべきアイテムは？
※これは拡張ネットワーク法というアルゴリズムを用いて各アイテムの関係や重要性を知ろうとした話です．
jupyter notebookで実行しています．また，可視化はCytoscapeで行っています．
拡張ネットワーク法
以下の図で説明されます．
存在するアイテムから現在クラフト可能なアイテムを調べ，それを存在するアイテムに追加します．
これを収束するまで繰り返します．
内部的には以下の行列で扱っています．
・レシピの左辺を表した行列R
| A | B | C | D | E | F | ... | |
|---|---|---|---|---|---|---|---|
| レシピ1 | 1 | 1 | 0 | 0 | 0 | 0 | |
| レシピ2 | 0 | 1 | 1 | 0 | 0 | 0 | |
| ... |
・レシピの左辺の要素数を表したベクトルB
| 数 | |
|---|---|
| レシピ1 | 2 |
| レシピ2 | 2 |
| ... |
・レシピの右辺を表した行列P
| A | B | C | D | E | F | ... | |
|---|---|---|---|---|---|---|---|
| レシピ1 | 0 | 0 | 0 | 1 | 0 | 0 | |
| レシピ2 | 0 | 0 | 0 | 0 | 1 | 0 | |
| ... |
・存在するアイテムを表した行列x
| A | B | C | D | E | F | ... | |
|---|---|---|---|---|---|---|---|
| 存在する？ | 1 | 1 | 0 | 0 | 0 | 0 |
手順ですが，
1. Rとxの内積をとり，それがBと一致するか確かめる
つまり，クラフトに必要なアイテムがすべて存在するかどうか確かめます．
2. 一致した場合，そのレシピがクラフトされたとしてRに対応するPをxに加える
クラフトされたアイテムをxに追加します．
これを収束するまで繰り返します．
レシピのデータベース作成
minecraftのレシピのデータベース(上の説明でいう「全レシピ」)を作成します．
minecraft wiki からレシピを引用しました．
csvファイルでまとめておきます．
""で囲っているのは文字列を取り出す処理で便利だからです．
実行
流れをスクリーンショットで紹介します．プロブラムは上の拡張ネットワーク法を実装したものがメインです．
インポート
アイテム辞書作成
取り込んだレシピをもとに，アイテムの辞書を作成します．
初期アイテムを指定
みなさん，サバイバルモードで降り立ったらまず何を手に入れますか？
というわけで今回は比較的初期に揃うであろう木(log)，丸石(cobblestone)，鉄インゴット(iron ingot)を初期アイテムとしました(鉄インゴットの入手はそんなに簡単ではないかもしれませんが．．．)．
実行結果
上略ですが，計62個のアイテムがクラフトされました．
可視化
Cytoscapeで可視化してみましょう．
多数のエッジが伸びているノードが重要アイテムということになります．
今度は初期アイテムにダイヤモンドを追加してみました．
結論
棒，大事．
ご覧いただきありがとうございました．
参考文献
https://www.cell.com/fulltext/S0092-8674(17)30133-2
拡張ネットワーク法について書かれています．