15 ms·
Enhancing Factorio with SAT solvers
- Lichtso 3y agoCool project! Wish we would see more applications of SAT solvers or logic programming in general.
- JonChesterfield 3y agoSAT solvers are magic. CSP solvers are the same magic with a much friendlier interface. Got a discrete NP hard problem? A CSP solver will probably get that done.
- Chirono 3y agoFor anyone wondering what this does, it looks like it produces optimal configurations for belt balancers given a specified number of input and output belts. Belt balancers evenly distribute items between belts: https://wiki.factorio.com/Balancer_mechanics https://wiki.factorio.com/Balancer_mechanics
- perihelions 3y agoFun to see that that math (linked in that wiki) coincides with early 20th-century analog telephony problems—the problem of how to arrange electromechanical switches to support large numbers of simultaneous circuits, avoiding bottlenecks. There's people reading Bell Labs technical papers from the 1950's as part of the process of playing an addictive video game.
- TeMPOraL 3y ago> There's people reading Bell Labs technical papers from the 1950's as part of the process of playing an addictive video game. It's a nice break from reading orbital mechanics textbooks as part of the process of playing another addictive video game.
- perihelions 3y agoOrigin of my HN name! :)
- beacon294 3y agoWhat games?
- skirmish 3y agoI personally bought this real world fighter plane tactics book for playing military flight sims: https://www.amazon.com/dp/0870210599 https://www.amazon.com/dp/0870210599 .
- kzrdude 3y agoEven the 90 degree turn 4x4 balancer is new to me, nice to see.
- francoisdevlin 3y agoDude, that is sick.
- r2_pilot 3y agoI didn't see that (I've been using these for a while now, they're especially helpful with my K2+SE run) so I'll have to check into that some more.
- patio11 3y agoThat’s going straight into my blueprint book; solves a problem I have at almost every mining train station much more elegantly than the standard linear 4x4 does.
- less_less 3y agoThe 90 degree turn 4x4 balancer is even better if your inputs and/or outputs are on opposite sides, making a T-shape. This is pretty common depending on the position of the balancer. In that case it fits into a 4x6 rectangle.
- jvanderbot 3y agoThis is my favorite pastime as well! Well done. I've also dipped my toes in the "over engineer a game" with: A highfleet ship optimizer which chooses optimal module sets using ILP at https://hfopt.jodavaho.io https://hfopt.jodavaho.io (try desktop site on mobile) And a hunt showdown loadout A/B test package that lets you run stats queries on your game journal at (for now) https://crates.io/crates/kda-tools https://crates.io/crates/kda-tools
- sapiogram 3y agoCan this also generate "universal" balancers? I've found them more useful in practice: https://wiki.factorio.com/Balancer_mechanics#Universal_balancers https://wiki.factorio.com/Balancer_mechanics#Universal_balan...
- klysm 3y agoI don't see why that couldn't be added as constraints
- Yesway 3y agoYou can combine narrow balancers to make wider balancers. That way it is possible to save space, energy, latency .... same as is done in modern CPU / GPUs... And funny enough, ultimate Factorio tool is tool to make great cpus... ;) I like your, what i presume is, "joke" animation at the end…
- Yesway 3y agowhole system look can provide some unexpected "optimizations" too. is balancing really even needed in/as a solution... in cases when synchronization is not necessary you can simplify system greatly just by oversaturating belts with inputs. output machinery cadence dictates whole feeding mechanism rate.
- ivanjermakov 3y agoWhat is the math name for the problem of belt balancing? The one that SAT solvers solve. Perhaps Beneš network?
- r2_pilot 3y agoIt's the Boolean satisfiability problem : https://en.m.wikipedia.org/wiki/Boolean_satisfiability_problem https://en.m.wikipedia.org/wiki/Boolean_satisfiability_probl...
- deleted 3y ago[deleted]
- dragontamer 3y agoBenes network is a simple recursive pattern for power-of-2. So a 4-to-4, 8-to-8, and 16-to-16 perfect balancer can be calculated out by hand using Benes networks. This allegedly creates odd-numbers like 7-to-7 balancers. But in my experience, i just grab a 8-to-8 balancer from my blueprints and ignore 1 input/output.
- reaperman 3y agoClos networks is what I studied for factorio belt balancing.
- snapcaster 3y agoThis is super cool! Will never not upvote a post about factorio. If anyone is reading this and into programming you should try the game, it's incredible source: 3000 hours+ on the game :)
- zeroonetwothree 3y agoTo me it feels like programming with an awkward IDE.
- elbear 3y agoSo ... not enjoyable? I have yet to try it, but I was thinking of giving it a shot after reading so many positive comments.
- falcolas 3y agoIMO, it's more like circuit design than programming. Similar mindset, slightly different method of solving issues. And personally, if you're a fan of puzzles and optimization, I think you'll love it. There's an amazing amount of gameplay for the price. Worst case, you're out $35 and supporting an amazing developer.
- jl6 3y agoYou can play it in many different ways. One advanced playstyle is to use combinators heavily, but you don't need to. A lot of people get hooked on optimizing their factories, which leads down a rabbit hole of ratio calculation, but that's also not required. It's perfectly enjoyable without doing anything extremely technical.
- rgoulter 3y agoI'd say "feels like programming" applies to even a vanilla playstyle. Broadly, the game is about building up systems. Even in a disorganised first playthrough, you'll naturally find 'systems' for solving things. (They'll just be hard to change, and hard to scale up, and hard to build upon). Which is somewhat similar to how a someone who just learned to program might be able to complete a task, but probably in a way a more experienced dev wouldn't.
- zero_k 3y agoThis is cool :) My only small gripe is that python-sat (i.e. pysat) is nice, but it kinda hides all the work that SAT solver writers (like me... :D) do. It gives a nice interface to access them all, but it also means that e.g. if something doesn't work, the user may not know who to contact as they may not be aware which SAT solver they are using. I guess it's the rule of something becoming so mainstream that the authors of the underlying technology fade away, and those doing the (actually really hard work!) of maintaining the common API are referenced only. I have seen publications/work where the SAT solver was credited only as pysat, which is not a SAT solver :) Kinda cool and sad at the same time!
- natpalmer1776 3y agoIn a way, you and every other author who created a SAT solver being used by pysat ARE pysat! :) Another way to look at it is that you are the "giant" in the famous quote "If I have seen further than others, it is by standing on the shoulders of giants"
- klysm 3y agoAnd that's exactly the power of SAT right? It's a universal way of expressing a large set of problems.
- everforward 3y agoIn the same sense that SQL is a universal way of expressing a large set of problems. I.e. all the implementations speak the same language, but they operate and prioritize differently. SAT solvers are NP-Hard, so there isn't a single SAT solver to rule them all. Which one you choose matters, same as with databases. CockroachDB, PostgreSQL and SQLite all speak SQL, but are not interchangeable. Same with SAT solvers. I'd agree with OP; the SAT writers should get more credit. It's a hard problem, and I'd bet most of us are either incapable or unwilling to spend ages working on it (myself included, no shade intended). It's also vitally important. To my understanding, SAT solvers underly most package managers. It's how npm or pip or apt know what version to install for each package such that no version violates another packages constraints (if any, it's also where the "no valid version combinations exist" message comes from).
- bloopernova 3y agoInteresting! My standard play style in Factorio is to use rail squares and 12-lanes inside those squares. I use 12 because 2 warehouses from the warehouse mod are 12 squares wide. All my blueprints are based on that, along with all the Angels+Bobs mods it makes for a fun-to-me playthrough. All my blueprints are based on 12 buildings, and it's neat because many of the modded buildings are 3, 5, or 7 squares wide so I have 3 standard sizes of lane direction changes, inputs, outputs, etc. In my current playthrough I'm up to almost 1,000 stations :D I would like to see if this can create a 12 to 12 universal+lane+throughput-unlimited balancer. Plus I've been wanting a 12 to 24, 12 to 36, and 12 to 48 lane balancer too because I'm a masochist :)
- terrelln 3y agoI've recently started playing Factorio for the first time, and was thinking about using SAT solvers for automated sub-factory blueprint design with beacons. E.g. for a given recipe how do I design a sub-factory that builds the recipe with the minimum number of entities (or a given total entity weight, to allow for weighting buildings based on their impact on UPS). I've seen a paper [0] on a similar problem, but it doesn't take beacons into account. It seems like beacons make the problem significantly harder, because now positioning matters in order to share beacons. Does anyone have any ideas on how to approach this? [0] https://arxiv.org/pdf/2310.01505.pdf https://arxiv.org/pdf/2310.01505.pdf
- thenipper 3y agoI definitely knew people in the Wayfair logistics org that used the same kind of algos that we used at work with their Factorio games...
- dexwiz 3y agoBalancers are probably one of the most common but least understood parts of Factorio. Most players copy a blueprint book from the web, and don’t think about it. They are very tricky to build by hand without a deep understanding of belt mechanics and high attention to detail. Also without testing it’s easy to build one that looks correct but fails under certain conditions. Same lane balancers and powers of two aren’t bad, but anything else usually requires loop backs so the network becomes cyclic. Also every belt in Factorio is two independent lanes. Splitters will move items between belts but always preserve lanes. A 4-2 splitter should compress 4 left-only lanes across 4 belts to 2 belts of 2 left and 2 right lanes. The naive splitter setup wont do that.
- declan_roberts 3y agoAs someone who’s never played factorial it sounds incredibly boring and tedious from the outside.
- fnordpiglet 3y agoIt’s built for engineers that are nerds at heart and love building because they love building. There are certainly engineers that love making engineer money, and there’s nothing wrong with that. But what one finds boring and tedious another may find pleasure in. I would say given how loved factorio is a reasonable position is to assume they’re not all entire idiots that can’t distinguish between fun and tedium and give it a try!
- moomin 3y agoFactorio, Satisfactory and Oxygen Not Included (very different games) all have this thing of building something while it's running, debugging and expanding it, and give you fairly meaningful rewards in terms of new challenges and removing tedium. To compare: * Satisfactory: the lowest stress, best guided, the prettiest and the easiest to analyse. A lot of the challenge involves figuring out how to best use 3D space. 1.0 is coming this year. * Factorio: Biters provide a base level of threat making your factory breaking a potential problem. But you can switch it off. Much more complex tech tree and routing. But building railways is pretty tedious compared to Satisfactory (which is a pity when they're essential.) * Oxygen Not Included: Everything you try to do has side effects. The game physics matters _a lot_. Mess up and everything dies. Easily the most stressful of the three. Has the shallowest tech tree of the lot, too. All are good, although I cannot recommend Oxygen Not Included if you want to relax while playing.
- yogurtboy 3y agoThis is really cool! Is there a page that has a list of useful concepts like this that might not be explicitly mentioned in the game itself? I don't have that much fun trolling the forums.
- Sohcahtoa82 3y agoIs belt balancing really that important in Factorio? I've played Factorio, but only launched the rocket once and I think have about 100 hours in it. I never bothered with belt balancing, and simply had many rows of belts traveling east, with splitters moving things to columns of assemblers which then go to another belt to the east. As I expanded the factory to build new products, I'd play whack-a-mole with fixing bottle necks in materials. Heck, I never even used trains or any sort of drone. Have I just never built a factory big enough to need balancing? What does it really accomplish versus just overproducing source materials and allowing the factory to back up a little?
- ynik 3y agoBelt balancing is necessary when unloading trains, as otherwise uneven consumption can lead to some chests/wagons running out of resources but the train doesn't leave because other wagons are still full. For mining outputs, it can also be nice to avoid the outpost getting slow/stuck (never able to fill a train) when ore runs out for the outer lanes of miners. Anywhere else, balancers are unnecessary and just serve to obfuscate a lack of resources. (But if you really want to play without any balancers at all, that's quite possible: the train problems can also be solved by letting trains leave on a schedule independent of cargo status. All remaining balancers, including those on mining outposts, can be replaced with priority splitters.)
- a1369209993 3y ago> Belt balancing is necessary when unloading trains, as otherwise uneven consumption can lead to some chests/wagons running out of resources Not in general, actually. If you standardize on N-wagon trains, and build assemblers (et al) in groups of N, each assembler can take inputs from one wagon in lockstep with N-1 other assemblers taking from the N-1 other wagons, and since productivity is deterministic[0], they'll also produce outputs in lockstep. This means that as long as all your input trains are balanced (they should be, by being completely full), all your output trains will also be balanced. Science labs are same as any other machine, just without output, and trains feeding a logistics network can unload into active provider chests. In practice I pretty much only use balancers for a: mining outposts, or b: random kludges, at least when and if I'm using trains as my main transport mechanism. 0: Ask me about quality once 2.0 drops; for now I just special-case uranium processing.
- j2kun 3y agoI wonder if there are any real-world factory configurations that employ SAT solving techniques.
- ineedasername 3y agoOn Valentines Day? Seriously? This post should be titled “I’m going to ruin Valentine’s Day for every Factorio player here with a non-Factorio partner” I’ll see you all in a month, linking to my own post titled “How Factorio Ruined My Marriage”
- Donaldzibe 3y ago[dead]
- makerdiety 3y agoDoing anything with Turing-complete games like Factorio or Minecraft is never impressive. Because building SAT solvers or, more generally, logic gate nodes for an abstract Turing based computing machine with digital video game items like in-game conveyor belts is only running a simulation on top of a finite substrate that isn't optimized for productive work. And I don't care one bit about people deriving pleasure from leisure like digital entertainment. In contrast, what is impressive amounts to nothing less than discovering a successor to the universal Turing machine. And you can do that with pen and paper instead of fancy technical equipment like a clunky and uncomfortable development environment that's concerned with manipulating virtual conveyor belts as one of its programming primitives.
- jamesrom 3y agoThis is awesome, but balancing belts is usually a fool's errand. It's better to design your base as factories with inputs prioritized with priority splitters.
- fnordpiglet 3y agoIs it a fools errand if a SAT solver can tell you the optimal belt balancer configuration?
- ge0ffrey 3y agoI once optimized Factorio's belts with OptaPlanner (now Timefold.ai), our open source metaheuristics solver in Java. The source code is still here: https://github.com/kiegroup/optaplanner-quickstarts/tree/8.6.x/quarkus-factorio-layout https://github.com/kiegroup/optaplanner-quickstarts/tree/8.6...