Interesting puzzle:

[blazespinnaker]

Let's say you start off on a world with no rocks, but you have 100 coal, 100 stone, 1 burner miner, and 1 furnace. Infinite ore is adjacent (coal / stone / copper / iron). Hand mining is disabled. Placement of all entities is immediate (zero time), as is feeding / grabbing of resources.. Everything is implicitly powered (don't need to power anything).

Feel free to further simplify if you run into a quandary.

What is the maximum number of miners you can build in 10 minutes?

Bonus points for algorithms / equations!

[blazespinnaker]

one approach is using genetic algorithms

GA is actually not that hard to do usually, though mapping factorio build order to code and mating them will be a bit of a task.

fitness evaluation in this case is just max # of miners.

the idea behind GA here is actually easy to explain. it's based on darwinism, a concept most people are familiar with.

a. create a random set of valid build orders as your first population
b. select the 'fittest' build orders from the population. keep a record of the most fit build order found so far
c. 'mate' many different random pairs of 'fit' build orders to generate new 'child' build orders. think of it as pairs of attractive parents having children who will be potentially attractive themselves
d. optionally mutate the new child build orders
e. using the children generated in c/d as your new population, loop back to b.

as mentioned, the fittest build orders would be the build orders with the most miners.

mating involves taking 'dna' or build sub-sequences from the parent build orders. this is done randomly. this could be a bit tricky with factorio as you want the children to be viable / valid

there are variations, but that's the basic idea.

There was a lot of hubbub about using GA with Starcraft build orders.

https://link.springer.com/article/10.10 ... 013-0263-2
http://lbrandy.com/blog/2010/11/using-g ... ld-orders/

I'm wondering if anyone has tried this with Factorio. I'm not a big fan of re-inventing wheels when it comes to coding (though it was fun with factorio blueprints

[DaveMcW]

Since everything is implicitly powered, you don't need any coal. I am going to ignore the starting 100 stone, but also assume that growth is a continuous function. You can use the extra stone to accelerate the completion of buildings so their output matches the continuous function.

There are two phases:
1. Build burner mining drills and stone furnaces in the perfect ratio.
2. Upgrade all the stone furnaces into burner mining drills, giving the maximum number of burner mining drills at 10 minutes and a non-functioning factory.

Crafting time

The burner mining drill recipe has a crafting time, but the critical path goes through the last iron ore, the last iron plate, and the mining drill recipe. So we can account for the crafting time by doing nothing for the first 4 + 3.2 + 2 = 9.2 seconds of the 10 minutes.

Perfect ratio

The burner mining drill requires 9 iron ore, 9 iron plates, and 5 stone. Another stone furnace requires 5 stone. This means at a 1:1 ratio, we need (9+5+5)/0.25 = 76 seconds of mining and 9*3.2 = 28.8 seconds of smelting.

So the 1:1 ratio is wrong. We actually need a 76:28.8 ratio of burner mining drills to stone furnaces. This requires (9+5+5*(28.8/76))/0.25 = 63.6 seconds of mining and 28.8 seconds of smelting.

So the 76:28.8 ratio is wrong. We actually need a 63.6:28.8 ratio of burner mining drills to stone furnaces. This requires (9+5+5*(28.8/63.6))/0.25 = 65.1 seconds of mining and 28.8 seconds of smelting.

So the 63.6:28.8 ratio is wrong. We actually need a 65.1:28.8 ratio of burner mining drills to stone furnaces. This requires (9+5+5*(28.8/65.1))/0.25 = 64.8 seconds of mining and 28.8 seconds of smelting.

64.8:28.8 simplifies to a 9:4 ratio of burner mining drills to stone furnaces, which is our goal at the start of phase 1. By the end of phase 2, we should move all the stone miners to iron, and overbuild stone furnaces to smelt all that iron ore into plates. The ratio at the end of phase 2 is 3.2:(1/0.25) = 5:4 ratio of burner mining drills to stone furnaces.

We start at a 9:4 ratio, and end at a 5:4 ratio. This can be approximated by a 7:4 ratio of burner mining drills to stone furnaces over the entire 10 minutes.

Exponential growth

The formula for exponential growth is x = x0 * e^(k * t).

x0 = Starting population. Since we start with 1 burner mining drill and 1 stone furnace, this is (1+1)/(1+7/4) = 0.727 of our target ratio.
e = The base of the natural logarithm = 2.71828
k = The growth rate per second. At our target ratio, it takes 28.8 seconds to double the population, so the growth rate is 1/28.8 = 0.0347 per second.
t = Time. 10 minutes * 60 - 9.2 crafting time = 590.8 seconds.

So plugging everything into the formula:
x = (0.727) * (2.71828)^(0.0347 * 590.8)
x = 581962988

Remember that the units are a set of 2.75 burner mining drills and furnaces, all of which will be upgraded to burner mining drills. So we multiply x by 2.75.

The final answer is 1,600,000,000 burner mining drills.

[Jap2.0]

Is hand crafting instant?

Does the prohibition on hand mining specifically refer to resources or everything?

Is it correct to assume that "miners" specifically refers to burner miners, and as a result there is no benefit from any production of coal (due to implicit power) and potentially copper (as with infinite space and insertion/extraction of resources the electric system is useless and the only research that could potentially be of use is assemblers (dependent on question 1 above))?

[MassiveDynamic]

“I am not a smart man”
- Forrest Gump
- me

[blazespinnaker]

here's the datastructure I'm going to use. i like it because it doesn't make assumptions about what has already been built, so I can pull the DNA from parents. there are some rules I'll need to enforce, but I don't think it should be that hard. i think this can be scaled up to larger builds with longer time between build actions. it does assume you'd spend more time on specific tasks though and certain micro/tactical things can't change the outcome that much.

note that it doesn't account for walking time as Nefrums pointed out. that is a serious issue I have some ideas on how to resolve, but the solution is a bit specific to the assumptions made about the map and where entities are placed.

let me know what you think

Let's say you start off on a world with no rocks, but you have 100 coal, 100 stone, 1 burner miner, and 1 furnace. Infinite ore is adjacent (coal / stone / copper / iron). Hand mining is disabled. Placement of all entities is immediate (zero time), as is feeding / grabbing of resources.. Everything is implicitly powered (don't need to power anything).

every X seconds. X = 60 / APM (actions per minute) of assumed player. . r X = 1s means that player can do something different every 1s. will craft only whole objects, not partial, so if whole object can not be completed in 10s, then it won't start. eg, crafting an assembler requires gears, plates, GC.


terminology

actions=['c', 'p', 'fz', 'fh', 'ff', 'g']
==
c = crafting
p = placing
fz = feeding with z drop
fh = feeding half ctrl right click
ff = feeding full ctrl left click
g = grabbing (assume left click)


entities=['im', 'if', 'imfp', 'sm', cm', 'cf', 'cmfp', 'gasm', fasm', 'masm', 'casm', 'asasm']
==

im = iron miner
if = iron furnace
imfp = iron miner furnace pair
sm = stone miner (ignore chests)
cm = copper miner
cf = copper furnace
cmfp = copper miner furnace pair
gasm = gear assembler
gsasm = green circuit assembler
fasm = furnace assembler
masm = miner assembler
casm = coal assembler
asasm = assembler assembler

resources=['g', 'gs', 'coi', 'coa', 'i', 'cop', 's']
==
g = gears
gs = green circuits
coi = coil

coa = coal
i = iron
cop = copper
s = stone

amount for crafting / feeding
==
amount will be random number generated % amount of available resources. rng will be multiples of 25% (25,50,75,100%). use available resources
eg, for green circuits, use lower of iron and copper. eg, if it's 50%, and there are 1000 iron but only 3 copper, than only 1 gs can be created. placing assumes all, but rate limited

eg build steps:
(c, im, 50) means craft iron miners using 50% of available resources.
(c, im, c) means feeding with zdrop iron miners coal
(ff, gasm, i) means feeding with left click iron into gear assemblers

a build order is just a list of build steps [(c, im, 50) , (c, im, c) , (ff, gasm, i) ..]


rate_limiting
==
there is a rate limit to all activities.
crafting = CRLPS (default 5 per second)
placing = PRLPS (default 5 entities per second)
feeding = FRLPS (default 5 entities per second)
grabbing = GRLPS (default 5 entities per second)


rules
==

Certain things can't occur in a build order until other things have occured, even during mating. if invalid, another random build order item is generated or dna is selected
- c_*asm can't occur until ASM_IMFPS miners are placed and ASM_CMFPS copper miner furnacer pairs are placed.
- feeds can't occur until the resource has been crafted and grabbed if crafted in a assembler
- you can't have more than 8 thousand resources in your inventory at any time

Certain things can't be placed,
- cm, im, *f, g, gs, i, coi, coa, cop, s
better might be what can be placed
- *mfp, *asm, sm

[blazespinnaker]

The final answer is 1,600,000,000 burner mining drills.

Uhm, I think you simplified too much

but the answer might be ballpark right. the problem clearly is the instantaneous feeding / placing / grabbing resources which is not realistic. maybe also you assumed hand crafting was instant, which maybe is the over simplification

walking time is also an issue of course, but rather complicated to account for

[blazespinnaker]

Is hand crafting instant?

Does the prohibition on hand mining specifically refer to resources or everything?

Is it correct to assume that "miners" specifically refers to burner miners, and as a result there is no benefit from any production of coal (due to implicit power) and potentially copper (as with infinite space and insertion/extraction of resources the electric system is useless and the only research that could potentially be of use is assemblers (dependent on question 1 above))?

I re-added some complexities back in for my answer. so hand crafting is not instant anymore, at least in my approach. everything except walking is rate limited.

Thinking about it some more, while Dave didn't account for assemblers and I guess he made hand crafting instant, I think if feeding/grabbing/placing is also instant, the number is still going to be insanely large if not quite what he arrived at. ie, if you can instantaneously place down assemblers and there are no limits to ore, then you're going to get a doubling. maybe not 28.8 seconds, but still some constant that will grow the function very quickly.

rate limiting feeding feeding,

and yes, i'm thinking burner miners, but really the question is just a instantiation of a particular archetype. it's the over all optimization problem that i've been thinking about for awhile and had hoped someone had already tackled it.

[DaveMcW]

The basic concept is still exponential growth. The details are about how long it takes for the player (or CPU, or size of the universe) to become the bottleneck.

[blazespinnaker]

Yeah with instant assembler placement and hand feeding/grabbing (without limit), agreed, it'd be exponential.

however, those are clearly not useful simplifications as I've discovered, and I'm sure everyone else already arrived at that point a long time ago.

I think a logistics curve makes more sense for what it actually will end up loooking like.

logisticgrowth.png (15.05 KiB) Viewed 6773 times

of course, recursive blueprints are an entirely different thing

[4xel]

Crafting time

The burner mining drill recipe has a crafting time, but the critical path goes through the last iron ore, the last iron plate, and the mining drill recipe. So we can account for the crafting time by doing nothing for the first 4 + 3.2 + 2 = 9.2 seconds of the 10 minutes.

I'm not sure to understand, are you accounting for the delay introduce by crafting time? IMO, such a detail does not matter if you ignore any other aspect of crafting time (like the necessity to have assemblers) and the granularity of machines (which introduce a bigger delay.

k = The growth rate per second. At our target ratio, it takes 28.8 seconds to double the population, so the growth rate is 1/28.8 = 0.0347 per second.

28.8 is the time it takes to smelt 9 iron plates, or a single burner drill. If your unit is 2.75 burner drills and 1 furnace, you have to multiply that time accordingly.

With that change and only bothering for phase 1 (so a unit of 9/4 drill +1 furnace), the typical duplication time is much larger, 64.8, and the formula is:
x = (0.444) * (2.71828)^(600/64.8)

I've taken 4/9 as x_0 cause that's a safe lower bound, and there is not really any way to make use of the extra smelting power until you reach perfect ratio.

Which yields a drastically lower:
x = 4663 unit,

or 4663 furnaces and 10491 drills.

[4xel]

You could apply linear algebra to the problem.

Theory

• x is your assets vector.
• A is the production matrix: if you do nothing your asset increases by A.x (during a step or infinitesimally). It's a square matrix each of whose column represent production of an asset in the asset vector.
• R recipe table. A matrix each of whose column correspond to a recipe, with negative value for ingredients and positive for products.
• s(x) or s(x, t) strategy vector.

The strategy vector satisfies:

• s(x) >= 0 you can't craft negative amounts, recipes are assumed non reversible by default.
• R.s(x) is homogenous to an asset vector.
• (optional) C.(R.s(x) + A.x) =0. Where C is typically a projection, but can be any linear application. This constraint is useful to simulate resources you can't store, such as crafting time (you need to add idling recipe)

x follows the differential equation:
dx/dt = A.x + R.s(x)

and, at anytime, satisfies the constraint:
x >= 0 (you can't have negative amount of items)

Optionally, you can ask coordinates to be integers and still be able to say things (with linear recursive sequence instead of of differential equations), but I'll assume the problem is of continuous nature for machines from now on.

For simple problems, no tech involved, one clear strategy, and I think the current problem is mostly simple enough,
s(x) can be expressed as a linear function of x, making the problem easily solvable:

let a constant matrix S be such that:
s(x) = S.x

then
dx/dt = (A + RS).x

A spectrale analysis of A+RS gives the answer we are after. Usually, there is a biggest eigen value corresponding to the fastest growth, and the corresponding eigen vector(s) corresponding to the best ratio.

Other eigen values indicates how suboptimal it is to go other routes along there Eigen vectors. These Eigen vector also provides the value of your different assets relative to each other (as long as you move along non principal Eigen vectors, your asymptotic growth is unchanged).

Examples:

There are many different ways to define the asset vector and to assign things to production or to recipe. For example, you can choose whether to differantiate miners depending on the ore they stand on. You can have them produce ore, or you can have them only produce ore potential, and put in the recipe table a column to convert power into ore.


Example1:

In this example, I account for iron, stone and coal (drills and miners have to be powered).

The assets are:

• (Burner Mining) Drill
• (Stone) Furnace
• Coal
• ore
• plate

The productions are:

• 1/4 ore and -3/80 coal per burner drill
• 10/32 plate -10/32 ore and -9/400 coal per furnace

the recipees are:

• mine coal: -1 ore +1 coal
• craft furnace: -5 ores +1 furnace
• craft drill: -1 furnace -9 plates +1 drill
• some idle recipe that cancel production to ensure there is always a strategy with non negative coal on hand.

The strategy is:

• craft just enough coal to have it non negative.
• craft as many miners as possible, crafting new furnaces if needed
• craft as many furnaces as possible

Main Phase

Assuming

• You no longer have coal, ore or plate in reserve
• Your drill/furnace ratio is big enough so that you can spend all your plates at anytime

This strategy happens to be linear and stable.

The number of prescribed recipes is as follows:
The strategy is:

• craft coal: 3/80 per burner drill, 9/400 per furnace
• craft drill: 10/32/9 per furnace
• craft furnace with remaining ore: 1/4/5 per burner drill - craft coal/5 - 10/32/5 per furnace : 17/400 per burner drill, -58/1000 -68/1000 per furnace

As you can see, I abstracted away ores and plates completely, and coal partially. For clarity, it could have used more intermedairy steps.

So you can now write dx = (A+RS).x
Where x only has two dimensions (drills and furnaces). Precisely, if x1 -> drills and x2 -> furnaces:

• dx1 = 5/144 x2
• dx2 = 17/400 x1 - 58/1000 68/1000 x2 -5/144 x2

Which I had Wolfram analyzed:
https://www.wolframalpha.com/input/?i=E ... F144%7D%7D

The main Eigen value is 0.0138 0.0128 and that's our exponential coefficient as well. The corresponding Eigen vector is (2.51, 1) (2.72, 1) and it's the perfect drill to furnace ratio. The corresponding typical time is 72.5 78.3 seconds.

The other Eigen value is -0.107 -0.115499 which is negative and of very high absolute value, which I think means the strategy is very stable (perturbation decay quickly).

Now there are several ways to compute the solution to the problem, but the classiest has to be matrix exponentiation:
https://www.wolframalpha.com/input/?i=+ ... 2%7D%7D%29

Simply apply exp(t * (A+RS)) to your starting vector.

For example, starting with a single miner and no furnace, the result is the first column of this matrix:
3591 1922 drills and 1432 707 furnaces at the end.

Caution though, you can only apply this to a vector which satisfies the condition to be in the main phase, in particular, "Your drill/furnace ratio is big enough so that you can spend all you plate at anytime". So 1 Drill one furnace needs a different initial phase (or a pessimistic evaluation counting the furnace only as a fraction of himself).


Initial and final Phase

Initial phase are also linear, just with a different system. The added difficulty resides in checking for the stopping condition (when a new phase begins).

As for the final phase, if your goal isn't just growth, I guess a similar approach to the initial phase and studying the problem backward, from the end (assuming you know what it looks like) might help know when to start it, but in general, it's unclear whether this phase will be linear and whether it makes sense to start it "abruptly" (linear strategies still make for smooth transitions).

Edit:
I have since started to code the math in this post to automate it, and caught a typo in my math. I corrected it.

[4xel]

I don't think I'll bother with the initial phase, but I might do the rigorous math once you factor in crafting time and electricity setup. I think I already did it the quick and dirty way once for electric drill and the duplication time was around 5 or 6 minutes, very far from the 1 min+ from my correction of Dave's math.

[blazespinnaker]

Wonderful start 4xel. Was hoping that some of the deeper math folks would help tackle some of these very intriguing problems. Quite surprised (pleasantly though) that the subject of production curves hasn't been well covered before this. Everything else in Factorio seems to have.

Btw, what does your production curve look like? It would be a reasonable representational summary of your solution.

Very useful would be code, but if not, than something a bit more cookbook. A list of inputs, outputs, and straightforward summary of transformations performed. This can be used to quickly check correctness.

Any references on this I can check out that this is building on, or purely original work? I'll dig in more deeply, but it deserves some careful consideration before responding in full.

In general, I will say that algorithmic simulation using various gradient heuristic and searching strategies is the only way to solve this problem with any degree of accuracy and completeness. This is simply due to the nature of the beast and behavior of the many conditional particulars of problem.

The one conditional particular that overwhelms everything is reach + walking distance. The ultimate rate limiter in pre-bot factorio.

That said, having some techniques which are not so np-complete is preferable to the frightful amount of compute required for the above. There might be some useful ways to summarize certain large categories of activities which would avoid the simulation requirement.

Somewhat related link - TAS run - 1:21 https://www.youtube.com/watch?v=qYIplmAQcWU

Sadly, however, it didn't use bots, which I think would have been approaching the perfect solution. Writing a TAS script would be challenging enough, no doubt.

That all said, perhaps this all really should just be a bot discussion and should be framed as such. It would help remove the walking distance problem.

[4xel]

Btw, what does your production curve look like? It would be a reasonable representational summary of your solution.

It looks like an exponential. Solutions of these kinds of equations are linear combination of exponential (or polynomials times exponential in rare cases), and they mostly look like their main -biggest- component.

Patching several such linear phase should look like patched exponentials.

Very useful would be code, but if not, than something a bit more cookbook. A list of inputs, outputs, and straightforward summary of transformations performed. This can be used to quickly check correctness.

I've only scratched the surface, it will take more time to get to that point. Difficulties will arise when there are no obvious strategy. When there is only one way to do each things (eg burner drill is the only drill, stone furnace is the only furnace, assembler1 is the only assembler), it should be relatively easy using only linear algebra, otherwise, we're entering convex optimization I think, and I don't see a way to automate it yet.

Also patching phases (when you start too far from perfect ratio, eg with resources you can't instantly spend) looks hard to automate.

Any references on this I can check out that this is building on, or purely original work? I'll dig in more deeply, but it deserves some careful consideration before responding in full.

All orignal work in the sense I did not look up anything to write it, I just summoned what I learnt in undergrad and digested over the years. But I would be very surprised if it hasn't been done elsewhere already, though not necessarilly for factorio or even video games. I'll look it up and see if I can give pointers cleaner than what I've done in a forum post.

The Prismata community came up with some very similar notion, and I thought they used matrices as well, but they didn't, they use direct calculation, and recursion when things beome intricate. For the most part, it's all about linear systems, so it's not surprising that matrices are not necessary, but become very useful for intricate system (and my 1st example isn't intricate enough to demonstrate their power IMO, but an example accounting for assembler should be).

The game is free to play on steam if you want to understand it more before diving into the math. The mathematically interesting bits can be found here:

https://www.reddit.com/r/Prismata/wiki/ ... /inflation
https://yujiri.xyz/prismata/math

It should also hint at ways to optimize growth in factorio. What they call inflation of a unit is really it's interest rate.

However, the interest rate of the best units in a set do correspond to a global inflation, hence the name. This concept is especially useful to assess the strength of units whose power comes delayed. Transpose to factorio, an inflation (corresponding to the current growth rate) could be useful to account for latency; for example, if inflation is 10% per minutes, an outpost with 2 minutes latency is virtually 10% more expensive than the same outpost with 1 minute latency.

Gather rate of workers are known and put to good use in any RTS game, but they're usually too fast pace, too interactive and the map is too finite for math to be useful for economy beyond gather rate and consumption rate of production buildings (such maths could be used to find new build orders, but the search space is usually tight enough that you'd be likely to find something that isn't new, isn't good or isn't too different from something which already exists).

In general, I will say that algorithmic simulation using various gradient heuristic and searching strategies is the only way to solve this problem with any degree of accuracy and completeness. This is simply due to the nature of the beast and behavior of the many conditional particulars of problem.

I'm pretty sure there are ways to prove that Dave's or my solution are perfect with regard to some simplified versions of the problem (mine for example optimizes for assymptotic growth of everything instead of 10 minutes number of miners).

The more things you account for, the harder it is to get an exact solutions though, and the place of solution of simplified problems is, I guess, to provide guidlines to players, and a starting point (and maybe heuristics) to a more complete simulation.

The one conditional particular that overwhelms everything is reach + walking distance. The ultimate rate limiter in pre-bot factorio.
[...]
Sadly, however, it didn't use bots, which I think would have been approaching the perfect solution. Writing a TAS script would be challenging enough, no doubt.

That all said, perhaps this all really should just be a bot discussion and should be framed as such. It would help remove the walking distance problem.

I think it's good to have a discussion about growth, and this is how I understood this thread. Bots could use their own discussion, but relative to growth they're only one piece of the puzzle (the last one).

I'm not convinced bots are necessary for TAS any%. The same way automation is not necessary until after your resource gathering rate exceeds your initial crafting rate, Bots aren't necessary until after your mall outpaces your building rate, and while it's common wisdom humans should get bots early, I have zero clue as to where the exact point lies for them, even less for tool assisted runs.

The building rate of a TA runner being much higher than those of a regular human, I would expect bot to be only be useful much later for him (in progression, not necessarilly in time). So late that they might have already launched a rocket.

Now it's a really complex problem, which also depend on whether you're still handfeeding (handfeeding might be so good as a TA it might or might not be worth doing it the whole game even if it competes with building). Also, bear in minds that a TA runner can increase its speed with stone paths, belts, and vehicles (and place stone walls to insta break when needed), probably multiplying its effective speed by 2 or so, and multiplying its building speed as well.



It's not the first time I ponder these kind of questions, and I want to tackle them cleanly and comprehensively at some point, so I totally get why you're interested in cookbook and graphs and I intend to give some eventually, but it's gonna take time.

[reinforcefoking]

GA is actually not that hard to do usually, though mapping factorio build order to code and mating them will be a bit of a task.

[blazespinnaker]

GA is actually not that hard to do usually, though mapping factorio build order to code and mating them will be a bit of a task.

Hah! I completed this after a very serious (for me) effort. If you're actually into this kind of thing, feel free to PM me and I'll share the code. It's not entirely up to my standards (yet) to share publicly, but it does exactly what I set out to do.

The GA part is like 10% of the code and was trivial to implement, as all GA algs likely are. Path crossover (mating) is a very interesting topic, sadly there doesn't seem to be a lot of broadly applicable references that I found. Designing factorio related heuristics for evolving was very fun, and I guess you could call that the GA part, but it involves a blending of both GA and knowledge of factorio.

Mapping factorio is very time consuming, but worse, the more you do it, the more compute intensive GA becomes and your reward versus effort decreases significantly.

Better I found was try to come up with ways to summarize the simulation into broader phases of activities in order to minimize the permutations that GA would have to randomly evolve through. This reduces total compute resources required to find global minimas.

One interesting learning event was that blending in "asexual reproduction" with appropriate mutations was a very effective way to find more optimal fitness. Ie, don't mate, just randomly tweak the single parent. That could be because my crossover approach was sub optimal. Not sure the best approach there.

Another one, was that when you look at speedrun.com and factorio, they are behaving exactly like a human driven genetic algorithm. I'll leave that one as homework as this is all getting rather off topic to factorio itself.