Michal Mazurek | 20 Jan 19:26 2012

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


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

                 Summary: Did not find a cm solution in 25000 iterations
                 Project: Freeciv
            Submitted by: akfaew
            Submitted on: Fri Jan 20 18:26:27 2012
                Category: None
                Severity: 3 - Normal
                Priority: 5 - Normal
                  Status: None
             Assigned to: None
        Originator Email: 
             Open/Closed: Open
                 Release: 
         Discussion Lock: Any
        Operating System: None
         Planned Release: 

    _______________________________________________________

Details:

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?
(Continue reading)

Jacob Nevins | 21 Jan 18:45 2012

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


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

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.)

    _______________________________________________________

Reply to this item at:

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

_______________________________________________
(Continue reading)

Jacob Nevins | 27 Mar 22:44 2012

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

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
(Continue reading)

Jacob Nevins | 11 Jan 18:07 2014

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

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

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.

    _______________________________________________________

Reply to this item at:

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

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

_______________________________________________
Freeciv-dev mailing list
Freeciv-dev <at> gna.org
https://mail.gna.org/listinfo/freeciv-dev

Gmane