============== 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 ai_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 six difficulty levels: '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 ./common/players.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.