Re: (PR#10203) Greedy CM algorithm

"Jason Short" <[email protected]> Thu, 18 Nov 2004 17:19:50 -0800
Newsgroups gmane.games.freeciv.ai
Message-ID <[email protected]> 
<URL: http://rt.freeciv.org/Ticket/Display.html?id=10203 >

Benoit Hudson wrote:
> <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.

It is close to a linear programming problem, which is easy.  However 
it's actually an integer programming problem, which is hard.

> Things we can do to speed up the CM:

Yes.

I think the two easiest things we can do are:

1.  Call the CM less.

- Don't call it in the client at all.  Instead have the client send the 
CM parameters to the server and let the server run it.  Not only is the 
client-side CM inefficient because it doesn't really know when it should 
call CM, it also usually duplicates the work of the server.  When a new 
citizen is added on, the server CM runs and *then* the client CM runs 
(i.e., in series).  This is most obvious when playing with a city that 
takes 10 minutes for the CM to run, because for the first 10 minutes the 
client doesn't block and for the second 10 minutes it does.

- Call it less in the client.  This is an alternative to moving it 
entirely to the server that should be feasible for 2.0.

- Don't run the full CM to place one citizen.  This was, of course, one 
of the purposes of switching back to a greedy algorithm.  Implementing 
it will take some changes to the interface, naturally.  The problem is 
we have to decide what to do if the CM can't meet the requirements by 
placing just once citizen: does it run from scratch or give up?

2.  Don't block while calling the CM.

This doesn't really speed things up, but will give much better results 
for the user.  Too much we are concerned with timing function calls or 
server execution times.  The truth is that if the player is able to 
continue doing things while the CM runs, it doesn't really matter if it 
takes a little longer.

The way to do this is again to move CM into the server.  Of course the 
server blocks while running CM, but that's a little less obvious.  The 
client's supposed to be able to do most actions without waiting for 
server response anyway.

-----

Now, for the juicy stuff.  I applied the attached patch.  It makes the 
CITY_MAP_RADIUS into 80.  This means about 20,000 tiles in the citymap. 
  A hard problem for the CM!  So I ran it under both new and old code. 
The new code performed better by a factor of about 100.  I assume this 
is mostly because with such a large citymap, the advantage from using 
tile "types" is very large.

The numbers below give the time (in seconds) on the right it took to run 
the CM for a city of the size given on the left.  As you can see it's 
not possible to get very far.  The numbers aren't particularly accurate 
but should give a good overall picture.

Old (DP):

   1: 10
   2: 20
   3: 314 seconds

New (B&B):

   1: 0.2
   2: 0.8
   3: 2
   4: 6
   5: 20
   6: 55
   7: 75
   8: 917 seconds

One interesting thing I noted is that the client runs some rather 
lengthy CM code *even if there is no city under CMA control*.

Also of interest is the attached rc file which gives some settings I 
found helpful.  Or rather, I would have found them helpful had it been 
possible to play more than 10 turns of the game.

If you try to run a game under this patch, generating the map will take 
a very long time.  Actually this time is spent placing starting 
positions, since it has a city_map_iterate nested inside a 
whole_map_iterate.  Just wait 5-10 minutes and it will complete ;-).

jason
giant.diff (text/x-patch, 8.6 KB) 
? common/aicore/cm-old.c
? common/aicore/cm-old.h
Index: client/mapview_common.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/mapview_common.c,v
retrieving revision 1.160
diff -u -r1.160 mapview_common.c
--- client/mapview_common.c	15 Nov 2004 17:20:55 -0000	1.160
+++ client/mapview_common.c	19 Nov 2004 01:12:35 -0000
@@ -1577,6 +1577,7 @@
     } adjc_dir_iterate_end;
   } gui_rect_iterate_end;
 
+#if 0
   /* Draw citymap overlays on top. */
   gui_rect_iterate(gui_x0, gui_y0, width, height, ptile) {
     if (tile_get_known(ptile) != TILE_UNKNOWN) {
@@ -1608,6 +1609,7 @@
       }
     }
   } gui_rect_iterate_end;
+#endif
 
   /* Put goto target. */
   put_path_length();
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	19 Nov 2004 01:12:35 -0000
@@ -57,7 +57,7 @@
 
 
 /* Changing this requires updating CITY_TILES and network capabilities. */
-#define CITY_MAP_RADIUS 2
+#define CITY_MAP_RADIUS 80
 
 /* Diameter of the workable city area.  Some places harcdode this number. */
 #define CITY_MAP_SIZE (CITY_MAP_RADIUS * 2 + 1) 
Index: common/connection.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/connection.h,v
retrieving revision 1.37
diff -u -r1.37 connection.h
--- common/connection.h	12 Sep 2004 21:44:10 -0000	1.37
+++ common/connection.h	19 Nov 2004 01:12:35 -0000
@@ -22,7 +22,7 @@
 #include <sys/time.h>
 #endif
 
-#define USE_COMPRESSION
+//#define USE_COMPRESSION
 
 /**************************************************************************
   The connection struct and related stuff.
@@ -36,9 +36,9 @@
 struct hash_table;
 struct timer_list;
 
-#define MAX_LEN_PACKET   4096
+#define MAX_LEN_PACKET   65536
 
-#define MAX_LEN_BUFFER   (MAX_LEN_PACKET * 128)
+#define MAX_LEN_BUFFER   (MAX_LEN_PACKET * 1024)
 #define MAX_LEN_CAPSTR    512
 #define MAX_LEN_PASSWORD  512 /* do not change this under any circumstances */
 
Index: common/map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
retrieving revision 1.225
diff -u -r1.225 map.h
--- common/map.h	13 Nov 2004 08:34:17 -0000	1.225
+++ common/map.h	19 Nov 2004 01:12:35 -0000
@@ -603,8 +603,8 @@
 #define MAP_MAX_HUTS             500
 
 /* Size of the map in thousands of tiles */
-#define MAP_DEFAULT_SIZE         4
-#define MAP_MIN_SIZE             1
+#define MAP_DEFAULT_SIZE         29
+#define MAP_MIN_SIZE             29
 #define MAP_MAX_SIZE             29
 
 /* This defines the maximum linear size in _map_ coordinates.
@@ -615,10 +615,10 @@
 #define MAP_MAX_WIDTH            MAP_MAX_LINEAR_SIZE
 #define MAP_MAX_HEIGHT           MAP_MAX_LINEAR_SIZE
 
-#define MAP_ORIGINAL_TOPO        TF_WRAPX
-#define MAP_DEFAULT_TOPO         TF_WRAPX
-#define MAP_MIN_TOPO             0
-#define MAP_MAX_TOPO             15
+#define MAP_ORIGINAL_TOPO        3
+#define MAP_DEFAULT_TOPO         3
+#define MAP_MIN_TOPO             3
+#define MAP_MAX_TOPO             3
 
 #define MAP_DEFAULT_SEED         0
 #define MAP_MIN_SEED             0
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	19 Nov 2004 01:12:36 -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	19 Nov 2004 01:12:36 -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	19 Nov 2004 01:12:36 -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	= 40000
 
 ; 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.
Index: server/savegame.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/savegame.c,v
retrieving revision 1.206
diff -u -r1.206 savegame.c
--- server/savegame.c	17 Nov 2004 19:21:14 -0000	1.206
+++ server/savegame.c	19 Nov 2004 01:12:37 -0000
@@ -2690,7 +2690,8 @@
   i = -1;
   city_list_iterate(plr->cities, pcity) {
     int j, x, y;
-    char buf[512];
+    char citymap_buf[CITY_MAP_SIZE * CITY_MAP_SIZE + 1];
+    char impr_buf[MAX_NUM_ITEMS + 1];
 
     i++;
     secfile_insert_int(file, pcity->id, "player%d.c%d.id", plrno, i);
@@ -2764,14 +2765,25 @@
     for(y=0; y<CITY_MAP_SIZE; y++) {
       for(x=0; x<CITY_MAP_SIZE; x++) {
 	switch (get_worker_city(pcity, x, y)) {
-	  case C_TILE_EMPTY:       buf[j++] = '0'; break;
-	  case C_TILE_WORKER:      buf[j++] = '1'; break;
-	  case C_TILE_UNAVAILABLE: buf[j++] = '2'; break;
+	case C_TILE_EMPTY:
+	  citymap_buf[j++] = '0';
+	  break;
+	case C_TILE_WORKER:
+	  citymap_buf[j++] = '1';
+	  break;
+	case C_TILE_UNAVAILABLE:
+	  citymap_buf[j++] = '2';
+	  break;
+	default:
+	  citymap_buf[j++] = '?';
+	  assert(0);
+	  break;
 	}
       }
     }
-    buf[j]='\0';
-    secfile_insert_str(file, buf, "player%d.c%d.workers", plrno, i);
+    citymap_buf[j]='\0';
+    assert(j < sizeof(citymap_buf));
+    secfile_insert_str(file, citymap_buf, "player%d.c%d.workers", plrno, i);
 
     secfile_insert_bool(file, pcity->is_building_unit, 
 		       "player%d.c%d.is_building_unit", plrno, i);
@@ -2791,22 +2803,25 @@
     /* 1.14 servers depend on improvement order in ruleset. Here we
      * are trying to simulate 1.14.1 default order
      */
-    init_old_improvement_bitvector(buf);
+    init_old_improvement_bitvector(impr_buf);
     impr_type_iterate(id) {
       if (pcity->improvements[id] != I_NONE) {
-        add_improvement_into_old_bitvector(buf, id);
+        add_improvement_into_old_bitvector(impr_buf, id);
       }
     } impr_type_iterate_end;
-    secfile_insert_str(file, buf, "player%d.c%d.improvements", plrno, i);
+    assert(strlen(impr_buf) < sizeof(impr_buf));
+    secfile_insert_str(file, impr_buf, "player%d.c%d.improvements", plrno, i);
 
     /* Save improvement list as bitvector. Note that improvement order
      * is saved in savefile.improvement_order.
      */
     impr_type_iterate(id) {
-      buf[id] = (pcity->improvements[id] != I_NONE) ? '1' : '0';
+      impr_buf[id] = (pcity->improvements[id] != I_NONE) ? '1' : '0';
     } impr_type_iterate_end;
-    buf[game.num_impr_types] = '\0';
-    secfile_insert_str(file, buf, "player%d.c%d.improvements_new", plrno, i);    
+    impr_buf[game.num_impr_types] = '\0';
+    assert(strlen(impr_buf) < sizeof(impr_buf));
+    secfile_insert_str(file, impr_buf,
+		       "player%d.c%d.improvements_new", plrno, i);    
 
     worklist_save(file, "player%d.c%d", plrno, i, &pcity->worklist);
 
Index: utility/ioz.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/ioz.c,v
retrieving revision 1.17
diff -u -r1.17 ioz.c
--- utility/ioz.c	17 May 2004 02:16:15 -0000	1.17
+++ utility/ioz.c	19 Nov 2004 01:12:37 -0000
@@ -229,7 +229,7 @@
 #ifdef HAVE_LIBZ
   case FZ_ZLIB:
     {
-      char buffer[4096];
+      char buffer[65536];
       int num;
       num = my_vsnprintf(buffer, sizeof(buffer), format, ap);
       if (num == -1) {
giantpox.rc (text/plain, 245 B) 
set savename giantpox
set saveturns 1
set endyear 5000
set barbarians 0
set borders 24
set foodbox 5
set techlevel 50
set startunits cxxxxwwwwwwwww
set specials 1000
set steepness 20
set landmass 50
set alltemperate 1
set topology 3
set size 29