Archive for the ‘AI’ Category

AI Architecture Overview

Sunday, June 21st, 2009

I’ve had a heck of a hard time with the design and implementation of the AI for Solium Infernum. I’ve erased the drawing board twice in fact. The only thing that remains from the Armageddon Empires code is the basic structure of the goal objects themselves. A goal still activates — goal.Activate() — to do its data analysis and planning and then is processed — goal.Process() — when it comes time to generate the AI’s orders and actions. I also kept the concept of an AIBrain object as a containment device and goal action interpreter but that’s not really much of an innovation or big deal. I’ve also still got all the fuzzy logic modules and work that I had done but that’s not a big deal either (although a lot of saved work)

When I first went to approach the AI for Solium Infernum my major concern was to improve the “meta reasoning” and the prioritization system for the goals that were generated. In AE each top level goal was given a priority ranking and the goal might or might not get processed depending on how it ranked with other goals and how many action points were available. The ranking was of course dynamic so as the AI Brain’s gained information or processed new meanings from information the ratings of the goals that it was pursuing went up and down. This worked pretty well for AE since you averaged a good deal of action points each turn (even if you couldn’t predict exactly what you would have each turn due to the dice buy and roll system for initiative) but for SI it wasn’t working very well.

The reason was because the actions that you perform each turn are much tighter and fewer in number. You have a maximum of 6 order slots to use each turn and most games you will only have access to 2 to 4 slots. That means that you have to really focus your strategy. You can move legions, demand resources, perform rituals, bid on items in the bazaar but you can’t do them all in a single turn. If you are pursuing a vendetta against another player and only have 3 order slots then you will be moving at most 3 legions that turn. There are other orders that you can issue but they are “Response” orders that happen when you respond to an item in your turn log. For example if somebody makes a demand of you then your “response” generates an order but it doesn’t cost you a slot. But the short of it is that a competing priority system doesn’t make much sense when your actions have to be very focused like this.

So for SI I came up with the concept of a ranked pipeline with a two tiered goal system. Critical goals are tier 1 goals that must process through until some condition is met. They cover situations that just can’t be replaced by another goal and forgotten….things like pursue Vendetta, defend against Vendetta, pursue Blood Feud, retake Pandemonium etc. Mission goals are tier 2 goals that provide not only the foundations to pursue the tier 1 goals but also the “character for the AI’s.” These are goals that focus on building up your capabilities, pursuing your primary and secret objectives and determine to a large degree how the AI interacts with its opponents. Tier 2 goals often lead to situations that cause tier 1 goals to be generated.

You can have any amount of Tier 1 goals in the pipeline and they are ranked according to how critical each one is. If you are engaged in two Vendettas then one Vendetta is going to get a higher priority than the other depending on which situation is more dangerous. If a tier 1 condition ends then the goal is removed from the pipeline (stack) and all the remaining tier 1 goals pop up to fill the vacant space…. this is actually quite rare though. It’s the AI’s job (like any good human player) to make sure that it doesn’t have more tier 1 goals than it can handle. On the eve of the anniversary of Barbarossa this ironically is always easier said than programmed. What’s nice about the diplomatic system in SI is that in most cases you can avoid tier 1 goals to a point if you are willing to sacrifice something be it prestige, resources, land or even artifacts. So you can put off an inopportune bully but at a cost (and only for so long but that’s another discussion).

The Tier 2 goals can only ever exist one at a time and are very fragile. They fail easily and are replaced by another. The AI’s have Archetypes that are randomly chosen that determine their Avatar attributes, perks, rank etc (not deterministic but random within ranges and pools of choices for perks). The Archetypes define a play style by influencing the composition of a strategy pool of rated choices. For example if the AI was an #AggressiveWrath type then it would favor building up its military capabilities and start bullying its weaker neighbors if the opportunity looked good. When it needed a solution to some problem then aggressive type goals will be rated higher. It’s martial Skill attribute will get precedence so that it can increase its Command Rating and get more legions out on the board. So when a tier 2 goal is needed the AI constructs a list of possible goals that each have a specific rating for desirability. Some situations might prompt the AI to rule out certain goals entirely or only consider a singe goal. Finally a roulette wheel approach randomly determines which goal is chosen but goals with higher ratings will of course be more likely to be chosen. That’s the key to generating “character” or “personality” type behavior.

That’s a pretty good description of the high level architecture for the AI. The concept is nothing new and the hard work is all in creating the goal objects and their scripts that process information and yield discrete orders. In some follow on entries I see about discussing some of the new techniques that I used to solve some interesting problems that I encountered….like using genetic algorithms to choose the best resource cards given some desire for certain types (souls for example) and an offering of cards with different types and amounts.

When The Tip Of The Spear Breaks

Sunday, May 10th, 2009

Sometimes success can be your undoing. Even when the thrust of the plan is carried out to perfection and the objective is accomplished, a single unattended detail can be ruinous. That’s the case here:

BrokenTipThumb

I have been testing out and refining the AI goals that deal with pursuing and defending against Vendettas. In the case above, I had gambled prestige that I could capture a single place of power from another player within a given set of turns. Since my AI opponent had been involved in some ugly disputes with his neighbor to his North , I decided to try out a blitzkrieg operation to send two legions deep into enemy territory to see how the AI would react. The AI was both unlucky and a little imprudent. He didn’t have a lot of tribute cards left so my demand of 4 tribute cards was the equivalent of “outrageous” to his silicon sensibilities. He was doing his best to maintain his holdings to the north and in close proximity to his stronghold. The AI’s appraise territory according to a value system that includes the range to their stronghold, the presence of a choke point, the connectivity it has with places of power it owns, etc.

I don’t want to discuss the particulars of how the AI’s decide some things as that can lead to a sense of having the curtain pulled away to reveal the unimpressive little guy pulling the levers feeling, but the Concede to Demand decision can really be a tough one. In this case the AI was presented with its own Kobayashi Maru scenario. Either choice was going to doom him to some very nasty consequences. This highlights one of the toughest programming problems I’ve had to approach during the development of SI…. namely getting the AI to “hope for the best.” In this case it chose to keep fighting the Devil it knew to the North and resigned itself to hoping the one to the east was just bluffing or not as dangerous.

In retrospect it was probably the best choice even if it was for the wrong reason. When the AI ran simulations to see how dangerous the opponent to the east was it didn’t quite get the consequences right because my legions were pulled away from the border a bit and they both had very unusual movement rates. One legion actually had a 4 movement point rate which is really almost unheard of in Hell. The unusual movement bonus came from the fact that my Avatar had an expensive perk “Fiendish Energy” that boosted all legions under my control by +1 movement points. Not taking this into account the AI came to the conclusion that there was a strong Bluff element going on and refused the demand. Although here is the rub. Even if it had thought that the enemy might be serious about grabbing some land, I’m not sure that the right decision would be to concede the 4 tribute cards. With an ongoing already “blooded” conflict with his neighbor to the North those 4 tribute cards might do a lot of good…like buying another legion in the bazaar. So ironically enough getting the AI to choose the lesser of two evils is really a challenge in this game. It’s an AI conundrum that I run into a lot. Adding a small stochastic element helps simulate a “human” approach to some extent but it’s not a complete solution. You have to have constructed the probability matrix correctly in the first place.

This all leads to the final little irony of the blitzkrieg gambit that I had unleashed. The AI refused my demand and I naturally made a bolt for the Place of Power which was fortuitously a lower level one that I could overwhelm with a little support. My two highly mobile and motivated legions crashed across the border and stormed the parapets (actually just one did the other was adjacent lending support) and promptly found themselves trapped in a pocket of their own making. You see the Vendetta was satisfied and the Infernal Conclave awarded me my prestige stake and a small bonus plus I got to keep the Place of Power but I had miscalculated a bit.

The Protocols about the transfer of land holdings in Hell are a little archaic and conservative. You have to occupy a Canton at the end of the turn and it must be adjacent to own of your own in order for the Infernal Conclave to award you possession. You can daisy chain them together with multiple legion placements. But I had overshot my own border by a Canton too far and despite the fact that the conquered Place of Power functioned as a new anchor for determining borders, I was trapped.

You can see that in the screen shot above. Neither legion could fly so they were both stuck there until I managed to enter a Vendetta with my beleaguered AI neighbor again…and my other neighbors would look with glee upon my borders the next turn. The hard part of course is getting the AI’s to recognize a broken tip….but that’s another story.

Goals – AI Wars part II

Sunday, December 23rd, 2007

It’s the end of the year and AiGameDev.com is having an open nomination session for best game AI’s of 2007. One of the categories is for Indie Games. What I really like about the competition is the following from the AiGameDev website:
___________________________________________________
Criteria
Remember, you’re giving an award for the best artificial intelligence in a game. This means it must be a balance of two things:

Entertainment — The AI in a game isn’t supposed to behave perfectly; in fact it’s often supposed to make mistakes in a convincing way. So, are the non-player characters (NPC) or non-character AIs fun to play with or against?

Intelligence & Believability — Do the in-game actors fit in with the design and story? It’s not purely about smarts — but it helps!

Of course, the two are not mutually exclusive, on the contrary! The best games each year successfully use intelligent behaviors to create a fun experience for the players.
_________________________________________________

I’d like to tell you that I intentionally programmed into the AI for Armageddon Empires all the boneheaded moves that you might occasionally witness. As I’ve explained before the role of hidden information plays a large part. And to be honest the limits of the AI play a large role as well. When it comes right down to it the AI is just a collection of competing goals. There are over a 180 goals covering everything from building resource collectors to evacuating heroes when somebody like Nod is on the loose. Which goals are selected and what priority they are given determines how the AI will play. Here is a screen shot from my development environment that shows some of them:

AI goals

So the big three elements to the AI are:

1. Which Goals are selected

2. What priorities they are given

3. What they actually do when they are “processed”

Goals can also contain subgoals which is an aspect where it gets really fun and interesting. I created goals of 3 different basic types: Top (the big idea goal), Atomic (no sub goals) and Composite (a goal that sits in the middle and holds sub goals).

I’m a workman type AI builder. I enjoy reading the theory but I am not its master. I have an electrical engineering degree from almost 2 decades ago that helps me get a foot in the door but what I built for Armageddon Empires was very single minded and goal oriented (pun intended). If I had to accomlish something I scoped out what I needed and then scowered the web and fell back on my programming books. Speaking of which here are some of the books that I found really useful:

Programming Game AI by Example by Mat Buckland

AI Game Development by Alex J. Champandard

AI for Game Developers by Bourg & Seemann

AI Game Programming Wisdom (All of them) edited by Steve Rabin

Goals For the Future:

Improve the AI’s evaluation of and response to the opponents’ grand strategies.

Improve and expand the use of influence maps to identify key geography, danger areas and force dispositions.

Improve the system used for ranking basic things: Right now it is a mix of fuzzy logic and weighted sums…I’d like to try and expand the use of memory with the ranking system for things beyond animosity….and keep track of how goals performed.

Animosity – How much do I really hate you?

Saturday, December 22nd, 2007

Armageddon Empires is a game about annihilating your enemies. There is no negotiation, no sweet words, and no co-existance. It’s a zero sum game. There can be only one. Even in such a savage environment there is an order of sorts. Some enemies are greater threats than others. Some need to be dealt with now while others just need a watchful eye until it’s their turn to feel the trod of your boots. Figuring out who poses the greatest threat is not always trivial.

The AI opponents in Armageddon Empires use an animosity system. There are two components to the system: a memory that stores a stack of animosity incidents and an animosity processor that calculates an animosity number at the beggining of each turn. The number varies between 0.0 and 1.0 and is assigned to each opponent the AI faces including human of course. The sum of all these animosity numbers across all opponents is 1.0. So if the animosity against opponent A goes up 0.05 then it must go down by 0.05 against opponent B in a 3 player game.

The memory gives the system some stability so that it isn’t flip flopping in its threat assessments. Things that generate animosity are your run of the mill aggressive actions like destroying collectors, capturing outposts, assassinating heroes, picking off recon armies and fighting full scale battles.

Critical Shift: Sometimes two opponents can be skirmishing on a border trading blows and building up animosity between each other. Suddenly from out of nowhere a killer stack from a different opponent shows up at the doorstep. Since animosity and threat are heavily correlated there has to be a system in place to account for sudden shifts in threat. This is accomplished by backloading a lot of animosity into memory if some specific threatening event occurs. Moving a large army two within a few hexes of an AI’s stronghold is going to generate a big spike in animosity and shift it considerably. This will affect the offensive goals that the AI generates.

Defensive goals will be effected as well. The AI’s have multiple tiers of defense goals. Two of the most important are Threat Readiness and Threat Response. Threat Readiness is keyed in to animosity. It determines things like patrol routes for recon armies, the types of attachments that should be created and…. “other good things too.” Threat Response is a set of goals that get created when any enemy threatens the AI. Animosity does play a part in assessing the threats but at this stage things like range, power, and assets at stake are going to weigh more in the fuzzy logic that generates a threat rating. Every threat gets a rating and resources are assigned accordingly.

I had a bit of fun with creating the threat response goals. Assessments are made on the threat and fitness numbers are generated to select the best goal objects to create. Some of my favorites are using an assassin to decapitate the army, finding a choke point to cut off supply, harrassment with air attacks and coordinating multiple armies to intercept.

Spaceballs, There goes the campaign!

AI Wars

Thursday, March 15th, 2007

The plumbing for Armageddon Empires is in fine shape and only occasionaly do I get an error or bug that I have to stamp out in the interface or basic game logic.  The last several months have been almost entirely focused on getting the AI to play a competitive game.  Along the way I have had my fair share of groans as the AI players did some boneheaded things.  I’ve also been pleasantly surprised at some solid execution and even I might dare say “emergent” type behavior.  Without going into too much technobable that might bore the non code junkies, I built the game from the ground up with the AI in mind.  Since the game was going to be a solitaire game, I new that a solid AI would be crucial to a “fun” or “challenging” experience.  My computer coding skills go back to the early eighties when I was an undergad studying electrical engineering.  I coded in Pascal on a VAX 11780.  The year before I arrived at the school, they had just gotten rid of punch cards and switched to terminals.  Wooden ships and iron men.  I’m not a particularly talented programmer but I have what you might call the Sharingan Eye if you are a Naruto fan.  I’m a copy ninja.  If I see some good examples I can nuke them out and elaborate a little.  The AI for Armageddon Empires is inspired from many books I read but “Programming Game AI by Example” was probably the biggest help.  http://www.amazon.com/Programming-Game-Example-Mat-Buckland/dp/1556220782

 Mat Buckland has a section on Goal-Driven Agent Behavior that helped me design a goal based architecture for my AI players.  Basically each AI player has a goal qeue that stores a goal object.  The qeue is sorted by priorities assigned to each goal and every turn the AI moves through the qeue processing the goals and spending Action Points and resources as best it can.  The generation of goals and the appropriate priorities is a tricky thing but I divided up the possibilities into several basic categories….Exploration, Resource Collection, Offense Ops, Defense Ops, and Support Ops.  If a threat is detected then the priority for Defense Ops is increased.  More defense type goals will be generated and they will have a greater urgency. 

 Time after time I ran across a problem where I needed to rate options and come up with some type of metric to compare them.  I implemented my own fuzzy logic system inspired by Mat’s examples as well as others.  Fuzzy logic is a great way to take a bunch of crisp parameters like Attack = 8 dice, Defense = 2 dice, and HP = 5 points fuzzy them up into Attack = “Above Avg”, Defense = “Below Average” and HP =  “Average” and then manipulate them with some logic rules.  For example, If Attack = “Above Avg” then “Target Desire” = “Strong”, If HP = “Above Avg” then “Target Desire” = “Below Avg.”  By using a thing called “The Combs Method” you can drastically reduce the number of rules like this.  The end result is a target rating that you can use to compare with others.  Once you have that you can pick the highest, lowest or use some other scheme to come up with the best choice.

So a goal based architecture and extensive use of fuzzy logic are the two big components.  Finite state machines are also a key component but they are tireless work horses that are so common they are almost taken for granted.  Each goal object is really just a finite state machine of a sort.  These programming techniques make up the Brains of the AI players but another important part is the actual architecture of the game itself.  I really wanted to make a game whose AI’s saw the same thing that the human player did.  So information storage and access was designed from the outset to facilitate this.  Each player and AI has an Intel Object that stores it’s own copy of what the player or AI knows about the game board.  Every turn or as a playing piece moves and observes more of the map that information is transfered from the main game map object to the players’ Intel Objects depending on what they can see (as determined by dice rolls that make observation checks)  The AI can only see what its armies deployed to the board can tell it.  Sounds great huh!  Well it opens up a whole new challenge for getting the AI to seek out the information it needs or even infer (gasp!) information from what it does not see.  Countless times I’ve had to dig into the reasons why an AI player passed up opportunity X.  Did the Intel Object not have the info and it simply did not see it?  Did it rate the chance of success too low? If so should the parameters be adjusted so such a no-brainer is recognized. 

Hidden information from the human can make the AI look stupid.  The game that I was playing last week as the Machines is a good case in point.  After my initial exploration and expansion, the Imperials kicked my butt pretty badly and forced me to pull back my supply lines to a more defensible perimeter.  I hunkered down and started rebuilding an army to go back out and kick some human butt.  6 or 7 turns clicked by and I was completely unmolested.  I thought, “damn!, something is broken.” The AI should have pressed forward by now and come after me.  He had harrassed me with some air attacks but nothing serious.   I dug back into the saved files for each turn and was surprised to discover that the Humans and Xenopods had made contact right above my little holdings and had been savaging each other a mere hex from my stronghold.  Both had been moving in for a kill and stumbled upon the other.  Soon their aggression rating with each other had built up enough that they were going at it full tilt and leaving puny me to be dealt with later. 

That’s a pretty basic description of the AI.  Here is a screenshot of a game that I am currently testing that has had a pretty epic sweep.  After getting some great resources and finding some excellent specials (the ones that provide a free outpost are real momentum accelerators) I pushed headlong into Xenopod territory.  Playing as the Imperials I found some key allies out in the wastelands as the humans are wont to do and I had a nice army built around some advanced combat mechs.  I got a little ahead of myself and left my supply anchor lightly defended.  A Xenopod army captured it and that left my mech army out of supply and crippled.  They fought a series of battles retreating back to a hex in supply.  The momentum has definately swung in the Xenopods favor.  I’ve got a huge stockpile of resources and good scientists so once I can get some tactic cards created to ensure success I’m going to build a city killer and see if I can even the odds. 

XenopodAdvanse