Complete.Org: Mailing Lists: Archives: freeciv-ai: November 2004: [freeciv-ai] Re: (PR#10203) Greedy CM algorithm

[freeciv-ai] Re: (PR#10203) Greedy CM algorithm

[Top] [All Lists]

 To: per@xxxxxxxxxxx Subject: [freeciv-ai] Re: (PR#10203) Greedy CM algorithm From: "Benoit Hudson" Date: Thu, 18 Nov 2004 16:48:21 -0800 Reply-to: rt@xxxxxxxxxxx

```<URL: http://rt.freeciv.org/Ticket/Display.html?id=10203 >

On Thu, Nov 18, 2004 at 12:49:53PM -0800, Jason Short wrote:
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=10203 >
> I would like to try getting a truly huge city to see if the CM is even
> feasible.  This is an NP-complete or NP-hard problem, right?  With a map

I think it's NP-hard; I have no proof.  It is close to an assignment
problem, which is easy, but it's not exactly an assignment problem.

Things we can do to speed up the CM:

- A* rather than branch-and-bound.  This requires more space --
potentially lots more.  May or may not help.

- a better lower bound on the requirements vector.  Currently, we
get most of the pruning from knowing how much food we need; solutions
that can't produce enough food get pruned very early.  This is
essentially what makes the BB approach faster than the DP approach in
the default ruleset.  A lower bound on luxuries would also help quite
a bit on medium and large cities, but as discussed previously, this is
more complicated, so I haven't implemented it.

- a better upper bound on the quality of a solution.  I have no good
ideas here.  The current upper bound is that the most food you can
produce is what you'd get from taking all the best food tiles; the
most shields is what you'd get from taking all the best shields
tiles, etc.  Surely we can do better?

- use the current city setup, if it's valid, as an initial solution.
I doubt this would be a major help, because of the previous point.
Currently, pretty much every solution comes up as being potentially
better than the best known: if you have one idle worker, then a real
solution can only get either 2 gold OR 2 science, whereas the upper
bound says it can get 2 gold AND 2 science.

- faster generic_city_refresh equivalent.  It currently spends more than
half its time summing up the production from tiles, and half the
remainder figuring out the bonuses.  But the former is already known
by the CM, and the latter is fixed within a CM invocation.

- being smarter about not calling the CM.  The CM appears to get called:
1. for every changed city tile in auto_arrange_workers (multiple
times, if any invocation fails), for every changed city.
2. every time you click on a city (to get that city's dialog)
3. every time you change tab in the city's dialog
4. every time you buy a building

Least palatable:
- use an approximation: choose the first feasible solution, for example.
Or, time out after 1 second and take the best so far.

```