And Then It Exploded

I'm working on the AI code for PIC-Guam. In the last few months I have been able to spend a few hours optimizing the fire combat AI. I was able to get it to work reasonably well by replacing or changing a lot of LINQ statements from my "hello world" version from last year. This included movement code based on locating the phasing side's unit for maximum combat effect.

It did not scale.

I got three Japanese units to execute defensive fire, movement, and offensive fire on successive turns until the eight US units were eliminated. This worked rather well, but I needed to try the US side, as this approach would work in the offense but not the defense. I added code to run the US or the Japanese side (or both) in the AI depending on a selection.

This blew up in a combinatorial explosion resulting in OutOfMemoryExceptions. Every time. Optimizing the code was not going to solve the problem. The algorithm sucks: for a given set of attackers with range of target units it is O(Attackers ** Targets).

I decided to separate the movement AI from the combat AI. I will move the HQ units relative to the local FEBAs and other friendly HQs. Based on this, I will move the units to stay uniformly distributed to the FEBA in their respective HQs' sectors. Artillery will probably congregate near HQ units. As the lowest echelon HQ units need to be within 6 hexes of the FEBA in order for subordinate units to be in supply, this means most (US) artillery units will range the FEBA.

I did a proof of concept this afternoon. I hard coded a FEBA and let the allocation code run a movement. This worked fine for the US. I then proceeded to try combat. Which exploded.

I fixed the explosion by adding code to bias the AI in favor of attacks against adjacent units. This reduced the number of potential fire allocations by a factor of 50. For the eight US units against 3 Japanese units, it runs in almost no time: .167 seconds for 1024 fire allocations.

I may have to revisit the performance as I scale to the full Orote scenario, and again as I scale to the full ORBATs.

Total time this weekend was 8.5 hours.

Next step is to add code to determine a local FEBA. I can review the Eylau AI for useful techniques, and I can manipulate the test database to try different scenarios. It's also a good time to complete the Orote scenario ORBAT.

Fun with Zones of Control

I'm working on elaborating the movement rules by including an awareness of Zones of Control (ZOC). Every unit exerts a zone of control into the surrounding hexes. This has the effect of stopping movement, and triggers Defensive First Fire. I'm implementing movement in the prototype so that entering into movement mode identifies all hexes the unit can move to by highlighting those hexes. It's important to take ZOC's into account, especially since ZOC's stop movement and the rules do not permit movement from one ZOC to another.

This is what I had earlier today. There was a problem in the adjacent hex code...it did not always generate a list of adjacent hexes, resulting in the "jump" over the enemy units shown here.



I fixed the adjacent hex code by providing the proper offsets and better controlling code:

public static List<Hex> AdjacentHexes(int x, int y)
{
    List<Hex> adjacentHexes = new List<Hex>();

    int[] XOffsets = { 1, 0, -1, -1, 0, 1 };
    int[] evenYOffsets = { 1, 1, 1, 0, -1, 0 };
    int[] oddYOffsets = { 0, 1, 0, -1, -1, -1 };

    int[] YOffsets = (x % 2) == 0 ? evenYOffsets : oddYOffsets;

    for (int offset = 0; offset < 6; offset++)
    {
       adjacentHexes.Add(Hexes.Where(h => h.X == x + XOffsets[offset] && h.Y == y + YOffsets[offset]).First());
    }

    List<Hex> adjacentHexesOnMap = new List<Hex>();

    foreach (Hex h in adjacentHexes)
    {
       if (IsOnMap(h.Y, h.X))
       {
           adjacentHexesOnMap.Add(h);
       }
    }

    return adjacentHexesOnMap;
}

This resulted in the following improvement in testing.



I did some more testing, setting up a situation in which hex 1806 should not be in the movement footprint due to the ZOC code. I still had some work to do:



I had added the ZOC logic initially to the first set of adjacent hexes originating from the unit's starting location. I wondered whether I needed to also add that logic to the code that evaluated subsequent hexes further away from the starting point. This proved to be the case:



This finishes off the things on my list now for movement. I'm sure I've forgotten something, even cutting corners as I am for this prototype. Still, I think I have enough for now.

The next task I have is fire combat. This encompases Defensive First Fire, Offensive Fire, and Defensive Fire. This will take some doing.

Rolling Along...

I put in another hour and a half on the PIC-Guam prototype today. I am finishing up some additional features for movement. Today I was working on the rule that says a unit can't move from one Zone of Control (ZOC) directly to another. I moved the Hexes from the Game class to be a static member of the Hex class...this makes it easier to access everywhere I need it, and it turns out I need it everywhere. No problem: I relocated the declaration and "rode the compiler" to fix all references.

I'm very pleased with how quickly I can put together meaningful features using C# and LINQ techniques. Using extension methods and lambda expressions, I write terse code with minimal ceremony that is relevant to the requirements.

I like my chances of completing this game in 1000 hours (of effort).