はじめに
Minecraftをクリアするための計画を立てろ、と言われたらどのように計画を立てるでしょうか。
クリアというのはエンダードラゴンを討伐することです。エンダードラゴンを討伐するためにはエンドに行く必要があり、そのためにはエンダーアイが必要です。エンダーアイにはエンダーパールとブレイズパウダーが必要であり、そのブレイズパウダーを手に入れるためにはネザーへ行く必要があり…というような思考をするのではないでしょうか。
今回はこういうことを機械にやってもらいます。例えば、可能な限り早くエンダードラゴンを討伐するような計画を立てたりして欲しいところです。
どのように考えるか
マインクラフトにはクラフトという概念があり、複数の、または単一のアイテムを消費して別のアイテムを作ることができます。
これを他の概念にも当てはめます。
例えば木を素手で伐採する行為は時間を消費して原木をクラフトしているといえます。
また、鉄のツルハシを使ってダイヤモンドを採掘する行為は鉄のツルハシを（1÷鉄のツルハシの耐久値）個消費し、時間も少し消費してダイヤモンドを入手しているといえます。
採掘なども含めた各クラフトを何回行うかを計算するために、アイテムごとに「需要」と「供給」の数値を設定します。以下ではクラフトという言葉に採掘なども含めることとします。
あるクラフトを1回行うと、そのクラフトで得られるアイテムに供給が発生し、そのクラフトで使用するアイテムに需要が発生すると考えることができます。もし需要が供給を上回っている場合、クラフトに必要な素材が足りていないことを意味します。そのため、計算を行うときには、需要が供給を上回らないことを条件に含める必要があります。
例えば、ダイヤモンドのツルハシを1回クラフトすることを考えると、ダイヤモンドに3つの需要が発生し、棒に2つの需要が発生します。ダイヤモンドの需要を満たすためにダイヤモンドを3つ採掘することで供給する必要があります。
ちなみに時間はほぼ無限に供給されるものとします。
数理最適化問題とは
ある変数（例えばx）がある範囲内（例えば5＜x≦8）である関数（例えばx^2）の値が最も大きくなる場所（例えばx=8）を探す問題です。
範囲のことを制約条件と呼び、関数のことを目的関数と呼びます。
数理最適化問題の中でも範囲と関数が一次関数で記述されるような問題の場合は線形計画問題と呼ばれ、簡単に解くことができます。
また、変数が整数である場合は整数計画問題と呼ばれ、解く難易度が多少上がります。
問題の定式化
まずは考えている問題の分類から始めるといいらしいです。
考えている問題は、ドラゴン討伐にかかる時間を最小化し、各クラフトの実行回数を求める問題です。
その中で、制約として各アイテムの需要が供給を上回らない必要があります。
また、クラフトの回数は非負の整数回である必要があります。
以上を踏まえると、この問題は整数計画問題に分類されるような気がします。
具体的な条件としては
整数:x_0,x_1,\dots,x_{n-1},x_n
最小化:x_0 c_{0time}+x_1 c_{1time}+\dots +x_{n-1} c_{n-1time}+x_n c_{ntime}
\begin{aligned}
制約: &0\le x_0 p_{0i}+x_1 p_{1i}+\dots +x_{n-1} p_{n-1i}+x_n p_{ni}-x_0 c_{0i}-x_1 c_{1i}-\dots -x_{n-1} c_{n-1i}-x_n c_{ni}\\
&(i=time,0,\dots,m-1)\\
\end{aligned}
大変みにくいですが、まず$n$はレシピの数、$m$はアイテムの数、$x_r$はr番目のクラフトの実行回数、$c_{ri}$はクラフトrのアイテムiの消費量、$p_{ri}$はクラフトrのアイテムiの生産量です。
実際に解いてみる
pythonでortoolsを使ってみます。
from ortools.linear_solver import pywraplp
class Recipe:
def __init__(self,result,materials,results=1):
self.result=result
self.materials=materials
self.results=results
class Material:
def __init__(self,name,count):
self.name=name
self.count=count
items=["time","oak_log","oak_planks","stick","wooden_pickaxe","stone","stone_pickaxe","iron","iron_pickaxe","diamond","diamond_pickaxe"]
recipes=[
Recipe(
"oak_log",
[Material("time",1)]),
Recipe(
"oak_planks",
[Material("oak_log",1)],4),
Recipe(
"stick",
[Material("oak_planks",2)],4),
Recipe(
"wooden_pickaxe",
[Material("oak_planks",3),Material("stick",2)],1),
Recipe(
"stone",
[Material("wooden_pickaxe",1/59),Material("time",1)],1),
Recipe(
"stone_pickaxe",
[Material("stone",3),Material("stick",2)],1),
Recipe(
"iron",
[Material("stone_pickaxe",1/131),Material("time",1)],1),
Recipe(
"iron_pickaxe",
[Material("iron",3),Material("stick",2)],1),
Recipe(
"diamond",
[Material("iron_pickaxe",1/250),Material("time",1)],1),
Recipe(
"diamond",
[Material("diamond_pickaxe",1/1561),Material("time",1)],1),
Recipe(
"diamond_pickaxe",
[Material("diamond",3),Material("stick",2)],1),
]
solver = pywraplp.Solver("MIP", pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
infinity=solver.infinity()
def get_coeffs(item):
coeffs=[]
for recipe in recipes:
value=0
if recipe.result==item:
value+=recipe.results
for material in recipe.materials:
if material.name==item:
value-=material.count
coeffs.append(value)
return coeffs
def get_bias(item):
if(item=="time"):
return 1000000000
if(item=="diamond"):
return -1
return 0
recipe_counts=[]
for i in range(len(recipes)):
recipe_counts.append(solver.IntVar(0, infinity, str(i)))
for item in items:
coeffs=get_coeffs(item)
solver.Add(sum(recipe_counts[i] * coeffs[i] for i in range(len(recipe_counts)))+get_bias(item)>=0)
coeffs=get_coeffs("time")
solver.Maximize(sum(recipe_counts[i] * coeffs[i] for i in range(len(recipes))))
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
for recipe in recipe_counts:
print(f"{recipe.solution_value()}")
else:
print("No solution found.")
これで、出力を見てみると……（おそるおそる）
1.0
1.0
2.0
0.0
0.0
0.0
0.0
0.0
0.0
4.0
1.0
それぞれの数字が何のクラフトかというと
1回：原木の伐採
1回：木材の作成
2回：棒の作成
0回：木のピッケルの作成
0回：石の採掘
0回：石のツルハシの作成
0回：鉄の採掘
0回：鉄のツルハシの作成
0回：鉄のツルハシでダイヤを採掘
4回：ダイヤのツルハシでダイヤを採掘
1回：ダイヤのツルハシの作成
鉄のツルハシを使っていませんね。
数理最適化君はまずダイヤを3つ借金して借りて、ダイヤのツルハシを作ってダイヤを4つ採掘して、それから1つを目標の達成に充てて、残り3つを借金の返済に充てた、という感じでしょうか。
問題点
借金ができるのは問題ですね、確かに。
マイクラでは無からアイテムを錬成して後で返すなんてできませんからね。
では借金をしているところを発見したら、借金ループの外部からアイテムを供給する制約を追加して……と、思いましたがよく考えたらどうやって借金を発見するのでしょうか。
このソルバーで求められる答えは、各クラフトの回数であってクラフトの順番ではありません。
つまり、アイテムの数がマイナスになった（＝借金をした）タイミングを検出することができないわけです。
それだけでなく、もしこのソルバーで正しい解を求めることができたとしても、クラフトの順番が分からないので解の使い道がありません。
なんてこった／(^o^)＼
解決策
要は生産と消費を同時に行えてしまうのが問題なのです。
需要と供給の代わりに在庫とタイムステップを導入します。
在庫は現在持っているアイテムの数で、生産をするときは在庫が尽きないように消費をする必要があります。
生産されたものは次の時間ステップで利用可能になります。
例えば、時刻0では大量の時間を所有しており、時間を消費して原木を入手しました。この原木は時刻1以降で利用可能になります。時刻1では原木を消費して木材を入手する、といった具合です。
条件としては
整数:x_{0t},x_{1t},\dots,x_{n-1t},x_{nt} \quad(t=0,\dots,T-1)
最大化:s_{timeT}
\begin{aligned}
制約: &s_{it} \ge x_{0t} c_{0it}+x_{1t} c_{1it}+\dots +x_{n-1t} c_{n-1it}+x_{nt} c_{nit}\\
&s_{it+1}=s_{it}+x_{0t} p_{0it}+x_{1t} p_{1it}+\dots +x_{n-1t} p_{n-1it}+x_{nt} p_{nit}-x_{0t} c_{0it}-x_{1t} c_{1it}-\dots -x_{n-1t} c_{n-1it}-x_{nt} c_{nit}\\
&(i=time,0,\dots,m-1,t=0,\dots,T-1)\\
\end{aligned}
ただし、$x_{rt}$は時刻tのクラフトrの回数で、$T$はタイムステップの数、$s_{it}$は時刻tのアイテムiの在庫、$c_{rit}$は時刻tのクラフトrのアイテムiの消費量、$p_{rit}$は時刻tのクラフトrのアイテムiの生産量です。
前のモデルとの違いは、前のモデルの制約が供給≧需要だったのに対してこちらは在庫≧需要になっている点です。
実際に解いてみる（Part2）
from ortools.linear_solver import pywraplp
class Recipe:
def __init__(self,result,materials,results=1):
self.result=result
self.materials=materials
self.results=results
class Material:
def __init__(self,name,count):
self.name=name
self.count=count
items=["time","oak_log","oak_planks","stick","wooden_pickaxe","stone","stone_pickaxe","iron","iron_pickaxe","diamond","diamond_pickaxe"]
recipes=[
Recipe(
"oak_log",
[Material("time",1)]),
Recipe(
"oak_planks",
[Material("oak_log",1)],4),
Recipe(
"stick",
[Material("oak_planks",2)],4),
Recipe(
"wooden_pickaxe",
[Material("oak_planks",3),Material("stick",2)],1),
Recipe(
"stone",
[Material("wooden_pickaxe",1/59),Material("time",1)],1),
Recipe(
"stone_pickaxe",
[Material("stone",3),Material("stick",2)],1),
Recipe(
"iron",
[Material("stone_pickaxe",1/131),Material("time",1)],1),
Recipe(
"iron_pickaxe",
[Material("iron",3),Material("stick",2)],1),
Recipe(
"diamond",
[Material("iron_pickaxe",1/250),Material("time",1)],1),
Recipe(
"diamond",
[Material("diamond_pickaxe",1/1561),Material("time",1)],1),
Recipe(
"diamond_pickaxe",
[Material("diamond",3),Material("stick",2)],1),
]
T=9
solver = pywraplp.Solver("MIP", pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
infinity=solver.infinity()
def get_coeffs(item):
coeffs=[]
for recipe in recipes:
value=0
if recipe.result==item:
value+=recipe.results
for material in recipe.materials:
if material.name==item:
value-=material.count
coeffs.append(value)
return coeffs
def get_consume(item):
coeffs=[]
for recipe in recipes:
value=0
for material in recipe.materials:
if material.name==item:
value+=material.count
coeffs.append(value)
return coeffs
recipe_counts=[]
for t in range(T):
t_list=[]
for i in range(len(recipes)):
t_list.append(solver.IntVar(0, infinity, "r"+str(i)+"t"+str(t)))
recipe_counts.append(t_list)
inventories=[]
for i in range(len(items)):
inventories.append(solver.NumVar(0, infinity, "i"+str(i)+"t-1"))
counts=0
item=items[i]
if item=="time":
counts=10000000000
solver.Add(inventories[i]==counts)
inventories=[inventories]
for t in range(T):
t_list=[]
for i in range(len(items)):
item=items[i]
coeffs=get_consume(item)
old_inventory=inventories[t][i]
inventory=solver.NumVar(0, infinity, "i"+str(i)+"t"+str(t))
t_list.append(inventory)
indexies=list(filter(lambda x:coeffs[x]!=0,range(len(recipes))))
solver.Add(old_inventory>=sum(recipe_counts[t][j] * coeffs[j] for j in indexies))
coeffs=get_coeffs(item)
indexies=list(filter(lambda x:coeffs[x]!=0,range(len(recipes))))
solver.Add(inventory==old_inventory+sum(recipe_counts[t][j] * coeffs[j] for j in indexies))
inventories.append(t_list)
solver.Add(inventories[T][items.index("diamond")]==1)
solver.Maximize(inventories[T][items.index("time")])
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
recipe_s=[0]*len(recipes)
for t_list in recipe_counts:
print(", ".join(map(lambda x:str(x.solution_value()),t_list)))
for t_list in recipe_counts:
for i in range(len(t_list)):
recipe_s[i]+=t_list[i].solution_value()
print(", ".join(map(str,recipe_s)))
for i in range(len(items)):
print(items[i]+": "+str(inventories[T][i].solution_value()))
else:
print("No solution found.")
出力を見てみると……
2.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 2.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 3.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 3.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0
2.0, 2.0, 2.0, 1.0, 3.0, 1.0, 3.0, 1.0, 1.0, 0.0, 0.0
time: 9999999991.0
oak_log: 0.0
oak_planks: 0.999999999999999
stick: 2.0000000000000013
wooden_pickaxe: 0.9491525423728814
stone: -1.4582422516496985e-16
stone_pickaxe: 0.9770992366412214
iron: 3.5474580111052625e-16
iron_pickaxe: 0.996
diamond: 1.0
diamond_pickaxe: 0.0
おお、アイテム欄を見てみると木のツルハシや石のツルハシが作られて使われた痕跡があります。
正しく動いているようですね。
クラフト回数の方も問題なさそうです。
ただ浮動小数点数の精度が怪しいですね。
小数はあまり使わないほうが良いのかもしれません。
ところで、上の方の各タイムステップでクラフトを何回行ったのかの表には依存関係などが無いため、表に従って上から順に動けばダイヤモンドを入手することができます。（作業台などが無いですが）
とてもえらいですね。
さらに問題点
T（タイムステップの数）が過剰だと関係のない行動をして時間を無駄に浪費することがあります。
上のコードだと、例えばT=12の時。
出力は
3.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 2.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 2.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 3.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 3.0, 0.0, 0.0, 0.0, 0.0
0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0
3.0, 3.0, 3.0, 1.0, 3.0, 1.0, 3.0, 1.0, 1.0, 0.0, 0.0
time: 9999999989.999987
oak_log: 0.0
oak_planks: 2.9999999999999947
stick: 5.99999999999999
wooden_pickaxe: 0.9491525423728813
stone: 0.0
stone_pickaxe: 0.9770992366412212
iron: 0.0
iron_pickaxe: 0.9959999999999999
diamond: 1.0
diamond_pickaxe: 0.0
で、T=9の出力（最初の出力）と比べると、木材や棒を過剰に生産していることが分かります。これはバグですね。
原因は分かりません。
まとめ
数理最適化でマインクラフトをクリアできる可能性について書きました。
パラメーター数やタイムステップ数を増やしても精度を維持することができるのか、また実行速度はどうなるのかが疑問です。
また、放置をどのように扱うかも検討が必要になります。（かまどをたくさん設置すれば早く精錬が終わるとか、かまどを動かしている間に別のことをするとか）