Monday, October 27, 2003

More news about the game.

I spent about 8 hours working on the AI over the weekend, including a vacation day on 10/27. Good progress. I added classes for VictoryLocation, Plan, and Assignment, and I completed most of the code for enumerating the combinations of commands and goals (a.k.a. VictoryLocations) that make up the plans.

Taking a quick look at the number of combinations based on counts of commands and goals, it looks like I'll have to come up with code to identify the VictoryLocations along the FEBA, in order to reduce the combinatorial explosion. In the Opening Moves scenario, there are 4 VictoryLocations and 5 corps-level commands on the Imperial side, thus there are 4 to the 5 combinations or 1028 different plans to evaluate. In the larger scenarios we are looking at 18 VictoryLocations and 6 Imperial corps commands, for 18 to the 6th equals 34,012,224 plans. This is not happening!

I think it is reasonable to hope that the AI might be capable of evaluating 1000 plans per turn, particularly since much of the evaluating will consist of applying rules of thumb and common sense to prune candidate plans from the list. For the Opening Moves, we can say that any plan that does not assign all the VictoryLocations will be pruned immediately.

Upcoming work

Finish off the plan generator.
Add the first pruning rule for the Opening Moves.
Have a stab at writing the first evaluation function for plans.
Write the first plan ranking function.
Cleanup and evaluation. (Who knows, I might even produce a passable high level AI the first time around.)

Additional Thoughts

I may try to pre-rank plans prior to evaluation so the AI checks more likely plans first. I may also break up the plan evaluation and ranking steps so that the AI evaluates X number of plans, then checks for the user's Phase Turn signal, the evaluates the next X plans, and so on.

I think I will also introduce a separation between the high level AI and the low level AI, depending on how long it takes the low-level AI to operate. I will have the low-level AI run after the user has pressed the Phase Next button...this will introduce a roughly 60-120 second wait, but will ensure that the high level AI has tiem to do its work. If the high level AI completes its work, then of course the low-level AI will be run.


Post a Comment

<< Home