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

Genetic AI Development

Discussion in 'Civ4 - Community Enchancement Project' started by The Great Apple, Aug 30, 2006.

  1. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    I felt it needed a new thread.

    I'll try and maintain some current source code on this thread. Also, if anybody wants to contribute any code I'll gladly accept it and plug it in, providing you're willing to support if it goes wrong!

    If you browse through the souce you'll notice how I've plugged in my AI changes between the normal AI class and the object class. I suggest you do the same (ie. create a new file and set up inheritance) with any changes you wish to make for easy pluggability.

    Link to current source (v0.31)

    Link to current client files (v0.32) (with SDK debug information for crash dumps)

    Link to all data collected so far (1st Sept 2006)

    The SDK should compile straight off.


    See bottom of the post for various attachments involving some python programs I wrote to help analyse the data

    Also attached is the current AIFilter script.

    Basics:
    1) Load AIs.

    2) Normalise the data sets with other sets of their generation.

    3) Combine any AIs which are duplicated

    4) Filtering - this is the fun bit:
    a) Filter out many AIs based on fitness. AIs with the best of a particular stat will avoid this filter. Any which pass are mutated to form a similar AI, and added to the breeding list
    b) Set up to 5% of the population who have more then 95% of the maximum fitness to become elite. These members will carry on unchanged to the next sample.
    c) AIs on the breeding list are bred until we are back up to the minimum population.


    Mutation:

    All the AI's values can be mutated either up or down. They can rise by up to 20% + 2, or fall by up to -20% - 2. Half the values will be mutated every time.

    Boolean values to enable/disable custom functions have a 1 in 10 chance of being flipped. Don't currently have any of these yet.


    Breeding (crossovers):
    Simple. 2 AIs come in, each value on each AI has a 25% chance of changing to the value of the other AI.

    Spoiler Todo list :

    No particular order.

    1) Sort out AI names to reflect generations & victories.
    2) Do performance and bug checking on some alternative algorithms (data loading and SDK).
    3) Start writing program to pick out data values causing different traits.
    4) Sort out tracking - it's all slighlty messed up.
    5) Fiddle around with the reminder icons - they don't disappear when minimized and eat memory.


    EDIT: Filter updated 4 Sept 2006
     

    Attached Files:

  2. Craterus22

    Craterus22 Chieftain

    Joined:
    Oct 7, 2001
    Messages:
    689
    Regarding your Todo list:
    #3 - you may have missed it in other thread - I believe the slowdowns I was experienceing was due to using more AI's in my 4 initial games - instead of 10AI now it was 12AI (I used to rename all the ai with numbers and gen - play top10 vs bottom10 and odds vs evens - I would usually do this in order to have all the AI play the same Leader - my theory being if they all play the same leader there are less variables - this became tedious of course and now i just do auto).

    Perhaps the increase in time didn't have anything to do with your mod - perhaps it was a memory issue regarding the use of more AI's?

    At this point I now run around 9AI or less for the most part.

    #1 After tackling the name generation system (identifying victory types or Most Attractive Attribute) could you add something for aligning AI strength and civ leader traits? Even if the AI could recognise ONE trait of a particular AI it would be an improvement. Also, if during your data collection the games played would record the leader used during that game - correlations of success could be found.

    Perhaps future AI packs could include just 8 AI's? Have the AI's align (50/50 chance to pick trait to use) with appropriate leader (which could result in more than one civ in a single game using the same AI).

    Aggressive
    Free Combat I promotion of melee and gunpowder units.
    Double production speed of Barracks and Drydock.
    Creative
    +2 culture per city.
    Double production speed of Theater and Coliseum.
    Expansive
    +3 health per city.
    Double production speed of Granary and Harbor.
    Financial
    +1 commerce on plots with 2 commerce.
    Industrious
    Wonder production increased 50 percent.
    Double production speed of Forge.
    Organized
    Civic upkeep reduced 50 percent.
    Double production speed of Lighthouse and Courthouse.
    Philosophical
    Great People birth rate increased 100 percent.
    Double production speed of University.
    Spiritual
    No anarchy.
    Double production speed of the Temple.



    My last suggestion for a while:
    Is there anyway to switch AI in the middle of the game? It would be cool if during the game, the AI could change. Some AI's may be good at winning with a lead, others may be good at coming from behind. Some may be good at initial expansion, but needs a different strat once it gets to mid-game/end/game?

    For example, lets say Victoria starts out with the Expansive AI, but is not in the top half of the score list at the half way point in the game. Perhaps a switch to the Financial AI would be in order?

    Keep up the great work!

    BTW - I am currently looking for a good map script that would provide semi-equal starting positions - tried hub and wheel for awhile - currently using continents...
     
  3. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Updated with proposed version 0.30 source and client files. I would appriciate it if somebody with a bit more experience could check over my AI variable fetching method to make sure it's optimal as it is used ALOT during the course of a game. (see GeneticAI.cpp and an AI file (not GameAI, nor SelectionAI) for examples of how I use it).
     
  4. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    A dilemma - Warlords related.

    The Warlords AI is better then the vanilla AI, but the AI code for each of them is available to anybody with Warlords (ie. me). Having had a quick look few it wouldn't take too long to merge the Warlords AI improvements with the default game, and use that to improve the AI.

    The trouble is - I'm not sure it's legal. The code is available only to people with Warlords, and by putting it in this project I would be making it available to everybody, taking out one of the selling points of Warlords. This is bad.

    Any thoughts?

    EDIT: Craterus22 - the trouble with that would be that you wouldn't know which AI caused the ranking to be where it was (either good or bad). I suppose it might work for the final product.
     
  5. Craterus22

    Craterus22 Chieftain

    Joined:
    Oct 7, 2001
    Messages:
    689

    Legal: better safe than sorry... unless you hear from a firaxian, I would stick to having seperate versions. BTW - I agree with you 100% about waiting for at least the first patch on warlords before spending time on it - plenty of people will benefit from a civ4 specific ai improvement.

    regarding edit - yes for the final product was what i was getting at... but recording which leaders an Ai was successful with may be useful information to have a few generations down the line. Perhaps narrowing it down to 8ai would be bad though there may be multiple financial ai's that are successful in different ways - it may be worth having multiple ai's to be randomly assigned per civ trait.

    Regardless of what you do - thanks for all your hard work. I am hoping to spend some time with your code this week to see if I can figure some things out.
     
  6. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Okies. Should be fairly easy to tag the leaderhead and Civ on the game history data - will do so.

    If you have any questions about my code feel free to ask. I've been fairly sparse with my comments.
     
  7. se7en

    se7en Chieftain

    Joined:
    Apr 17, 2003
    Messages:
    96

    also, please change the leader's display name to the name of the AI that is playing it for those of us who like to watch :)
     
  8. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Done! The mouseover info on the scores still displays the leadername, but that's a tiny little thing and I'm not sure I can be bothered to fix it.

    Next release should be tonight. I might or might not run a new generation as well.
     
  9. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    I've updated the source and client files to version 0.31. I've added a few entries to the AI data mostly to do with new algorithms. Will be updating the one on the thread some time soon.

    I'm planning on sorting out a new project on SourceForge for this, rather then mess up the CCP CVS. When that's up the source should be slightly easier to manage.
     
  10. Craterus22

    Craterus22 Chieftain

    Joined:
    Oct 7, 2001
    Messages:
    689
    actually mouse over of name of leader might not be a bad idea so that we can see all relavent info -
    IOW: knowing both the ai and which leader it is playing is attractive to me.
     
  11. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Okies. A couple for testing:

    Run using the client files in the first post.
     

    Attached Files:

  12. se7en

    se7en Chieftain

    Joined:
    Apr 17, 2003
    Messages:
    96
    awesome, im running some tests now.

    i love that you can see the ai ranking now. :)
     
  13. se7en

    se7en Chieftain

    Joined:
    Apr 17, 2003
    Messages:
    96
    im getting a consistent ctd about 1 hour into it when running minimized (the only way i've tried to run it, so far.)

    attached are the debug logs for the second occurance, i didn't have logging enabled the first time. if there's anything else you need let me know.

    i didnt attach the mplog because it was 27MB uncompressed.
     

    Attached Files:

  14. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Hmm. Doesn't really tell me much, except that you have autosave on, and you might want to switch it off for a bit more speed ;)

    What would be really useful is the crash dump file. These logs are only really good for finding things which I either expect to find, or which occur in the python. This, unfortunetly, is neither.

    If you don't have crash dumping enabled it's another option in the .ini file. It's only really useful if you've got the debug info for it, which you do. If you can grab a normal crash dump next time and get that to me somehow it might reveal the problem.
     
  15. se7en

    se7en Chieftain

    Joined:
    Apr 17, 2003
    Messages:
    96
    of course now that i have my environment set up right for capturing debugging info it's working fine.. hmm. well, if it reappears at some point i'll be ready.
     
  16. se7en

    se7en Chieftain

    Joined:
    Apr 17, 2003
    Messages:
    96
    i finally sat down and did some math with regards to the mutation, number of offspring, etc and came up with a few ideas. i don't know what your current algorithm for developing offspring is but i'd be interested to hear it.

    i've assumed a active population of around 200 ais "in play" in any one generation. it doesn't change too much as you go either way except in test time, anyway.

    i think that the primary unit of mutation should be a single array (which, for those who haven't looked, basically corresponds to one CPP file.) Every generation should swap array sections, instead of blending values, to create children. since arrays are essentially functional areas, hopefully this would encourage different behavior sets to evolve moreso than random mutation. it also seems to me that blending would result in potential early convergence towards an "ok" solution.

    since we're keeping the successful population for the most part unchanged in the gene pool, i think that general mutations to the rest of the population need to be more severe. For example, instead of plus or minus one or two per generation it should be plus or minus a random percent between 25 and 75. i want to see AIs doing crazy things even if it causes them to play horribly.

    i also think that some of the worst performing ais should be re-entered into the gene pool on the assumption that they are at least doing something *different*, and possibly by combining them with a successful ai (using full section swaps) something interesting could come out.

    when ais are selected in-game, there should be a preference towards matching the strengths of the ai with the available leader traits, although it shouldn't be 100%. maybe more like 60% probability.

    here's an example distribution policy i came up with:

    10% (20) are from the top AIs and just go back in to the gene pool unchanged.
    20% (40) are from the top AIs and are heavily mutated within ONE array section, but without swapping arrays at all.
    20% (40) resulting from top AIs and top AIs breeding using full array swaps, followed by one pass of mutation to all values within one of the arrays.
    10% (20) resulting from top AIs and mid-level AIs breeding using full array swaps, followed by one pass of mutation to all values within one of the arrays.
    20% (40) resulting from top AIs and worst AIs breeding using full array swaps, followed by one pass of mutation to all values within one of the arrays.
    20% (40) of random AIs are bred with random AIs using array swaps, followed by one pass of mutation to all values within one of the arrays.

    any thoughts? is this already basically what you're doing?
     
  17. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Currently we're looking at nearer 400-500 AIs per generation. I create 1000 per generation, but it seems that quite a few get downloaded but don't get run, and are lost.

    My current system is alot more simple then what you propose. Currently this is the core of it:
    Code:
    for AI in self.AIList:
    	# AI has to have played a minimum amount of games to be eligable for removal
    	if AI.getNumGames() < g_iNumGames * (AI.getElite() + 1):
    		AI.setGeneration(AI.getGeneration() + 1)								
    		newAIList.append(AI)
    	elif AI.getAIName() == "Team Firaxis":
    		AI.setGeneration(AI.getGeneration() + 1)
    		AI.setGameHistory([])
    		newAIList.append(AI)
    	else:
    		iPass = 1
    		# Weighted towards better AIs. If this test isn't passed, AI is removed entirely.
    		while randint(0, iTopFitness * (iPass + 1) / 2) < AI.getFitness() and (randint(0, 1) or AI.getFitness() > iAverageFitness) or (iPass == 1 and AI in bestStats):
    			if iPass > 1:
    				AI = deepcopy(AI)
    			else:
    				breedingList.append(AI)
    
    			if (AI.getFitness() > iTopFitness * 0.95) and (self.iNumElites <= len(self.AIList) * g_iElitePercentage / 100) and iPass == 1:
    				print "Elite!", AI.getAIName()
    				if not AI.getElite():
    					self.iNumElites += 1
    				# This needs to be before we alter the generation
    				newAI = self.mutateAI(AI)	
    				newAIList.append(newAI)						
    				AI.setElite(AI.getElite() + 1)
    				AI.setGeneration(AI.getGeneration() + 1)
    				newAIList.append(AI)
    			else:
    				if AI.getElite():
    					self.iNumElites -= 1
    				AI.setElite(0)
    			
    			newAI = self.mutateAI(AI)
    			newAIList.append(newAI)
    			
    			iPass += 1
    
    while len(newAIList) < g_iAIMinPopulation:
    	if len(breedingList) > 2:
    		AI1 = choice(breedingList)
    		AI2 = choice(breedingList)
    		
    		# Better AIs breed more
    		while (AI1 == AI2) or (randint(0, iTopFitness) > AI1.getFitness()) or (randint(0, iTopFitness) > AI2.getFitness()):
    			AI1 = choice(breedingList)
    			AI2 = choice(breedingList)
    
    		newAIs = self.crossoverAI(AI1, AI2)
    
    		newAIList.append(newAIs[0])
    		newAIList.append(newAIs[1])
    	else:
    		AI = createNewAI()
    		newAI = self.mutateAI(AI)
    		newAIList.append(newAI)
    The mutateAI function just randomly changes values (up to +/- 20% +/- 2 - so it works on both low and high values), crossover crosses over individual values with a 25% likelyhood. Crossovers only occur on unmutated AIs, and AIs with a high fitness are much more likely to breed.

    At the moment each AI that passes the while loop once is put up for breeding and is mutated once. Any further passes have another mutation made based off them. Any AI can pass the first entry, however an AI with only 25% of the top fitness probably only has a 12.5% chance of doing so (unless the average is really low).

    Currently I have a cap at 5% on the number of elites, and they have to be within 5% of the highest score. I think I may raise these both to 10% as per your recommendation. While these AIs go through unchanged they still create new AIs mutated off them, and can still breed.

    I like your ideas of more sophisticate crossover and mutations of specific arrays rather then the whole. I think I'll have a mess around with those algorithms a bit.

    I've run out of third generation AIs, so I'm going to have to post up the next version. Hopefully I can fix whatever problem there is with a patch.
     
  18. se7en

    se7en Chieftain

    Joined:
    Apr 17, 2003
    Messages:
    96
    Here's the results for aidata60.
     

    Attached Files:

  19. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Good news everybody!

    Next version should have full load/save compatability. I've been doing some work on it today and it appears to be all working. It should even let you save it in the middle of a game so that you don't have to waste that time between when the latest game started and when you want to do something else big with your computer.

    Version posted in first post has this enabled.
     
  20. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Poking about with matching AIs to leader styles at the moment. What do people think the best way of doing this is? At the moment my plan is to get the AIs for the game (randomly from the pool), and then fit them to the leaders in the game, rather then fitting the pool to leaders.

    This should give a bit of randomization - agressive leaders will get the more aggressive leaders out of a small batch, rather then getting the agressive ones of them all. This should help maintain diversity a bit.

    Any thoughts?
     

Share This Page