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

["ue80@xxxxxxxxxxxxxxxxxxxxx" <ue80@xxxxxxxxxxxxxxxxxxxxx>]

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

On Thu, Nov 18, 2004 at 08:57:16PM -0800, Benoit Hudson wrote:
> 
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=10203 >
> 
> On Thu, Nov 18, 2004 at 06:07:30PM -0800, Jason Short wrote:
> > 
> > <URL: http://rt.freeciv.org/Ticket/Display.html?id=10203 >
> > 
> > On large cities the B&B algorithm performs much worse than the DP algorithm.
> > 
> > I'm only talking about the client here.
> > 
> > For instance in the game at 
> > http://rt.freeciv.org/Ticket/Attachment/75375/51725/jason-game.sav.gz 
> > (which is actually a real game of mine, unlike all the made-up games 
> > I've been testing with) the DP algorithm takes 0.1 seconds to 
> > recalculate Boston while the B&B algo takes 0.8 seconds.  Not good!
> 
> Really?  I'm surprised, because usually large cities have stringent
> demands on food, which means the vast majority of solutions the DP
> algorithm dreams up are pruned out.
> 
> By the way, what's the CMA settings?  The gui (gtk2) isn't very good
> about custom CMA settings: when I switch to the CMA tab, it decides to
> apply the first setting in my list.  Which makes it harder to debug.
> 
> > One possible reason why the DP algo is faster is because it uses 
> > caching.  Because the client calls CM so much more often than is needed 
> > cache hits are more likely I would think.
> 
> Cache hits are more likely, but that doesn't explain the dependence on
> city size.  What might explain half of it -- and this is a guess, is
> that under the B&B code, half the CM time is spent iterating over the
> tiles and doing base_city_get_food_tile and so on.  As the city grows,
> that fraction would grow since it's doing it on more tiles whereas the
> other work in generic_city_refresh will be equal.  The DP doesn't pay
> for this thanks to the cache.  
> 
> For small cities, the ratio of work per generic_city_refresh of DP / BB 
> is about 1 / 2.  We end up with BB being slightly faster because it does
> a lot less (about half as many) generic_city_refresh.
> 
> For large cities, the ratio would be more like 1 / 5.  This means the DP
> should be faster by a factor of two if they have the same ratio of
> generic_city_refresh calls.
> 
> So I've explained why BB should be expected to take .2 or .3 seconds.

I have not looked into the code so i don't know if my following
suggestion is allready implemented.

What is about first group all tiles into the possible gains for the
city.

2/2/1  4 times
2/1/2  2 times
1/0/0  4 times

And doing the algorithm afterwards. 
For a size 5 city it's possible to remove the 4 times 1/0/0 because
there is no optimal solution with it  because all other tiles are
better.

And i have to think if:

max f_1 * a1 * t1_1 + f_2 * a1 * t1_1 ... 
where sum a1 ... an <= citysize
a1 * t1_1 ... an* tn_1 >= needed food 
... prod
... lux

with f_1 .. f_n weights for CM
      a1 .. an  number of fields in citymap
      tx_1 .. tx_n gain for food,prod,lux 

is a NP problem ... but i don't think so.

Thomas
-- 
Thomas Strub  ***  eMail ue80@xxxxxxxxxxxxxxxxxxxxx
jb: people are stupid, they don't want to learn.