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:
Figure out where the enemy can attack.
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)
Decide which defenses are the most important.
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.
Once you run out of places you can successfully defend, retreat from all other places.
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.
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)
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!]
