[HN Gopher] Learning Solver Design: Automating Factorio Balancers
___________________________________________________________________
Learning Solver Design: Automating Factorio Balancers
Author : kolui
Score : 244 points
Date : 2024-12-27 17:32 UTC (4 days ago)
(HTM) web link (gianlucaventurini.com)
(TXT) w3m dump (gianlucaventurini.com)
| bombcar wrote:
| 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)."
| piebro wrote:
| https://github.com/R-O-C-K-E-T/Factorio-SAT is another codebase
| trying to tackle the same problem
| progbits wrote:
| 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.
| moomin wrote:
| The 4x4 with a 90 degree turn is a thing of beauty.
| Epa095 wrote:
| 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._
| H8crilA wrote:
| 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.
| wtallis wrote:
| > 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.
| eru wrote:
| 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.
| jvanderbot wrote:
| 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_ ).
| nullc wrote:
| 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).
| pclmulqdq wrote:
| 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.
| kolui wrote:
| Thanks for the feedback, I fixed the claims about complexity.
| Let me know if you find other incorrect parts.
| DannyBee wrote:
| 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.
| cedws wrote:
| 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.
| YeGoblynQueenne wrote:
| 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 :)
| qsort wrote:
| Ruby Storm player spotted? :)
| YeGoblynQueenne wrote:
| Hah! Nah, this is an M:tG Arena deck for Historic. Besides
| I'm too rogue for Ruby Storm :)
| ProjectArcturis wrote:
| Is there anything like an open source Magic emulator for
| optimization or ML purposes?
| YeGoblynQueenne wrote:
| 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.
| swyx wrote:
| im a factorio noob so just checking some intuitions
|
| > Example of 4 x 4 naive 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.
| maverwa wrote:
| 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?
| kolui wrote:
| 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...
| swyx wrote:
| 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
| theptip wrote:
| 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.
| lupusreal wrote:
| That's pretty cool, but balancers are cope for anything other
| than loading trains from ore patches.
| mfro wrote:
| I can see them coming in handy for large production lines and
| main bus inputs.
| lupusreal wrote:
| 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.
| sulam wrote:
| > 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.
| lupusreal wrote:
| 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.
| sulam wrote:
| 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.
| jnwatson wrote:
| 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.
| sulam wrote:
| 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.
| lupusreal wrote:
| 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.
| sulam wrote:
| 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.
| ge0ffrey wrote:
| 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...
| samsquire wrote:
| 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.
| bobim wrote:
| 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.
| tux3 wrote:
| >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.
| bobim wrote:
| ok, it seems I need to play this game, just have to convince
| the bosses.
| sulam wrote:
| 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.
| bobim wrote:
| 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.
| sulam wrote:
| 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.
___________________________________________________________________
(page generated 2024-12-31 23:01 UTC)