[Freeciv-Dev] Re: Cache win_chance in get_defender(attacker) (PR#1269)

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Fri, Feb 22, 2002 at 11:00:45PM +0100, Raimar Falke wrote:
> There may be other cases. The function for each case have to answer:
>  - how are my chances of success
>  - what happens if I win (which units gets destroys, city captured)
>  - what happens if I loose (which units gets destroys, city captured)
> 
> IMHO the best and most flexible solution would be to design a
> combat_unit struct which holds the necessary information of a unit for
> the combat and use two lists of such pseudo units for simulation. So I
> would design something like:
>  result_list = simulate(struct combat_unit *attacker_list,
>                       int attacker_x, int attacker_y,
>                       struct combat_unit *defender_list,
>                       int defender_x, int defender_y);
> 
> and result_list would contain entries like:
>  chance=0.90, destroyed_attackers=[], destroyed_defenders=[combat_unit_1]
>  chance=0.12, destroyed_attackers=[combat_unit_2], 
> destroyed_defenders=[combat_unit_1]
> 
> Such detailed analyses is needed IMHO because it may happen that
> value(combat_unit_2) >> value(combat_unit_1). So that a chance of 12%
> for destroying a mech. inf. (combat_unit_2) with your archer
> (combat_unit_1) is very good.

The more I think about it the more I like it. In the following I tried
to write down the interface.

comres = combat_result

#define MAX_COMRES_ENTRIES 30
#define MAX_COMRES_SUBENTRIES 10

struct comres {
  int used;
  struct comres_entry {
    int sub_entries_used;
    double rel_chance, abs_chance;
    int children[2];

    struct comres_sub_entry {
      enum comres_entry_type {COMRES_ROOT, COMRES_UNIT_KILLED,
                              COMRES_CITY_DESTROYED,
                              COMRES_CITY_CAPTURED
      } type;
      union {
        struct unit *punit;
        struct city *pcity;
      } value;
    } sub_entries[MAX_COMRES_SUBENTRIES];
  } entries[MAX_COMRES_ENTRIES];
};

So comres forms a binary tree where each node is a random decision.

Simple example:
 suppose there is a patt and a pdef unit and that
 unit_win_chance(patt, pdef) returns 0.7. Than the comres will look
 like this:
 comres={used=3,
   entries[0]={sub_entries_used=1, rel_chance=1.0, abs_chance=1.0, 
children={1,2},
     sub_entries[0]={type=COMRES_ROOT}

   entries[1]={sub_entries_used=1, rel_chance=0.7, abs_chance=0.7, 
children={-1,-1},
     sub_entries[0]={type=COMRES_UNIT_KILLED, value.punit=pdef}

   entries[2]={sub_entries_used=1, rel_chance=0.3, abs_chance=0.3, 
children={-1,-1},
     sub_entries[0]={type=COMRES_UNIT_KILLED, value.punit=patt}
 }

Complex example:
  suppose a unit (patt) wants to attack a city (city1) and this city
  holds two defending units (pdef1, pdef2). Than the comres could look
  like this (game.occupychance is set to 0.82):
 comres={used=9,
   entries[0]={sub_entries_used=1, rel_chance=1.0, abs_chance=1.0, 
children={1,2},
     sub_entries[0]={type=COMRES_ROOT}

   entries[1]={sub_entries_used=1, rel_chance=0.73, abs_chance=0.73, 
children={3,4},
     sub_entries[0]={type=COMRES_UNIT_KILLED, value.punit=pdef1}

   entries[2]={sub_entries_used=1, rel_chance=0.27, abs_chance=0.27, 
children={-1,-1},
     sub_entries[0]={type=COMRES_UNIT_KILLED, value.punit=patt}

   entries[3]={sub_entries_used=2, rel_chance=0.82, abs_chance=0.5986, 
children={5,6},
     sub_entries[0]={type=COMRES_UNIT_KILLED, value.punit=pdef1}

   entries[4]={sub_entries_used=2, rel_chance=0.18, abs_chance=0.1314, 
children={-1,-1},
     sub_entries[0]={type=COMRES_UNIT_KILLED, value.punit=pdef1}

   entries[5]={sub_entries_used=2, rel_chance=0.6, abs_chance=0.35916, 
children={7,8},
     sub_entries[0]={type=COMRES_UNIT_KILLED, value.punit=pdef1}
     sub_entries[1]={type=COMRES_UNIT_KILLED, value.punit=pdef2}

   entries[6]={sub_entries_used=2, rel_chance=0.4, abs_chance=0.23944, 
children={-1,-1},
     sub_entries[0]={type=COMRES_UNIT_KILLED, value.punit=pdef1}
     sub_entries[1]={type=COMRES_UNIT_KILLED, value.punit=patt}

   entries[7]={sub_entries_used=3, rel_chance=0.82, abs_chance=0.2945112, 
children={-1,-1},
     sub_entries[0]={type=COMRES_UNIT_KILLED, value.punit=pdef1}
     sub_entries[1]={type=COMRES_UNIT_KILLED, value.punit=pdef2}
     sub_entries[1]={type=COMRES_CITY_CAPTURED, value.pcity=city1}

   entries[8]={sub_entries_used=2, rel_chance=0.18, abs_chance=0.0646488, 
children={-1,-1},
     sub_entries[0]={type=COMRES_UNIT_KILLED, value.punit=pdef1}
     sub_entries[1]={type=COMRES_UNIT_KILLED, value.punit=pdef2}
 }

possible ai_military_findvictim implementation:
   adjc_iterate(x, y, x1, y1) {
     comres=calc_combat_unit_vs_tile(punit, x1, y1);
     i = <find index of first COMRES_CITY_CAPTURED>;
     if(i!=-1 && comres.entries[i].abs_chance==1.0) {
        // captured a city without risk
     }

     double fitness (or gain or benefit) = 0.0;

     // leaf-nodes have children = {-1, -1}, sum over abs_chance over all leaf 
nodes is 1.0

     comres_interate_over_leaf_nodes(comres, pentry) { 
       int tmp=0;
       comres_iterate_over_sub_entries(pentry, psub) {
         switch(psub->type) {
           COMRES_UNIT_KILLED:
              if(unit_owner(psub->data.punit)==unit_owner(punit))
                 tmp -= unit_value(psub->data.punit)
              else
                 tmp += unit_value(psub->data.punit)
              break;
            same for other COMRES_*
         } // end switch
       } comres_interate_over_leaf_nodes_end;
       fitness += tmp*pentry->abs_chance;
     } comres_interate_over_leaf_nodes_end;
     if(fitness > best_fitness) ....

I'm sure that you can remove the special case for empty city. In fact
the calculation of the benefit from a comres is very generic.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Of course, someone who knows more about this will correct me if I'm
  wrong, and someone who knows less will correct me if I'm right."
    -- David Palmer (palmer@xxxxxxxxxxxxxxxxxx)