[freeciv-ai] Re: (PR#2477) Improved Auto-Explore

["cameron@xxxxxxxxxx via RT" <rt@xxxxxxxxxxxxxx>]

On Fri, Dec 13, 2002 at 02:06:16AM -0800, aas02101@xxxxxxxxxxxxxxxxxx via RT 
wrote:
> I both looked at and tested your patch.  The behaviour is very nice!

Thanks.

> Do you think you can use explorer_desirable function in the Part3 of the
> function as well?  I think it can and should be done, with an appropriate
> weighting for the distance.  This you'll need to tweak, so that the explorer
> doesn't go across the whole map to uncover one ocean tile if there are plenty
> non-ocean ones around.

It still requires some tweaking of values, but the idea is there. It will 
mostly be a matter of judgement as to what values are right. (Actually I 
figured out how to let one AI play on its own; I'm running a whole bunch of 
trials (1000), and recording the score at 1000 AD. If I can show a 
statistically significant improvement by fiddling with the numbers, I know the 
new value is better.)

I greatly simplified part 3; it now uses explorer_desirable, but stores the 
output as a double and reduces the desirability of tiles depending on their 
distance. I didn't want to use integers, since it needs to be able to order 
preference of tiles, even if they are really bad (0 < desirability < 1).

> Also, it is very useful to uncover tiles that are within city radius of one of
> player's cities (especially so for the AI, it seems).  Can you add a special
> weighting for it in explorer_desirable ?  To check this condition, you can
> city_radius_iterate around the tile and see if you hit a city.

I used is_friendly_city_near(pplayer, x, y), which will tend to explore a short 
distance around cities. Not quite the same result, but not significantly worse 
and much simpler code.

I also fixed a bug that could theoretically come up where exploring an tile 
which is unknown but is equally likely to be land or water was accidentally 
assigned a desirability of zero. So now an unknown tile is assigned a certain 
value, then a value is added to it, depending on if it's water or land. If we 
don't know, we don't add anything additional.

Exploring units should not enter cities, even if they "can" (diplomats and 
caravans). I removed that code.

> As for get_range function, it is ok, you indeed fixed the FIXME so you can 
> merge
> two comments into one explaining why this function exists and also fix the
> header comment of this function.  Personally I think this fortress effect 
> should
> be altogether ignored when exploring.  I don't think anyone ever enables
> watchtowers and/or builds fortresses.

Watchtowers are enabled by default, with a range of 2.

As it turns out, in my rewriting of part 3, I no longer use get_range_at; it is 
only used in explorer_desirable. I suppose I could inline it, but I think it 
makes sense to leave it, and the compiler will optimize it out of existence 
anyway.

Most of the checks that were present in part 2 but missing in part 3 have been 
added to explorer_desirable().

Index: ai/aiunit.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/ai/aiunit.c,v
retrieving revision 1.239
diff -u -3 -p -r1.239 aiunit.c
--- ai/aiunit.c 2002/12/11 10:39:40     1.239
+++ ai/aiunit.c 2002/12/14 01:14:42
@@ -256,6 +256,170 @@ static bool tile_is_accessible(struct un
 }
  
 /**************************************************************************
+  Determine if a tile is likely to be water, given information that
+  the player actually has. Return the % certainty that it's water
+  (100 = certain, 50 = no idea, 0 = certainly not).
+**************************************************************************/
+int likely_ocean(int x, int y, struct player *pplayer)
+{
+  int sum = 0;
+
+  if(map_get_known(x,y,pplayer)) {
+    /* we've seen the tile already. */
+    if(map_get_terrain(x,y) == T_OCEAN) {
+      return 100;
+    } else {
+      return 0;
+    }
+  }
+  
+  /* Now we're going to do two things at once. We're going to see if
+   * we know any cardinally adjacent tiles, since knowing one will
+   * give a guaranteed value for the centre tile. Also, we're going
+   * to count the non-cardinal (diagonal) tiles, and see how many
+   * of them are ocean, which gives a guess for the ocean-ness of 
+   * the centre tile. */
+  sum = 50;
+  adjc_dir_iterate(x, y, x1, y1, dir) {
+    if(map_get_known(x1, y1, pplayer)) {
+      if(DIR_IS_CARDINAL(dir)) {
+       /* If a tile is cardinally adjacent, we can tell if the 
+        * central tile is ocean or not by the appearance of
+        * the adjacent tile. So, given that we can tell, 
+        * it's fair to look at the actual tile. */
+       if(map_get_terrain(x, y) == T_OCEAN) {
+         return 100;
+       } else {
+         return 0;
+       }
+      } else {
+       /* We're diagonal to the tile in question. So we can't
+        * be sure what the central tile is, but the central
+        * tile is likely to be the same as the nearby tiles. 
+        * If all 4 are water, return 90; if all 4 are land, 
+        * return 10. */
+       if(map_get_terrain(x1, y1) == T_OCEAN) {
+         sum += 10;
+       } else {
+         sum -= 10;
+       }
+      }
+    }
+  } adjc_dir_iterate_end;
+  return sum;
+}
+
+/**************************************************************************
+Return the vision range that a unit would experience at the given location.
+**************************************************************************/
+
+int get_range_at(int x, int y, struct unit *punit)
+{
+  int range;
+  /* Check if there is a watchtower at the given tile, and return the 
+   * vision range that the unit would have as a result. */
+  if (unit_profits_of_watchtower(punit)
+      && map_has_special(x, y, S_FORTRESS)) {
+    range = get_watchtower_vision(punit);
+  } else {
+    range = unit_type(punit)->vision_range;
+  }
+  
+  return range;
+}
+
+/**************************************************************************
+Return a value indicating how desirable it is to explore the given tile.
+**************************************************************************/
+
+int explorer_desirable(int x, int y, struct player *pplayer, 
+                      struct unit *punit)
+{
+  /* relative value of exploring terrains which are the same type
+   * as us (ie land for land units, ocean for boats). */
+  const int base_score = 5;
+  const int different_score = 60;
+  const int known_base_score = 0;
+  const int known_different_score = 16;
+  const int friendly_city_desirability = 181;
+
+  int land_score, ocean_score, known_land_score, known_ocean_score;
+  int ocean;
+  int range;
+  int desirable = 0;
+  int unknown = 0;
+  int continent;
+
+  /* Localize the unit */
+  if(is_ground_unit(punit)) {
+    continent = map_get_continent(punit->x, punit->y);
+  } else {
+    continent = 0;
+  }
+
+  /* First do some checks that would make a tile completely non-desirable.
+   * If we're a trireme and we could die at the given tile, or if there
+   * is a city on the tile, or if the 
+   * tile is on a different continent, or if we're a barbarian and
+   * the tile has a hut, don't go there. */
+  if((unit_flag(punit, F_TRIREME) && trireme_loss_pct(pplayer, x, y) != 0)
+     || map_get_city(x, y)
+     || map_get_continent(x, y) != continent
+     || (is_barbarian(pplayer) && map_has_special(x, y, S_HUT))) {
+    return 0;
+  }
+
+  /* What value we assign to the number of land and water tiles
+   * depends on if we're a land or water unit. */
+  if(!is_sailing_unit(punit)) {
+    land_score = 0;
+    ocean_score = different_score;
+    known_land_score = 0;
+    known_ocean_score = known_different_score;
+  } else {
+    land_score = different_score;
+    ocean_score = 0;
+    known_land_score = known_different_score;
+    known_ocean_score = 0;
+  }
+
+  range = get_range_at(x, y, punit);
+  square_iterate(x, y, range, x1, y1) {
+    ocean = likely_ocean(x1,y1, pplayer);
+    if (!map_get_known(x1, y1, pplayer)) {
+      unknown++;
+      /* if it's a tile we don't know, weight the value of
+       * exploring it by if it's likely to be ocean or not. 
+       */
+      desirable += base_score;
+      if(ocean > 50) {
+       desirable += ocean_score;
+      } else if(ocean < 50) {
+       desirable += land_score;
+      }
+    } else {
+      desirable += known_base_score;
+      if(ocean > 50) {
+       desirable += known_ocean_score;
+      } else if(ocean < 50) {
+       desirable += known_land_score;
+      }
+    }
+  } square_iterate_end;
+
+  if(is_friendly_city_near(pplayer, x, y)) {
+    desirable += friendly_city_desirability;
+  }
+
+  /* Now make sure we'll uncover at least one unexplored tile. */
+  if(unknown <= 0) {
+    desirable = 0;
+  }
+
+  return desirable;
+}
+
+/**************************************************************************
 Handle eXplore mode of a unit (explorers are always in eXplore mode for AI) -
 explores unknown territory, finds huts.
 
@@ -268,23 +432,6 @@ bool ai_manage_explorer(struct unit *pun
   int x = punit->x, y = punit->y;
   /* Continent the unit is on */
   int continent;
-  /* Unit's speed */
-  int move_rate = unit_move_rate(punit);
-  /* Range of unit's vision */
-  int range;
-
-  /* Get the range */
-  /* FIXME: The vision range should NOT take into account watchtower benefit.
-   * Now it is done in a wrong way: the watchtower bonus is computed locally,
-   * at the point where the unit is, and then it is applied at a faraway
-   * location, as if there is a watchtower there too. --gb */
-
-  if (unit_profits_of_watchtower(punit)
-      && map_has_special(punit->x, punit->y, S_FORTRESS)) {
-    range = get_watchtower_vision(punit);
-  } else {
-    range = unit_type(punit)->vision_range;
-  }
 
   /* Idle unit */
 
@@ -367,58 +514,36 @@ bool ai_manage_explorer(struct unit *pun
    */
   
   while (punit->moves_left > 0) {
-    /* Best (highest) number of unknown tiles adjacent (in vision range) */
-    int most_unknown = 0;
+    /* most desirable tile, given nearby water, cities, etc. */
+    int most_desirable = 0; 
     /* Desired destination */
     int best_x = -1, best_y = -1;
 
     /* Evaluate all adjacent tiles. */
-    
-    square_iterate(x, y, 1, x1, y1) {
-      /* Number of unknown tiles in vision range around this tile */
-      int unknown = 0;
-      
-      square_iterate(x1, y1, range, x2, y2) {
-        if (!map_get_known(x2, y2, pplayer))
-          unknown++;
-      } square_iterate_end;
-
-      if (unknown > most_unknown) {
-        if (unit_flag(punit, F_TRIREME)
-            && trireme_loss_pct(pplayer, x1, y1) != 0)
-          continue;
-        
-        if (map_get_continent(x1, y1) != continent)
-          continue;
-        
-        if (could_unit_move_to_tile(punit, x1, y1) == 0) {
-          continue;
-        }
+    adjc_iterate(x, y, x1, y1) {
+      int desirable;
 
-        /* We won't travel into cities, unless we are able to do so - diplomats
-         * and caravans can. */
-        /* FIXME/TODO: special flag for this? --pasky */
-        /* FIXME: either comment or code is wrong here :-) --pasky */
-        if (map_get_city(x1, y1) && (unit_flag(punit, F_DIPLOMAT) 
-                                     || unit_flag(punit, F_TRADE_ROUTE)))
-          continue;
+      /* we can't move there anyway, don't consider how good it might be. */
+      if(!could_unit_move_to_tile(punit, x1, y1)) {
+       continue;
+      }
 
-        if (is_barbarian(pplayer) && map_has_special(x1, y1, S_HUT))
-          continue;
-          
-        most_unknown = unknown;
-        best_x = x1;
-        best_y = y1;
+      desirable = explorer_desirable(x1, y1, pplayer, punit);
+
+      if(desirable > most_desirable) {
+       most_desirable = desirable;
+       best_x = x1;
+       best_y = y1;
       }
-    } square_iterate_end;
+    } adjc_iterate_end;
 
-    if (most_unknown > 0) {
+    if (most_desirable > 0) {
       /* We can die because easy AI may stumble on huts and so disappear in the
        * wilderness - unit_id is used to check this */
       int unit_id = punit->id;
       bool broken = TRUE; /* failed movement */
       
-      /* Some tile have unexplored territory adjacent, let's move there. */
+      /* Some tile has unexplored territory adjacent, let's move there. */
 
       /* ai_unit_move for AI players, handle_unit_move_request for humans */
       if ((pplayer->ai.control && ai_unit_move(punit, best_x, best_y))
@@ -452,57 +577,41 @@ bool ai_manage_explorer(struct unit *pun
    */
 
   {
-    /* Best (highest) number of unknown tiles adjectent (in vision range) */
-    int most_unknown = 0;
+    const double distance_attenuation = 0.9;
+
+    /* most desirable tile, given nearby water, cities, etc. */
+    double most_desirable = 0;
     /* Desired destination */
     int best_x = -1, best_y = -1;
   
     generate_warmap(map_get_city(x, y), punit);
 
-    /* XXX: There's some duplicate code here, but it's several tiny pieces,
-     * impossible to group together and not worth their own function
-     * separately. --pasky */
-    
     whole_map_iterate(x1, y1) {
-      /* The actual map tile */
-      struct tile *ptile = map_get_tile(x1, y1);
-      
-      if (ptile->continent == continent
-          && !is_non_allied_unit_tile(ptile, pplayer)
-          && !is_non_allied_city_tile(ptile, pplayer)
-          && tile_is_accessible(punit, x1, y1)) {
-        /* Number of unknown tiles in vision range around this tile */
-        int unknown = 0;
-        
-        square_iterate(x1, y1, range, x2, y2) {
-          if (!map_get_known(x2, y2, pplayer))
-            unknown++;
-        } square_iterate_end;
-        
-        if (unknown > 0) {
-#define COSTWEIGHT 9
-          /* How far it's worth moving away */
-          int threshold = THRESHOLD * move_rate;
-          
-          if (is_sailing_unit(punit))
-            unknown += COSTWEIGHT * (threshold - warmap.seacost[x1][y1]);
-          else
-            unknown += COSTWEIGHT * (threshold - warmap.cost[x1][y1]);
-          
-          /* FIXME? Why we don't do same tests like in part 2? --pasky */
-          if (((unknown > most_unknown) ||
-               (unknown == most_unknown && myrand(2) == 1))
-              && !(is_barbarian(pplayer) && tile_has_special(ptile, S_HUT))) {
-            best_x = x1;
-            best_y = y1;
-            most_unknown = unknown;
+      double desirable;
+
+      desirable = explorer_desirable(x1, y1, pplayer, punit);
+
+      if (desirable > 0) {
+       /* now we want to reduce the desirability of far-away
+        * tiles, without reducing it to zero, regardless how
+        * far away it is. So we use floating point numbers. */
+       if (is_sailing_unit(punit))
+         desirable *= pow(distance_attenuation, warmap.seacost[x1][y1]);
+       else
+         desirable *= pow(distance_attenuation, warmap.cost[x1][y1]);
+       
+       if (((desirable > most_desirable) ||
+            (desirable == most_desirable && myrand(2) == 1))) {
+         best_x = x1;
+         best_y = y1;
+         if(desirable > most_desirable) {
+           most_desirable = desirable;
           }
-#undef COSTWEIGHT
         }
       }
     } whole_map_iterate_end;
 
-    if (most_unknown > 0) {
+    if (most_desirable > 0) {
       /* Go there! */
       if (!ai_unit_goto(punit, best_x, best_y)) {
         return FALSE;

pgpZumsHtZcXK.pgp
Description: PGP signature