Follow-up Comment #2, bug #19311 (project freeciv):

Benoît Hudson just posted some hints on freeciv-dev
<https://mail.gna.org/public/freeciv-dev/2012-03/msg00229.html>:

I just noticed this closed-a-year-ago bug _[bug #17604]_ 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
_[not this gna ticket -- JN]_.  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.

    _______________________________________________________

Reply to this item at:

  <http://gna.org/bugs/?19311>

_______________________________________________
  Message sent via/by Gna!
  http://gna.org/


_______________________________________________
Freeciv-dev mailing list
Freeciv-dev@gna.org
https://mail.gna.org/listinfo/freeciv-dev

Reply via email to