Fixed AI trade route evaluation to use correct speculated homecity instead of unit's

[freeciv.git] / doc / README.AI

==============
THE FREECIV AI
==============

This document is about freeciv's default AI. Freeciv supports also
using custom AI modules, though at the time of writing none exist.
See README.AI_modules about support of custom modules.


CONTENTS
========
Introduction
Contacting the current AI developers
Long-term AI development goals
Want calculations
Amortize
Estimation of profit from a military operation
Selecting military units
Ferry system
Diplomacy
Difficulty levels
Things that needs to be fixed
Idea space


INTRODUCTION 
============ 

The Freeciv AI is widely recognized as being as good as or better
military-wise as the AI of certain other games it is natural to compare
it with.  It is, however, still too easy for experienced players.

The code base used to be in a bad shape but it has gotten a lot
better.  The reason for this is that the developer (Syela) who in a
few months put together a working AI had suddenly disappeared.  His
bright ideas could only be matched by his inability to name variables
and to comment the code.  Subsequent AI developers were not brave (or
stupid?) enough to start from scratch, taking instead a small bite
here and there, trying hard not to break much, to understand Syela's
original design and only then to throw it away.  Or perfect it.

Code that implements the AI is divided between ai/ and server/advisors.
Latter is used also by human players for such automatic helpers
as auto-settlers and auto-explorers.


CONTACTING THE CURRENT AI DEVELOPERS
====================================

AI development used to have its own mailing list, freeciv-ai@freeciv.org.
Go to 

  http://www.freeciv.org/wiki/Community_Forums

to read the archives.

Currently freeciv-dev@gna.org is used for all discussion about freeciv
development.


LONG-TERM AI DEVELOPMENT GOALS
==============================

The long-term goals for Freeciv AI development are
 -> to create a challenging and fun AI for human players to defeat
 -> to create an AI that can handle all the rules possibilities that
    Freeciv can offer


WANT CALCULATIONS
=================

Build calculations are expressed through a structure called adv_choice. 
This has a variable called "want", which determines how much the AI 
wants whatever item is pointed to by choice->type. choice->want is

   -199   get_a_boat
   < 0    an error
   == 0   no want, nothing to do
   <= 100 normal want
    > 100 critical want, used to requisition emergency needs
    > ??? probably an error (1024 is a reasonable upper bound)
    > 200 Frequently used as a cap. When want exceeds this value,
          it is reduced to a lower number.

These are ideal numbers, your mileage while travelling through the 
code may vary considerably.  Technology and diplomats, in particular, 
seem to violate these standards.


AMORTIZE
========

Hard fact:
amortize(benefit, delay) returns benefit * ((MORT - 1)/MORT)^delay
(where "^" == "to the power of")

Speculation:
What is better, to receive 10$ annually starting in 5 years from now
or 5$ annually starting from this year?  How can you take inflation
into account?  The function amortize is meant to help you answer these
questions.  To achieve this, it rescales the future benefit in terms of
todays money.

Suppose we have a constant rate of inflation, x percent.  Then in five
years time 10$ will buy as much as 10*(100/(100+x))^5 will buy today.
Denoting 100/(100+x) by q we get the general formula, N dollars Y
years from now will be worth N*q^Y in todays money.  If we will
receive N every year starting Y years from now, the total amount
receivable (in todays money) is N*q^Y / (1-q) --- this is the sum of
infinite geometric series.  This is exactly the operation that
amortize performs, the multiplication by some q < 1 raised to power Y.
Note that the factor 1/(1-q) does not depend on the parameters N and Y
and can be ignored.  The connection between MORT constant and the
inflation rate x is given by
    (MORT - 1) / MORT = q = 100 / (100 + x).
Thus the current value of MORT = 24 corresponds to the inflation rate
(or the rate of expansion of your civ) of 4.3%

Most likely this explanation is not what the authors of amortize() had
in mind, but the basic idea is correct: the value of the payoff decays
exponentially with the delay.

The version of amortize used in the military code (military_amortize())
remains a complete mystery.


ESTIMATION OF PROFIT FROM A MILITARY OPERATION
==============================================

This estimation is implemented by kill_desire function (which isn't
perfect: multi-victim part is flawed) plus some corrections.  In
general,
        Want = Operation_Profit * Amortization_Factor
where 

* Amortization_Factor is completely beyond me (but it's a function of the
estimated time length of the operation).

* Operation_Profit = Battle_Profit - Maintenance

where

* Maintenance 
  = (Support + Unhappiness_Compensation) * Operation_Time 
  (here unhappiness is from military unit being away from home
   and Support is the number of shields spent on supporting this unit 
   per turn )

* Battle_Profit
  = Shields_Lost_By_Enemy * Probability_To_Win 
    - Shields_Lost_By_Us * Probability_To_Lose

That is Battle_Profit is a probabilistic average.  It answer the
question "how much better off, on average, we would be from attacking
this enemy unit?"


SELECTING MILITARY UNITS
========================

The code dealing with choosing military units to be built and targets
for them is especially messy.  Here is what we've managed to decipher.

Military units are requested in military_advisor_choose_build
function.  It first considers the defensive units and then ventures
into selection of attackers (if home is safe).  There are 2
possibilities here: we just build a new attacker or we already have an
attacker which was forced, for some reason, to defend.  In the second
case it's easy: we calculate how good the existing attacker is and if
it's good, we build a defender to free it up.

Building a brand-new attacker is more complicated.  Firstly,
ai_choose_attacker_* functions are charged to find the first
approximation to the best attacker that can be built here.  This
prototype attacker is selected using very simple attack_power * speed
formula.  Then (already in kill_something_with) we search for targets
for the prototype attacker (using find_something_to_kill).  Having
found a target, we do the last refinement by calling
process_attacker_want to look for the best attacker type to take out
the target.  This type will be our attacker choice.  Note that the
function process_attacker_want has side-effects wrt the tech selection. 

Here is an example:

First ai_choose_attacker_land selects a Dragoon because it's strong
and fast.  Then find_something_to_kill finds a victim for the
(virtual) Dragoon, an enemy Riflemen standing right next to the town.
Then process_attacker_want figures out that since the enemy is right
beside us, it can be taken out easier using an Artillery.  It also
figures that a Howitzer would do this job even better, so bumps up our
desire for Robotics.

This is the idea, anyway.  In practice, it is more complicated and
probably less efficient.


FERRY SYSTEM
============

The ferry (i.e. boats transporting land units) system of Freeciv is
probably better described by statistical mechanics than by logic.
Both ferries and prospective passenger (PP) move around in what looks
like a random fashion, trying to get closer to each other.  On
average, they succeed.  This behaviour has good reasons behind it, is
hell to debug but means that small bugs don't affect overall picture
visibly (and stay unfixed as a result).

Each turn both boats and PPs forget all about prior arrangements
(unless the passenger is actually _in_ the boat).  Then each will look
for the closest partner, exchange cards and head towards it.  This is
done in a loop which goes through all units in essentially random
order.

Because most units recalculate their destination every turn, ignoring
prior arrangements is the only good strategy -- it means that a boat
will not rely on the PP to notify it when it's not needed anymore.
This is not very effective but can only be changed when the PPs behave
more responsibly.  See diplomat code for more responsible behaviour --
they try to check if the old target is still good before trying to
find a new one.

When a boat has a passenger, it's a different story.  The boat doesn't
do any calculations, instead one of the passengers is given full
control and it is the passenger who drives the boat.

Here are the main data fields used by the system.
Value of ai.ferry in the passenger unit is:
  FERRY_NONE : means that the unit has no need of a ferry
  FERRY_WANTED : means that the unit wants a ferry
  >0 : id of it's ferry
Value of ai.passenger in the ferry unit can be either of:
  FERRY_AVAILABLE : means that the unit is a ferry and is available
  >0 : id of it's passenger

When boat-building code stabilizes, it can be seen how many free boats
there are, on average, per PP.  If there are more boats than PPs, it
makes sense that only PPs should look for boats.  If boats are few,
they should be the ones choosing.  This can be done both dynamically
(both possibilities are coded and the appropriate is chosen every
turn) and statically (after much testing only one system remains).
Now they exist in parallel, although developed to a different degree.


DIPLOMACY
=========

The AI's diplomatic behaviour is current only regulated by the 
'diplomacy' server setting.

AI proposes cease-fire on first contact.

AI is not very trusting for NEUTRAL and PEACE modes, but once it hits 
ALLIANCE, this changes completely, and it will happily hand over 
any tech and maps it has to you.  The only thing that will make the AI 
attack you then is if you build a spaceship.

For people who want to hack at this part of the AI code, please note
 * pplayers_at_war(p1,p2) returns FALSE if p1==p2
 * pplayers_non_attack(p1,p2) returns FALSE if p1==p2
 * pplayers_allied(p1,p2) returns TRUE if p1==p2 
 * pplayer_has_embassy(p1,p2) returns TRUE if p1==p2
i.e. we do not ever consider a player to be at war with himself, we
never consider a player to have any kind of non-attack treaty with
himself, and we always consider a player to have an alliance with
himself. 

The introduction of diplomacy is fraught with many problems.  One is
that it usually gains only human players, not AI players, since humans
are so much smarter and know how to exploit diplomacy, while for AIs
they mostly only add constraints on what it can do.  Another is that it
can be very difficult to write diplomacy that is useful for and not in
the way of modpacks.  Which means diplomacy either has to be optional,
or have fine-grained controls on who can do what diplomatic deals to
whom, set from rulesets.  The latter is not yet well implemented.


DIFFICULTY LEVELS
=================

There are currently seven difficulty levels: 'handicapped, 'novice',
'easy', 'normal', 'hard', 'cheating', and 'experimental'.
The 'hard' level is no-holds-barred. 'Cheating' is the same
except that it has ruleset defined extra bonuses, while 'normal'
has a number of handicaps. In 'easy', the AI also does random stupid
things through the ai_fuzzy function. The 'experimental' level is
only for coding - you can gate new code
with the H_EXPERIMENTAL handicap and test 'experimental' level
AIs against 'hard' level AIs. In 'novice' the AI researches slower
than normal players.

Other handicaps used are:
  H_DIPLOMAT     Can't build offensive diplomats
  H_LIMITEDHUTS  Can get only 25 gold and barbs from huts
  H_DEFENSIVE    Build defensive buildings without calculating need
  H_RATES        Can't set its rates beyond government limits
  H_TARGETS      Can't target anything it doesn't know exists
  H_HUTS         Doesn't know which unseen tiles have huts on them
  H_FOG          Can't see through fog of war
  H_NOPLANES     Doesn't build air units
  H_MAP          Only knows map_is_known tiles
  H_DIPLOMACY    Not very good at diplomacy
  H_REVOLUTION   Cannot skip anarchy
  H_EXPANSION    Don't like being much larger than human
  H_DANGER       Always thinks its city is in danger

For an up-to-date list of all handicaps and their use for each
difficulty level see ./ai/handicaps.h.


THINGS THAT NEED TO BE FIXED
============================

* Cities don't realize units are on their way to defend it.
* AI builds cities without regard to danger at that location.
* AI won't build cross-country roads outside of city radii.
* Locally_zero_minimap is not implemented when wilderness tiles 
change.
* If no path to chosen victim is found, new victim should be chosen.
* Emergencies in two cities at once aren't handled properly.
* Explorers will not use ferryboats to get to new lands to explore.
The AI will also not build units to explore new islands, leaving huts alone.
* AI sometimes believes that wasting a horde of weak military units to
kill one enemy is profitable (PR#1340)
* Stop building shore defense in landlocked cities with a pond adjacent.
* Fix the AI valuation of supermarket. (It currently never builds it).
See farmland_food() and ai_eval_buildings() in advdomestic.c
* Teach the AI to coordinate the units in an attack (ok, this one is a bit
big...)


IDEA SPACE
==========

* Friendly cities can be used as beachheads
* Assess_danger should acknowledge positive feedback between multiple 
attackers
* It would be nice for bodyguard and charge to meet en-route more 
elegantly.
* struct choice should have a priority indicator in it.  This will
reduce the number of "special" want values and remove the necessity to
have want capped, thus reducing confusion.