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

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

On Sat, Dec 07, 2002 at 09:10:33AM -0800, Gregory Berkolaiko via RT wrote:
> 
> It's a very good patch but there are some issues with it.
> 
> I won't comment on minor points, they can be fixed later.
> 
> I think that calculation of a tile's goodness should be separated into a 
> separate function, which calls liekly_ocean and applies all the weights.  
> Then this function can not only be called from Part2 but also from 
> Part3.

Take a look at the attachment. It does a few things different from my earlier 
patches:

* explorer_desirable(...) calculates how much we want to visit a tile. 
Reachability could be considered in here.
* I added a function get_range_at(x, y, punit) to calculate what the vision 
range of a particular unit would be if it were at the given (x, y) location. We 
need this since the range is required both in likely_ocean and Part 3 of 
ai_manage_explorer. I removed the code that used to do this (badly) in 
ai_manage_explorer.

I also replaced a square_iterate(x, y, 1, ...) that existed before my patch 
with adjc_iterate(x, y, ...).

> Also, it surfaced recently that uncovering tiles that are reachable from 
> your cities makes a tremendous difference on the AIs performace.  It is 
> also helpful to humans.  So this should also be factored into the 
> calculation IMO.
> 
> G.
> 
> P.S.  When attaching a patch, can you make sure it is attached as a 
> plain-text?  Makes it easier to read...

Here's the text of the patch. I'll attach it also.

Index: ai/aiunit.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/ai/aiunit.c,v
retrieving revision 1.232
diff -u -3 -p -r1.232 aiunit.c
--- ai/aiunit.c 2002/12/04 13:34:26     1.232
+++ ai/aiunit.c 2002/12/08 16:22:46
@@ -256,6 +256,146 @@ 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 of a given unit, in its current situation.
+**************************************************************************/
+
+int get_range_at(int x, int y, struct unit *punit)
+{
+  int range;
+  /* Get the range */
+
+  /* I believe I have fixed this FIXME. --CJM
+   *
+   * 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(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.
+Store the number of unknown tiles that would be revealed into unknown)
+**************************************************************************/
+
+int explorer_desirable(int x, int y, struct player *pplayer, 
+                      struct unit *punit, int *unknown)
+{
+  /* relative value of exploring terrains which are the same type
+   * as us (ie land for land units, ocean for boats). */
+  const int same_score = 5;
+  const int different_score = 60;
+  const int known_same_score = 2;
+  const int known_different_score = 25;
+
+  int land_score, ocean_score, known_land_score, known_ocean_score;
+  int ocean;
+  int range;
+  int desirable = 0;
+  (*unknown) = 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 = same_score;
+    ocean_score = different_score;
+    known_land_score = known_same_score;
+    known_ocean_score = known_different_score;
+  } else {
+    land_score = different_score;
+    ocean_score = same_score;
+    known_land_score = known_different_score;
+    known_ocean_score = known_same_score;
+  }
+
+  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. 
+       */
+      if(ocean > 50) {
+       desirable += ocean_score;
+      } else if(ocean < 50) {
+       desirable += land_score;
+      }
+    } else {
+      if(ocean > 50) {
+       desirable += known_ocean_score;
+      } else if(ocean < 50) {
+       desirable += known_land_score;
+      }
+    }
+  } square_iterate_end;
+
+  return desirable;
+}
+
+/**************************************************************************
 Handle eXplore mode of a unit (explorers are always in eXplore mode for AI) -
 explores unknown territory, finds huts.
 
@@ -273,19 +413,6 @@ bool ai_manage_explorer(struct unit *pun
   /* 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 */
 
   if (punit->activity != ACTIVITY_IDLE) {
@@ -369,21 +496,26 @@ 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 adjacent water */
+    int most_desirable = 0;
+
     /* Desired destination */
     int best_x = -1, best_y = -1;
 
     /* Evaluate all adjacent tiles. */
     
-    square_iterate(x, y, 1, x1, y1) {
+    adjc_iterate(x, y, 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;
+      int desirable;
+
+      desirable = explorer_desirable(x1, y1, pplayer, punit, &unknown);
 
-      if (unknown > most_unknown) {
+      /* regardless how desirable a tile is, if we don't discover
+       * any new territory, don't go there. */
+      if (unknown > 0 && (desirable > most_desirable)) {
         if (unit_flag(punit, F_TRIREME)
             && trireme_loss_pct(pplayer, x1, y1) != 0)
           continue;
@@ -406,11 +538,14 @@ bool ai_manage_explorer(struct unit *pun
         if (is_barbarian(pplayer) && map_has_special(x1, y1, S_HUT))
           continue;
           
-        most_unknown = unknown;
+       if(unknown > most_unknown) {
+         most_unknown = unknown;
+       }
+       most_desirable = desirable;
         best_x = x1;
         best_y = y1;
       }
-    } square_iterate_end;
+    } adjc_iterate_end;
 
     if (most_unknown > 0) {
       /* We can die because easy AI may stumble on huts and so disappear in the
@@ -474,6 +609,7 @@ bool ai_manage_explorer(struct unit *pun
         /* Number of unknown tiles in vision range around this tile */
         int unknown = 0;
         
+       range = get_range_at(x1, y1, punit);
         square_iterate(x1, y1, range, x2, y2) {
           if (!map_get_known(x2, y2, pplayer))
             unknown++;


-- 
+-----------------------------------------------------------------
| PGP http://www.eng.uwaterloo.ca/student/cjmorlan/public-key.pgp
| Cameron Morland             ----             Cameron@xxxxxxxxxx
|
| First they ignore you, then they laugh at you, 
| then they fight you, then you win.
|     --Gandhi
+-----------------------------------------------------------------

Index: ai/aiunit.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/ai/aiunit.c,v
retrieving revision 1.232
diff -u -3 -p -r1.232 aiunit.c
--- ai/aiunit.c 2002/12/04 13:34:26     1.232
+++ ai/aiunit.c 2002/12/08 16:22:46
@@ -256,6 +256,146 @@ 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 of a given unit, in its current situation.
+**************************************************************************/
+
+int get_range_at(int x, int y, struct unit *punit)
+{
+  int range;
+  /* Get the range */
+
+  /* I believe I have fixed this FIXME. --CJM
+   *
+   * 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(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.
+Store the number of unknown tiles that would be revealed into unknown)
+**************************************************************************/
+
+int explorer_desirable(int x, int y, struct player *pplayer, 
+                      struct unit *punit, int *unknown)
+{
+  /* relative value of exploring terrains which are the same type
+   * as us (ie land for land units, ocean for boats). */
+  const int same_score = 5;
+  const int different_score = 60;
+  const int known_same_score = 2;
+  const int known_different_score = 25;
+
+  int land_score, ocean_score, known_land_score, known_ocean_score;
+  int ocean;
+  int range;
+  int desirable = 0;
+  (*unknown) = 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 = same_score;
+    ocean_score = different_score;
+    known_land_score = known_same_score;
+    known_ocean_score = known_different_score;
+  } else {
+    land_score = different_score;
+    ocean_score = same_score;
+    known_land_score = known_different_score;
+    known_ocean_score = known_same_score;
+  }
+
+  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. 
+       */
+      if(ocean > 50) {
+       desirable += ocean_score;
+      } else if(ocean < 50) {
+       desirable += land_score;
+      }
+    } else {
+      if(ocean > 50) {
+       desirable += known_ocean_score;
+      } else if(ocean < 50) {
+       desirable += known_land_score;
+      }
+    }
+  } square_iterate_end;
+
+  return desirable;
+}
+
+/**************************************************************************
 Handle eXplore mode of a unit (explorers are always in eXplore mode for AI) -
 explores unknown territory, finds huts.
 
@@ -273,19 +413,6 @@ bool ai_manage_explorer(struct unit *pun
   /* 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 */
 
   if (punit->activity != ACTIVITY_IDLE) {
@@ -369,21 +496,26 @@ 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 adjacent water */
+    int most_desirable = 0;
+
     /* Desired destination */
     int best_x = -1, best_y = -1;
 
     /* Evaluate all adjacent tiles. */
     
-    square_iterate(x, y, 1, x1, y1) {
+    adjc_iterate(x, y, 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;
+      int desirable;
+
+      desirable = explorer_desirable(x1, y1, pplayer, punit, &unknown);
 
-      if (unknown > most_unknown) {
+      /* regardless how desirable a tile is, if we don't discover
+       * any new territory, don't go there. */
+      if (unknown > 0 && (desirable > most_desirable)) {
         if (unit_flag(punit, F_TRIREME)
             && trireme_loss_pct(pplayer, x1, y1) != 0)
           continue;
@@ -406,11 +538,14 @@ bool ai_manage_explorer(struct unit *pun
         if (is_barbarian(pplayer) && map_has_special(x1, y1, S_HUT))
           continue;
           
-        most_unknown = unknown;
+       if(unknown > most_unknown) {
+         most_unknown = unknown;
+       }
+       most_desirable = desirable;
         best_x = x1;
         best_y = y1;
       }
-    } square_iterate_end;
+    } adjc_iterate_end;
 
     if (most_unknown > 0) {
       /* We can die because easy AI may stumble on huts and so disappear in the
@@ -474,6 +609,7 @@ bool ai_manage_explorer(struct unit *pun
         /* Number of unknown tiles in vision range around this tile */
         int unknown = 0;
         
+       range = get_range_at(x1, y1, punit);
         square_iterate(x1, y1, range, x2, y2) {
           if (!map_get_known(x2, y2, pplayer))
             unknown++;

pgpaZuDvkFLPq.pgp
Description: PGP signature