[freeciv-ai] Re: (PR#8992) Patch: Building ferries

["Benedict Adamson" <badamson@xxxxxxxxxxx>]

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

Attached is the latest version of my centralised ferry building patch,
based on Gregory Berkolaiko's original. This patch is applicable to the
2004-11-03 CVS development version.

This differs from my previous versions of the patch as follows.
* The AI can choose to switch cities that were building improvements or 
domestic units (units that do not want to go abroad) to ferry building, 
if the demand is great enough. Previously it would switch cities only if 
they were building units that themselves needed ferries. This is 
important when the demand for ferries is very great or there are many 
waiting passengers.
* The AI can choose to build ferries in cities that would take a long 
time to complete them. This is important when the AI has plenty of gold.
* Ever increasing numbers of waiting passengers increases the 'want' 
score for ferries. Previously that situation made the 'want' asymptote 
to 200, and could therefore cause the 'want' to decrease.
* Removed the last vestiges of the 'straits' values. The AI now produces 
a less bogus guess for how enemy hunters will spread out to attack other 
players.
* Removed the duplication of the sea_overlap_move function, as requested 
by Per.
* Replaced bogus use of the pcity->ai.founder_want field with a new 
field, as requested by Per.
* Replaced, with an enum, hard coded constants for the ferry building 
mode, as requested by Per.
* Made it possible for the journey_length to vary from sea to sea 
(although it does not yet do so).
* The selection of which cities will build ferries takes into account 
the 'want' scores of the cities, to avoid building in cities that have 
urgent non-ferry requirements.

diff -ru -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/advdomestic.c 
freeciv.PR8992/ai/advdomestic.c
--- vendor.freeciv.current/ai/advdomestic.c     2004-10-22 23:16:36.000000000 
+0100
+++ freeciv.PR8992/ai/advdomestic.c     2004-11-05 00:09:09.000000000 +0000
@@ -204,7 +204,6 @@
       choice->type = CT_NONMIL;
       choice->choice = unit_type; /* default */
       choice->need_boat = TRUE;
-      ai_choose_role_unit(pplayer, pcity, choice, L_FERRYBOAT, -want);
     }
   }
 
diff -ru -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/advmilitary.c 
freeciv.PR8992/ai/advmilitary.c
--- vendor.freeciv.current/ai/advmilitary.c     2004-11-03 19:46:36.000000000 
+0000
+++ freeciv.PR8992/ai/advmilitary.c     2004-11-05 00:09:09.000000000 +0000
@@ -962,8 +962,8 @@
 3. calculates the relevant stats of the victim.
 4. finds the best attacker for this type of victim (in process_attacker_want)
 5. if we still want to attack, records the best attacker in choice.
-If the target is overseas, the function might suggest building a ferry
-to carry a land attack unit, instead of the land attack unit itself.
+If the target is overseas, the function might suggest using a ferry
+to carry a land attack unit.
 **************************************************************************/
 static void kill_something_with(struct player *pplayer, struct city *pcity, 
                                struct unit *myunit, struct ai_choice *choice)
@@ -1126,23 +1126,9 @@
   if (best_choice.want > choice->want) {
     /* We want attacker more than what we have selected before */
     copy_if_better_choice(&best_choice, choice);
-    CITY_LOG(LOG_DEBUG, pcity, "ksw: %s has chosen attacker, %s, want=%d",
-            pcity->name, unit_types[choice->choice].name, choice->want);
-
-    if (go_by_boat && !ferryboat) { /* need a new ferry */
-      /* We might need a new boat even if there are boats free,
-       * if they are blockaded or in inland seas*/
-      assert(is_ground_unit(myunit));
-      ai_choose_role_unit(pplayer, pcity, choice, L_FERRYBOAT, choice->want);
-      if (SEA_MOVING == unit_types[choice->choice].move_type) {
-        struct ai_data *ai = ai_data_get(pplayer);
-
-        freelog(LOG_DEBUG,
-                "%s has chosen attacker ferry, %s, want=%d, %d of %d free",
-                pcity->name, unit_types[choice->choice].name, choice->want,
-                ai->stats.available_boats, ai->stats.boats);
-      } /* else can not build ferries yet */
-    }
+    CITY_LOG(LOG_DEBUG, pcity, "has chosen attacker, %s, want=%d%s",
+            unit_types[choice->choice].name, choice->want, 
+            (best_choice.need_boat ? "(need boat)" : ""));
   } 
 }
 
@@ -1390,9 +1376,7 @@
     destroy_unit_virtual(virtualunit);
   }
 
-  /* Consider a land attacker or a ferried land attacker
-   * (in which case, we might want a ferry before an attacker)
-   */
+  /* Consider a land attacker or a ferried land attacker */
   unit_type = ai_choose_attacker(pcity, LAND_MOVING);
   if (unit_type >= 0) {
     virtualunit = create_unit_virtual(pplayer, pcity, unit_type, 1);
diff -ru -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/aicity.c 
freeciv.PR8992/ai/aicity.c
--- vendor.freeciv.current/ai/aicity.c  2004-11-03 19:46:36.000000000 +0000
+++ freeciv.PR8992/ai/aicity.c  2004-11-05 00:09:09.000000000 +0000
@@ -46,6 +46,7 @@
 #include "advdomestic.h"
 #include "advmilitary.h"
 #include "aidata.h"
+#include "aiferry.h"
 #include "aihand.h"
 #include "ailog.h"
 #include "aitools.h"
@@ -981,6 +982,8 @@
     ai_city_choose_build(pplayer, pcity);
   } city_list_iterate_end;
 
+  aiferry_choose_build_global(pplayer);
+
   ai_spend_gold(pplayer);
 }
 
diff -ru -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/aiferry.c 
freeciv.PR8992/ai/aiferry.c
--- vendor.freeciv.current/ai/aiferry.c 2004-11-03 19:46:36.000000000 +0000
+++ freeciv.PR8992/ai/aiferry.c 2004-11-05 00:09:09.000000000 +0000
@@ -16,22 +16,28 @@
 #endif
 
 #include "log.h"
+#include "mem.h"
+#include "rand.h"
 #include "unit.h"
 
 #include "path_finding.h"
 #include "pf_tools.h"
 
 #include "hand_gen.h"
+#include "maphand.h"
 #include "unithand.h"
 #include "unittools.h"
 
 #include "aidata.h"
 #include "aiexplorer.h"
+#include "aihand.h"
+#include "aihunt.h"
 #include "ailog.h"
 #include "aitools.h"
 #include "aiunit.h"
 
 #include "aiferry.h"
+#include "settlers.h" /*for amortize*/
 
  
 /* =================== constants with special meaning =================== */
@@ -51,12 +57,54 @@
 
 /* Logging in ferry management functions */
 #define LOGLEVEL_FERRY LOG_DEBUG
+#define LOGLEVEL_BUILDFERRY LOG_NORMAL
 /* Logging in go_by_boat functions */
 #define LOGLEVEL_GOBYBOAT LOG_DEBUG
 /* Logging in find_ferry functions */
 #define LOGLEVEL_FINDFERRY LOG_DEBUG
 /* Extra consistency checks */
 #define DEBUG_FERRY_STATS 0
+/*
+ * The maximum number of turns to look ahead.
+ * For each city, the code looks ahead no further than the completion of the
+ * item currently being built. This should therefore not be much longer
+ * than a typical build time.
+ */
+#define MAX_TURNS_HORIZON 10
+
+
+
+/*
+ * Data about one sea area for one player.
+ */
+struct sea_stats {
+  unsigned int future_psngrs;
+  unsigned int future_escorts;
+
+  unsigned int psngrs;
+  unsigned int escorts;
+  unsigned int boats;
+  unsigned int avail_boats;
+
+  unsigned int hunters_seen;
+  unsigned int hunters_guess;
+
+  unsigned int sea_area;
+  unsigned int journey_length;
+  unsigned int n_cities; /*our cities*/
+
+  /*Number of locations that can hold enemy hunters:*/
+  unsigned int danger_area;
+  unsigned int danger_area_known;
+  unsigned int danger_area_seen;
+
+  int ferry_want;
+
+  /*extra_passengers[t] = increment in passengers in turn t from now*/
+  unsigned int extra_passengers[MAX_TURNS_HORIZON];
+  /*extra_escorts[t] = increment in escorts in turn t from now*/
+  unsigned int extra_escorts[MAX_TURNS_HORIZON];
+};
 
 
 /* ========= managing statistics and boat/passanger assignments ======== */
@@ -73,7 +121,7 @@
   ai->stats.available_boats = 0;
  
   unit_list_iterate(pplayer->units, punit) {
-    if (is_sailing_unit(punit) && is_ground_units_transport(punit)) {
+    if (unit_has_role(punit->type, L_FERRYBOAT)) {
       ai->stats.boats++;
       if (punit->ai.passenger == FERRY_AVAILABLE) {
        ai->stats.available_boats++;
@@ -95,8 +143,8 @@
   struct ai_data *ai = ai_data_get(pplayer);
   int n = 1;
 
-  freelog(LOG_NORMAL, "Boat stats for %s[%d]", 
-         pplayer->name, pplayer->player_no);
+  freelog(LOG_NORMAL, "Boat stats for %s[%d] in turn %d", 
+         pplayer->name, pplayer->player_no, game.turn);
   freelog(LOG_NORMAL, "Registered: %d free out of total %d",
          ai->stats.available_boats, ai->stats.boats);
   unit_list_iterate(pplayer->units, punit) {
@@ -867,3 +915,926 @@
  
   return;
 }
+
+/* Least Common Multiple of 2,3,..,8 (a very divisible number) */
+#define DENOM 840
+
+/*
+ * Constants for the shipping model used by estimate_cost.
+ * These values are chosen to produce a reasonably accurate simulation
+ * for a wide range of games.
+ *
+ * HUNT_RATE:
+ *    How rapidly hunters can sink ferries (100 == about as rapidly as ferries
+ *    can deliver, all other factors equal).
+ *    Should be < 100 because a ferry can deliver and be sunk in one turn.
+ *    Important when there are many hunters.
+ * BATTLE_RATE:
+ *    How rapidly hunters and escorts can sink each other
+ *    (100 == about as rapidly as ferries can deliver, all other factors
+ *    equal).
+ *    Important when there are many escorts.
+ */
+#define HUNT_RATE 70
+#define BATTLE_RATE 70
+
+/**************************************************************************
+ Pick up and put down some passengers.
+ Calculate together so a boat can not pick up and deliver in one turn
+
+ This part of the shipping model makes the following assumptions:
+ * all journeys take the same time
+ * maximum of 1 passenger per boat
+ * we can treat numbers as continuous variables
+ * all ships are uniformly distributed
+**************************************************************************/
+static void sim_pickup_deliver(unsigned int *psngrs,
+                              unsigned int *avail_boats,
+                              unsigned int *used_boats,
+                              unsigned int ferry_rate)
+{
+  unsigned int deliveries =
+    MIN(*used_boats, (*used_boats * ferry_rate) / DENOM);
+  unsigned int pairs = MIN(*psngrs, *avail_boats);
+  unsigned int pickups = MIN(pairs, (pairs * ferry_rate) / DENOM);
+
+  *avail_boats += deliveries;
+  *avail_boats -= pickups;
+  *used_boats += pickups;
+  *used_boats -= deliveries;
+  *psngrs -= pickups;
+}
+
+/**************************************************************************
+ Simulate attacks upon the ferries by enemy hunters.
+
+ This part of the shipping model makes the following assumptions:
+ * maximum of 1 passenger per boat
+ * we can treat numbers as continuous variables
+ * all ships are uniformly distributed
+ * each hunter can sink at most one ferry each turn
+**************************************************************************/
+static void sim_sink_ferries(unsigned int *boats,
+                            unsigned int *avail_boats,
+                            unsigned int *used_boats,
+                            unsigned int *sinkings,
+                            unsigned int *lost_psngrs,
+                            unsigned int hunters,
+                            unsigned int hunt_rate)
+{
+  unsigned int pairs = MIN(*boats, hunters);
+  *sinkings = MIN(pairs, (pairs * hunt_rate) / DENOM);
+  *boats -= *sinkings;
+  /*target loaded ferries first*/
+  if (*used_boats < *sinkings) {
+    /*sink them all*/
+    unsigned int empty_sinkings = *sinkings - *used_boats;
+    *lost_psngrs = *used_boats;
+    *used_boats = 0;
+    /*now target the empty ferries*/
+    assert(*sinkings <= *avail_boats);
+    *avail_boats -= empty_sinkings;
+  }else{/*empty ferries ignored this turn*/
+    *lost_psngrs = *sinkings;
+    *used_boats -= *sinkings;
+  }
+}
+
+/**************************************************************************
+ Simulate battles between our escorts and enemy hunters
+
+ This part of the shipping model makes the following assumptions:
+ * we can treat numbers as continuous variables
+ * all ships are uniformly distributed
+ * each warship can sink at most one warship each turn
+**************************************************************************/
+static void sim_fight_battles(unsigned int *hunters, unsigned int *escorts,
+                             unsigned int battle_rate)
+{
+  unsigned int pairs = MIN(*escorts, *hunters);
+  unsigned int sinkings = MIN(pairs, (pairs * battle_rate) / DENOM);
+  *escorts -= sinkings;
+  *hunters -= sinkings;
+}
+
+/**************************************************************************
+ Simulate building of ships and passengers
+
+ This part of the shipping model makes the following assumptions:
+ * all ships are uniformly distributed
+ * new ferries appear instantly
+   (that is, gold is likely to be spent to buy them)
+ * each extra ferry we build replaces one passenger we might have built
+ * we build additional ferries to replace losses
+**************************************************************************/
+static void sim_build(unsigned int *psngrs,
+                     unsigned int *boats, unsigned int *avail_boats,
+                     unsigned int *escorts,
+                      unsigned int *build, unsigned int *extra_skipped,
+                     const unsigned int sinkings,
+                     const unsigned int extra_passengers[],
+                     const unsigned int extra_escorts[],
+                     unsigned int t)
+{
+  unsigned int extra;
+
+  /*replace sunk ferries*/
+  *extra_skipped += sinkings;
+  *build = sinkings;
+  *boats += *build;
+  *avail_boats += *build;
+
+  /*build more passengers*/
+  extra = extra_passengers[t] * DENOM;
+  if (*extra_skipped && extra <= *extra_skipped) {
+    /*We built ferries instead of all the passengers
+     *we might have built this turn*/
+    *extra_skipped -= extra;
+  } else if (extra_skipped && extra) {
+    /*We built ferries instead of some of the passengers
+     *we might have built this turn*/
+    *psngrs += extra - *extra_skipped;
+    *extra_skipped = 0;
+  } else {
+    *psngrs += extra;
+  }
+
+  /*build escorts*/
+  *escorts += DENOM * extra_escorts[t];
+}
+
+/* 
+ * Constants for the cost model used by estimate_cost.
+ * These values are harder to decide than the constants used for the shipping
+ * model, being somewhat subjective.
+ * The costs are in arbitrary units, so it is the relative values that matter.
+ *
+ * BUILD_COST:
+ *    The cost of building a ferry.
+ *    Fix this at 100 and vary the other costs relative to it.
+ * PASSENGER_COST:
+ *    The cost of a passenger being sunk while on a ferry.
+ * WAIT_COST:
+ *    The cost of having a passenger waiting to arrive for one turn.
+ * IDLE_COST:
+ *    The cost of having a ferry idle (that is, not carrying a passenger)
+ *    for one turn.
+ *
+ * The value (BUILD_COST / WAIT_COST) is about the maximum number of turns
+ * that a unit may await a ferry; if a unit would wait longer than that,
+ * the AI would be better off building another ferry to shorten the waiting
+ * time.
+ * The value 100% * IDLE_COST / (IDLE_COST + WAIT_COST) is roughly the minimum
+ * acceptable utilisation of the ferries; if the utilisation is lower than
+ * that, the AI would be better off with fewer ferries. If ferries are
+ * only 'exporting', which is the usual case, the ferries will be empty
+ * for their return journeys and utilisation greater than 50% difficult,
+ * therefore have IDLE_COST <= WAIT_COST.
+ */
+#define BUILD_COST 100
+#define PASSENGER_COST 100
+#define WAIT_COST   33
+#define IDLE_COST   22
+
+/**************************************************************************
+  Estimate the total cost of starting to build a given number of ferries
+  this turn.
+  The total cost is the cost of the new ferries, plus the subsequent costs
+  due to waiting passengers, idle passengers and idle ferries.
+  The estimation uses two models: a 'shipping model' for estimating movement
+  and combat of ships, and a 'cost model' for estimating the cost of the
+  ship movements.
+
+  Building more ferries decreases the costs of waiting passengers,
+  hence there will be an optimum number of ferries to build.
+
+  The calculation uses numbers scaled by factor DENOM.
+
+  The cost model makes the following assumptions:
+  * we can discount future costs at the usual amortisation rate
+  * all passengers are equally valuable
+**************************************************************************/
+static int estimate_cost(const struct sea_stats *sea,
+                         Unit_Type_id boattype,
+                         unsigned int turns_horizon,
+                         unsigned int build)
+{
+  /* Assess the capabilities of the boats, assuming:
+   * * all boats have the same movement rate
+   * * the ferries are vulnerable to hunting
+   * * hunters and escorts are vulnerable to each other
+   * * all journeys take the same time
+   */
+  unsigned int move_rate = get_unit_type(boattype)->move_rate;
+  unsigned int base_rate = (DENOM * move_rate)
+                           / (sea->journey_length * SINGLE_MOVE);
+  unsigned int ferry_rate = base_rate;
+  unsigned int hunt_rate = base_rate * HUNT_RATE / 100;
+  unsigned int battle_rate = base_rate * BATTLE_RATE / 100;
+
+  unsigned int deflate = DENOM;
+  unsigned int t;
+  unsigned int used_boats;
+  unsigned int lost_psngrs = 0;
+  /*future passengers replaced by ferries:*/
+  unsigned int extra_skipped = build;
+
+  int cost = 0;
+
+  /*rescale, so can use integer arithmetic for continuous variables*/
+  unsigned int boats = sea->boats * DENOM;
+  unsigned int psngrs = sea->psngrs * DENOM;
+  unsigned int avail_boats = sea->avail_boats * DENOM;
+  unsigned int hunters = sea->hunters_guess * DENOM;
+  unsigned int escorts = sea->escorts * DENOM;
+  build *= DENOM;
+  extra_skipped *= DENOM;
+
+  /*build the new boats*/
+  boats += build;
+  avail_boats += build;
+
+  used_boats = boats - avail_boats;
+
+  for(t = 0; t < turns_horizon; t++) {
+    unsigned int sinkings;
+    int turn_cost = WAIT_COST * (psngrs + used_boats)
+                    + IDLE_COST * avail_boats
+                    + BUILD_COST * build
+                    + PASSENGER_COST * lost_psngrs;
+    turn_cost = (turn_cost * deflate) / DENOM;
+    cost += turn_cost;
+    freelog(LOGLEVEL_BUILDFERRY,
+            "Ferries sim.: t=%d b=%d a=%d p=%d h=%d e=%d D=%d C=%d",
+            t, boats, avail_boats, psngrs, hunters, escorts,
+            deflate, turn_cost);
+
+    /*Advance the shipping simulation by one turn*/
+    sim_pickup_deliver(&psngrs, &avail_boats, &used_boats, ferry_rate);
+    sim_sink_ferries(&boats, &avail_boats, &used_boats,
+                    &sinkings, &lost_psngrs,
+                    hunters, hunt_rate);
+    sim_fight_battles(&hunters, &escorts, battle_rate);
+    sim_build(&psngrs, &boats, &avail_boats, &escorts, &build, &extra_skipped,
+             sinkings, sea->extra_passengers, sea->extra_escorts, t);
+    assert(used_boats == boats - avail_boats);
+
+    /*adjust for inflation*/
+    deflate = (deflate * (MORT - 1)) / MORT;
+  }
+
+  return cost;
+}
+
+/****************************************************************************
+  Calculate some geography metrics that are useful for assessing ferry needs.
+  Calculating these, rather than using constants, is important for unusual
+  maps.
+
+  SPRAWL:
+     This adjusts the distances to account for peninsulas,
+     which narrow the seas between islands.
+     Assumed to be the same for all map generators.
+  COAST_LEGS:
+     A typical journey is considered to consist of a leg across open sea
+     plus one or two legs along a coast. This constant is the total length
+     of the coastal legs, relative to the size of a typical island.
+
+  *journey_length:
+     the estimated length of a typical sea journey
+
+  TODO: At present, this retursn the same value for each player for each sea
+  each turn, but a more sophisticated version would not.
+****************************************************************************/
+#define SPRAWL 1.8
+#define COAST_LEGS 0.7
+static void ferry_geography(unsigned int *journey_length)
+{
+  /*
+   * Just like the human players, the AI uses meta game information
+   * to help decide its strategy.
+   */
+  double globe_area = map.xsize * map.ysize;
+  /* TODO: Use the H_MAP handicap to dcide whetehr the AI knows the true value
+   * for n_isloands; otherwise make an intelligent guess based on our
+   * exploration so far */
+  double n_islands = map.num_continents;
+  double territory_area, territory_size;
+  double square_island_size, island_size, open_sea_leg, coastal_legs;
+
+  /*The size of a single island, including territorial waters:*/
+  territory_area = globe_area/n_islands;
+  territory_size = sqrt(territory_area);
+
+  square_island_size = sqrt(territory_area * map.landpercent/100.0);
+  island_size = SPRAWL * square_island_size;
+  open_sea_leg = MAX(1.0, territory_size - square_island_size * sqrt(SPRAWL));
+  coastal_legs = island_size * COAST_LEGS;
+
+  *journey_length = open_sea_leg + coastal_legs;
+
+  assert(0 < island_size);
+  assert(0 < open_sea_leg);
+  assert(0 < journey_length);
+}
+
+/****************************************************************************
+ Convert facts about a sea into an opinion about how many boats to build
+ for that sea.
+
+ Desiradata for building more boats:
+ * if we have many passengers waiting,
+ * if our boats are slow and have far to travel
+ * if we expect many more passengers in the future
+ * if we expect heavy losses from enemy hunters
+
+ The function does a cost-benefit analysis for several values for the number
+ of boats to build, and returns the value that gives the greatest profit.
+ The implementation exploits the fact that the cost function has a well defined
+ minimum and we expect the optimum to be a small value.
+ However, it overides that calculation to prevent building boats on ponds
+ and to prevent passengers waiting forever.
+****************************************************************************/
+static unsigned int new_boats_to_build(const struct sea_stats *sea,
+                                       Unit_Type_id boattype,
+                                       unsigned int turns_horizon)
+{
+  bool force_no_build = (sea->sea_area < 49);/*no boats on ponds*/
+  bool force_build = FALSE;
+  unsigned int build = 0;
+  int previous_cost, cost = FC_INFINITY;
+
+  /*Force building if we have no ferries but will need one*/
+  force_build = !force_no_build && (0 == sea->boats && 0 < sea->psngrs);
+  if (!force_build && !force_no_build && 0 == sea->boats) {
+    unsigned t;
+    for(t = 0; t < turns_horizon; t++) {
+      if (sea->extra_passengers[t]) {
+        force_build = true;
+        break;
+      }
+    }
+  }
+
+  /*Build the number of boats that minimises the total cost*/
+  do {
+    previous_cost = cost;
+    cost = estimate_cost(sea, boattype, turns_horizon, build);
+    freelog(LOGLEVEL_BUILDFERRY, "Ferries: building %d costs %d",
+            build, cost);
+    build++;
+  }while(cost < previous_cost);
+  build -= 2;
+
+  if (0 == build && force_build) {
+    /*Ensure we will always have at least one ferry
+     *for each sea that has passengers.
+     *Prevents passengers waiting forever*/
+    build = 1;
+  } else if (force_no_build) {
+    build = 0;
+  }
+
+  return build;
+}
+
+/****************************************************************************
+  Abstract interface for using the ferry building mode of a city
+****************************************************************************/
+static enum city_ferry_mode get_city_ferry_mode(const struct city *acity)
+{
+  return acity->ai.ferry_mode;
+}
+
+static void set_city_ferry_mode(struct city *acity,
+                               const enum city_ferry_mode mode)
+{
+  acity->ai.ferry_mode = mode;
+}
+
+/*
+ * Constants used for assessing the suitability of a city for ferry building
+ */
+#define SCORE_NEVER -20000
+#define SCORE_TIME_SCALE 1000
+#define TURNS_FACTOR_BUILDING 2400
+#define TURNS_FACTOR_NONMIL    600
+#define TURNS_FACTOR_ATTACKER  840
+#define TURNS_FACTOR_DEFENDER 8400
+#define TURNS_FACTOR_VETERAN   600
+/****************************************************************************
+ Evaluate how suitable a city is as a ferry builder.
+ Larger values mean more suitable. only positive values indicate suitable
+ cities.
+
+ Desiradata:
+ * Only cities on the shore of the current ocean are suitable.
+ * Only cities not already building ferries are suitable.
+ * Cities that can complete a boat sooner are better.
+ * Cities that want a boat themselves are better.
+ * Cities building defenders are unsuitable.
+ * Cities with port facilities are better.
+ * Cities not building wonders are better.
+****************************************************************************/
+static int ferry_builder_score(struct player *pplayer, struct city *acity,
+                               Unit_Type_id boattype)
+{
+  int score = 0;
+  Impr_Type_id port_facility;
+  int turns;
+
+  assert(0 <= acity->ai.choice.want);
+
+
+  /* Consider only appropriate cities: */
+  if (get_city_ferry_mode(acity) != CFM_COUNTED
+      || !can_build_unit(acity, boattype)
+      || (!acity->is_building_unit && is_wonder(acity->currently_building))) {
+    return SCORE_NEVER;
+  }
+
+  if (acity->ai.choice.need_boat) {
+    /* if you *really* want a ferry, you should be prepared to build it
+     * yourself */
+    score = acity->ai.choice.want;
+  } else {
+    /* if you do not much care for what you are doing, you might be asked
+     * to build a ferry instead */
+    score = -acity->ai.choice.want;
+  }
+
+  turns = city_turns_to_build(acity, boattype, TRUE, TRUE);
+
+  switch (acity->ai.choice.type) {
+  case CT_BUILDING:
+    turns = turns * TURNS_FACTOR_BUILDING / DENOM;
+    break;
+  case CT_NONMIL: 
+    turns = turns * TURNS_FACTOR_NONMIL / DENOM;
+    break;
+  case CT_ATTACKER:
+    turns = turns * TURNS_FACTOR_ATTACKER / DENOM;
+    break;
+  case CT_DEFENDER:
+    turns = turns * TURNS_FACTOR_DEFENDER / DENOM;
+    break;
+  default:
+    break;
+  }
+
+  /* Prefer building veteran units (resistant to hunters) */
+  port_facility = ai_find_source_building(pplayer, EFT_SEA_VETERAN);
+  if (port_facility != B_LAST && city_got_building(acity, port_facility)) {
+    turns = turns * TURNS_FACTOR_VETERAN / DENOM;
+  }
+
+  /* Sooner is better */
+  score += SCORE_TIME_SCALE / MAX(1, turns);
+
+  return score;
+}
+
+/****************************************************************************
+  Whether a unit type is suitable as a convoy raider or convoy escort
+****************************************************************************/
+static bool is_warship_type(Unit_Type_id type_id)
+{
+  struct unit_type *type = get_unit_type(type_id);
+  int attack_power = type->attack_strength * type->hp * type->firepower;
+
+  return (SEA_MOVING == type->move_type)
+    && (2 * SINGLE_MOVE <= type->move_rate)
+    && 1 < attack_power
+    && (unit_type_flag(type_id, F_PARTIAL_INVIS)
+        || type->transport_capacity < type->attack_strength);
+}
+
+/****************************************************************************
+  Extrapolate from the known to the unknown (non omniscient AI)
+****************************************************************************/
+static unsigned int guess_unknown(unsigned int seen,
+                                 unsigned int area_seen,
+                                 unsigned int area_known,
+                                 unsigned int area)
+{
+  unsigned int guess;
+  assert(area_known <= area);
+  assert(area_seen <= area_known);
+  if (area_known < area) {/*ignorant of geography*/
+    /*The AI guesses the area,
+     *  but the guess is more accurate the more it knows.*/
+    unsigned int unknown = area - area_known;
+    unsigned int area_guess = area_known + myrand(2 * unknown);
+    guess = (seen * area_guess) / area_seen;
+  } else if (area_seen < area) {
+    /*ignorant of current dispositions*/
+    guess = (seen * area) / area_seen;
+  } else {/*knows all*/
+    guess = seen;
+  }
+  assert(seen <= guess);
+  return guess;
+}
+
+/****************************************************************************
+  Adjust wants in the cities needing or building ferries
+****************************************************************************/
+static void adjust_wants(struct player *pplayer, bool shortage, int ferry_want)
+{
+  city_list_iterate(pplayer->cities, acity) {
+    if (get_city_ferry_mode(acity) == CFM_BUILDING) {
+      /*Building a ferry here.*/
+      acity->ai.choice.want = ferry_want;
+    } else if(shortage && get_city_ferry_mode(acity) == CFM_COUNTED
+             && acity->ai.choice.need_boat && ai_fuzzy(pplayer, TRUE)) {
+      /*We have a shortage, and this city will make the shortage worse,
+       so spending gold here would be foolish*/
+      acity->ai.choice.want = MIN(ferry_want - 1,
+                                 acity->ai.choice.want / 2);
+    }
+  } city_list_iterate_end;
+}
+
+/****************************************************************************
+  Initialise the statistics about one sea for one player.
+****************************************************************************/
+static void sea_init(struct sea_stats *sea, unsigned int turns_horizon)
+{
+  unsigned int t;
+
+  assert(sea);
+  assert(turns_horizon <= MAX_TURNS_HORIZON);
+
+  sea->future_psngrs = 0;
+  sea->future_escorts = 0;
+
+  sea->psngrs = 0;
+  sea->escorts = 0;
+  sea->boats = 0;
+  sea->avail_boats = 0;
+
+  sea->hunters_seen = 0;
+  sea->hunters_guess = 0;
+
+  sea->sea_area = 0;
+  sea->n_cities = 0;
+
+  sea->danger_area = 0;
+  sea->danger_area_known = 0;
+  sea->danger_area_seen = 0;
+
+  sea->journey_length = 0;
+
+  sea->ferry_want = 0;
+  
+  for(t = 0; t < turns_horizon; t++) {
+    sea->extra_passengers[t] = 0;
+    sea->extra_escorts[t] = 0;
+  }
+}
+
+/****************************************************************************
+  Add, to the various statistics about a sea for one player,
+  the contribution of a city.
+****************************************************************************/
+static void sea_examine_city(struct player *pplayer,
+                            struct sea_stats *sea,
+                            struct city *acity,
+                            unsigned int turns_horizon)
+{
+  bool is_building_unit;
+  int turns_to_build;
+  unsigned int te;
+  assert(acity);
+
+  if (acity->owner != pplayer->player_no) return;
+
+  is_building_unit = is_unit_choice_type(acity->ai.choice.type);
+  turns_to_build = 
+    is_building_unit?
+    city_turns_to_build(acity, acity->ai.choice.choice, is_building_unit,
+                       TRUE)
+    :FC_INFINITY;
+  assert(0 < turns_to_build);
+  te = MIN(turns_to_build, turns_horizon - 1);
+  
+  assert(get_city_ferry_mode(acity) == CFM_UNPROCESSED);
+  set_city_ferry_mode(acity, CFM_COUNTED);
+
+  sea->n_cities++;
+  if (acity->ai.choice.need_boat) {
+    sea->future_psngrs++;
+    sea->extra_passengers[te]++;
+    sea->ferry_want += acity->ai.choice.want;
+  } else if (is_building_unit
+            && is_warship_type(acity->ai.choice.choice)) {
+    sea->future_escorts++;
+    sea->extra_escorts[te]++;
+  }
+}
+
+/****************************************************************************
+  Add, to the various statistics about a sea for one player,
+  the contribution of a unit.
+****************************************************************************/
+static void sea_examine_unit(struct player *pplayer,
+                            struct sea_stats *sea,
+                            struct unit *aunit,
+                            unsigned int turns_horizon)
+{
+  struct player *owner = get_player(aunit->owner);
+  bool warship = is_warship_type(aunit->type);
+  if (warship && DS_WAR == pplayer_get_diplstate(owner, pplayer)->type) {
+    /*a danger to our shipping*/
+    sea->hunters_seen++;
+  }
+  if (owner != pplayer) {
+    return;
+  } else if (unit_has_role(aunit->type, L_FERRYBOAT)) {
+    sea->boats++;
+    if (aunit->ai.passenger == FERRY_AVAILABLE) {
+      sea->avail_boats++;
+    } else if (aunit->ai.passenger == 0) {
+      freelog(LOG_ERROR, "Passenger field set to 0");
+      sea->avail_boats++;
+    }
+  } else if (aunit->ai.ferryboat == FERRY_WANTED) {
+    sea->psngrs++;
+  } else if (warship) {
+    sea->escorts++;
+  }
+  /*FIXME: also consider air units*/
+}
+
+/****************************************************************************
+  Add, to the various statistics about a sea for one player,
+  the contribution of a tile.
+  The tile may be in the sea or on its shore.
+****************************************************************************/
+static void sea_examine_tile(struct player *pplayer,
+                            struct sea_stats *sea,
+                            struct tile *ptile,
+                            unsigned int turns_horizon)
+{
+  struct city *acity = map_get_city(ptile);
+  bool ocean = is_ocean(map_get_terrain(ptile));
+  bool is_danger_area = ocean
+                        || (acity && DS_WAR == pplayer_get_diplstate(
+                          get_player(acity->owner), pplayer)->type);
+
+  if (ocean) {
+    sea->sea_area++;
+  }
+  if (is_danger_area) {
+    sea->danger_area++;
+  };
+
+  if (ai_handicap(pplayer, H_MAP) && !map_is_known(ptile, pplayer)) {
+    /* The tile is unknown */
+    return;
+  }
+
+  if (is_danger_area) {
+    sea->danger_area_known++;
+  };
+
+  if (ai_handicap(pplayer, H_FOG) 
+      && !map_is_known_and_seen(ptile, pplayer)) {
+    /* The tile is fogged */
+    return;
+  }
+  if (is_danger_area) {
+    sea->danger_area_seen++;
+  };
+
+  if (acity) {
+    sea_examine_city(pplayer, sea, acity, turns_horizon);
+  }
+
+  unit_list_iterate(ptile->units, aunit) {
+    sea_examine_unit(pplayer, sea, aunit, turns_horizon);
+  } unit_list_iterate_end;      
+}
+
+/*
+ * The degree to which the number of target players is reduced
+ * because of alliances, etc.
+ */
+#define TARGET_DILUTION 3
+/*
+ * The following two constants are to ensure that having many waiting
+ * passengers will increase the 'want' for ferries.
+ * WAIT_FERRY_WANT_0:
+ *    The minimum 'want' for ferries if there are any massengers waiting.
+ * WAIT_FERRY_WANT_1:
+ *    The extra 'want' for each currently waiting passenger per boat.
+ */
+#define WAIT_FERRY_WANT_0 200
+#define WAIT_FERRY_WANT_1 400
+/****************************************************************************
+  Compute various statistics about a sea for one player,
+  for use in determining how many ferries to build there.
+
+  *sea:
+     the computed statistics
+  turns_horizon:
+     maximum look-ahead for statistics
+  pfmap:
+     a map of the sea and its shore
+****************************************************************************/
+static void sea_examine_sea(struct player *pplayer,
+                           struct sea_stats *sea,
+                           unsigned int turns_horizon,
+                           struct pf_map *pfmap)
+{
+  unsigned int n_enemy_targets;
+  sea_init(sea, turns_horizon);
+
+  /* We want to consider the place we are currently in too, hence the 
+   * do-while loop */
+  do {/*all tiles in the sea or on its shore*/
+    struct pf_position pos;
+    pf_next_get_position(pfmap, &pos);
+    sea_examine_tile(pplayer, sea, pos.tile, turns_horizon);
+  } while (pf_next(pfmap));
+
+  sea->hunters_guess = guess_unknown(sea->hunters_seen,
+                                    sea->danger_area_seen,
+                                    sea->danger_area_known,
+                                    sea->danger_area);
+
+  ferry_geography(&sea->journey_length);
+
+  /*convert total to average*/
+  sea->ferry_want = sea->ferry_want / MAX(1, sea->future_psngrs);
+
+  /*if there are many waiting passsengers, increase the 'want' for ferries*/
+  if (sea->psngrs) {
+    int waiters_want = WAIT_FERRY_WANT_0
+                       + sea->psngrs * WAIT_FERRY_WANT_1 / MAX(1, sea->boats);
+    sea->ferry_want = MAX(sea->ferry_want, waiters_want);
+  }
+
+  /*spread the hunters out to attack all shipping, not only ours*/
+  n_enemy_targets = MAX(TARGET_DILUTION, game.nplayers - 1)/TARGET_DILUTION;
+  sea->hunters_seen /= n_enemy_targets;
+  sea->hunters_guess /= n_enemy_targets;
+
+  assert(sea->avail_boats <= sea->boats);
+}
+
+/****************************************************************************
+  Choose the cities that will build the boats
+****************************************************************************/
+static void select_ferry_builders(struct player *pplayer,
+                                 unsigned int boats_to_be_built,
+                                 Unit_Type_id boattype)
+{
+  while (boats_to_be_built > 0) {
+    int best = SCORE_NEVER;
+    struct city *bestcity = NULL;
+
+    /*Find the best city to build the next ferry*/
+    city_list_iterate(pplayer->cities, acity) {
+      int score = ferry_builder_score(pplayer, acity, boattype);
+      if (best < score && 0 < score) {
+       assert(is_ocean_near_tile(acity->tile));
+       best = score;
+       bestcity = acity;
+      }
+    } city_list_iterate_end;
+
+    if (!bestcity) {
+      break;
+    }
+
+    /* FIXME: separate a function ai_set_build from 
+     * aicity.c:ai_city_choose_build and use it here */
+    CITY_LOG(LOGLEVEL_BUILDFERRY, bestcity, "will build a boat");
+    bestcity->currently_building = boattype;
+    bestcity->is_building_unit = TRUE;
+    set_city_ferry_mode(bestcity, CFM_BUILDING);
+    boats_to_be_built--;
+  }
+
+  if (0 < boats_to_be_built) {
+    freelog(LOGLEVEL_BUILDFERRY,
+           "Ferries: %s unable to build %d boats",
+           pplayer->name, boats_to_be_built);
+  }
+}
+
+/****************************************************************************
+  A global ferry build selector.  Estimates our want for the boats and finds
+  cities who will build them.
+****************************************************************************/
+void aiferry_choose_build_global(struct player *pplayer)
+{
+  struct city *pcity;
+  /* The worst case is that each of our cities
+   * is on the coast of a different ocean:*/
+  int inf_loop_guard = city_list_size(&pplayer->cities);
+
+  /*The harder the AI, the further ahead it looks:*/
+  unsigned int turns_horizon = MAX(2, MAX_TURNS_HORIZON
+                                      - (2 * MAX_TURNS_HORIZON
+                                         * pplayer->ai.fuzzy / 1000));
+  /* Path-finding stuff */
+  struct pf_map *pfmap;
+  struct pf_parameter parameter;
+
+  /*Choose type of boats to build*/
+  Unit_Type_id boattype = best_role_unit_for_player(pplayer, L_FERRYBOAT);
+  if (boattype == U_LAST) {
+    freelog(LOGLEVEL_BUILDFERRY,
+            "Ferries: %s lacks the technology to build boats",
+            pplayer->name);
+    return;
+  }
+
+  /* Initialize */
+  city_list_iterate(pplayer->cities, acity) {
+    set_city_ferry_mode(acity, CFM_UNPROCESSED);
+  } city_list_iterate_end;
+
+  parameter.turn_mode = TM_NONE;
+  parameter.get_MC = sea_overlap_move; /*an ocean and its shore*/
+  parameter.get_TB = NULL;
+  parameter.get_EC = NULL;
+  parameter.get_costs = NULL;
+  parameter.get_zoc = NULL;
+  parameter.is_pos_dangerous = NULL;
+  BV_CLR_ALL(parameter.unit_flags);
+  parameter.owner = pplayer;
+  parameter.omniscience = TRUE; /*this code handles ignorance itself*/
+  /* These don't matter */
+  parameter.moves_left_initially = 0;
+  parameter.move_rate = 3;
+
+  do {/*each ocean for which we have coastal cities*/
+    struct sea_stats sea;
+    unsigned int boats_to_be_built, shortage;
+
+    /* Find an unprocessed coastal city;
+     * such a city is on the shore of an unprocessed ocean. */
+    pcity = NULL;
+    city_list_iterate(pplayer->cities, acity) {
+      if (get_city_ferry_mode(acity) == CFM_UNPROCESSED 
+          && is_ocean_near_tile(acity->tile)) {
+        pcity = acity;
+        break;
+      }
+    } city_list_iterate_end;
+
+    if (!pcity) {/*no more oceans*/
+      break;
+    }
+
+    /* Get a map of the sea plus shore accessible from pcity*/
+    /* If the city is adjacent to more than one ocean,
+     * or oceans are accessible from the city through channels in allied
+     * cities, this processes all those oceans as one sea.*/
+    parameter.start_tile = pcity->tile;
+    pfmap = pf_create_map(&parameter);
+
+    /* Part 1: measure the demand for boats for this ocean*/
+    sea_examine_sea(pplayer, &sea, turns_horizon, pfmap);
+
+    pf_destroy_map(pfmap);
+
+    freelog(LOGLEVEL_BUILDFERRY,
+           "Sea near %s's %s: journey %d",
+           pplayer->name, pcity->name,
+           sea.journey_length);
+    freelog(LOGLEVEL_BUILDFERRY,
+            "Sea near %s's %s: %d/%d hunters, %d+%d escorts",
+            pplayer->name, pcity->name,
+           sea.hunters_seen, sea.hunters_guess,
+            sea.escorts, sea.future_escorts);
+    freelog(LOGLEVEL_BUILDFERRY, "Sea near %s's %s: %d/%d boats, "
+            "%d+%d/%d waiting, want %d", pplayer->name, pcity->name,
+            sea.avail_boats, sea.boats, sea.psngrs, sea.future_psngrs,
+           sea.n_cities, sea.ferry_want);
+
+    /* Part 2: Decide how many boats we want built */
+    boats_to_be_built = new_boats_to_build(&sea, boattype, turns_horizon);
+    freelog(LOGLEVEL_BUILDFERRY,
+            "Sea near %s's %s: should build %d boats", 
+            pplayer->name, pcity->name, boats_to_be_built);
+    shortage = 0 < boats_to_be_built;
+
+    /* Part 3: Decide where to build the boats */
+    select_ferry_builders(pplayer, boats_to_be_built, boattype);
+    adjust_wants(pplayer, shortage, sea.ferry_want);
+
+    /* Part 4: Cleanup */
+    city_list_iterate(pplayer->cities, acity) {
+      if (get_city_ferry_mode(acity) == CFM_COUNTED
+          || get_city_ferry_mode(acity) == CFM_BUILDING) { 
+        set_city_ferry_mode(acity, CFM_DONE);
+      }
+    } city_list_iterate_end;
+
+    inf_loop_guard--;
+  } while(inf_loop_guard > 0);
+}
diff -ru -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/aiferry.h 
freeciv.PR8992/ai/aiferry.h
--- vendor.freeciv.current/ai/aiferry.h 2004-10-22 23:16:36.000000000 +0100
+++ freeciv.PR8992/ai/aiferry.h 2004-11-05 00:09:09.000000000 +0000
@@ -48,4 +48,10 @@
  */
 void ai_manage_ferryboat(struct player *pplayer, struct unit *punit);
 
+/* 
+ * A function for a centralized (i.e. per-civilization rather than per-city
+ * estimation of need to build more ferries and where to build them
+ */
+void aiferry_choose_build_global(struct player *pplayer);
+
 #endif /* FC__AIFERRY_H */
diff -ru -Xfreeciv.PR8992/diff_ignore 
vendor.freeciv.current/common/aicore/pf_tools.c 
freeciv.PR8992/common/aicore/pf_tools.c
--- vendor.freeciv.current/common/aicore/pf_tools.c     2004-10-22 
23:16:36.000000000 +0100
+++ freeciv.PR8992/common/aicore/pf_tools.c     2004-11-05 00:09:09.000000000 
+0000
@@ -80,9 +80,9 @@
   anywhere, unless we are leaving a friendly city, in which
   case we can move into the ocean but not into the land.
 ************************************************************/
-static int sea_overlap_move(const struct tile *ptile, enum direction8 dir,
-                           const struct tile *ptile1,
-                           struct pf_parameter *param)
+int sea_overlap_move(const struct tile *ptile, enum direction8 dir,
+                    const struct tile *ptile1,
+                    struct pf_parameter *param)
 {
   if (is_ocean(ptile->terrain)) {
     return SINGLE_MOVE;
diff -ru -Xfreeciv.PR8992/diff_ignore 
vendor.freeciv.current/common/aicore/pf_tools.h 
freeciv.PR8992/common/aicore/pf_tools.h
--- vendor.freeciv.current/common/aicore/pf_tools.h     2004-10-22 
23:16:36.000000000 +0100
+++ freeciv.PR8992/common/aicore/pf_tools.h     2004-11-05 00:09:09.000000000 
+0000
@@ -29,6 +29,10 @@
 enum tile_behavior no_fights(const struct tile *ptile, enum known_type known,
                             struct pf_parameter *param);
 
+int sea_overlap_move(const struct tile *ptile, enum direction8 dir,
+                    const struct tile *ptile1,
+                    struct pf_parameter *param);
+
 #define pf_iterator(map, position) {                       \
   struct pf_position position;                             \
   while (pf_next(map)) {                                   \
diff -ru -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/common/city.h 
freeciv.PR8992/common/city.h
--- vendor.freeciv.current/common/city.h        2004-10-22 23:16:36.000000000 
+0100
+++ freeciv.PR8992/common/city.h        2004-11-05 00:09:08.000000000 +0000
@@ -161,6 +161,16 @@
 #define ASSERT_REAL_CHOICE_TYPE(type)                                    \
         assert(type >= 0 && type < CT_LAST /* && type != CT_NONE */ );
 
+/*
+ * Used while determining how many and where to build ferries.
+ */  
+enum city_ferry_mode {
+  CFM_UNPROCESSED,
+  CFM_COUNTED,
+  CFM_BUILDING,
+  CFM_DONE
+};
+
 
 struct ai_choice {
   int choice;            /* what the advisor wants */
@@ -212,6 +222,7 @@
 
   int worth; /* Cache city worth here, sum of all weighted incomes */
   int next_recalc; /* Only recalc every Nth turn */
+  enum city_ferry_mode ferry_mode;
 };
 
 struct city {
diff -ru -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/diff_ignore 
freeciv.PR8992/diff_ignore
--- vendor.freeciv.current/diff_ignore  2004-10-22 23:16:37.000000000 +0100
+++ freeciv.PR8992/diff_ignore  2004-11-05 00:09:10.000000000 +0000
@@ -17,6 +17,7 @@
 *~
 .#*
 .deps
+.svn
 CVS
 Freeciv.h
 Makefile