[Freeciv-Dev] Re: (PR#14763) Advanced govt patch

["Benedict Adamson" <badamson@xxxxxxxxxxx>]

<URL: http://bugs.freeciv.org/Ticket/Display.html?id=14763 >

Per I. Mathisen wrote:
...
> [The rule-set] should have an
> "ai.better" field set (which Anarchy, Despotism and Monarchy have) so that
> [bad governements] are only used temporarily on the way to the viable ones.
...

I've been mulling that over, and I'm not too keen on such 'better' 
fields. The problem is that they are useful only if there is only one 
reasonable progression (in this case, progression of governments). As 
you have eloquently argued elsewhere, for the game to be interesting 
there should be several viable playing strategies. The current AI in 
fact handles that rather well at the moment, I think, switching to 
Communism, or advancing to Republic via Monarchy if it is useful to do so.

[And previously]
> The reason for this approach is 1) that the current governments evaluation
> code became unviable with 5x5x6 combinations of governments, and 2) it
> seemed superfluous to make the AI choose a personality and then select the
> governments that suited its personality, when it the AI instead could
> _express_ its personality through its choice of governments and diplomatic
> actions.

But what if more than one kind of government can express the AI's 
personality? How is the AI to choose between them?

I think retaining the current AI government selection code in some form 
is a good idea. But how to do so without being crippled by the 
combinatorial explosion? I think I have an answer.

First, generalise the AI government selection code in the manner of the 
following pseudo code:

Initialise a table of government evaluations
WHILE still have work to do DO
    Pick a government to evaluate
    Evaluate the chosen candidate government, computing a 'want' value
    (that is the expensive part)
    Record in the table the evaluation of that candidate
END WHILE
Examine the table of government evaluations
Choose the government in the table that has the highest 'want' value.

The current algorithm is as follows:
* The AI 'still has work to do' while the table does not have an entry 
for all possible governments.
* The AI picks a government to evaluate by simply choosing the next 
un-evaulated government in the list of governments.

With advanced governments, the algorithm could be as follows:
* The AI 'still has work to do' while the table has less than the 
maximum permitted number of entries. We therefore avoid the cost of 
combinatorial explosion by providing a hard limit on the number of 
candidate governments evaluated. The 'easy' and 'novice' AI difficulty 
levels could have lower limits.
* The AI picks a government to evaluate as follows:
    IF the table of government evaluations is empty THEN
      Pick the current government
    ELSE
      Examine the table of government evaluations,
      to determine the best candidate so far.
      Pick a candidate government that is similar to the best so far,
      but is not in the table, as follows:
      Set the candidate to be NULL
      FOR ALL the possible governments DO
         IF this government has already been evaluated THEN
            CONTINUE
         ELSE IF the candidate is NULL THEN
            consider this government as the candidate
         ELSE IF the candidate is marked
         with an AI hint for the personality of this AI,
         but this government is not THEN
            CONTINUE
         ELSE IF this government is marked
         with an AI hint for the personality of this AI,
         but the candidate is not THEN
            consider this government as the candidate
         ELSE IF this government is closer (fewer differences)
         to the best so far than the candidate THEN
            consider this government as the candidate
         END IF
      END FOR
* Note that the selection of candidates uses true AI hints: the hints 
help the AI choose which governments to evaluate, but do not tell the AI 
which government to choose.