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
Freeciv-dev@gna.org
https://mail.gna.org/listinfo/freeciv-dev
