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

["Benoit Hudson" <bh@xxxxxxxxxxxxxxxxxxx>]

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

        -- Benoît