Back in July, while testing functionality for Random Earth Map (REM), I noticed some peculiar behavior with the AI and decided to take some notes for a future fix.  Shortly thereafter, I got bogged down in personal stuff and never picked it back up.  With the upcoming patch making some tweaks to the AI, I opened my July analysis and decided it might be worthwhile sharing in case it results in improvements to the AI.

TL;DR: For those who don’t want to read the whole thing, I’ll start with the recommendations.

StandardAI would perform better with the following changes:

• Ground units from the “CQ” list shouldn’t get a “Go Home” order when another unit uncovers their hidden tile and it’s not a city.  This causes them to get stuck.
• Debug why <Hm> order is given before units reach their destinations, seems like an over-reactive fail safe that also seems to stop the other fail safes from working.
• SAIEarlyExplore exploration needs logic to verify if the unit is an Air unit.  It should only use the SAIEarlyExplore exploration pathing for non-air units.
• SAIEarlyExplore needs to use SAIExplore exploration pathing for aircraft (related to second point above)
• Add a check in SAIEarlyExploreCheck to ensure your production queue isn’t stuck in a build/fly/crash loop.  This loop is explained in detail below.
• Check SAIExplore, SAIEarlyExplore for any potential hard coded range/move values.  Verify these are checking [Range/2] and, more importantly, not skipping the low fuel notification.
• Units exploring should “Move To” a revealed tile where the path is confirmed. Right now, it appears to be targeting an unrevealed tile instead of a revealed adjacent tile.
• Consider flagging some unrevealed tiles as “explored” when a unit is already en-route to that location, or if it is “impassible” to that unit type.  This will help avoid AI tunnel vision.
• Change code for the SAI_UT_EARLY arrays to cycle through options instead of always [0]. This allows AI modders to assist the AI in overcoming situational exploration issues.
• Replace the if(ex_type.Count > 0) with a [EX_RATIO] array that is configurable in the AI file, allowing modders to fix it when needed.

There you have it!  However, if you are a glutton for punishment, then read on.  What follows is my full assessment of the AI testing I conducted as part of the REM release back in July.

The Test Parameters

Three of the most common complaints about the AI in EDCE are:

1. The AI struggles when it is on an island.
2. The AI struggles when it is on a landmass and has only landlocked cities.
3. The AI never leaves a landmass with only one city.

I set up three AI players using REM in a head to head match.  Their locations are as follows:

• AI1: Cape Verde, representing island start with no nearby landmass
• AI2: Madagascar, representing the landlocked city start
• AI3: Papua New Guinea, representing large landmass with one city

I opted to use MUD as I am more familiar with debugging this set than the Enhanced set.  I then ran this simulation to turn 1,000 a hundred times and noted the results.  What I found surprised me.

• AI1: Successfully located and explored West Africa. Total cities varied between 4 and 12 per run. Verdict: Marginal Success
• AI2: Successfully captured all of Southern Africa and sometimes conquered the Indian subcontinent. Performed far above expectations. Verdict: Complete Success
• AI3: Always had just one city. Except for one case, it did not explore outside its starting landmass. Verdict: Complete Failure

From this I concluded the following:

1. The problem with landlocked AI’s (i.e. AI2) is not with the AI code, it’s with the unit sets. Increasing the range or speed of air transports will greatly improve AI performance.  Based on these results, I recommend changing the speed setting to 4 for all air transports and leaving range as-is.
2. Random chance is the main issue with island starts. The AI needs some help identifying nearby opportunities in the way a human would.  Some improvements can be made here.  I also noticed some strange exploration pathing, so I took a note of it for later if I have time.
3. The complete failure of AI3 was baffling. It’s location near Australia should have made it the top performer.  Something is definitely wrong here.  My initial reaction is that there is some logic in the code preventing it from performing the same actions as AI2.

With that said, my next step is clear.  I need to focus on making AI3 an actual opponent and not just a colorful neutral player.

Root Cause Analysis

For the rest of this writeup, I will use StandardAI to refer to the current un-modded AI.  ModAI will refer to a test AI I am running and making changes to in parallel.  If ModAI performs better than Standard AI, I will note the impact to performance and will make recommendations based on those results.

With that in mind, I re-ran the same test as earlier but this time I watched, turn by turn, how StandardAI played.  For this analysis, I will complete 50 runs and record all anomalies found.

By the fifth run, I am already seeing the problems.  After 50 runs, I concluded several repeat issues occurred every time.  Here is a list of the behavioral issues I saw that occurred with regular frequency:

• Every time the AI built a new airplane for exploration, all of its land explorers return to the city.
• No matter what, the AI never explored a sea tile with an aircraft unit until every last tile of its starting island was explored.
• StandardAI tended to crash it’s planes with alarming frequency and then rebuild them. The AI crashed no less than three planes or helicopters in every run I performed.  Usually, it crashed all of them.
• StandardAI almost never finished exploring it’s starting island because the last tile was both impassible to land explorers and out of range of airplanes.
• Whenever an airplane would crash, StandardAI would stop all production and build another one. This put it in a loop that started around turn 200 and the StandardAI would not make any significant progress thereafter.

By the end of my test, it was clear these were the main issues preventing it from succeeding.  I even checked its performance against the other two AI starts and noticed the same behavior was occurring there, but less noticeable for some reason.

With that, let’s dig into some code and try to fix it.

Debugging

I booted up Visual Studio and Memory Explorer and got to work.  I should note that I do not have experience coding this AI and am relying heavily on trial and error and best judgement.  Moreover, I never got a script working with all of my recommendations in one file, only for individual recommendations. As such, some of my references below may be incorrect.  An expert on this AI will to validate my statements.

I’m going to take each of the problems I outlined above separately and see what I can find.

Infantry “Go Home” When Airplane Takes Off

Every time the StandardAI build an airplane from the SAI_UT_EARLY_EX list, I noticed a momentary blip where all ground forces would head home (<Hm>).  The infantry would start back out again once the airplane also went home.  As they traversed further away from their home city, the <Hm> order caused serious issues. They would get stuck going back and forth on the same tiles somewhere in the middle of the airplane’s maximum range.  I called this behavior “blobbing up.”  The more I thought about it, this explains why the AI has trouble traversing large maps without lots of cities to capture, and is the main problem I am seeing with REM right now.

At first, I thought this had to be something with range settings being applied to the ground units.  However, it turned out to be related to how the AI is picking tiles for exploration.  I tracked it to SAIOrders.cs before I lost track of the process.  It’s possible that this method for picking what tiles are selected for exploration is relying on some code outside of what I had available for ModAI.

My theory is that SAIEarlyExplore and SAIExplore are giving instructions to “Move To” a tile outside of its movement range. It’s probably in GetClosestUnexploredLoc somewhere.  I verified this happens to both types of exploration.  When I removed all SAI_UT_EARLY_EX unit types and noticed that SAI_UT_AIR_EXPLORE will send the unit to uncover one specific tile before sending the “Go Home” order if the tile distance was greater than speed value.

To fix this, I removed air units from SAI_UT_EARLY_EX and SAI_UT_AIR_EXPLORE.  I also had to comment out any uses of SAI_UT_EARLY_CQ as the code will produce non-explorer units in early game.  When I did this, ModAI properly explored the entire continent but stopped completely after it was finished (presumably because no unit is identified for next step).  Thus, this change outperformed StandardAI by exploring two tiles more than StandardAI, but was completely useless as a hotfix since the AI still stops working after this happens.

The main difference was the speed at which exploration happened, and the fact that the exploration algorithm actually completed.  If that can be built into the StandardAI, it should fix the performance considerably.

EDIT: After running some additional tests, I’ve determined that Ord <Hm> seems to be issued to AI units with high frequency whenever it is in Early game mode.  This makes me think the code is re-writing the unit’s mission after each turn, which could explain the odd jittery movement I see sometimes.  It might be a good idea to add some simple if(logic) to make sure the AI isn’t on a mission (or at least attempt the mission for x turns) before changing it.

Conclusion:  Infantry units on explore should not alter to a “Go Home” order when the “Move To” tile is revealed by another unit.  The correct move would be to to complete the “Move To” action and then issue new orders after it gets there.  As a human player, this would seem counter intuitive, but this flaw is the reason that the issues I’m about cover can occur in the first place.

Aircraft Only Explore Landmass

Every playthrough produced the same peculiar result.  The AI would attempt to use its aircraft to explore the landmass, despite ample sea tiles (and lucrative cities just beyond).  When the distance to the furthest landmass tile exceeded the max range of the plane, instead of going for the sea tiles it would constantly send its plane towards this far away tile, thus crashing the plane short of the target.  Then it would build another plane and do the same action again.  Thus, the AI falls into a build/fly/crash cycle that goes on indefinitely.

As a side note, while debugging this I noticed that SAI_UT_AIR_EXPLORE correctly cycles through the units in this list when creating a build queue.  I had inadvertently made this list increment to more expensive units with longer range, which had the effect of improving the overall exploration capabilities of the AI and thus made the AI more effective the longer it played.  This method would be a great way for a human player to make performance improvements without modifying the DLL’s if we could use it for early exploration units as well.  I noted this down for future investigation.

Back to the issue at hand.  SAIEarlyExplorCheck uses GetLandMass which is the issue here.  In ModAI, I changed IsExplored() to always return true and the impact was immediate and definitive.

This fixed the issue with aircraft exploration!  The downside to this is that all land units effectively stopped exploring.  I set the other two AI players to use ModAI and saw changes in their performance.  I concluded that setting it like this was sending the explore command to SAIExplore instead of SAIEarlyExplore, but since the SAI_PRI_EXP_CITY_CRITERIA and SAI_PRI_EXP_LAND_CRITERIA weren’t met, it was still building units in the SAI_UT_EARLY_EX queue.  Moreover, SAIExplore uses GetLandMass as well, so it was impacting all units, when in reality this change was best suited for Air only.

This uncovered two problems, and highlighted the dangers of the earlier issue.

1. The code handling SAI_UT_EARLY_EX units should use the SAIExplore pathing algorithm (i.e. ignore landmass) for airplanes and continue using SAIEarlyExplore for everything else.
2. SAI_UT_EARLY_EX only builds one unit type (ex_type[0]) instead of cycling like SAI_UT_AIR_EXPLORE.

And now the alarming truth this all revealed.  Remember that “Go Home” issue I talked about earlier? Well…

I found that if the flight range (usually [range / 2] unless it is sacrificing itself) of an exploration plane is ever greater than its build time, infantry on exploration will receive a “Go Home” order half way through its attempt to reach the unexplored tile.  Thus, it creates a never-ending build/fly/crash loop for the plane.  On top of it, the loop also traps infantry/armor in this loop as well because the land exploration units receive a “Move to” explore command and then a “Go Home” order right after, and indefinitely.  This problem compounds itself because drain further erodes the build times for your planes, and every time an explorer is created, the build queue switches to SAI_UT_EARLY_CQ, which is usually cheap infantry units, thus increasing drain and the construction time of new planes.

In effect, if the AI cannot get off its starting island before this cycle starts, it’s game over for this player.  There needs to be some kind of check that prevents this, or drain needs to be temporarily removed until the AI can figure things out.

EDIT: Based on how land units explored with the StandardAI in a follow up test, I think the SAIEarlyExplore logic was originally built for [SAI_UT_EARLY_CQ] and was later changed to SAI_UT_AIR_EXPLORE.  I think the logic from the original AI creator was that a player would reveal his own island before exploring elsewhere.  But the ASL approach is more effective, even for human players, when airplanes use the DFS pattern instead of this method.

Conclusion: There are three issues here.

1. The SAIEarlyExplore needs to check if it is an Air unit type and NOT apply the landmass restriction if it is.
2. The SAI_UT_EARLY_** should cycle the build order and not take only the first option.
3. There needs to be a check in place to make sure the AI is avoiding the build/fly/crash loop.

High Rate of Airplane Crashes

When the SAI_UT_EARLY_EX unit is an airplane, it tends to crash that airplane during it’s exploration mission.  I couldn’t figure out any reason for this at first, but ultimately, I concluded that range was not being factored in the SAIEarlyExplore algorithm.  I checked all the range types I could think of, the best I found was MV_MOVING_OUT_OF_RANGE and range checks in Landmass.  They aren’t triggering properly for some reason.  I would need someone to help me understand this one.

For kicks, I loaded up the default unit set to see if this problem was related to my MUD set and not the AI.  What I found is the problem occurs with less frequency, but it does exist.  The reason for the lower frequency is because it relies on that clever trick we saw with infantry earlier.  After it finds it’s target tile, it gets a “Go Home” order.  Because the range is less (18 range in Standard vs 60 or more in MUD) the issue is less pronounced and thus harder to notice since most explorers stay close to the city.  Maybe there is an issue with pathfinding after a certain distance, I don’t know.

However, this problem becomes noticeable when the planes take more than two turns to reach their exploration “Move To” tile.  I noticed bombers taking strange snakelike paths to eventually crash once they hit a certain distance from their city.  This meant the issue was occurring in the default unit set as well.  Moreover, I had the airplanes use SAIExplore instead of SAIEarlyExplore and the problem exists in both methods.  That leads me to believe there is no easy code fix for it.

Alas, I have no fix for this one.  I believe the original creator of this script intended for the AI to uncover another city or for the landmasses to be small enough to be revealed before the airplane ran out of fuel.  However, the script never recognizes its failure and thus doesn’t switch to boats or build an airbase as it should.

The reason this problem showed up on my original July test is because MUD set airplanes to have ranges of 60 or higher.  This meant the issue was easier to spot.  The fix for this is to add or verify the range checks to all move orders (including those originating from an Explore command) and not allow units to exceed it.  That or figure out why the MV_MOVING_OUT_OF_RANGE “Go Home” command on SAIEarlyGame isn’t triggering properly.

In fact, the behavior Airplanes display in the SAIExplore algorithm seems to indicate the range values are hard coded somewhere.  I couldn’t figure out where, but the giveaway is that it will carefully reveal one tile at a time before going on an all-out suicide run after it gets to about 325 tiles uncovered.  This is when the range was set to 60 and it should have been able to reveal 3,000 tiles before needing a suicide run.

Conclusion: Check the code for any hard-coded ranges in SAIExplore, SAIEarlyExplore, and anything else being used to determine exploration range.  Check the SAIEarlyGame code for bugs, specifically that MV_MOVING_OUT_OF_RANGE is triggering when it is supposed to.  Other than that, better range checking would be advised.

EDIT: One additional update from after I posted this.  The screenshots used in this section were taken using ModAI.  This is because when I tested the AI1 start (and AI2 with similar results) I had a hard time getting airplanes to fly once the landmass trigger was true.  I noticed the StandardAI tends to build the air SAI_UT_EARLY_EX unit then have it sit idle until a destroyer is available.  The AI should be coded to avoid having Air exploration units ever sit idle in cities.  Even if it doesn’t have an exploration target, it should be checking for enemies and patrolling randomly if there are none.  That said, ModAI was able to perform the screenshots with only the modifications shown in this post, and improved its ability to get off the AI1 and AI2 starts once the changes were applied.

Impassable Tiles Cause Looping

One thing you may have noticed in my earlier screenshot is the blobbing of infantry units in the middle of the island.  After carefully reviewing how units were moving on the map, I concluded this was because of two issues.

• Half of the units had a “Go Home” order and half had a “Move To” order creating a traffic jam. See the issue above for details behind this.
• The “Move To” tile was the last unexplored tile on the continent, and it was impassible to Infantry.  Thus, they had no where to go but they would keep trying.

I covered the first bullet already. To summarize, the way that tiles are selected for exploration causes units to get stuck in a loop, usually in the middle of a continent.  It gets worse as the game goes on.  Watch Britain on the Falklands map, it happens every time without fail.

The second bullet you can say was very circumstantial.  In fact, once I figured out how move orders were being implemented, I definitively concluded that it was this exact issue that was making all the other AI issues obvious and caused me to look into it in the first place.  You see, as it turns out on this specific map, a very specific impassible tile farthest on the left was always the last tile the exploration algorithm asked the units to uncover. Thus the algorithm had no way to reveal this tile as it is impossible for an airplane to get there and impassible to ground units.  Go figure.

It was the perfect storm.  The infantry would continue to try because the unrevealed tiles (giving a possible path in theory) were adjacent.  Unfortunately, I as a human knew they are “coast” tiles which it cannot traverse.  Also, the tile is exactly one range too far for the exploration aircraft.  To compound the whole thing was the infantry who would get their “Go Home” order every time the plane was built, only to be sent to reveal that one tile again once the plan crashed a few turns later.  Thus, as long as the AI stayed laser focused on revealing that one useless tile, it was game over.

Anyway, I fixed it by replacing my SAI_UT_EARLY_EX unit with an air unit with higher range.  Sure this issue was circumstantial, but it’s indicative of an underlying problem with how the code selects tiles for exploration.  If I wanted to fix it the right way so it didn’t happen elsewhere, what I really need to do is change the way exploration is assigning tiles.

I would recommend “cheating” the algorithm a bit by adding a step.  There are two ways to do this:

• Have units “Move To” a tile ADJACENT to its target that is already explored. Verify this is a valid “Move To” location and that the unit has a path to get there. This is what a human player would do, by the way.
• Or, if you still “Move To” an unrevealed tile, the “Move to” should still verify if this a valid location and the unit has a path to it. Then, make sure this only applies to AI players.

In my case, I prefer the first option.  It’s easier to debug if there are issues with pathing.  Not only that, it doesn’t cause issues if the target tile gets revealed or something and thus cause the unit to change course.  This should help the AI keep momentum going.

One quality of life improvement would be to allow AI modders to specify the max number of units the AI will send to explore a single tile.  A setting like this would help us diversify the pathing used by the AI. A possible example would be to add [EX_PER_TILE_MAX][1] to the AI file, meaning the AI will only send one unit to explore a tile, and can be changed if a player desires.  This can end the tunnel vision.

Finally, another Quality of Life improvement is to allow players to specify build ratios instead of just verifying if one was built.  An example of implementing this would be to place [EX_RATIO] in the AI file in place of the if(ex_type.Count > 0) where the ratio can be 3:1 (three EX units for every one CQ unit) instead of just “> zero.”  I would also verify if there are other similar checks like this (there are I’m sure, just outside the scope of what I’m reviewing here) and apply a similar strategy.

EDIT: One additional point after re-testing this.  Regardless of the option you take with your AI, make sure the unit actually gets to its destination or finds something else to do if it is stuck. If you continue to issue <Hm> orders at the end of each turn, it won’t matter what you do since the AI can’t remember what it was doing and will fail anyway.  Also, the AI should never have this level of tunnel vision, and there needs to be a check in place to ensure it diversifies it’s targets.

Conclusion: When exploring, units shouldn’t path to an unrevealed tile.  They should instead go to an adjacent revealed tile that has a valid move path.  If it can’t get there, then it should consider this explored/invalid and stop sending other units there.  I also recommend placing a limit on how many AI units can “Move To” the same non-city tile.

Updated Production for Exploration

While debugging the issues above, I kept kept coming across another peculiarity. The code for SAIEarlyExploreCheck checks an array called have_ex (if you have an early explore unit) then changes production to your first SAI_UT_EARLY_EX unit in the list.  This probably works correctly in normal circumstances, but there are two cases where it’s an issue.

• When you are stuck in a build/fly/crash loop. It overwrites your chance to get out of the loop and literally forces you to stay in it.
• If you are in ANY single city island situation and your exploration unit crashes.

Originally, I tried to modify the SAI_UT_EARLY_EX code to include multiple units, expecting that it will cycle through them.  That way, if my airplane crashes, I can build an exploration Seabee for example.  That way I could manually input options in the build order until I found the optimal combination.

However, I found that the code is literally hard coded to only take the first value.  So in this case, there is no escape from the loop.  I am stuck with the AI performing the build/fly/crash loop because it wants to constantly rebuild airplanes.  The quickest fix for this is simply having it cycle through the SAI_UT_EARLY_EX list because there is also an if statement checking to see if a unit from this category already exists.  However, the right fix is to define ratios (maybe 1QC:1TR:1EX) for various starting types (see the three start types above, plus the default start type if none of those options apply), swapping the build ratios in or out based on its situation.  This allows multiple fixes for AI modders to improve performance until you exit early game.

I should also note that there is a late early explore option.  I didn’t really dig into this, mainly because it seems to only apply if you manage to get off your island.  All I know for sure is modifying the SAI_PRI_EXP_CITY_CRITERIA and SAI_PRI_EXP_LAND_CRITERIA seem to have an impact here.  SAI_PRI_EXP_CITY_CRITERIA is the number of cities you possess.  Reducing this to 0 is the same as deleting it altogether.  This will move the build queues into mid game.  Also, the right recommendation for AI modders, who dont want early game exploration, is to delete this line as opposed to making it 0. There is actual code to check and ignore SAIEarlyExplore if it is deleted, and setting it to zero may impact code elsewhere.

I never figured out how SAI_PRI_EXP_LAND_CRITERIA work.  I thought it was the number of land tiles explored, but I reduced this to 100 and it didn’t have an effect the code suggests it would have, which is to send it into SAIExplore.

EDIT: After re-testing this and watching how the other AI’s operated, I noticed a peculiarity.  When on an island with a sea-based city, the AI seems to build but not fully deploy its airplanes.  It moved straight into the sea exploration queue and uses that as it’s primary exploration unit.  I thought this odd, but it seems to completely ignore the SAI_UT_EARLY_EX code.  I didn’t look into this, but it’s something to note as there is no early sea exploration option, thus nothing obvious to debug.  It made exploration much much slower for these players when it didn’t have to, which is probably why island-based AI’s tend to have issues.  The fix would be for the AI to use SAIExplore for air units in this case, and not wait for sea-based units only.

Conclusion: ex_type[0] should be ex_type[i] so we can create build orders.  I would also check the code for other similar cases and update to cycle through arrays (i.e. carriers).  I would also add a way to control this through a ratio or numeric value instead of just ex_type.Count > 0 but rather allow modders to input ratios.

Concluding Recommendations

There you have it.  Unfortunately, I don’t understand the AI script well enough to make all of these suggestions work together.  With the right amount of time and dedication I could probably pull it off.  That will wait, at a minimum, until after the new patch so I don’t have to duplicate effort.

To summarize, my results were as expected with one pleasant surprise.  I was actually really impressed with the AI’s inherent understanding of air transports.  In fact, I would argue it’s probably better than how human players use them.  The AI is being held back by the Air transports movement of 2.  The AI performed better when I raised this to 4 and 6 respectively.  To give you a sense of accomplishment, once I removed the air exploration restrictions, in 1000 turns the Madagascar AI routinely built an empire that controlled Half of Africa and the Indian Subcontinent.  That is an impressive accomplishment for a map this size.

The last thing I did to close out my analysis was run the entire test case again, but this time with the default Enhanced Units set.  I just wanted to make sure I didn’t miss anything.  While the AI appeared to perform “better” with this set, I still saw the same issues especially now that I knew and looked for them.  That tells me that the enhancements would still be good suggestions for direct modification into StandardAI instead of just posting a new ModAI.

I’ll see what changes come out of the upcoming patch and make a decision at that point.  Until then, feel free to make changes to your own ModAI and see if you have any changes to suggest as well.