Learning Solver Design: Automating Factorio Balancers | Hacker News Reader

Learning Solver Design: Automating Factorio Balancers

gianlucaventurini.com

266 pointskolui50 comments

SAT solvers have also been thrown at the Factorio belt weaving problem (which has in-game reasons to maximize).

https://youtube.com/watch?v=2NKK_2v4jiE&lc=Ugx5goGzTGz-z1g8t...

Search:

“ @Jodmangel 2 weeks ago I wrote a quick script to find the longest belt weave with an SAT solver. It finds your 32-tile bridge, but also a 34-tile one:

The circles are the "external" belts and the squares the 34 "internal" ones. No longer solutions exist (unless I messed up the script, obviously).”

Solve it with an SAT solver, or solve it with a random heuristic—either way, you’re dealing with a trivial belt-laying puzzle that any standard constraint tool can handle. The fact that you found a 34-lane weave is neat, but it’s basically a re-skin of solving simple combinatorial constraints. Sure, it proves Factorio can be used for demonstrations of off-the-shelf solvers, but it hardly reflects a ‘deep’ puzzle worthy of computational bragging rights. The real irony is that these same SAT-based methods can also optimize bin-packing, scheduling, or any other standard NP problem with more interesting constraints. Factorio’s belt weaving doesn’t add enough genuine complexity to stand out—it’s basically the same problem in a different costume.

This is a cool article! And it lead me down the path to another cool factorio compsci paper called 'The steady-states of splitter networks' where they really go into the theoretical properties of the belts and splitters.

But I can't help to feel that the following paragraph should be removed, since it really seems to be a bit confused about the concepts of both Np-complete and NP-hard.

> Finding a feasible solution is NP-hard because we can't do any better than start placing the components on a 2D grid and check if the properties are respected. Furthermore, finding the optimal solution (i.e., minimum number of components) is NP-complete because it will require enumerating all the possible solutions in order to find the best one.

It's a classic undergraduate student mistake when learning computational complexity: "this problem is really hard, but I can represent it as SAT - well, it is NP-hard!". Whereas what you need is to represent SAT as an instance of your problem! Otherwise computing XOR of two bits would be NP-hard, as I can write a SAT formula to express it.

> we can't do any better than start placing the components on a 2D grid and check if the properties are respected

That specifically seems to be the bit where the explanation goes wrong. Proving that there's no easier method than brute forcing is a hard problem, not something to wave away as an exercise for the reader.

Actually, you can wave it away as an exercise to the reader, you just need to be careful how you formulate it.

Something like 'Frobbing the fnutz might be NP-hard. The proof via reduction of SAT is left as an exercise for the reader.'

Not very reader friendly, but at least you haven't said anything wrong.

For anyone curious (and testing my recall), this should just mean: Solve a SAT problem using fnutz that are Frobbed correctly.

e.g., "Just set up a belt sequence that would solve a 3-SAT problem" to show that belt sequencing is at least as hard as 3-SAT.

(The reverse, setting up a SAT solver to solve belt sequencing only shows that SAT is at least as hard as belt sequencing, which is true for any problem that's not hard hard).

> [...] which is true for any problem that's not hard hard.

Yes, basically true for any problem where you can verify a correct answer in polynomial time (especially if someone gives you extra hints to help your verification).

You can also think of these 'hints' as 'extremely lucky guesses'.

Eg you can verify that a number is composite, and not prime, by 'guessing' its prime factors.

Or you can guess the solution to a Sudoku and then just verify it.

The traveling salesman problem is interesting: it's trivial to verify that any given candidate solution has a specific cost (and that cost can be very low), but it's not trivial to verify that the candidate is minimal. (I'm not even sure it's possible in polynomial time.)

Even when you get the direction correct-- e.g. that you could encode an arbitrary SAT problem as an instance of your problem... that doesn't mean that in practice most instances of your problem can't be solved to an arbitrarily good approximation quickly or even solved optimally in a reasonable amount of time. It only means that in the worst case there is no efficient optimal solution or good approximation.

I've repeatedly encountered people using crappy solutions to problems because they read some result from complexity theory that made them think they couldn't do better. .. when in reality a slightly smarter algorithm does much better on average.

Consider for example the min cover problem: You have a set of bit vectors and you want to find the minimum collection where at least one vector is true for every bit. (e.g. optimizing a collection of tests). There is a simple greedy algorithm-- include the vector that covers the most yet-uncovered bits. There is a proof that this algorithm achieves the best possible worst case approximation error.

But in practice this is a useless result. Worst case approximation error is driven by pathological inputs. It's easy to come up with modifications of the greedy algorithm that significantly improve the quality of the solutions on average (or at least do in the sorts of real problems I've applied it to).

Yes, "NP-complete" is not correct on the author's part and neither is "NP-hard." "NP-hard" is the author's intent since the problem is solvable using a SAT solver but presumably has no polynomial algorithm (so it is harder than P but not as hard as NP), but NP-hardness actually requires the other direction to be true: for a problem to be NP-hard, an oracle for the problem needs to be able to solve everything in NP. NP-complete is a stricter condition that requires NP-hardness but also requires that the problem be in NP.

The author was missing the words "in NP" if they are talking about complexity.

Thanks for the feedback, I fixed the claims about complexity. Let me know if you find other incorrect parts.

I once wrote an open source factory design optimizer with Timefold (previously OptaPlanner). It figured out the best layout to produce a particular item, for example green vials.

We ended up removing it from the default quickstarts [1], but maybe we should reinstate it in timefold-sandbox?

[1] https://github.com/TimefoldAI/timefold-quickstarts/commit/d9...

So I started building a solver for satisfactory for someone. Code is on GitHub if you are bored. It can do similar things, as well as finding optimal recipes and such (like some websites do) but I did it to speed up their app where their current solving of graphical models can be quite slow (20 minutes to solve a model) I've tried a lot of approaches as a result, including going down the same paths.

The balancer issue is different in particular but in my experience, for this kind of problem, using z3 and cvc5 give much faster result than mnilp solvers or cp-sat. On smaller models they are all quite fast. But as it gets larger it's actually much faster for me to binary search an optimal objective through sat with z3 or cvc5 than it is to ask most nlp solvers to optimize it. I haven't tried gurobi or cplex of course.

But I expect this is because of their ability to do really effective incremental solving so that binary searching the objective is very efficient (z3 has an optimizer and soft constraints but they do not advertise it as supporting non linear logic and I can get it to hang on some models)

Especially for this type of problem, I would consider using an SMT solver and seeing how it does

If you stick with Clos networks, a homegrown solver using bdds is probably quite fast and wildly memory efficient.

How did you learn to work with Z3? I dipped my toes in recently having no prior experience. ChatGPT got me started but once the problem got complex enough I was stumped. I also don’t really have any mathematics ability.

This is tickling my curiosity... Anyone knows if Factorio is time-accurate and could be used for production line design/balancing? Is it implementing things like locks on shared resources (e.g. operators), and random stoppages? That would be fun to introduce it in corporate environment.

>things like locks on shared resources (e.g. operators), and random stoppages?

Not natively, but the game gives you a lot of tools. You could probably add some of those things with circuits (the "Factorio redstone"), or with a little more effort writing a mod.

The game is hard deterministic (so that multiplayer works) despite having plenty of multithreaded optimizations. You could probably do something with it. Although that may raise some eyebrows.

ok, it seems I need to play this game, just have to convince the bosses.

It’s very good at modeling real world distributed systems problems and solutions, so it would not surprise me to find applications to production line design. For instance a very basic realization is that the typical throughput/latency tradeoffs have to be made.

That's effectively the question: what is the buffer size needed to insulate two unit operations without introducing penalizing ramp up and ramp down phases. If one could get such answers from Factorio that would be very funny for the 10-20k dedicated software packages.

I think that would be trivial to model in Factorio. Honestly every factory beyond beginner size is dealing with that, not always in a principled way of course.

Personally I find the new DLC with compact design on space platforms to be really fun that way. Back pressure has been a necessary mechanism to create to prevent all sorts of deadlocks for instance.

Nice. I'm lazily hacking on some code to optimise a mana-acceleration engine for a Magic: the Gathering deck. If it works, I'll post something about it :)

Ruby Storm player spotted? :)

Hah! Nah, this is an M:tG Arena deck for Historic. Besides I'm too rogue for Ruby Storm :)

Is there anything like an open source Magic emulator for optimization or ML purposes?

I don't know. I haven't seriously looked for one. There's Forge which seems to be still active but I have no idea whether you can use it like you want:

https://github.com/Card-Forge/forge

You'd need an AI player API, something that lets you hook an AI player into the engine and run it without graphics obviously so you can train fast. Forge has an AI player (or more?) but I don't know if can be used that way.

I guess with a bit of elbow grease you could make a bot to play Arena (and even play against itself), but that may not be acceptable by WotC.

https://github.com/R-O-C-K-E-T/Factorio-SAT is another codebase trying to tackle the same problem

This is the one from which most balancer books are made and if I recall correctly the first one that made SAT work for this problem.

The 4x4 with a 90 degree turn is a thing of beauty.

im a factorio noob so just checking some intuitions

> Example of 4 x 4 naïve Throughput-Limited belt balancer. This is not what we want.

is this because a slowdown on belt #1 doesnt then get filled by belts 3 and 4? so this isn't a properly completely rebalancing system?

> 4 x 4 Throughput-Unlimited belt balancer. This is what we want.

but then this is weird too. the top left tunnel entrance thingy goes down and then immediately up again. why? maybe it tunnels all the way to the top right, in which case it has the same exact flaw as the first throughput limited example that we didnt want - belts 3 and 4 dont get to redistribute their stuff to it if belt 1 dies.

Yeah, the underground belts in the first and fourth row look odd, I currently don’t see a reason why the couldn’t be replaced by simple belts, which would be somewhat cheaper. Maybe that’s an additional UPS optimization applied in that design?

I agree that using underground belts makes harder than it should to understand the example. I replaced it with simple belts. I re-calculated the design with the latest version of the code that has an optimization function that favors normal belts to underground ones https://github.com/gianluca-venturini/factorio-tools/blob/ma...

now my comment looks out of date :)

thanks but also i am very intimidated by how much work you put into this game lol

is this why i am a bad engineer

A mixer can run at the full speed of its input belts (ie given two full belts input, it will output two full belts).

In the naive solution you are effectively allocating a single belt output from each layer-1 mixer, so the system will run at half throughput. But the fan-out to a pair of mixers in layer-3 does mean that your 4 output belts are balanced, which might be good enough in some cases - for example of downstream smelters have lower capacity than the theoretical 4-belt max throughput.

CPUs and railway signalling come to mind.

The low level uops (microops) of a CPU seem to be relevant.

Openttd is another example of a game where you can implement train signalling.

That's pretty cool, but balancers are cope for anything other than loading trains from ore patches.

I can see them coming in handy for large production lines and main bus inputs.

Bus inputs maybe, I usually just put a few splitters before and after tapping off of main bus lines. For large production like circuits I design for some integer multiple of my train length, usually 1x or 2x of four cargo wagons, so I stopped using balancers for that and haven't missed them. The only place I still use belt balancers, except to patch over a design mistake, is loading ore into trains. And for that it's almost always something to four, rarely something to eight. I have a book for all sorts of balancers but almost all of them go unused.

> I usually just put a few splitters before and after tapping off of main bus lines

You are literally describing balancing. You are using an ad hoc solution as opposed to a blueprint, which can be fine, but I wouldn’t dismiss the convenience of being able to belt off a line of variable consumption from your bus and then guarantee each line down the bus will continue to have a fair flow of components. You clearly appreciate that this is desirable, and are solving for it in your own way.

I wouldn't call priority output splitters a form of belt balancing, but I'll accepted there is some conceptual overlap. However:

If you're tapping off the side most lane it doesn't matter what balancer you have at the head of the bus, you have to "balance" it after that point.

Furthermore, if you need real balancers in the middle of your bus to prevent the later stages of the line from being starved, that's a failure to plan for sufficient capacity. Balancers are a convienent way to patch over that mistake, but that's the sort of thing I'm talking about when I say they're cope.

The balancers could literally be part of the plan in your bus. Maybe you branch off a line of iron and two of copper to a green circuit plant that is then coming back onto the bus and being used downstream by both modules and red circuits. You know that for the next few hours those lines will be completely consumed by the number of modules you’ll be creating but after that your red circuit production will be able to go full speed and feed electric engines for robots. Your argument seems to be that you should just have enough lines to do both at full speed. That’s reasonable for the late game, but earlier the needs of your production are variable.

You need them for loading, unloading, and smelting.

Space Age (the most recent DLC) required me to use several 6:4 and 6:3 balancers.

I usually start by hacking it. Once I place a premade balancer, throughout dramatically improves.

Any time you find yourself dismissing something many people put a lot of work into, you should be suspicious that maybe you aren’t operating in the same context they did. For instance a problem some balancers solve (but many do not) is lane balancing, such that each input has an equal chance to show up in either lane of the output. This solves problems with balancing the pull (input) side, as opposed to the push side, and can recruit idle machines that otherwise wouldn’t get work. This in and of itself doesn’t apply to fully utilized production chains but in times of lower utilization it may matter. As another example, maximizing freshness of components is a factor in the latest DLC and this is much easier to do if you can guarantee equal drawing from all assemblers.

Balancers are conceptually cool so I understand the appeal of trying to find aesthetically pleasing, compact or otherwise interesting designs, however I just don't think they have practical use outside of the two niches I listed (loading ores, and fixing mistakes.)

For instance on Gleba, you better have a plan to either use or burn the full belt. It doesn't matter if you're balancing the lanes, you need a plan for the same throughput of spoilage.

Equal consumption of all the miners on an ore patch. The opposite ore loading, unloading at an equal rate so trains spend the minimum at a station (probably the more critical part to balance since you can solve the input side with buffering). Taking multiple less than full lines down to fewer full lines in a way that is evenly distributed, either to conserve space or, in larger bases, UPS. On Fulgora, with uneven recycler load, balancing the flow of an unfiltered belt before you separate it. Those are examples I just pulled from my current play through but I could probably find more.

Reply on news.ycombinator.com