Building an AI that plays Axis and Allies games, need help with strategy

[Veqryn]

Hey,
Wisconsin and a good number of other people are designing an AI that will play Axis and Allies (and similar games).  While the code will be in Java, we are first putting it in pseudo-code and English, that way everyone can read it, understand it, and critique it; hopefully offering up better methods and strategies for the AI.

Please come read what we have so far, and help us to make a simple but good AI.

http://tripleadev.1671093.n2.nabble.com/Brand-New-AI-Development-Thread-tp5780797p5780797.html

Some notes:
We have already decided it will mostly be a heuristic ai, and not an AI that considers all possible moves or does an Alpha-Beta search with branch pruning.  So in english, this is not a deep-blue type of Chess AI that will think about things many moves ahead.
Also, because this is for the TripleA game engine, it has to work with more maps than just Axis and Allies maps, so nothing will be hardcoded to any specific units or nations, etc.

Please come have a look, help us out,
thx,
veqryn

[Veqryn]

Here is a preview of some of the stuff in that thread I linked to earlier…

Currently, this is the best AI algorithm we have…
I came up with it in about 2 hours, so I really would like some people to comment on it and improve it:

Post1:
I wish to expand on what i wrote before:

1. The AI should first figure out what battles it can possibly win. 
1.1 First the AI should figure out “what enemy territories can my land units reach” and “what sea zones can my sea units and/or air reach”. 
1.2 Simple evaluation heuristic of the enemy zones found in 1.1: Hitpoints and Defense strength of enemy territories (simply add up the number of units [counting 2 hit units as 2 units] and call that hitpoints, then add up the total defense strength of those units).  So for example, a territory with 1 BB, 1 CV, 1 DD, and a Fighter would have 5 hp and 12 defense. 
1.3 Now we can use a heuristic to reduce the number of territories we must look at.
1.3.1 Is there any land units that can hit our capital (including by sea)?  If so, decide how much is needed to attack it and win with 99.5%, then remove this territory or territories from the list we made in 1.2.  If we can not attack it and win (like if for example it is an amphibious attack), see how many units would be needed to defend successfully against it, subtract the number of units we will be building in the capital, then move the required number of units to the capital, prioritizing movement coming from interior territories first.
1.3.2 Are there any multi-move & blitzable units that can reach into our interior money territories?  If so, decide how much is needed to attack them and win with 95%, then remove that territory from the list.  If we can not win against it, move a cheap unit to block the blitzing path and make sure to not include that unit in our further calculations.
1.3.3 Can we move to an enemy capital?  If so, can we win (with at least 1 land unit left over)?  Is the TUV swing not too horrible?  If we can, do it, then remove that territory and the used units from out lists.
1.3.4 Do we have any multi-turn-amphibious-transporting-moves pending?  If so, complete the transport chain movements, then remove any affected units and territories from the list.
1.4 Now we must make a full inventory of what forces WE have at our disposal that can reach each territory on the enemy-territory-list. 
1.4.1 For each territory on that list, analyze all our territories within max_map_land_movement spaces for land units, max_map_air_movement spaces for air, and max_map_transport_movement spaces for amphibious troops.  Like before, simply add up hitpoints and attack power, storing them for each territory on the list.  Make sure not to include any units used in parts 1.3.1-1.3.4. 
1.4.2 Now do a simple evaluation to remove territories where we would not win from the list.  This could be something like: if ((our attack power + (hitpoints * 2)) < (enemy defense power + (hitpoints * 2))) then remove territory from list.
1.4.3 Now we have a much much smaller list of territories.  We can run a battle calc simulation on each territory to see if we truly would win or not.  This does not need to be to 5000 calcs, this can be something like 100 for low luck and 500 for dice.  I dunno, this can be tweaked in the future.  Record the results for each territory.  Remove the territory from the list IF (we have less than 75% chance of winning with a large TUV swing, or less than 95% chance of winning with a moderate or small TUV swing) [TUV should be considered as a percentage of total TUV on the map or a multiple of the average unit price, that way this function will scale up with big maps or expensive unit maps]. 
DONE PART 1, we now have a list of places we can win.  The list only includes places that we can win with 95% certainty, or 75% certainty with a big TUV swing.

2. The AI should then decide which of those battles are the most important in forwarding its objectives. 
2.1 Before we can remove the little battles from the list, we need to find out if we need those units to be committed to a more important bigger battle.
2.1.1 Analyze each territory to come up with a value of each territory based on: is it in the direction of an enemy capital, can the enemy retake the territory next turn, how big is the TUV swing if i attack, and territory PUs (multiply territory PUs by 3 if there is a factory present).  For example, if the AI is germany, it might look at belorussia and add up the following: +6 points because it is in the direction of the enemy capital, -11 because it can be retaken by russia the next turn with only -11 TUV swing, +6 because the TUV swing is 6 in its favor for the attack this turn, and +2 because the territory is worth 2 PUs.  This gives belorussia a score of 3 in the AI’s mind.  (the only subjective thing here is how many points to give a territory because it is on the way to a capital, and perhaps also how we wish to calc the counter-attack-possibility part [we may have to add something here to give the destruction of land units a bonus over the destruction of air and sea units, because air and sea units cost a lot more but are usually less important, but this can wait][the value we give territories on the path to a capital will also have to scale up to maps with expensive units]).  Resolving ties could be done randomly or a new function could be applied.  If there are no moves that have a positive value, then exit loop (this would mean everywhere has a big big counter attack potential, so we should hold off attacking and build up forces). 
2.1.1.1 How we could analyze the position of a territory is this: 1) Is the closest enemy capital to the territory-we-would-move-to, also closer to our capital Than any other enemy capitals? (ie: is this the closest enemy capital we are moving towards)  If so, give 3 points.  2) Is the territory-we-would-move-to closer to the closest enemy capital than the territory-we-are-currently-in?  (ie: are we moving towards any enemy capital at all)  If so, give 3 points.  [We could also add in: Are we moving towards the closest enemy factory?  If so, add 1 or 2 points, depending on value of factory and territory.]

3. After analyzing all attacks, pick the one with the highest score.  Perform that attack with as many units as can reach it to achieve 97% win chance, choosing first units that can only reach that territory (stopping when we reach 97% or when we run out of units to move).  [debug may wish to recalc the battle, to make sure everything is going according to plan].  Commit those forces, removing both those forces and the territory from the list.

4. Now loop back to 2.1. 
4.1 We may wish to include a special function for little attacks & land grabs that runs once after 2-3 loops.
4.2 Loop back to 2.1 again.

5. Continue looping until we have either run out of units to attack with, or run out of time.  We should perform at least 4 loops minimum before we check for running out of time.

DONE PARTS 2,3,4,5, the AI has now attacked a variety of places. 
Now the AI starts rolling battles, starting with the biggest battles first.

I hope this makes more sense,
perhaps I can put it into pseudocode later
thx,
veqryn

ps:
Most of the moving towards enemy capitals will actually occur during non-combat, when the AI should be reinforcing towards the closest enemy capital that it can reach, while making sure to send enough to defend against other nearby enemy capitals.

The only multi-turn considerations in my stuff above are, 1) calcing counter attacks during part 2.1.1, and 2) Processing any multi-turn-objectives.

The only multi-turn-objectives we should create for now are sea transports + amphibious landing/reinforcing objectives.  Anything else would be too complex.  These sorts of objectives should be created during the purchase unit phase, then handed over to combat and noncombat moves, as well as deployment.  I believe that all movement that would involve a sea transport should be handled under multi-turn-objective handlers.  This would prevent things like moore-ai’s short attention span where it loads a unit onto a transport and then offloads him to the same spot he loaded him from.

Nations who do not have a direct land path from their capital to an enemy capital should have special purchasing functions that create many multi-turn objectives to build land units and sea transports and then load and drop off those land units in a staging area.  After the drop off, the multi-turn objective for those land units ends, and the normal considerations above take effect (ie: move towards the enemy, etc.).  The transports that just dropped off guys will create new objectives to return to the capital or other island factories to pick up more guys.  After they pick up, that objective ends and they get a new one to drop those units off in some staging area.  Etc.  As you can see, these objectives are linked to individual transport units and the land units that are created on islands with no land link to enemy capitals (assuming they have already cleared the island/continent of other enemy territories, which should be checked for).  The objectives should be simple, and try to drop off units at the closest valuable land point, but they must also allow for situations where a map might have a lot of water and it could take many turns to reach that territory (think of america in the Great War map).

Post2:
1. How do I figure out how much is needed to defend against an enemy capital?
How I imagine it:
First, figure out what nations are your enemy.  This could be done at the beginning of each turn, in order to spread the work load.  Basically, compare their distance from you on land, their distance from you on water, their TUV, and your TUV, and Check to see if you have allies that are closer to them than you are.  Based on that info, come up with a list that includes 1 primary enemy, X secondary enemies, and Y enemies that will not be considered for now. 
Second, use some route-finding info to figure out the quickest couple paths from their capital to yours, then include any paths that are within x of that (lets say x=1, and the quickest path from russia_cap to germany_cap is 4, then you will include any routes that are 4 or 5 territories long [to allow bigger maps, x could by dynamically set as a percentage of the quickest route but at least equal to 1]).  Get a list of all territories that are in those routes, discarding duplicates. 
Third, analyze those territories to figure out current balance of power.  IF (((Enemy #ofHitPoints4 + total_attack_power + total_defense_power) - (Allied #ofHitPoints4 + total_attack_power + total_defense_power)) > X) {send more units in that direction}

2. What is the general purchase algorithm for the AI?
I don’t think moore ai’s purchase algorithm is that bad actually.  Basically,
first you need to figure out, are we an island nation, or a land nation?
If we are a land nation, should we buy any sea units defensively?  If not, buy a good mix of land and air units.  If we have very little money, focus only on cheap land (compare the average price of land units to our total money, AND/OR compare the number of open production slots we have to our money).  If we have a decent amount of money, still buy at least 50% cheap land units, but use the other 50% for expensive things like tanks and fighters.  AI should try to maximize hit points before anything else.  Hit points are worth at least 2 or 3 times more than attack/defense values. 
(Some maps have specialty units with high attack and low defense, like bombers [4/1] or mortars [5/0], or high defense, low attack, like bunkers [0/3] or fortresses [0/4], etc.  The AI should give things that are not balanced a small disadvantage, so for example if something has an attack or defense value of zero, or has no movement, or has an attack or defense that is >= triple the other value, then it gets a small disadvantage in the purchasing algorithms.)
If we are an island nation or there are no more enemy territories connected by land to us, we should figure out first if we should buy defensively or offensively.  Evaluate the navies and airforces of our primary and maybe secondary enemy, then try to keep at least equal.  Assume v3 transport rules, that transports are not used in combat.  Purchase enough fighting navy + airforce to keep ahead of rival nation(s).  Any money left over should then go to transports and amphibious land.  Figure out how many transports will be arriving next turn to be filled up (based on multi-turn-objectives attached to each transport), and buy enough land units to fill them.  Extra money should be spent first on 1 transport, then on land to fill it, then on another transport, then on land to fill that one, etc, (or the other way around).

3. What is the general placement algorithm for the AI?
Place land stuff as close to the enemy as we can.  Cheap & slow stuff goes closer, expensive and fast stuff goes further away because it can catch up.  Make sure capital will have enough in it to be defended successfully.  Make sure we are placing our ships together and on the correct side, especially placing them with other combat ships or further away from enemy.  Make sure if placing transports, that you also place land to be transported there too.

Post 3:
A quick run down of Non-Combat turn:

1. Figure out where the enemy can attack.
2. Figure out which of those areas we can defend successfully.  (first try to defend capital)(make sure to include place/deploying units in these calcs)
3. Decide which defenses are the most important.
4. Commit those defenses, looping back to choose other places to defend, that way the most important place gets defended first, etc, down the line.  You need to loop in order to remove units from consideration once you have decided to move them.
5. Once you run out of places you can successfully defend, retreat from all other places.
6. Make sure to leave single blockers in places that could be blitzed, when either the blitzing force is huge or the territories are worth a lot of money.
7. Make sure to move air units to places that will be defended successfully.  (occasionally the ai will f-up and have air that can’t be defended. make sure to still move it, even if you will lose it)
8. Now look at units that have not yet moved.  Begin moving them towards the primary enemy, and a little towards any secondary enemies if applicable (except do not move them to places you can not defend, found in #5).  Try to clump them together, not spread them out (a simple bonus to moves that end in larger stacks, over moves that end in smaller stacks, or something like that).

(we need a way to keep track of units that have not yet moved, units that have moved, and units that should not move at all because they are staying put)
(if you want this could all be done during combat move, … with the exception of landing planes)

As you can see, this bears a lot of resemblance to my combat move algorithm. 
Hope you like it,
thx,
veqryn

[please go check out the whole thread for more details!]

[Gargantua]

Put in a function that checks unit actions. Defence aside, this prevents the AI from doing things like putting subs on the board and leaving them there.
forever.  Make sure the AI chooses to move every piece on the board, even if the move is “NO MOVE - DEFENCE”

Also make sure that when you are calculating battles, that the AI calculates battles it knows are worth winning.  And bases it’s attacks on that.  Making it mathematical.  Not only gaining territories, but doing things like sinking transports for free.

Also consider making a map up, and assigning a value of how important territories are.  IPC’s aside.  This really can help for aircraft and naval placement.  For example, no one ever goes off the coast of canada, or greenland.  or south america.  so those territories are worth 1.  but western europe,  the english channel, etc, are going to see alot of action, make them worth 1, 2, 3, etc.  What this kind of thing can do, is allow the A.I. to know where the BEST place to place it’s aircraft are, so it has the MOST available options the following turn.  Russian bombers in Siberia, don’t do much good.

The only other suggesstion I have, is to play a round of axis and allies, are mark out every single thought processes, Kind of like what you’ve got for the capital protection clause.  You know, like - what do I need to buy? what did my opponent buy? where can I make gain value attacks? what territories should I take? etc etc.  Then make your A.I. go through the process.  You sort of have something like that already, just make sure it’s as good as you would play mentally.

Also, Multinational can-openers are going to own your AI, unless you can figure away around it.

[calvinhobbesliker]

Any AI is going to suck against a decent AA player.

[Veqryn]

yes, probably true and we accept that it will not be competitive out of the box.  but we hope that with a small bid and perhaps a small bonus income each round, our ai can be pretty darn competitive.

garg, thx for the info, i really like the idea of making sure each unit gets moved or at least looked at.

[Gargantua]

Honestly Veqryn, you should consider a series of independant AI’s. Modelled after each other of course but, independant none the less.

What I mean is, each country, really has it’s own needs, and it’s own goals,  thus it needs to have it’s own strategies.  You can script some of these to a point, and I think you’ll have to.  For example, the carolines is crucial for japan, but technically worth nothing,  an AI might abandon it.  You need to assume some of these moves,  and help the AI with some of it’s buys and strategies. I would plan a game with a relative script 8 or 9 turns deep,  most games don’t go that long.  This will give your AI, a players head-start.

I would look at the three best, and most common opening strategies for each power, A B C, and then tell the computer to randomnly select a script, or select a script depending on opposing moves and buys.

Things like buying a naval base in Hainan, won’t happen, unless the AI scripts it.  Same with multinational moves, like a NB in Soviet Far East, so American units can shuck back and forth.  It has to be scripted, or it wont happen.

make sure to have a clause for balls out battles, those tend to pay off often enough, you know, 1 inf on 1 inf, or sometimes sending a sub against a cruiser and an aircraft carrier.  These kinds of moves can really make or break the game, even if they “seem” crazy statistically.  Nothing like taking a territory with a new factory on it, because you sent your 1 inf against a fighter and won.

Make your AI a little bit nuts, should make for fun games, and unexpected results.

Also, if you really want,  as a general strategy, if making a play for capitals is too complex,  just have the AI focus on economic game control.  He who has the most money, usually wins.  If that is the focus of the AI, it should make less mistakes, and be a force to be reckoned with.

[Veqryn]

considered to some degree, but we need to have our AI be able to play not just global 1940, but also AA50, 1942, revised, classic, and non-A&A games like New World Order, 270BC, pact of steel, and Napoleonic Empires just to name a few.

Right now, we want to have the AI read a special new properties file in the maps folder that will provide the AI with some <optional>hints.  Things like what territories are important, etc.</optional>

[Gargantua]

The best way then is going to be to start with the simplest of AI’s.  That’s going to be Russia.

Once you get that one down, you can build on it to form the rest, with each game in mind.

Have fun Veqryn!

[captainjack]

1.2 Simple evaluation heuristic of the enemy zones found in 1.1: Hitpoints and Defense strength of enemy territories (simply add up the number of units [counting 2 hit units as 2 units] and call that hitpoints, then add up the total defense strength of those units).  So for example, a territory with 1 BB, 1 CV, 1 DD, and a Fighter would have 5 hp and 12 defense.

I’m no expert, but I wanted to mention to you how my playgroup adds up hitpoints….
We add up the attack or defense value like you, but what we do different is we add to that number to total number of hits it takes to win the battle.  For example, using your 1BB, 1CV, 1DD, 1FIG with a defense of 12, our defense number would be 17 (12 + 5 hits required to destroy the group).  Another example:  3 inf, 2 arm, 2 figs attacking would be a total attack value of 22.
Like I said, I’m no expert, this is just what my group does and it seems to be more accurate…
Thanks.

[newpaintbrush]

This thread shouldn’t just be in A&A Global 1940.  I suggest creating a main thread, and stickying a sub-thread in each forum that refers to the main thread.