Sunday, April 08, 2012

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.

Labels: , , , ,