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.

Game Development Status 11/6/11

I am continuing to work on the prototype for the AI and UI for PC PIC-Guam. This weekend I wrote the evaluation function for the Fire Combat AI, hooked the AI up to the game system, and got the Japanese to conduct a Defensive Fire. I'm filling in around the edges now. The UI is not displaying color overlays to indicate the target hexes of the AI's fire combats. I also have some additional testing to do to make sure the game phases out of AI fire phases OK. After that I need to make sure the AI moves execute, and then I will change the game to have the AI run the US side.

My backlog (from Evernote) looks like

Finish the prototype

Write the Eval method

11/6/11 - 2 hours

Hand-calc the stat avg values

this was not necessary, as it is possible to calculate the values.

Write the allocation selection code

11/6/11 - 1 hour

Write code to apply the selected fire allocation and resolve the attacks

11/6/11 - 1 hour

Test to confirm that attacks occur and make sense: phase, AI runs, game resolves fires from selected allocation, player reviews results, phase again and results no longer display

Write code to move the AI's units.

Change the code to play the US side

Test the movement part of the code

Remove assault and reorg phases

Test to confirm that AI and player phase the game and that each phase has something real happening

Write code to detect victory conditions and display a victory message (turns/duration date of victory, victory conditions)

Add the full orbat for the first scenario

Test the first scenario

do I need to remove other (unused) phases ?

Write an installer including a EULA with full disclaimers

test on home laptop and dawn's laptop: install, uninstall, BVT (run 1 turn), full game to include victory conditions

Game Development Status 8/28/11

Doing some work on the prototype for PIC-Guam today. I did an hour yesterday; trying to build some momentum. I am implementing a prototype AI.

Today I had to refactor some code pertaining to movement footprint generation in order to reuse it in the AI.

My first approach to this AI is brute force. I am traversing the phasing unit list, generating all possible attacks permitted by the movement footprint. For each possible attack (firing unit in hex X versus target unit Y) for a unit, create a new allocation (list of such attacks) containing that attack and recursively call the allocation method for the next unit. As an allocation is completed (by adding an attack for the last unit in the list), concentrate the attacks in the allocation so that all units attacking the same enemy unit participate in the same FireCombat. Then evaluate the allocation by summing average fire combat results for each attack. The top N allocations are kept, and the actual allocation is randomly selected from among the top N allocations. During movement phases, the selected allocation also determines unit movement: each unit is moved to the

This will produce a very large combinatorial explosion, especially for the full order of battle. The questions are whether it will work in the first place for the small Orote scenario, how slowly it will run, and whether the results are any good.

I can reduce the processing and memory requirements of this brute force AI in several ways. I can pre-calculate the movement footprints and attack footprints for each of the phasing units. I can sort those movement/attack footprints by descending size and reorder the unit list accordingly, minimizing the number of nodes in the notional graph of partial allocations. I can also prune the movement footprints by accounting for overstacked hexes and removing allocations from consideration that exceed a threshold. I think I can also remove allocations that result in very few attacks (for the US side). For the Japanese side I may have to increase the difficulty by min-maxing to select the most casualties inflicted versus the least casualties incurred within a subsequent phase or two. Also, the Japanese side will need to constrain their movement in order to fully occupy the current generated FEBA line.

I'll eventually have to add some additional code to split out a certain number of Japanese engineers to create fallback defensive works. I'll need to control movement of AAA units with separate code as well in order to reduce the effects of US air.

PIC-Guam Progress

I am continuing to playtest the PIC-Guam game. I have been reviewing the rules, particularly from the point of view of writing a computer "AI" opponent. My latest set of questions includes

• Do landing units have to stay in their lanes? For example, the way the lanes are drawn it looks as if Red 1 can land in either 2712 or 2711.
• Can you add a note about the lagoon half strength rule to the CRTs?
• Is a lagoon hex considered to be a non-clear hex? Can I cause X fire casualties by firing into a lagoon hex?
• 2.12.1.2 Which hex is the "sea" hex? Is the sequence properly sea-lagoon-beach, or really lagoon-beach?
• 2.12.1.2 What happens if landing units are stuck on the lagoon or beach? Do stacking limits prevent further entry to a lagoon or beach hex, delaying further landing waves? Do stacking limits apply in a lagoon hex?
• 3.4 What is the size of an HQ unit? Should there be an exception to 3.4 Stacking that permits a regimental HQ to stack with its regiment in violation of the stacking rules?
• 2.12.1.2 Can a landing unit move from one lagoon hex to another? Can a landing unit move outside the designated lanes?
• 3.6 Can Japanese replacements be chosen for an HQ unit that was destroyed?
• Are Naval units placed at the "start of each turn" per 11.2, or are they placed in Movement phase? In other words, when are ships placed on the map?
• Can 6.2.4 Air-Ground suppression take place if the Japanese unit is in a fortification?
• Does 5.5 Japanese infiltration apply to all Japanese units, including armor?
• 2.12.1.3 I think the last sentence should be removed. It seems to me that per 2.12.1.2, a unit in a lagoon is obliged to either move to a clear beach hex (see my first question above), or is obliged to perform an Amphibious Assault against an enemy controlled beach hex. There appears to be no logical way for a US unit in a lagoon to perform an Amphibious Assault against a non-beach hex.

I think this is a great set of rules. It is pretty easy to play, very easy to develop an AI for, and reasonably faithful to what I have been able to learn about the Battle of Guam in 1944. I am very happy to be participating in the playtest.

I'm currently putting together a proposal to develop a PC-based game for this title. I don't know whether GSI of TX will be interested in it, but I certainly am: I think I can build the entire game, including multiple play modes and an acceptable AI opponent, in less time that I can complete the work on PC Eylau.

Game Development Status 3/28/08

monthly total 7 h 41 m; yearly total: 20 h 17 m

I took the afternoon off and worked on the game today. I'm still working on decoupling the AI thread from the main thread storage.

I'm guessing it will be another month or so before we can crank out another "beta". I want to finish the decoupling work, then fix a few of the more obvious bugs that have cropped up recently, then at least get through the single-division, test version of the "Opening Moves" scenario with the AI.

Chris already gave the good housekeeping seal of approval to putting out a new version.

This next version should be available on this site between the end of April and the end of May, depending on my progress and my other commitments.

By the way, the software will be distributed on the Yahoo gsibetatest2 site with a password...this will be made available to each person who has signed the non-disclosure agreement (NDA).

vive l'E!