AI Trouble

I’ve been rewriting the enemy AI to try to make it more intelligent. My first thought was to take a holistic approach and have a brain that considers where all the player programs are, and decides how it can use all its programs to cause the most damage. However, when writing it, I discovered it was more difficult than I expected.

It’s easy enough to see what each program can do individually given the state of the grid, but of course the grid changes whenever a program moves. The script might determine that two of its programs could both attack one big player program to kill it, but after moving one of them, its trail of sectors gets in the way of the other program’s route, or when it attacks it removes the sector that the other program would have attacked.

I considered brute forcing it and iterating through all possible moves to find the best one, but because of the power of exponential increase, there could have been tens of millions of possible moves, which would have taken a long time to get through. Imagine playing the game, ending your turn, then waiting for 20 minutes on a still grid while the enemy works out what to do. I decided the holistic approach is more trouble than it’s worth, and instead did something more similar to the old AI, moving programs one by one.

It’s not a complete loss. The new AI considers the order in which it moves programs, and moves the ones with only one reachable player program first. This gets the easy decisions out of the way and narrows down the choice for the programs with more targets. The old AI moved programs in an arbitrary order. The new one also moves programs more if they can’t get to any player programs because of islands or barricades.