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

["Benoit Hudson" <bh@xxxxxxxxxxxxxxxxxxx>]

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

> [bhudson - Thu Sep 23 22:32:39 2004]:
> By the way, somewhat sparked by this, I implemented a branch & bound
> algorithm.  It's quite a bit faster on small cities, although I think
> I can make the current CM get those advantages too.  It's slower on
> large cities to get the optimal answer.  But, if we just choose the first
>  feasible answer, we get almost the algorithm you just outlined.

Here's the branch-and-bound algorithm all coded up.  This gives identically
good solutions to the dynamic programming CM code we had -- at least,
it does in an 8-AI game to 500 AD and another 8-AI game (different random 
seeds) to past 800 AD when it died of a punit->transported_by assertion.  By
identically good, I mean that it doesn't have the tie-breaker that the old CM 
code had, and it can't without limiting the pruning I can do, so the solutions
have the same fitness but may be different.

Only it does so with 1/3 fewer evaluations of solutions (generic_city_refresh,
or a cache hit).  This makes it about 10% faster than the current CM.  And,
it has support for Jason's pet project of specialists that produce food or
whatever: specialist positions are just "tiles" of which there happen to be an 
infinite number available.

The code has one function where it makes all sorts of assumptions to be able 
to prune effectively.  This is what got me thinking about #10290.  Apart from
that, there is little required of the ruleset except for 1 position takes 1 
worker,
and more is better.

Last pro to consider: it would be easy with this code to go down one branch
and take it as our solution.  For an example, look in init_bb_state where I do
just that (building up a food-optimal solution).

To build warning-free requires #10294.

cm_branch_bound.diff
Description: Binary data