[Better than BTS] Threats,Targets, Reserves and Plans

Discussion in 'Civ4 - Better AI' started by Yakk, Jul 2, 2008.

  1. Yakk

    Yakk Cheftan

    Joined:
    Mar 6, 2006
    Messages:
    1,288
    Currently, the AI mostly runs itself on a per-unit or per-stack basis.

    I'm thinking that we might want to generate a "start of turn" process where the AI identifies threats, targets, and locations that need reserves.

    A threat is something like an enemy stack that is in your territory or near your territory. Possibly unexplored enemy terrain near your borders would also have low-grade threat attached.

    A target is something like a city you want to take.

    Cities, by their very existence, will have a presumed level of threat, plus extra threat based off being near borders (or near water), based off of the total power of neutral and enemy powers (and enemy units). They also like having reserves located in them.

    Ideally, we want to do this without adding extra save game data (or cheat, and store it in a way that is compatible old save games). If we can do without actually saving anything, that would be ideal.

    Once the AI identifies threats, it can then iterate over it's units, and propose a plan to deal with threats, and resources that can be directed towards targets. It would be acceptable to decide that a given threat should be ignored, but the AI should make that decision.

    Explicit threats, like enemy stacks, can be dealt with by two methods.

    First, you can beef up defenses of nearby cities (that leaves the pillage threat of the enemy stack intact).

    Second, you can attempt to eliminate the enemy stack. In that case, an attempt to keep most baseline defenses intact, and protect the attacker against threat after the fight, should be taken into account.

    Targets would be delt with similarly, except you'd look at where units are planning to go, and bias your target selection towards their plans. (Ie, if you have a large number of units gathering in a given city, the AI would think about plans for naval invasions being launched from that city, and about land-wars being launched from that city, each turn. This might even take into account the current number of nearby cities producing boats (ie, potential transport capacity) for the naval invasion case.)

    This all would happen in:
    void CvPlayer::doTurnUnits();
    or, more accurately, in the function:
    void CvPlayer::AI_doTurnUnitsPre();
    that doTurnUnits() calls.

    or maybe in the CvPlayer::doTurn() code.

    Currently, unit movement decisions are done in:
    CvPlayer::AI_unitUpdate()
    which iterates over each selection group, and makes plans for it.

    This is called from:
    CvGame::updateMoves()
    which is called from
    CvGame::update()
    which seems to be called from the DLL.

    CvPlayer::setTurnActive() calls CvPlayer::doTurnUnits()
    which is called from CvGame::doTurn()
    which is called from CvGame::update() before it calls updateMoves().

    So... that looks like the vaguely the right place to do this.

    A pass to identify:
    Low-level threats (all cities are threatened)

    Unknown-level threats (cities that are near boarders have extra, unknown threat)

    Immediate threats (enemy stacks)

    Ideal reserves (clumps of units over the empire, stationed at cities -- but if you have to dip into these, that's what they are there for)

    Targets or Goals (a massing naval invasion, a massing land invasion, a marching army at an enemy city, etc)

    Then a pass to identify resources that can reach each of the threats, reserve locations, immediate threats and targets & goals, a "is it already on it's way there" detector, an idea of how soon it it can engage.

    This would include an idea about the future already-queued production of resources on what time-lines, and the possible "omg, let's make units quick" options.

    Then a check to see if we can deal with all immediate threats in a single turn while maintaining sufficient defenses to deal with low-level and unknown threats... (including to the units that are used to attack the threats in question) Then see if you can make a plan for multiple turns, etc.

    Do this check for each of, say, 1, 2, 3 or 4 turns into the future. Once you know you can deal with it in N turns, you can fine-tune the plan (mass the units at a particular location, instead of charging in, etc, or determine if you can reinforce threatened cities along the enemy advance route). -- ie, what is the cost of the delay?

    Now, determine what happens if you start dipping into the "unknown threat" reserves. This is dangerous, but if that is the only way to deal with an incoming army that is about to take out a major city, it might be worth it...

    Ie: you see a monster stack approaching. Can you kill it or damage it enough that it isn't a danger any more? If not, should you start whipping?

    Or, you see an enemy naval force off of your coasts. Can you take it out? Do you have naval forces to spare to take it out?

    The idea is to try to get the AI to think less on a per-unit basis, and more on a "here are the resources I have, and here are the problems I have" basis.

    This might be way way way way way to ambitious. :)
     
  2. armand453

    armand453 Chieftain

    Joined:
    Jul 25, 2007
    Messages:
    45
    it's a very good idea, but don't forget this kind of loops are cpu killing process you must be very carefull when you'll implement that ;)
     
  3. glider1

    glider1 Deity

    Joined:
    May 29, 2006
    Messages:
    2,905
    Location:
    Where animals hop not run
    It may be ambitious but it's the first coherant "Use Case" model I've seen. It would definetly have to be a branch off the main development tree because of the risk.

    I suggest continuing to hone it more and more. Even in this initial model you have suggested a way to integrate production and planning with strategy and tactics. A challenge.

    I'm no expert in AI programming but the "blackboard" AI intelligence design might fit in well with this "use case" and what seems to be a partial implementation of a "blackboard" AI in BTS anyway.....

    There seems to be a nice article on it here:
    http://bbtech.com/papers/ai-expert.pdf

    It does look like a total redesign! Perhaps better is to continue to hone the use case you have initiated here. Thanks for all the hard links to actual code functions. This does help zero in better what is achievable short to medium term.

    Cheers.
     
  4. Yakk

    Yakk Cheftan

    Joined:
    Mar 6, 2006
    Messages:
    1,288
    So, my first goal is "bug stomping".

    "Bug stomping" is where I look for hostile stacks, and determine if I can kill/heavily wound them using nearby resources in a single turn, without opening myself up to easy counter-attack.

    For simplicities sake, we might not consider commando enemies for counter-attacks against stack-stomping units.

    And, it is a pretty modular change.

    I think that a unit with a mission won't have the mission overridden by the per-unit AI loop (which is another problem . . .). So if we insert missions on units in this "global planning" stage, it should persist afterwards.

    There already seems to be a "area target city". Global planning could improve this by ... hmm ... building a stack at a staging ground near the area target city? That would require finding a staging ground. . .

    "Cherry picking", where you find enemy cities that are near an existing stack, might also be a tempting global optimization.

    A sub-task would be figuring out "how big of a stack do I need before I try to attack" that doesn't result in the AI going into an economically crippling infinite arms race?

    Basically, I want to leave the existing AI intact.

    Note that both the "first-run approximation of how many units are needed to smash a stack" (ie, better unit power approximation), and the "simulate a battle using given attacking units" code will be rather key for efficient bug-smashing.
     
  5. glider1

    glider1 Deity

    Joined:
    May 29, 2006
    Messages:
    2,905
    Location:
    Where animals hop not run
    Yeah it's a dilemma. I really don't think the blackboard AI should be totally ignored. It seems to fit nicely with this AI problem. The thing about it is that the blackboard AI is actually perfect for a prototyping development environment because experts can be honed independently of executive decision. There might even be certain slabs of existing code that could be retained. Whatever.

    This would seem to need a directive piece of code to keep this conflict from dissolving the mission. Another reason for a blackboard?

    Another reason for a blackboard? There is already a very ridiculously simple interaction language between "knowledge sources (experts)" in the code (for example in warplanning with AI_startWarVal).

    It would seem that the problem would be to clarify which existing slabs of code in the AI could be used as knowledge sources and experts. Which slab of the code can be used as inputs and outputs. Once that is done all that has to happen is that a control component and blackboard has to be devised. That's all :)

    Yeah it's completely impossible except in the long term and by then AI theory will be way beyond the blackboard. Sorry.

    Cheers.
     
  6. jdog5000

    jdog5000 Revolutionary

    Joined:
    Nov 25, 2003
    Messages:
    2,601
    Location:
    California
    We will soon be able to have several different repositories on sourceforge and definitely should have a few experimental versions for collaboration on things like this.
     
  7. Iustus

    Iustus King

    Joined:
    Jul 18, 2006
    Messages:
    609
    Location:
    Sunnyvale, CA
    Following up my post in the amphibious assault thread here, as it is more appropriate in this context...

    When the AI decides on an amphibious attack (pre war declaration, just when it decides to start building for the attack), instantiate a new instance of a strategic plan class, of subclass warplan, perhaps even further subclass amphibious assault (or type)

    Then cityAIs, unitAIs, etc would get attached to that plan if they were associated with it. Once enough units (of the right types), were associated with the plan, then the ships would embark, etc.

    During a turn, city and unit moves could happen in two stages, first move everything that is associated with a strategic plan (perhaps things could have more than one plan, and they would be prioritized), then those cities/units which are unassigned could be moved. Somewhere along the way you would want to be able to add units/cities to a plan if it was short, or remove if it had enough and other plans were short.

    You would want to be able to abandon a plan at times (if you were invaded and your new defend the homeland plan felt it did not have enough units/cities without stealing some from the assault plan)

    -Iustus
     
  8. glider1

    glider1 Deity

    Joined:
    May 29, 2006
    Messages:
    2,905
    Location:
    Where animals hop not run
    What do you think about production planning? Subclass of a master plan class or seperate planning classes Unit, Production, Economy and Diplomacy linked by multiple inheritance??

    Your thoughts are great and seem to be directed at creating a blended solution:
    1) of introducing more complex behaviour to the AI without completely re-engineering it.

    2) The other "thought" is a blackboard AI where you properly organise strategic thinking across the board.

    I personally favour (1) because it is short to medium term while a blackboard AI is basically a PhD exercise long term, or a complex collaborative exercise medium term.

    Problem with (1) is that it could get messy unless it is really thought out well. It seems that without a blackboard, you essentially would have to divide up planning classes to handle different categories and this could get complex on top of an already complex engine.

    However even a unit planning class would be good on it's own even if nothing else gets done. At least that class would coordinate unit activities better. It get's conceptually messy of course because in theory there is a distinction between planning and coordination the list goes on!

    EDIT: I apologise for muddying the waters. I vote for keeping it simple on lines with your original idea but just fleshed out a little more. Option (1) produces a better AI but not a super ai, while option (2) could quite possibly be the way to a super AI that is incapable of running on slower PC boxes but plays a damn good game :)....

    Cheers.
     
  9. Iustus

    Iustus King

    Joined:
    Jul 18, 2006
    Messages:
    609
    Location:
    Sunnyvale, CA
    Well, the elegance of having these 'plan' classes attached to units and cities is that the units and cities will go through the same basic decisionmaking they do now, but they would just use these to make a better strategic decision.

    So, in the case of production, the key thing might be to make sure the right cities get assigned to the 'assault plan'. You might want to make it so each thing that is assigned to a plan can be given an optional assignment, so you know that say these 3 cities are assigned production of naval units for the assault, and if you picked the right 3 cities for unit production, etc. You would not necessarily have to plan in advance every turn's production (this might be too big a change), just give them assignments based on their overall production value. So if you picked, say 2-4 port cities in the right location with high production to produce ships, and 3-6ish (figuring out how many would be another problem) high production cities of the right distance to produce units, then you could leave the rest of the cities (particularly the new ones) to their own devices, growing.

    You could use this idea for some production specific plans if there are some that make sense. If there is a key wonder (or other build) that might require a tailored set of builds, in one city or multiple cities, this could all be coordinated with one of these plans.

    You could potentially use these plans also to determine when a threshold is met before starting a plan. So, if say you needed 3 cities with production over a certain value before you could start some plan, you would not bother to try unless you met the starting criteria.

    -Iustus
     
  10. Yakk

    Yakk Cheftan

    Joined:
    Mar 6, 2006
    Messages:
    1,288
    I think avoiding "persistent" plans might be a good idea - it maintains save game compatibility.

    The idea is that a "clean slate" plan class would be started at the start of the turn. Existing game state (unit missions, build orders, unit locations, power levels of the empire, enemy stacks or units) would be factored in.

    Potential plans would then be manipulated. (Ie: Plan: crush the enemy stack. Units that can reach the enemy stack in 1 turn are collected. A battle is simulated (say, 5 times), and the results are gauged (Did this leave us open to counter-attack? did we win economically and/or tactically?). Secondary plans are simulated (can we move units to maintain sufficient defense against counter attack?) If the potential plan is considered good enough, it is engaged in.

    If that doesn't work, a "defend and mass troops to stack-stomp later" plan might be tested.

    An amphib assault consists of three phases:
    1> Build the resources needed
    2> Move the fleet and army to the launch point, together
    3> Invade!

    (Note that 1 and 2 can happen "at the same time" -- but sometimes, 2 can happen without 1 happening!)

    The "amphib support" plan is one that might be triggered by a besieged oversea colony, or an overseas colony that wants more troops to continue expanding.

    The fact that you are building a lot of boats, or have lots of boats is a sign to the planner that "maybe we should continue with an amphib assault buildup".

    There are also some AI variables that can imply a plan might be in progress: the target city by region (I think that is saved), the AI state (there are a number of them), the mission queue of a unit (is that AI, or game-mechanics?), the waypoint target of a unit (indicated that the AI thought that going to that location was a good idea in the past -- maybe we are massing troops there for a reason?)

    ...

    The advantage of this "memoryless" plan system is that the AI doesn't need any new save/load data. It also means that the "plan reconstruction" step includes the "well, I have a better plan for those resources" -- units that are massing for an invasion will be considered "not really in use" and automatically claimed to stack-stomp and enemy force. Afterwards, the balance of units on the map might be way different, leading to a different massing point and a different invasion target. . .

    Of course, this could also lead to instability, where moving a stack towards city A results in the planning engine deciding that city B is a better target. :) Without "plan state", the AI wouldn't even know it was going back and forth between the two targets. . .

    ...

    However, the basic "stack stomp" can be done in the "stateless planning" mode. I'm trying to figure out if there is an easy way to control the order that units attack later in the turn (or maybe units should move during the planning phase? That seems pseudo-cheating. . .)
     
  11. Iustus

    Iustus King

    Joined:
    Jul 18, 2006
    Messages:
    609
    Location:
    Sunnyvale, CA
    Not wanting to change the save data but wanting to have some long term decisions stick across turns gets us back to why that code was put in based on starting position to make some strategic decisions (see the other thread).

    There are many tradeoffs in maintaining save game compatibility, and this is one of them.

    Other options would be to:
    - use the "ExtraSaveGameData" functionality I wrote, to take advantage of some unused parts of the save game file (there are some structures which are saved out, but immeditately thrown away when loading a saved game)
    - save all the extra data in a separate parallel file, and be able to run fine when the file is not there (not sure how possible this would be, since I dont think the lib currently does and file io)

    -Iustus
     
  12. Iustus

    Iustus King

    Joined:
    Jul 18, 2006
    Messages:
    609
    Location:
    Sunnyvale, CA
    Each unit knows if it has been moved (or rather how many moves it has left) on its own, so...

    I think you could build a separate (ordered) list of units that you want to move first during the turn. Then, just before you do the regular unit moves, run through your ordered list and move those units first. Then fall through to the regular code, which will go through all the units, but it will skip the units you already moved (there may be some issues with units you decided to keep in place, so they still have movement left, I do not recall where the 'skip' command gets cleared, I think it is at the beginning, in which case you are fine, if it is right before all the units move, then you want to make sure you insert after that).

    -Iustus
     
  13. Nor Me

    Nor Me Chieftain

    Joined:
    Feb 22, 2003
    Messages:
    50
    Couldn't you do a bit of both by calling most of the planning code from CvPlayerAI::AI_unitUpdate. Plans move units. When the AI has run out of plans, it does the "loop through all units" plan.
     

Share This Page