1. We have added a Gift Upgrades feature that allows you to gift an account upgrade to another member, just in time for the holiday season. You can see the gift option when going to the Account Upgrades screen, or on any user profile screen.
    Dismiss Notice

Ai

Discussion in 'Civ4 - Community Enchancement Project' started by Olleus, Jun 2, 2006.

  1. Olleus

    Olleus Warlord

    Joined:
    Oct 30, 2005
    Messages:
    6,478
    Location:
    England
    If the only purpose of having a genetic AI is to decide the size of a certain variable, wouldn't we be better off using human experience by doing the experiment I described above, where you note down everything you do and why?
     
  2. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    But turning every experience into a number, or a combination of numbers based on different things is rather hard...
     
  3. Olleus

    Olleus Warlord

    Joined:
    Oct 30, 2005
    Messages:
    6,478
    Location:
    England
    But at least it gives a starting point on what the structure of the code should be...
     
  4. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    But turning every experience into a number, or a combination of numbers based on different things is rather hard...

    My idea was, as you say, to optimise the values (such as build values) for each factor within the AI. Main reason for this is that it isn't such a big project. It seems to me that while the algorithms can't really be simplified to the numbers that define them, optimising these numbers will produce a better AI, even if we don't change the way it "thinks". Would the fact that we're starting from a pretty good AI help cut down the number of generations needed?
     
  5. NikG

    NikG SDK Lover

    Joined:
    Nov 30, 2005
    Messages:
    170
    Location:
    Glorious state of Denmark
    Well I still believe we should try and implement a hierarchical layered AI. But the problem with optimizing pure numbers, is that it can get stuck at a local optimum. Of course having a good AI should (in theory) be better than having a less good one. The problem is still just that these numbers in the end corrospond to direct action, which is factored by so many different things, that in some games it is better to build cottage, while i others in would be better to build workshops.
    So by having a fitness function of the outcome, would not really say something general about the AI (ie. "this is better than others"), and poor startpositions could well turn a perfectly turned AI into the bad one, quickly getting wiped off by a less perfect, simply becuase of startpositions.

    AI will always be an extreme undertaking, but if we use a hierarchical layered and change the way the AI "thinks", we might well create a very powerful and much better AI, coupled with a kind of simple learning neural net, which learns the values of these variables we are taking about (often more effective when many factors are in play, and have the ability to learn under the game to).
     
  6. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    You are correct. The numerical factors are there to decide this, but they don't cover everything.

    However...

    I'm planning on writing a genetic one anway based on the idea I suggested above :D. While it may not give any good results, I think it would be quite a fun thing to do. I could leave it running in the background of my computer when I'm not using it, and I'd quite like to see what results it does come out with.

    This is why I would run each AI through several different games. This will mean that the fitness determined will be for the good starts, and the bad. 10 may not be enough - it'd have to be tested by applying the fitness function to a load of default AIs and seeing what the variation after every few games is.
    How would we teach it? Would this be another case of AIs bashing their heads against each other?
     
  7. NikG

    NikG SDK Lover

    Joined:
    Nov 30, 2005
    Messages:
    170
    Location:
    Glorious state of Denmark
    Well a quick comment: Yes, a neural network could be used. An experiment where only AI vs. AI, no human involvement. It would be an unsupervised learning algorithm of some sort. Maybe we should even have more than one. Actually one for each of the layer of the hierarchical layered AI, because after all if we should only have one, it would get so generalized that it wouldn’t help, or it would take to long to learn it anything, or even takes to much time to compute.

    However modeling this neural net, would be just as hard as a modeling a genetic algorithm (I am talking about the representation),
    but it would certainly be more doable, and it would even learn after the mod has been released (don’t be afraid about contamination ;))
    My project is due to be finished to night (wooh 7 weeks in row of writing docs and programming), so I will try getting a design document of the AI by Monday afternoon, including both the hierarchical layered AI and aspects of the neural net. I will not dig to much into the genetic algorithm, unless people want it.

    Btw TGA you are more than welcome to program a genetic algorithm, which will be very interesting, and it could turn out to our favor anyway, which will be a good thing. And if not you have learned something in the process (never to old to learn something).
     
  8. chrusion

    chrusion Chieftain

    Joined:
    May 5, 2006
    Messages:
    36
    Location:
    Seattle, WA
    NikG has the right idea in my opinion. The AI is best organized as a military organization:
    The King has Generals have Captains have Lieutenants have Sergeants

    All current CivIV game AI functionality is the peasants.

    The depth of this layering should be easily changeable and variable to functionality area of coverage.
    The AI that is a pseudo-recursive agent (becomes many sub AIs) down to the lowest layer.
    The recursion then bubbles appropriate data back up the layers as each recursion cycle finishes.
    Each cycle uses data from the previous cycle (or from several cycles derives an average, median, or some other algorithmic value).

    Each possible action is the responsibility of the Sergeants, obeying the orders of his superiors in the context of the current situation; no other level has direct control of the CivIV game. The Sergeants place local, action related / situational data on a whiteboard data object.

    Each Lieutenant is concerned with his orders to pass on to his Sergeants; these orders are affected by the data his Sergeants have gathered. The Lieutenant puts a summery of the data on the white board.

    Each Captain is concerned with his orders to pass on to his Lieutenants; these orders are affected by the data his Lieutenants have gathered. The Captain puts a summery of the data on the white board.

    The Generals do the same.

    The King takes in the whole picture, as summarized by his Generals, and gives new orders.
     
  9. 12monkeys

    12monkeys Chieftain

    Joined:
    Nov 24, 2003
    Messages:
    440
    Location:
    Germany, Europe
    I havn't follow this thread very deeply, but are you all sure that this became a bit to much for that project? The plans you have will have to much impact to the SDK that it could be done between two releases. That makes it hard to organize. Also I think that this is an complete own project. Maybe its even an own project to create the concept without an SDK. I have my doubts that we are able to manage that.
     
  10. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    I see no reason why there should be any problem with spreading changes over two, or more, releases.

    Another thing I randomly read:
     
  11. Impaler[WrG]

    Impaler[WrG] Civ4:Col UI programmer

    Joined:
    Dec 5, 2005
    Messages:
    1,750
    Location:
    Vallejo, California
    I like chrusion's description and had some thoughts to add.

    Each of the Entities he describes could hold "priorites" which are basicaly the goals its striving for. The King AI takes a broad overview of the game state and takes input from the Leadhead flavor tags and sets himself priorites that are apropriate. Priorities can be have a weight (vHigh to vLow)and a time frame (Imediatly to Eventualy). At times when the kind changes his priorities he may instantiate or destroy minister AI's, or re-alocate assets to them. The kind dose not tell them how to complete their tasks or set their internal priorites other then through the timeframe value.

    Minister AI's fall under 2 loose catagories Military (called a General and is focused on miliary campaigns) and Domestic (called a Govenor which focuses on Cities and workers) the naming is purely symantical as any asset can be controled by any Govenor. Different types of Ministers are generated acording to the kings priorites and it then generates its own set of priorites based on the time frame value and Asset array passed to it by the King using its internal logic. These priorites are updated each turn to see they are apropriate, so for example if the King sets "MORE GOLD" as a Priority its instantiates the "Greedy Govenor" and passes it the timeFrame and control of some Assets with which to achive the goal. A "Greedy Govenor" could be given several Cities to run and some workers with whitch to build improvments. The Govenor might instantiate additional sub AI's to control individual units or Cities. The King would personaly control Research as this so heavily impacts every aspect of the game and needs to be cordinated with all his priorites.

    When the King desides to end a priority the minister is terminated and its Assets reassigned to other ministers. If the King desides to change the Weight of a priority it will re-assin Assets to reflect this change in Weight. So for example if "Milirary Buildup" Weight goes from low to High several additional cities would likly get re-assigned to reflect that. A change in timeframe is passed directly to the minister so that it may re-evaluate its own priorites. When new Assets (Units and Cities) are created they get assigned to the govenor that can make the best use of them. Periodicaly the King (or any AI) will re-allocate assets based on a "desirability" value that the sub-ministers will report back when ased to evaluate the desirability of an asset. So for example the "Offensive Warfare" general will report that it more highly desires a unit that has a CityRaider promotion then one with a City Garrison promotion, the "City Defence" general would do just the opposite.

    The King owns all assets and can ask any of his sub ministers to evaluate the assets they currently control along with any other asset he might wish to querry them about. He will frequently (idealy at the start of every turn and durring key parts of turn processing) ask them to give a desirability for an asset they dont control. The King takes all this under advisment and re-assignes accordingly. So for example the "Protect the Workers" minister could beseach the king that he should be alowed to take control of a threatened worker away from the "Build Growth Improvments" minister that currently controls it, it could also grab an archer from a nearby city (if "Defend Cities" minister dosn't need it too badly) and move both units into a forest for defence. Once the threat passed the Protector reports low desirability for its assets and they will get re-assigned. The now assetless Protector would hang around and each turn the King would ask it if feels any of the workers are threatened. A "Protect Improvments" general would likewise be responsible for prevent pillaging. Map plots within the players Cultural borders are also evaluated and assigned as assets both for the purposes of determining which city will work any overlapping City plots and for desiding what type of Improvments will be built.

    Desirability serves as the primary means to make shure the AI "stays the course" and finishes doing what it starts and dosn't flit between half finished tasks. For example a City govenors would take into account the current progress of buildings at a City so if a Wonder is a few turns from completion the govenor will report very high desirability to control the Cities build quee so that it may complete the wonder. The "Defend Cities" general would have to deside the city was in such iminent danger with no possibility of outside reinforcments ariving in time to beat out the domestic govenor for control of the queue and change to building a defender.

    Such compartmentalization means each minister can be very narrowly focused on its area of expertease, by writing minister Instantiations, weights and timeframes to a log file the Kings behavior could be interprited and tweaked. Ministers would log their desirability allocations to see if they are making poor choices.
     
  12. chrusion

    chrusion Chieftain

    Joined:
    May 5, 2006
    Messages:
    36
    Location:
    Seattle, WA
    Bravo Impaler! Very nice analysis and extension! I like the narrowly focused ministers! Puts a very nice parallel algorithm into effect with tension(Desirability). A sort of fuzzy matrix if you will :)

    Yes, this is a big project but it CAN be broken up into several steps. Lets finish brainstorming out our ideas and come to a consensus on a plan. Only then can we see the steps we have to take and how we should break them up into sub projects.

    The options will be clearer then!
     
  13. Impaler[WrG]

    Impaler[WrG] Civ4:Col UI programmer

    Joined:
    Dec 5, 2005
    Messages:
    1,750
    Location:
    Vallejo, California
    Some thoughts on combining above system with Genetic fitness functions.

    We could use the above plan in combination with traditionaly programed ministers and it would likly work fine and be a huge improvment on the AI. but seeing as everything is naturaly encaplusated its should be possible for some or all ministers to be created or tested in non traditional ways.

    I remember reading some interesting stuff about node based genetic algorithms being used to teach little "bots" to fight a shooter game (wish I could remember that link). The little bots take a set of simple inputs "angle of nearest enemy", "range of nearest enemy" "is enemy in crosshairs" and output simple things like "move forward", "rotate clocwise", "shoot". If we have an automated play system then we can set up AI vs AI games and use the loging feature of the King combined with a fitness function we give him to record an evaluation of the ministers he used.

    Different Civs in the game would be instructed to use different minister Instances for the same Kingly Priority. Each game would test only a single priority/minister pairing so all other factors remain constant and the only differences in AI logic will be the effectivness of that particular minister type. After the game ends the Kings evaluation log could be digested by an outside program (or better yet the Python layer outside the game instance). Said program tabulates scores for the various ministers types taking into account the Kings performance evaluation AND an evaluation of the Kings game score. This way we catch and penalize ministers that achive their goals by screwing the rest of the Civ (for example a "Get Gold" minister that neglected food and starved his cities). Once sufficient tabulations have been gathered the mutations are made and another round of testing begins.

    It would likly be nessary to build up the minister tree from the bottom up, At first the King would be an almost wholey automated pice of code that just switched priorites at random. Once the ministers are developed to the point of basic competency you could begin developing a thinking King which would start to set priorities based onthe game state. A cycle between minister improvment and King improvment would then commence and each generation the King would be taught to recognize the improving skill of the ministers and comensuratly call upon them more often.
     
  14. Impaler[WrG]

    Impaler[WrG] Civ4:Col UI programmer

    Joined:
    Dec 5, 2005
    Messages:
    1,750
    Location:
    Vallejo, California
    Further Musings...

    Their are likly going to be a lot of 3 way tug of wars between ministers and these need to be handled well or the AI could end up doing su-optimal things for example when say the Sciene, Culture and Gold ministers all want to have a Harbor built in the City to boost Commerce but the Military general wants a Barracks.

    If the King allocates resorces based soley on the minister with the highest desire for the asset (after taking Priorities into acount ofcorse) then you have the potential for mis-alocation. The simplest solution would be for the King to ask each minister what they intend to do with an Asset and votes are talleyed by camps of usage rather then individual ministers. The highest camp then gets the resorce with the highest priority minister actualy being assigned the asset. The king only runs this kind of check if their is no clearly dominant minister.

    A whole class of "Efficiency" ministers would exists as well, they would aim for overall efficiency in the economy and act to give balance to the very narrow views of most other ministers.

    Lastly another minister type, the "Advisor", these can be though of as the Power behind the throne. Advisors would be persistent and instantiated at the start of the gamem, they never control assets. Under this new interpritation the King acts like on Operating System Kernel, the only thing he dose it ask for the advise of advisors and apoints/removes minister and alocates assets. His only memory is the Priority list, the minister lists and the asset list of each. Advisors tell the King what Priorities to set and then he passes thouse Priorities to other advisors who tell him what generals and govenors to apoint and what assets to give them. This further compartmentalizes the AI logic and makes it easy to understand the Kings desisions and modify them by use of different Advisor types. It also allows us to write a small and efficinent King who's code will be stable and completle very quickly before trying to build upon it with minsters and advisors.

    I am not realy shure I like the many layered military hierarchy chrusion layed out. One of the AI's current problems is lack of cordination between units. I think it would be best if the lowest level of minister was more of a Luitenent comanding a whole stack or group of units tasked with achiving an objective, this would allow good cordination of forces at the critial tactical level. Luitenents would have types such as "Besige City", "Pillage Countryside", "Take City", "Amphibius Landing". As Lord Olleus pointed out the AI dosn't re-evaluate desisions as the units are moved, we would allow the Luitent to re-asses after each unit movment/attack as the turn is exicuted. Above the Luietenent is a General who as you know is reporting to the King, the General will usualy only comand 2-4 Luietenants, often just 1 in the early game, Generals will usualy comand an entire war-front with a designated enemy player to wage it against, multiple wars on multiple fronts will nessesitate multiple generals in addition to the Homeland Defense General. Generals instantiate and delete Luitenents to activate campagins, for example removing a "Besige City" Luitenent who just bombards the City and re-assigning the assets to the "Take City" Luitenent which actualy performs the attack. Another point in the context of military units the timeframe parameter basicaly equates to expendability, short timefram leads to rekless suicidal behavior, long to cautiosness and defensiveness.

    The Advisor Concept can be extended to the Military level ware they become "Strategists", again the Generals and Luitenents become kernel like as they have no real internal logic. (On the Domestic level you have Staff for the Govenors, remember this is all just symantical nonsense at the code level their no domestic/military split and only only modest functional difference between ministers and advisors). The Luitenent could themselves have Strategists (perhaps we can call these by a different name to do destinguish them from thouse at the General level).

    NikG && TGA what do guys think?
     
  15. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Sorry, been busy lately with end of exams, and having far too much fun ;)

    I'm concerned about time. We don't have to just create a good AI, we need to create a good AI which will be able to do all it's calculations in a reasonably small timescale so that the player(s) don't get bored. While this may sound good on paper, I'm worried that it might not be possible to do all the calculations neccessary in an appropriate timescale. At the moment each city only really runs one minister, and the king has very little impact on the decisions. Running 5 ministers and evaluating their choices to find which is the best is going to take longer.

    At the moment the time is about right. At the start of the game it isn't really noticable, however, once we get to the latter stages with hundreds of units each, it starts to become noticable. We may be able to get away with allowing the AI a bit more time, as the turns progress pretty quickly at the moment, but not too much.

    To keep this idea from swallowing time might be rather hard, although I'm sure there are solutions which hopefully can be implemented without degrading the AI skill too much.
     
  16. Olleus

    Olleus Warlord

    Joined:
    Oct 30, 2005
    Messages:
    6,478
    Location:
    England
    one possible way of saving time is for the AI to do its calculations while the human is playing. This would not work during war, for obvious reasons, but during peace there is no way (or very little) in which the human player can affect the best improvement for a tile in a distant continent.

    This might be very difficult to implement though.
     
  17. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    I had a brief discussion with Rhye about something similar to what you just proposed LO. I'm not certain, but I think it may be just about doable. Given that decisions are processed at the end of turns, rather than the start of turns we could do as much work as possible during the player's turn, and then check to see if anything has been changed which may invalidate the decsions (declaration of war, important tech trade, contact with a new civ etc.)

    You'd almost certainly have to restrict it to decisions not relating to unit movement, but that shouldn't be a problem.
     
  18. chrusion

    chrusion Chieftain

    Joined:
    May 5, 2006
    Messages:
    36
    Location:
    Seattle, WA
    Good one LO! I was going to suggest along those lines.
    Also, some decisions do not need to be made every turn so the work can be spread over several turns.
     
  19. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    I've pretty much got most of the genetic AI stuff nailed (for value tweaking, nothing more complicated). I just need to traul through the SDK finding values.

    Then I need to find a way to get the game to keep running games with no interferance needed.
     
  20. SpoiledFruit

    SpoiledFruit Chieftain

    Joined:
    Mar 11, 2006
    Messages:
    72
    Location:
    Boise, Idaho
    If the warlords expansion comes out before you get the auto AI working, you should take a look at the Genghis Kahn scenario Firaxis is making. It sounds to me like they are having the AI play a lot of turns before you enter into the world.
     

Share This Page