"AI AI Two" by Troy H. Cheek on Aug 17, 2009
As I mentioned a few weeks back (and several times previously), there's a RTS game I like to play called XTA which runs on a game engine called Spring. As I also mentioned, I was working on an AI opponent for that game. At the time of that writing, my AI could defeat two of the three AIs which shipped with Spring. These were the old, reliable AAI and the newer, fancier RAI. KAI, or KAIK as I've also seen it written, was beating my AI fairly regularly, but I thought I had a handle on it. I was working on a new approach and expected to overtake it at any moment.
Since then, a couple of release candidates of the next Spring version have come out. Mentioned in the release notes was one little line: "some AIs play better now (especially KAIK)." This bothered me a mite because KAI was the one of the three that I couldn't beat yet. Fortunately, KAIK didn't work for me when I tried it with XTA, so I didn't have to suffer the humiliation of being beaten by it. Neither did AAI. RAI worked. In fact, RAI started beating me regularly, so I've got to rethink my approach yet again.
The three Rs of any real time strategy game are Resources, Resources, and Resources. XTA's resources are energy and metal. Energy can be created any number of ways. You can construct wind generators or solar panels just about anywhere. Geothermal plants can tap active vents, though most maps I've tried have only a few of those and some have none at all. You can also construct fusion power plants of various sizes. These tend to blow up real good, so you have to be careful with them.
To gather metal, you need metal extractors or mines as some call them. These are only really effective when built on top of metal outcroppings. Some maps have tons of metal spots while others have only a few. There are also metal maps where every square inch of the map has metal, but I've never played those. There are rumors of maps with no metal at all, but I've never played those, either. You can also convert energy into metal with metal makers, but this is a very inefficient process.
When I first started programming the AI, I didn't know how to locate metal spots so as to place extractors, so I just went with makers. While very inefficient, it worked as long as I spent most of the metal they were making to build enough solar collectors to power them. I eventually did figure out how to detect metal spots, mostly by finding a metal-detecting Lua script that someone else had written, deciding it was hopelessly overcomplicated, and almost completely rewriting it. In the end, I kept the general idea and a few specific call-ins that I hadn't know about. Everything about this game has been a learning experience.
Of course, knowing where you can build metal extractors isn't as important as knowing which metal spot to build on and when. I discovered that if you just keep building on the nearest spot, eventually your AI is going to venture into enemy territory, get your builders killed, make some more builders, send them off to the same spot, get your builders killed, etc. I eventually settled on a limit of sorts. By checking the position of all my existing units, I could calculate the center of my "base" and how far out from the center I had already built. If the nearest metal spot was too far outside what I'd already built, I just wouldn't build an extractor right then and would instead build a maker.
The "when" was also difficult. I couldn't just build metal producers when I was low on metal ("mstall"), because metal might be low simply due to lack of energy ("estall"). I couldn't just not build metal producers when I had plenty of metal, because then my AI would never expand. My compromise was to flag and prioritize all the other things I needed to build. If there is nothing else that needs building, then and only then try to expand to the next metal spot. I even threw in a little flag to keep track of whether any of my units had encountered any enemy units yet. If not, then I let my AI assume that it's okay to send builders far outside of the base to set up camp at new metal spots.
Radar coverage and scouting are important. Otherwise, you don't know where the enemy is until he's actually attacking you. If you fight a purely defensive game in XTA against an opponent who is actively seeking your demise (instead of playing defensively himself), you will most likely lose. My AI has radar covered pretty well. Pretty much any time a builder is idle, it checks to see if it's near an existing radar tower. If not, it builds one. There's some overlap, of course, and the AI doesn't check to see if radar towers have been knocked out (a favorite tactic of RAI) leaving gaps in the cover, but all in all it this approach works pretty well. I don't think my AI has been surprised due to lack of radar coverage. Surprised due to having no units on hand to counter an attack is a whole other matter.
Scouting is difficult, but I think I've got a handle on it. Previously, my Harass AI widget (a helper AI which sent idle combat units after the nearest radar blip) just sat idle until it detected a threat. In the last revision, I had it start sending random movement orders to idle units. These units would wander a random number of steps in a random direction. About the only restriction I placed on them was that they not try to wander off into deep water or off the map edge. As I only give a single random walk order every second or so, and I always start with the lowest numbered units, this has the effect of a small collection of units wandering around and usually covering about half the map before they encounter an enemy.
Once mobile units with radar are available (after certain factories are built allowing more choices of combat units) the AI has more scouting options. Lots of mobile radar units bog down the game -- updating all those lines of sight takes quite a bit of processing power, apparently -- so I limit the AI to building just one mobile radar unit of each type. I send these on a grand tour of all the metal spots I calculated earlier. Every map I've played has metal spots scattered all over. I don't think there's any location on any map I've played that isn't within radar range of a metal spot, and unless the opponent is using metal makers exclusively, he has to have at least some units near a metal spot.
The current grand tour isn't very efficient. I basically set patrol points on metal spots in the order in which they were discovered, which is East to West and North to South, so there's a lot of backtracking. This isn't really a problem because most of the radar units I'm using currently are pretty fast airplanes, but I'm considering limiting the use of airplanes on maps which are mostly or all land. As such, I'm going to add a routine to cover the spots in some kind of "nearest first" or perhaps "nearest to center of base first" order. This isn't an ideal solution to the traveling salesman problem, but if the finest minds in mathematics haven't found an easy solution to the problem in the last 75 years, I'm not going to find one this weekend. For 60 spots the number of permutations is supposedly about the same as the number of atoms in the known universe and calculating the ideal path will take longer than the life of said universe, so simply proceeding to the next nearest metal spot will have to do.
I did realize that just because a metal spot is on land doesn't mean that any land unit can reach it. Stupid lousy islands.
When it comes to scouting, the temptation to "cheat" is pretty strong. As a human, I know where the map's startpoints are defined, I know where the game lobby put each AI player, and I know where human players are likely to start. That's information that the AI technically doesn't have any way of knowing, though I think it can parse the map files to find the defined start points. When I play myself, I don't so much scout as send attack forces to the other start points. Though this is how a human plays, and I want the AI to play as humanlike as possible, for some reason, this feels like cheating.
Next week: Pathfinding!
