bugFreeciv - Bugs: bug #19311, Did not find a cm solution in...

 
 
Show feedback again

bug #19311: Did not find a cm solution in 25000 iterations

Submitted by:  Michal Mazurek <akfaew>
Submitted on:  Fri 20 Jan 2012 06:26:27 PM UTC  
Votes:  90  
 
Category: NoneSeverity: 3 - Normal
Priority: 5 - NormalStatus: None
Assigned to: NoneOpen/Closed: Open
Release: Operating System: None
Planned Release: 

Add a New Comment (Rich MarkupRich Markup):
   

You are not logged in

Please log in, so followups can be emailed to you.

 

Sat 11 Jan 2014 05:07:11 PM UTC, comment #3:

In Longturn (or at least LT32), all cities have radius 4 or thereabouts (init_city_radius_sq = 15), and they frequently run into this.

Maybe implementing some of Benoît Hudson's hints would help here.

Is there a good way to test the CMA is still sane before/after, other than lots of playtesting? Can't use autogames.

Jacob Nevins <jtn>
Project Administrator
Tue 27 Mar 2012 08:44:20 PM UTC, comment #2:

Benoît Hudson just posted some hints on freeciv-dev:

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.

Jacob Nevins <jtn>
Project Administrator
Sat 21 Jan 2012 05:45:11 PM UTC, comment #1:

What I wrote in the 2.3.1 release notes about this message (hopefully true):

"Limit the maximum amount of calculation the citizen governor will do for a city. This could cause the server to spend many minutes between turns, particularly with large city radii, for instance when auto-arranging citizens after city growth. This is only a partial solution; in this situation, the governor will not make an optimal decision."

I think this has become apparent with the larger city radii in 2.3.x. Originally the number of loops was limited to 10000 (bug #17255); then upped to 25000 (bug #17604); then backported to S2_3 (bug #18407).

But bailing out after a maximum number of iterations is a bit of a bodge, so I've been meaning to raise a ticket for investigating it properly. It would be nice if the computational complexity of whatever it's doing could be reduced to produce a solution without eating lots of CPU. I haven't looked into the algorithm at all, but there were hints in the other tickets of it perhaps getting stuck in a loop when there is insufficient food? (Unless I've misread it.)

Jacob Nevins <jtn>
Project Administrator
Fri 20 Jan 2012 06:26:27 PM UTC, original submission:

Looking at the console of LTeX I found this:

1: Did not find a cm solution in 25000 iterations for Mastiff.
1: last message repeated 2 times

Is it bad? What can I do to help fix this?

Michal Mazurek <akfaew>

 

(Note: upload size limit is set to 1024 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by rogier
  • -unavailable- added by jtn (Posted a comment)
  • -unavailable- added by akfaew (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 90 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follows 1 latest change.

    Date Changed By Updated Field Previous Value => Replaced By
    Sun 19 Oct 2014 07:59:35 PM UTCrogierCarbon-Copy-=>Added rogier
    Show feedback again

    Back to the top


    Powered by Savane 3.1-cleanup