[Freeciv-Dev] (PR#9596) Better nation selection

["Mateusz Stefek" <mstefek@xxxxxxxxx>]

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

About a year ago I wrote a patch which made AI select nation from the  
same class as user. (PR#3751)

Unfortunately it doesn't work as I expected. When I choose Persians AI  
picks Boers just because these nations are in the same class  
(historical).
If AI knew something about the history of the real world it could  
probably choose more inteligently.
Attached patch adds two new fields into the nation struct:  
founding_year and collapse_year. When AI chooses nation it tries to  
minimalize the sum of "time distance" between nations.

The second patch contains updated nation files. Most dates comes from  
wikipedia (I'm not historian)
There will be probably some controversy:

- I assumed that Tolkien placed his stories in -100000BC - -50000BC  
despite that Tolkien's fans would probably place them 7000 years ago. I  
needed these "nations" to be really far away from human nations.
-Bavaria
-Catalonia
-Cornwall (I haven't found any date)
-Estonia
-Ethiopia (I included also ancient Ethiopia)
-Finland
-Ireland
-Israel (Legend describes modern Israel, but there are ancient Kings in  
ruleset)
-Italy
-Serbia
-Silesia
Please correct me or send more acurate dates if you know them.
--
mateusz



----------------------------------------------------------------------
Laczysz sie przez modem? Mamy dla Ciebie bonusy!
>>> http://link.interia.pl/f1826

nations2.diff
Description: Binary data

diff -ur -Xdiff_ignore freeorig/common/nation.h freeciv/common/nation.h
--- freeorig/common/nation.h    2004-07-26 09:46:11.000000000 +0200
+++ freeciv/common/nation.h     2004-08-03 10:20:50.947581344 +0200
@@ -91,6 +91,10 @@
   int init_techs[MAX_NUM_TECH_LIST];
   int init_buildings[MAX_NUM_BUILDING_LIST];
 
+  /* Historical dates which helps AI to choose nations */
+  int founding_year;
+  int collapse_year;
+
   /* Following basically disabled -- Syela */
   /* Note the client doesn't use/have these. */
   struct {
diff -ur -Xdiff_ignore freeorig/server/ruleset.c freeciv/server/ruleset.c
--- freeorig/server/ruleset.c   2004-07-26 09:46:13.000000000 +0200
+++ freeciv/server/ruleset.c    2004-08-03 10:20:50.952580584 +0200
@@ -2478,6 +2478,19 @@
     if (check_strlen(pl->legend, MAX_LEN_MSG, "Legend '%s' is too long")) {
       pl->legend[MAX_LEN_MSG - 1] = '\0';
     }
+
+    /* Historic period It helps AI to choose nations more intelligently*/
+    pl->founding_year = 
+        secfile_lookup_int_default(file, -4000, "%s.founding_year", sec[i]);
+    pl->collapse_year = 
+        secfile_lookup_int_default(file, pl->founding_year + 10000,
+                                   "%s.collapse_year", sec[i]);
+    if (pl->founding_year > pl->collapse_year) {
+      freelog(LOG_ERROR, "founding_year is greater than collapse_year "
+              "for %s. Changing collapse_year to %d", pl->name, 
+              pl->founding_year + 100);
+      pl->collapse_year = pl->founding_year + 100;
+    }
   }
 
   /* Calculate parent nations.  O(n^2) algorithm. */
diff -ur -Xdiff_ignore freeorig/server/srv_main.c freeciv/server/srv_main.c
--- freeorig/server/srv_main.c  2004-08-03 08:52:55.000000000 +0200
+++ freeciv/server/srv_main.c   2004-08-03 10:32:31.018154440 +0200
@@ -1092,68 +1092,68 @@
     }
   }
 }
-
 /**************************************************************************
-  If all players have chosen the same nation class, return
-  this class, otherwise return NULL.
-**************************************************************************/  
-static char* find_common_class(void) 
+   Sum of historical distance between given nation and nations selected by
+   other players. Distance is measured in years between collapse of one nation
+   and foundation of the other. If historical periods overlap distance is 0.
+   AI tries to minimaze this in select_random_nation.
+   So if you pick Persians AI will prefer Greeks to Americans.
+**************************************************************************/
+static int historical_distance(struct nation_type* nation1)
 {
-  char* class = NULL;
-  struct nation_type* nation;
-
+  int distance = 0;
+  struct nation_type* nation2;
+   
   players_iterate(pplayer) {
     if (pplayer->nation == NO_NATION_SELECTED) {
-      /* still undecided */
-      continue;  
-    }
-    nation = get_nation_by_idx(pplayer->nation);
-    assert(nation->class != NULL);
-    if (class == NULL) {
-       /* Set the class. */
-      class = nation->class;
-    } else if (strcmp(nation->class, class) != 0) {
-      /* Multiple classes are already being used. */
-      return NULL;
+      /* still undecided, distance = 0 */
+      continue;
     }
+    nation2 = get_nation_by_idx(pplayer->nation);
+    if (nation2->collapse_year < nation1->founding_year) {
+      distance += nation1->founding_year - nation2->collapse_year;
+    } else if (nation2->founding_year > nation1->collapse_year) {
+      distance += nation2->founding_year - nation1->collapse_year;
+    }    
   } players_iterate_end;
-
-  return class;
+  return distance;
 }
 
 /**************************************************************************
-  Select a random available nation.  If 'class' is non-NULL, then choose
-  a nation from that class if possible.
+  Select a random available nation. Adjust historical period intelligently.
 **************************************************************************/
-static Nation_Type_id select_random_nation(const char* class)
+static Nation_Type_id select_random_nation()
 {
-  Nation_Type_id i, available[game.playable_nation_count];
-  int count = 0;
-
-  /* Determine which nations are available. */
+  Nation_Type_id i;
+  int count;
+  int distance;
+  int lowest_distance = 999999999;
+  struct nation_type* nation;
+  Nation_Type_id considered[game.playable_nation_count];
+  
+  /* find lowest possible value of historical_distance in available nations */
   for (i = 0; i < game.playable_nation_count; i++) {
-    struct nation_type *nation = get_nation_by_idx(i);
-
-    if (nations_available[i]
-       && (class == NULL || strcmp(nation->class, class) == 0)) {
-      available[count] = i;
-      count++;
+    nation = get_nation_by_idx(i);
+    if (nations_available[i]) {
+      lowest_distance = MIN(lowest_distance, historical_distance(nation));
     }
   }
-
-  /* Handle the case where no nations are possible. */
-  if (count == 0) {
-    if (class) {
-      /* Try other classes. */
-      return select_random_nation(NULL);
+  
+  /* consider only nations with lowest historical_distance
+   * There is 50 years of flexibility and some randomness added */
+  for (count = i = 0; i < game.playable_nation_count; i++) {
+    if (nations_available[i]) {
+      nation = get_nation_by_idx(i);
+      distance = historical_distance(nation);
+      if (myrand(historical_distance(nation) - lowest_distance + 1) < 50) {
+        considered[count++] = i;
+      }
     }
-
-    /* Or else return an invalid value. */
-    return NO_NATION_SELECTED;
-  }
-
-  /* Then pick one. */
-  return available[myrand(count)];
+  } 
+  
+  assert(count > 0);
+  
+  return considered[myrand(count)];
 }
 
 /**************************************************************************
@@ -1184,12 +1184,10 @@
   char player_name[MAX_LEN_NAME];
   struct player *pplayer;
   int i, old_nplayers;
-  char* common_class;
 
   /* Select nations for AI players generated with server
    * 'create <name>' command
    */
-  common_class = find_common_class();
   for (i=0; i<game.nplayers; i++) {
     pplayer = &game.players[i];
     
@@ -1212,7 +1210,7 @@
       continue;
     }
 
-    nation = select_random_nation(common_class);
+    nation = select_random_nation();
     if (nation == NO_NATION_SELECTED) {
       freelog(LOG_NORMAL,
              _("Ran out of nations.  AI controlled player %s not created."),
@@ -1236,13 +1234,6 @@
     announce_ai_player(pplayer);
   }
   
-  /* We do this again, because user could type:
-   * >create Hammurabi
-   * >set aifill 5
-   * Now we are sure that all AI-players will use historical class
-   */
-  common_class = find_common_class();
-
   /* Create and pick nation and name for AI players needed to bring the
    * total number of players to equal game.aifill
    */
@@ -1262,7 +1253,7 @@
   }
 
   for(;game.nplayers < game.aifill;) {
-    nation = select_random_nation(common_class);
+    nation = select_random_nation();
     assert(nation != NO_NATION_SELECTED);
     mark_nation_as_used(nation);
     pick_ai_player_name(nation, player_name);