Complete.Org: Mailing Lists: Archives: freeciv-ai: November 2004: [freeciv-ai] Re: (PR#10203) Greedy CM algorithm

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

[Top] [All Lists]

 To: per@xxxxxxxxxxx Subject: [freeciv-ai] Re: (PR#10203) Greedy CM algorithm From: "Jason Short" Date: Thu, 18 Nov 2004 17:19:50 -0800 Reply-to: rt@xxxxxxxxxxx

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

```
```? 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 @@
} 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. */

/* 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]

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

; 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) {
}
} 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) {
```
```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
```