5 ms·

Learning Solver Design: Automating Factorio Balancers

266 points by kolui 2y ago

bombcar 2y ago
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-z1g8ttd4AaABAg 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).”
- Xinti 2y ago
  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.
piebro 2y ago
https://github.com/R-O-C-K-E-T/Factorio-SAT https://github.com/R-O-C-K-E-T/Factorio-SAT is another codebase trying to tackle the same problem
- progbits 2y ago
  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 2y ago
    The 4x4 with a 90 degree turn is a thing of beauty.
Epa095 2y ago
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 2y ago
  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 2y ago
    > 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 2y ago
      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.
      - deleted 2y ago
DannyBee 2y ago
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 2y ago
  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.
jpcookie 2y ago
[flagged]
- fxwin 2y ago
  Eh, i can think of worse ones. Quite a lot of those actually
  - jpcookie 2y ago
    It's "optimizing things to prove you are smrt" (yes that was deliberate). Playing a complicated game only proves you are wasting your time. For half that effort you can learn something helpful
    - fxwin 2y ago
      calling factorio the worst videogame implies you think there are good games out there to play - which ones would that be? (And why wouldn't those also be a waste of time?)
- endigma 2y ago
  Don’t click into posts just to comment empty ragebait dude, actually grim if this is your passtime
- DonHopkins 2y ago
  Obviously this dude's never played ET on the Atari 2600! https://www.youtube.com/watch?v=WUsQmYRfynw https://www.youtube.com/watch?v=WUsQmYRfynw
  - lupusreal 2y ago
    It's no Berzerk, but ET isn't really so bad as people meme it.
YeGoblynQueenne 2y ago
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 2y ago
  Ruby Storm player spotted? :)
  - YeGoblynQueenne 2y ago
    Hah! Nah, this is an M:tG Arena deck for Historic. Besides I'm too rogue for Ruby Storm :)
- ProjectArcturis 2y ago
  Is there anything like an open source Magic emulator for optimization or ML purposes?
  - YeGoblynQueenne 2y ago
    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 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 2y ago
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.
- maverwa 2y ago
  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 2y ago
    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/main/balancer.py#L440 https://github.com/gianluca-venturini/factorio-tools/blob/ma...
    - swyx 2y ago
      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 2y ago
  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 2y ago
That's pretty cool, but balancers are cope for anything other than loading trains from ore patches.
- mfro 2y ago
  I can see them coming in handy for large production lines and main bus inputs.
  - lupusreal 2y ago
    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 2y ago
      > 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 2y ago
        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.
ge0ffrey 2y ago
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/d9e83463f0d620eba5ab6610495170d397390788#diff-e501d06aa51ffa2824bb54c515c2f4103fc8210334cd828d9291c5140ca607a5 https://github.com/TimefoldAI/timefold-quickstarts/commit/d9...
samsquire 2y ago
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 2y ago
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 2y ago
  >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 2y ago
    ok, it seems I need to play this game, just have to convince the bosses.
- sulam 2y ago
  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 2y ago
    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 2y ago
      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.

266 points by kolui 2y ago

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-z1g8ttd4AaABAg 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).”

Xinti 2y ago
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.

piebro 2y ago

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

progbits 2y ago
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 2y ago
  The 4x4 with a 90 degree turn is a thing of beauty.

Epa095 2y ago

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 2y ago
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 2y ago
  > 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 2y ago
    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.
    - deleted 2y ago

DannyBee 2y ago

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 2y ago
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.

jpcookie 2y ago

[flagged]

fxwin 2y ago
Eh, i can think of worse ones. Quite a lot of those actually
- jpcookie 2y ago
  It's "optimizing things to prove you are smrt" (yes that was deliberate). Playing a complicated game only proves you are wasting your time. For half that effort you can learn something helpful
  - fxwin 2y ago
    calling factorio the worst videogame implies you think there are good games out there to play - which ones would that be? (And why wouldn't those also be a waste of time?)
endigma 2y ago
Don’t click into posts just to comment empty ragebait dude, actually grim if this is your passtime
DonHopkins 2y ago
Obviously this dude's never played ET on the Atari 2600! https://www.youtube.com/watch?v=WUsQmYRfynw https://www.youtube.com/watch?v=WUsQmYRfynw
- lupusreal 2y ago
  It's no Berzerk, but ET isn't really so bad as people meme it.

YeGoblynQueenne 2y ago

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 2y ago
Ruby Storm player spotted? :)
- YeGoblynQueenne 2y ago
  Hah! Nah, this is an M:tG Arena deck for Historic. Besides I'm too rogue for Ruby Storm :)
ProjectArcturis 2y ago
Is there anything like an open source Magic emulator for optimization or ML purposes?
- YeGoblynQueenne 2y ago
  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 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 2y ago

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.

maverwa 2y ago
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 2y ago
  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/main/balancer.py#L440 https://github.com/gianluca-venturini/factorio-tools/blob/ma...
  - swyx 2y ago
    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 2y ago
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 2y ago

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

mfro 2y ago
I can see them coming in handy for large production lines and main bus inputs.
- lupusreal 2y ago
  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 2y ago
    > 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 2y ago
      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.

ge0ffrey 2y ago

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/d9e83463f0d620eba5ab6610495170d397390788#diff-e501d06aa51ffa2824bb54c515c2f4103fc8210334cd828d9291c5140ca607a5 https://github.com/TimefoldAI/timefold-quickstarts/commit/d9...

samsquire 2y ago

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 2y ago

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 2y ago
>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 2y ago
  ok, it seems I need to play this game, just have to convince the bosses.
sulam 2y ago
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 2y ago
  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 2y ago
    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.