RE: AI (very long)

[Lincoln Peters <peters2000 at mindspring dot com>]

I meant to send this message while the idea of writing a new AI was
being tossed around, but it turned out that this message took a long
time to write.  Not surprisingly, it is very long, and probably more
than a little incoherent.  Hopefully it all makes sense.


First, I suspect that the most effective (although most difficult to
write) AI would be one that uses some kind of fractal algorithm to make
decisions based on cause-and-effect chains and branches.  With such a
thought process, an AI might do the following in the standard game:

1. I cannot move any fighters from Point A to Point B.  Why not?
2. The distance from Point A to Point B is 24 cells.  Fighters have a
range of only 18.
3. How can I get the fighters to Point B despite their short range?
4. I could (a) build a base within 18 cells of both Point A and Point B
(I'll call it Point C), or (b) I can use an aircraft carrier to
transport the fighters from Point A to Point B.

5a. I need an infantry unit to build a base at Point C.  Is any infantry
idle and close to Point C, or should I build a new one?
5ai. Yes, there is an infantry near Point C, and it is idle.  Use it.
5aii. No, there is no infantry near Point C, or it is busy.  Build a new
one.
6a. Move that infantry to Point C, then build base.
7a. When base is completed, move fighters at Point A to Point C, then
resupply fuel, then move to Point B.

5b. Do I have an aircraft carrier?
5bi. No, I don't, or all of my aircraft carriers are busy.  Build one.
5bii. Yes, I do.  Move it to point A.
6b. Aircraft carrier will pick up the fighters, then move to within 9 of
Point A.
7b. When aircraft carrier is within 9 of Point A, wake up the fighters.


What might be especially useful is if the AI had some sort of learning
mechanism that it could apply when something goes wrong or happens
unexpectedly, and then it could avoid making the same mistake twice.  I
know that such a mechanism exists in PowerChess, but I doubt that any of
us has access to its source code (I can't even find its web page
anymore!).



Second, the AI needs to always know what questions to ask itself when it
is choosing a course of action.  Its inability to understand detonating
units, for example, prevents it from effectively using nuclear bombs in
the standard game, car bombs in beirut.g, etc.

I have tried to consider as many such questions as possible, grouped by
category (each category or subcategory might represent an individual
function or class in a new AI).  There are likely to be lots of things
that I overlooked, especially low-level questions and questions
regarding more obscure strategies (e.g. using decoys).  If you can think
of something I missed, feel free to tack it on.

(Note: Most of these questions are meant to be asked and answered from
the perspective of individual units, although in a few cases such as
4.2.1, the unit doesn't matter.  Units that are referred to as "Unit X"
are those that the unit in question might build or otherwise deal with
in some specific way.)

1. Construction

1.1. Construction possibilities

What can I build right now? (without toolup, development, or advances)
What can I build if I toolup?
What can I build if I develop?
What can I build if I develop *and* toolup?
What can I build if I get a certain advance?

1.2. Tech, tooling, and advances

How many tech points do I need before I can build Unit X?
How many tooling points do I need before I can build Unit X?
What advance(s) do I need before I can build Unit X?
What advances, including prerequisites, do I need before I can build
Unit X?
How many construction points does Unit X require?

1.3. Time management

How long will it take to develop Unit X?
How long will it take to toolup to build Unit X?
How long will it take to acquire the necessary advances to build Unit X?
How long will it take to build Unit X? (not counting tech, et al.)
How long will it take to build Unit X, including advances, tech
development, and tooling?

1.4 Material handling

1.4.1 Construction materials

What materials are needed to create Unit X?
What materials are consumed by creating Unit X?
What materials are needed to add 1 CP to Unit X?
What materials are consumed by adding 1 CP to Unit X?
Do I have the materials necessary to build Unit X?
If I don't have the materials, where can I get them? (consider
resupplying or extracting as per 4.3)

1.4.2 Post-construction materials

What does Unit X have once created?
What does Unit X have once completed?
What does Unit X consume (as per base consumption)?
What does Unit X produce?
What does Unit X require to act?
What does Unit X require to move?
What does Unit X require to attack?
What does Unit X require to fire?
What does Unit X consume per size?
What does Unit X consume to grow by 1?
How  is Unit X's production affected by terrain?
Where can Unit X go in order to resupply (if applicable)?

1.5. Choosing what to build

1.5.1. Building for production

What units can Unit X build?
What materials can Unit X produce?
Can Unit X alter terrain?
Can Unit X affect the productivity of another unit? (see 4.1)

1.5.2. Building for transportation

What units can Unit X carry?
What terrain can Unit X cross that its occupants cannot?
What is the effective range of Unit X compared to the units it could
carry?
What materials can Unit X carry that its occupants might need?

1.5.3. Building for supply purposes

What materials can Unit X store?
What materials can Unit X produce?
What units might need the materials that Unit X can store or produce?

1.5.4. Building for combat

[See 2.1 and 2.2, from the standpoint of Unit X]

1.5.5. Building for colonization

On what kind of terrain can Unit X live?
Where can I find such terrain that is not currently occupied?
Is more exploration necessary to find such a place?
Is there any known enemy activity in that area?
[should elaborate?]

2. Combat

2.1 Offensive action

2.1.1. Offensive possibilities

What units can I attack?
What units can I capture?
What units can I protect? (as occupant/transport or as neighbor)
What units can attack me?
What units can capture me?

2.1.2. Evaluation

What enemy units are within my tactical range?
What allied units are nearby? (within tactical range?)
What allied units are nearby and idle?

2.1.2.1. Attack to kill

What is my chance of destroying one of the enemy units in one-on-one
combat?
What is my chance of destroying more than one of them?
What is my chance of destroying one of them if I call one or more of my
allies?
What is my chance of destroying more than one of them if I call my
allies?

2.1.2.2. Attack to capture

What is my chance of capturing one of them in one-on-one combat?
What is my chance of capturing more than one of them (if applicable)?
What is my chance of capturing one of them if I call one or more of my
allies?
What is my chance of capturing more than one of them if I call my allies
(if applicable)?

2.1.3. Risk analysis

What is my chance of being destroyed if I attack alone?
What is my chance of being destroyed if I call my allies?
What is my chance of being captured if I attack alone?
What is my chance of being captured if I call my allies?

2.1.4. Action

Shall I attack?
Shall I capture?

2.2 Defensive action

2.2.1. Defending another unit

2.2.1.1. Defensive analysis

What allied units are nearby?
Can the allied unit be captured?
Is the ally worth protecting if it is in immediate danger?
Is the ally worth protecting even if not in immediate danger?
What is the allied unit's immediate chance of being destroyed?
What is the allied unit's immediate chance of being captured? 
Which is worth more: me or the allied unit?

2.2.1.2. Planning a defense

Can I protect the allied unit by occupying it?
Can I attack the allied unit's attacker(s)?
[There should be more options]

2.2.1.3. Executing a defense

What is my chance of successfully saving the unit?
What is my chance of successfully saving the unit and surviving?
What is my chance of being captured myself?

2.2.1.4. Action

Shall I occupy?
Shall I attack the attacker?

2.2.2. Defending an area

[need to work this out; how does it work currently?]

3. Exploration

3.1. Mapping new lands

3.1.1. Vision

What is my vision range?
What is my vision range at night?
What is my vision bend?
What is my eye height?
What is my operational range? (not firing range)

3.1.2. Discovering terrain

What is the proportion of terrain on the map that I can move on?
What is my speed on such terrain? (calculate individually for each
terrain type)
What is my productivity on such terrain (if applicable)?

3.1.3. Discovering units

What is my chance of seeing any unit within my vision range?
What is my chance of seeing any unit adjacent to me?
How might the visibility of other units be affected by terrain?
What is my chance of mistaking one unit for another?
What units look like other units?

3.1.4. Risk analysis

What is my chance of being seen?
What is my chance of being attacked if I'm seen?
What is my chance of being destroyed if I'm seen?

3.2. Reconnaissance/Patrolling

3.2.1. Where to patrol

What friendly units within my tactical range could be captured?
What is their current risk of being captured?
How many turns would it take to respond to a surprise attack? (consider
capture chance over the next few turns as units move in to defend)

3.2.2. Cost/Benefit analysis

How much is the chance of surviving the attack reduced if the
attacker(s) are sighted before they are in position?

3.2.3. Action

Should I patrol the area around the friendly unit and watch for enemies,
and if so, how far away should I patrol?

[should elaborate?]

4. Improvements

4.1. Improving units

Can Unit X improve my production of any material?
Can Unit X produce materials for me?
Can Unit X allow me to cover more cells?
Can Unit X give me more ACP per turn?
Can Unit X protect me?
Can Unit X improve my attack strength?
Can Unit X improve my defend strength?

Can I build Unit X?
Can I find and capture Unit X?
Can an ally build Unit X for me?
Can an ally find and capture Unit X for me?

4.2. Improving terrain

4.2.1. Terrain analysis

What materials, if any, does this terrain produce?
What materials, if any, does this terrain consume?
What materials, if any, can this terrain store?
What happens to this terrain if "damaged" by an explosion?
What happens to this terrain if it is exhausted?
How does this terrain affect the productivity of units?
How quickly can units enter this terrain?
How quickly can units leave this terrain?
How quickly can units traverse this terrain?

What terrain, if any, is considered to be a road?
What terrain, if any, is considered to be a river?
What terrain, if any, is considered to be a valley?

4.2.1.1. Connection terrain

What units can move along this terrain faster than they can move along
other terrain?
Does this connection allow units to move across impassable terrain?

4.2.1.2. Border terrain

What units, if any, does this terrain impede the movement of?
What units, if any, can "border slide" along this terrain?

[coating terrain not specifically considered here; should it be?]

4.2.2. Abilities

Can I replace one kind of cell terrain with another?
Can I add borders, connections, or coatings?
Can I remove borders, connections, or coatings?

4.2.3. Actions

Shall I build a road connecting one unit to another?
Shall I dig a river? (if the river provides something like +1 food)

[need more things to do here]

4.3. Material collection

What material(s) can I collect?
What unit(s) have use for such material(s)?

4.3.1. Collect from units

What units can store the material(s) that I can collect?
Are any such units known?
Of those known, which are not exhausted?

4.3.2. Collect from terrain

What terrain can store the material(s) that I can collect?
Where is such terrain known to exist?
Of that terrain known, what areas are not exhausted?


And, of course, on top of all this, Xconq *still* needs an improved
pathfinding algorithm and working supply code.  


Any questions or comments?  Anything that I've missed?

-- 

Lincoln Peters <peters2000@mindspring.com>