[Freeciv-Dev] Unit-vs-stack sim (was: Cache win_chance)

[Gregory Berkolaiko <gberkolaiko@xxxxxxxxxxx>]

 --- Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx> wrote: 
> 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.

ow-wow-wow, let's calm down.
First of all, we were talking about passing back an already computed and
potentially useful value in a simple and straightforward manner.  But
apperently it does not satisfies us since it too simple and straightforward.
So the patch is going to be binned.  Fine, this one sorted.

Now we seem to be diverted to discussion of general unit-vs-stack simulation. 
Let's change the subject first.... Done.
Now let's identify the needs: precisely what information are we seeking from
this potentially very complicated simulation?  How are we going to use it?
[remains to be filled in]

Now let's identify the potential difficulties:
1. Outcome of one attack is already a complicated thing: besides won/lost
distribution we have a much wider distribution of the remaining health of the
winner.  It is not hard to compute (it's done in win_chance) but should it be
stored and used?  Or just a conditional mean(*) would do?
2. Outcome of one attack will be affecting the next attack.  If it ever
happens, because we have one more branch here: what if the defender decides to
attack us?
3. More branching will follow: what if reinforcements arrive to the city we
are sacking?  What if we are awarded veteran status?

I feel it's enough for now.
(*) conditional mean: here average health of our unit provided it has won.

The present AI follows a very simple (thus unsatisfactory for some of us)
mathematical principle: step-by-step maximization.  AI takes an action if on
average it would be better off after this action (apart from the broken
auto-attack which I will fix as soon as Raahul supplies me with the promised
savegame).  Sometimes it fails to take into account side effects of the action
and this should be fixed, but on a lesser scale than trying to compute all
possible outcomes for 10 moves ahead.

But maybe we can come up with the algorithm which would go into sufficient
depth for you and be sufficiently simple for my small brain.  So let's
discuss.

Best,
G.

> 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)
>  

__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page
from News and Sport to Email and Music Charts
http://uk.my.yahoo.com