Hi all! I just noticed this closed-a-year-ago bug after looking at the 2.3.0 NEWS.
I wrote the CM code several lifetimes ago, but it appears to mostly be the same still. Since freeciv is starting to push bigger cities, the CM code will be a bottleneck. tl;dr version: fix the damn ruleset or it'll never work for truly big cities. If not, then change the algorithm up in one function near the bottom of the file. There's probably GPL code to do the heavy lifting so this is only a moderate-sized project (~20 hours). Add another 20ish if no LP solver works for us. There's zero chance I can contribute the code, but I can happily advise. Gory details version: Basically the way the CM works is that it places workers one by one, using a heuristic to figure out what the "best" worker is to add next, then evaluates the solution. Then it switches out the last worker it added, etc, until it's checked all possibilities. When it's partway through placing its workers it checks what the best possible result is of finishing out the worker assignment, and backs off if that assignment doesn't work (e.g. doesn't produce enough goods) or isn't as good as the best solution so far. So, by and large, it mostly makes sense to cut off the search after some number of solutions have been looked at. Normally, the algorithm will have looked at the best solution first and then only worse solutions after. The main problem is with happiness: the heuristic is pretty naive about how to make a city content or happy. So for example you can demand the solution be happy, requiring lots of entertainers -- but the code will first iterate through all the mines and grasslands rather than look at entertainers. In a big city it could easily fail to find the right solution. Making the heuristic be smarter about happiness would improve performance a lot in most cases. The main thing to do is prune out solutions that can't possibly work due to the city happiness / content not being satisfied. There's a function to estimate how well we can do from a given partial solution with a FIXME comment about this. I couldn't figure out a good way to translate an estimate of luxury + trade into an estimate of the happy/content state. It depends on the ruleset and various other details that I didn't want (or was too lazy) to pull into the core of the CM. I suspect on large cities without much excess luxuries, this criterion is what's killing us: the best-looking solution is to make lots of food and goods, but the correct solution is to have several entertainers. Another thing to do that would help a lot is to make the heuristic work off linear programming rather than the max-stat heuristic currently used. At the moment, given 4 remaining workers, the code assigns 4 to the fields and sees how much food they could generate; then assigns 4 to the mines and sees how much goods they generate, then assigns 4 to be taxmen, etc, and combines the best of each single-minded assignment. This is a huge overestimate. An LP solution would assign say 3.5 to the fields, 0.4 to the mines, and 0.1 to be taxmen. Still an overestimate, but much tighter. Then we could much more effectively realize that this solution isn't as good as the best, or isn't even as good as required. Even better for performance would be to change the rules: make that assignment of 3.5 to the fields, 0.4 to the mines and 0.1 to taxes actually be legal. That changes the asymptotics from exponential time to polynomial time. I'm sure there's reasonable GPL solvers for linear programming. The only issue is that we have small problems that we run often, and dedicated LP codes tend to be optimized for solving a few big problems so they have a lot of overhead setting up the problem. The simplex method is relatively simple and extremely well explained all over the place so we could implement a small version quickly if we needed to. -- Benoît PS: I filter freeciv-dev aggressively, so I will only be reading this thread. Last time I got involved in freeciv it nearly got me kicked out of grad school :) Though the experience set me up for a very fast ramp-up when I got a real software development job. _______________________________________________ Freeciv-dev mailing list [email protected] https://mail.gna.org/listinfo/freeciv-dev
