Last month I wrote about Neal Agarwal’s web game Infinite Craft. Tom Fang wrote to tell me he’s created a dictionary of Infinite Craft elements, along with their uses and recipes. This got me thinking about the game’s mathematical structure.

By “mathematical structure,” I mean something like how we make recipes and the metrics by which we might compare one recipe to another. For example, if our goal is to make Sandwich, we could do it like this:

Wave = Water + Wind
Steam = Fire + Water
Plant = Earth + Water
Sand = Earth + Wave
Tea = Plant + Steam
Sandwich = Sand + Tea

Or like this:

Wave = Water + Wind
Sand = Earth + Wave
Glass = Fire + Sand
Wine = Glass + Water
Sandwich = Sand + Wine

If we diagram these recipes, we find that the first one is shallower, in the sense that we combine only the primitive elements, elements made from the primitives (Wave, Steam, Plant), and elements made from those elements (Sand, Tea). But the second one is terser, in the sense that it is five lines long instead of six.

At first glance, the world of Infinite Craft forms a directed hypergraph with a lot of structure: each directed hyperedge connects a set of one or two vertices to a set of exactly one vertex. But a recipe isn’t merely a “path” on that hypergraph! Mathematicians define the hypergraph analogue of a “path” as a set of incident hyperedges — “incidence” meaning that the edges share at least one vertex. In this sense there is a “path” from the starting elements to Sandwich that consists of only a single hyperedge; namely,

Sandwich = Wind + Grilled Cheese

That definition of “path” doesn’t help us.

I asked MathOverflow, and they pointed me to another example of the same problem: addition chains. An “addition chain” for an integer \(n\) is a sequence starting with 1 and ending with \(n\), such that each element in the sequence is the sum of exactly two previous elements. For example, we might make 31 in any of these three ways:

2 = 1 + 1              2 = 1 + 1              2 = 1 + 1
3 = 1 + 2              3 = 1 + 2              3 = 1 + 2
6 = 3 + 3              4 = 2 + 2              6 = 3 + 3
7 = 1 + 6              8 = 4 + 4              12 = 6 + 6
14 = 7 + 7             12 = 8 + 4             14 = 2 + 12
15 = 1 + 14            16 = 8 + 8             17 = 3 + 14
30 = 15 + 15           28 = 12 + 16           31 = 14 + 17
31 = 1 + 30            31 = 3 + 28

The middle chain is shallowest, but the right-hand one is tersest.

Addition chains are idiomatically written as just an increasing sequence of integers: (1 2 3 6 12 14 17 31). We don’t need to specify how each integer (say, 17) is constructed from the preceding elements, because it’s obvious. We could represent Infinite Craft recipes just as concisely — (Wave Sand Glass Wine Sandwich) — but that wouldn’t be very reader-friendly because it’s not obvious which two preceding elements combine to make, say, Wine.

Finding the tersest addition chain is directly relevant to the world of computer programming. Suppose we want to calculate the 31st power of an unknown number in register A, using only multiplication. Then we can do any of:

mul A, A, B  # A^2     mul A, A, B  # A^2     mul A, A, B  # A^2
mul A, B, C  # A^3     mul A, B, C  # A^3     mul A, B, C  # A^3
mul C, C, D  # A^6     mul B, B, D  # A^4     mul C, C, D  # A^6
mul A, C, E  # A^7     mul D, D, E  # A^8     mul D, D, E  # A^12
mul E, E, F  # A^14    mul D, E, F  # A^12    mul B, E, F  # A^14
mul A, F, G  # A^15    mul E, E, G  # A^16    mul C, F, G  # A^17
mul G, G, H  # A^30    mul F, G, H  # A^28    mul F, G, R  # A^31
mul A, H, R  # A^31    mul C, H, R  # A^31

Our “shallowness” metric translates into a measure of the data dependencies involved in these computations. The middle program, being the shallowest, is also the fastest on any machine with at least two multiplier units.

Another practically relevant metric for the “goodness” of a chain is its width: the number of registers it uses in its most optimal coloring. The left-hand recipe above is the narrowest, with width 2, whereas the others have width 3:

mul A, A, B  # A^2     mul A, A, B  # A^2     mul A, A, B  # A^2
mul A, B, B  # A^3     mul A, B, A  # A^3     mul A, B, A  # A^3
mul B, B, B  # A^6     mul B, B, C  # A^4     mul A, A, C  # A^6
mul A, B, B  # A^7     mul C, C, B  # A^8     mul C, C, C  # A^12
mul B, B, B  # A^14    mul C, B, C  # A^12    mul B, C, C  # A^14
mul A, B, B  # A^15    mul B, B, B  # A^16    mul A, C, A  # A^17
mul B, B, B  # A^30    mul C, B, B  # A^28    mul C, A, R  # A^31
mul A, B, R  # A^31    mul A, B, R  # A^31

The left-hand recipe corresponds to Russian peasant multiplication, which always generates an addition chain of width 2. For in-depth coverage of various algorithms to generate addition chains, see Knuth Volume 2 §4.6.3 “Evaluation of Powers.”

Surprisingly, the “tersest chain” problem is non-trivial in both Infinite Craft and addition-chains. Knuth writes:

Several authors have published statements (without proof) that the binary method [that is, Russian peasant multiplication] actually gives the minimum possible number of multiplications. But that is not true. The smallest counterexample is \(n = 15\), when the binary method needs six multiplications, yet we can calculate \(y = x^3\) in two multiplications and \(x^{15} = y^5\) in three more, achieving the desired result with only five multiplications.

This suggests the algorithm Knuth calls the “factor method”; but yet again, you can find numbers whose optimal chain eludes both the binary method and the factor method! It appears that there is no fast (non-exponential-time) algorithm that generates an optimal addition chain for every input.

To get an intuitive sense of the difficulty — in particular, why no greedy algorithm helps — look again at our tersest route to Sandwich:

Wave = Water + Wind
Sand = Earth + Wave
Glass = Fire + Sand
Wine = Glass + Water
Sandwich = Sand + Wine

This route to Sandwich passes through Wine on the fourth step. Now, the tersest route to Wine itself is only three steps:

Plant = Earth + Water
Dandelion = Plant + Wind
Wine = Dandelion + Water

But if you make Wine by that route, you’ll never reach Sandwich in the optimum number of steps!

Similarly, our tersest route to 31 was (1 2 3 6 12 14 17 31), passing through 17 on the sixth step. There are two routes that make 17 in only five steps:

(1 2 4 8 9 17)
(1 2 4 8 16 17)

But if you make 17 by either of these routes, you’ll never reach 31 in the optimum number of steps!

Neill Clift of AdditionChains.com produced this example for me — my utmost thanks to him! According to Neill, there are exactly five optimal chains for 31 that contain the number 17: none of those chains contain (1 2 4 8). Meanwhile there are seventy-two other optimal chains for 31 that don’t contain 17 at all.

UPDATE, April 2024: A third algebraic structure with this shape is this one from StackOverflow. We have one primitive element A representing a fair coin flip that lands heads with probability \(0.5_{10} = 0.1_2\). We can construct new elements using either of two binary operations: & (representing a coin that lands heads iff both inputs were heads) and | (representing a coin that lands tails iff both inputs were tails). We’re trying to reach a target state representing a coin that comes up heads with probability \(p\) (for some \(p = a/2^b\) between 0 and 1).

For example, we can make a coin that lands heads with probability \(0.5675_{10} = 0.1001_2\) in either of these ways:

B = A & A = 0.01          B = A | A = 0.11
C = B & A = 0.001         R = B & B = 0.1001
R = C | A = 0.1001

I have not thought much about this particular structure, but it feels just as non-trivial as addition chains.

Still, knowing that Infinite Craft and addition chains are two examples of the same hypergraph structure doesn’t tell me whether there’s an accepted name for this particular hypergraph structure. If you have any leads, please pop over to MathOverflow and/or send me an email!

Observe that the addition-chain structure is commutative and associative, whereas the Infinite Craft structure is commutative but non-associative:

Plant = Water + Earth
Lava = Earth + Fire
Smoke = (Water + Earth) + Fire
Stone = Water + (Earth + Fire)

This makes much of Knuth’s discussion (particularly “Graphical representation” and the generation of equivalent dual addition chains) inapplicable to Infinite Craft.

To explore the Infinite Craft hypergraph offline — without stressing Neal’s backend or needing to evade his Cloudflare bot-detection filter — you can download a compressed database containing about 30,000 elements from Tom Fang’s GitHub, szdytom/infinite-craft-dictionary. Computing the tersest recipe for each element, and inventing a compact way to represent such a recipe in the database, is left as an exercise for the reader!