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

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

ue80@xxxxxxxxxxxxxxxxxxxxx wrote:

> Have you tried it with big cities? (Size about 30-40 tiles, you have to
> increase the cityradius for that)

Now here we have a problem.

Try with the attached patch.  Load the attached savegame with and 
without the branch-bound patch.  Enable logging on the client.

With:

2: CM-opt: overall=1.849262s queries=1 1849.262000ms / query, 1690 applies
2: CM-opt: overall=1.948663s queries=2 974.331500ms / query, 1784 applies
2: CM-opt: overall=24.593312s queries=3 8197.770667ms / query, 26264 applies
2: CM-opt: overall=25.512793s queries=4 6378.198250ms / query, 27954 applies
2: CM-opt: overall=39.301072s queries=5 7860.214400ms / query, 52434 applies
2: CM-opt: overall=39.322752s queries=6 6553.792000ms / query, 52528 applies

Without:

2: CM: overall=2.917165s queries=1 2917.165000ms / query
2: CM: overall=2.947391s queries=2 1473.695500ms / query
2: CM: overall=5.713380s queries=3 1904.460000ms / query
2: CM: overall=8.740909s queries=4 2185.227250ms / query
2: CM: overall=10.122729s queries=5 2024.545800ms / query
2: CM: overall=10.151202s queries=6 1691.867000ms / query

So in this case (CITY_MAP_SIZE of 11 with a city of size 50, plus two 
smaller cities) the DP algorithm is much (7x) faster than the BB 
algorithm (on the third optimization).  Why are there 52,000 applies 
when nothing changes?

Note that all 6 of these CMA calls are basically superfluous.  On 
loading the game the CMA is already set and is optimized (although maybe 
the client doesn't know that so will need to call the CMA thrice - once 
for each city) but why would we call it a second time?

P.S.  Colossus, Richard's Crusade, and Shakespeare's theater are very 
good for a city with 50 workers in the fields.

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 
size of 29 and a CITY_MAP_RADIUS of 50 or 100, you could get cities with 
thousands of citizens.  For best results your cities need to overlap a 
little so that you get the nice feedback between cities that causes the 
CMA to run over and over again.  Make sure your citymap isn't bigger 
than the world - if one map tile is inside the citymap twice, I think 
very bad things will happen.

jason

? common/aicore/cm-old.c
? common/aicore/cm-old.h
Index: common/city.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/city.h,v
retrieving revision 1.166
diff -u -r1.166 city.h
--- common/city.h       10 Nov 2004 17:01:59 -0000      1.166
+++ common/city.h       18 Nov 2004 20:39:15 -0000
@@ -57,7 +57,7 @@
 
 
 /* Changing this requires updating CITY_TILES and network capabilities. */
-#define CITY_MAP_RADIUS 2
+#define CITY_MAP_RADIUS 5
 
 /* Diameter of the workable city area.  Some places harcdode this number. */
 #define CITY_MAP_SIZE (CITY_MAP_RADIUS * 2 + 1) 
Index: data/default/buildings.ruleset
===================================================================
RCS file: /home/freeciv/CVS/freeciv/data/default/buildings.ruleset,v
retrieving revision 1.59
diff -u -r1.59 buildings.ruleset
--- data/default/buildings.ruleset      18 Oct 2004 17:18:58 -0000      1.59
+++ data/default/buildings.ruleset      18 Nov 2004 20:39:16 -0000
@@ -2184,7 +2184,7 @@
 
 ; Special values:
 
-aqueduct_size=8
+aqueduct_size=100
 default="Coinage"
 
 ; FIXME: remove all of the following when gen-impr implemented...
Index: data/default/cities.ruleset
===================================================================
RCS file: /home/freeciv/CVS/freeciv/data/default/cities.ruleset,v
retrieving revision 1.11
diff -u -r1.11 cities.ruleset
--- data/default/cities.ruleset 9 Jun 2004 04:39:13 -0000       1.11
+++ data/default/cities.ruleset 18 Nov 2004 20:39:16 -0000
@@ -36,7 +36,7 @@
 ;forced_gold = 0
 
 [parameters]
-add_to_size_limit  = 8         ; cities >= this cannot be added to.
+add_to_size_limit  = 50                ; cities >= this cannot be added to.
 
 ;
 ; City styles define the way cities are drawn
Index: data/default/game.ruleset
===================================================================
RCS file: /home/freeciv/CVS/freeciv/data/default/game.ruleset,v
retrieving revision 1.20
diff -u -r1.20 game.ruleset
--- data/default/game.ruleset   18 Nov 2004 09:56:35 -0000      1.20
+++ data/default/game.ruleset   18 Nov 2004 20:39:16 -0000
@@ -28,7 +28,7 @@
 min_dist_bw_cities     = 2
 
 ; Square of initially visible radius (true distance).
-init_vis_radius_sq     = 5
+init_vis_radius_sq     = 10
 
 ; What happens when a hut is overflown:
 ;   "Nothing"  - Just fly over; hut remains.
@@ -49,8 +49,8 @@
 ;   if city_size > num_inis;
 ;     city_granary_size = (granary_food_ini[num_inis] * foodbox) +
 ;        (granary_food_inc * (city_size - num_inis)) * foodbox / 100
-granary_food_ini       = 2
-granary_food_inc       = 100
+granary_food_ini       = 1
+granary_food_inc       = 0
 
 ; Method of calculating technology costs
 ;   0 - Civ (I|II) style. Every new tech add researchcost to cost of next tech.

biggame1.sav.gz
Description: Unix tar archive