Disclaimer: I am by no means an expert in this sort of thing so please do correct me if I get things entirely wrong! I should also warn you that, whilst I’ll try to keep this as accessible as possible, some prior programming/comp-sci knowledge is recommended.
Back in 2018 (geesh, how time flies!) I wrote about how Autocrafting in Minecraft was NP-hard, by reducing the Boolean satisfiability problem (SAT) to Minecraft recipes. While this shows a lower bound, it does not show an upper bound.
Since then, I’ve found something a little more horrifying. Minecraft recipes are equivalent to Petri nets.
An introduction to Petri nets
Wikipedia does a far better job than I could, but in summary Petri nets are a special kind of graph, composed of two kinds of node: places and transitions, edges between these nodes, and a marking.
- Places are a store of a resource we call tokens. Each place can hold any number of indistinguishable tokens.
- Transitions move tokens between places. Transitions consume a specific number of tokens (possibly zero) from each place and convert them to a new set of tokens which we can store in a different place.
- Markings describe how many tokens are at each place. A Petri net starts with an initial marking, and the marking changes as transitions move tokens about.
This might be easier to demonstrate with a diagram. Here we’ve got a Petri net with the following:
- Three places, , and .
- A single transition , which takes 2 tokens from A and 3 from B. It then produces 1 token, sending it to C.
- Place A contains 3 tokens, B has 5 and C has 0. This is our initial marking.
After our transition fires once, our Petri net ends up with a new marking. There is now 1 token at A, 2 at B and 1 at C.
Crafting with Petri nets
If you squint a little bit, you can see how this is a bit like a crafting recipe, with places corresponding to items and transitions corresponding to recipes. Let’s swap out our places and transitions with something from Minecraft, and see what our network might look like then:
Then, if our storage system contains three sticks and five cobblestone, we’d put three tokens on our stick place, and five on our cobblestone place - just like the original figure!
It’s pretty simple to see how we could extend this for all of Minecraft’s crafting recipes, building one absolutely massive Petri net of items and recipes. We could even extend this network to contain other recipes (such as smelting) or even other resource types (fluids, exp, etc…), to build an incredibly complex model of Minecraft’s crafting system.
It’s worth mentioning here that while we’ve (informally) shown that we can reduce crafting recipes to Petri nets, we haven’t gone the other way round: can we generate crafting recipes from arbitrary Petri nets?
Technically, no. Unlike crafting recipes, Petri nets can have more than 9 inputs, and any number of outputs, and so there’s no simple bijection between the two. However, we’re going to ignore this distinction here1.
Autocrafting with Petri nets
It’s definitely nice to know that crafting recipes and Petri nets are equivalent. And, given Petri nets are of great interest to many computer scientists, surely there’s some nice tricks we can do to build powerful auto-crafting solvers?
Well, before we get onto that, let’s look at one of the common properties of petri nets, and see how it’s useful for us.
The reachability problem for Petri nets asks us whether, given a Petri net and an initial marking, if it’s possible to reach a different target marking just by firing our transitions. Or, in Minecraft terms, is it possible to craft this item given the items available to us?2.
This is definitely useful to know! In fact, it sounds just like what we’re looking for. And, even better, reachability in Petri nets is a useful problem in many domains, and so there’s been lots of research into it.
Alas, things are not as ideal as they might be. It turns out the complexity of determining reachability in Petri nets is even worse than that of SAT. Much worse.
Infinite powder, infinite states
Let’s backtrack a bit and talk about a classic Minecraft dupe bug: blaze rods and blaze powder. Vanilla Minecraft contains a recipe to convert one blaze rod into two blaze powder.
Some Minecraft mods also add a recipe to reverse this, such as using transmutation or a compressor. Other mods may also add a more efficient way to get blaze powder, turning one blaze rod into 3 or 4 powder.
We can abuse this interaction between the two extra crafting recipes to obtain infinite blaze powder. First convert one blaze rod into three powder, and then two powder into one rod. For each cycle, we get one powder left over.
If we were to put these recipes into our autocrafting system, we could then ask it to magic up 100 blaze powder from a single rod. But what would that actually involve?
As a human, it’s easy to describe: just repeat the two recipes a few hundred times until you’ve got enough. But an autocrafter doesn’t have this sort of luxury; instead it has to apply each step, one at a time. And what starts off as a simple request (100 of this item please) can explode into a solution exponentially longer than the original problem.3
As a bit of a general rule4 in complexity theory, if the solution to a problem is pretty big, then it took even longer to actually find the solution. Indeed, solving the reachability problem doesn’t take exponential time (EXPTIME), or even exponential space (EXPSPACE). Instead, it instead lives beyond the realm of primitive-recursive functions, in a complexity class best described as 5.
Autocrafting with Petri nets, pt 2
Well, here we are, at a disappointing end, finding that autocrafting is a near-impossible and intractable problem. And yet, Applied Energistics and Refined Storage don’t seem to have got the memo - they still appear to work fine!
I mentioned this in the previous rambling, but I think it’s worth stressing again: in practice, none of this really matters. While you can express some really wacky problems with crafting recipes, this sort of weirdness just doesn’t show up in normal play. Aside from storage blocks (iron blocks to iron ingots), I’m not even sure vanilla Minecraft has any loops!
That said, I do think it’s fun to talk about these things. I do still think there’s scope for improvement in the world of autocrafting6, and hopefully this inspires someone. And failing that, I at least hope you’ve learned something!
As mentioned at the top, I’m definitely not an expert in any of this! If you do spot a mistake (or a typo!), please let me know on the issue tracker or get in touch directly.