AI: Decision trees

On the hierachy of lameness, you have:

1. A guy playing a video game
2. A guy watching his friend playing a video game
3. A guy watching computer players play each other in a video game.

I am at the bottom.

I watch computer players play each other. To see what smart things they do in different situations and what dumb things they do.  So much of good computer AI really boils down to play testing. The best algorithms in the world are no match for real world playing. And what looks like a good idea on paper can end up being a disaster in the real game.

The decision tree in Galactic Civilizations is actually pretty significant. Consider the choices it has to make. Then consider other strategy games you've played and think of the choices that have to be made there:

1. What should my tax rate be? The higher, the more unhappy my people will be which will slow down population growth but the more money I get.
2. What should my spending rate be? Spend too much and I'll run out of money or not have enough to make quick purchases. Spend too little and I'll fall behind.
3. How should I set my ratios of research, social, and military?
4. How should I design my ship? There's an infinite number of designs possible.
5. What technology should I research? There's over a dozen distinct, non-connected branches in GalCiv (look carefully at the # of branches in other games -- usually less than 3 or 4). Pick the wrong one and my economy might be weakened or maybe my industry weak or my military weak or my morale weak or maybe I won't be able to get those special worlds or maybe my logistics will be too low or maybe my miniaturization won't be competitive and so on.
6. What should I put on my planets? Do I use that special farming tile (i.e. put a farm on it?) or should I sacrifice it for another factory or a research center or save it for a galactic achievement or a fusion power plant? Or maybe build a farm but if I do, will I have space to put on morale improving buildings?
7. How should I use my military forces? Is the human player my friend or is his build up designed for a sneak attack? Should I escort my transport even though my transport moves at 10 moves per turn while my escorts only move at 4 or do I send it at that undefended planet that is only 12 moves away and the fog of war might be hiding an enemy there?
8. Should I hold back my fleet and wait for more shpis to be built to make a bigger fleet or should I send it out now and wreak some havoc?
9. Should I build a transport (only transports can take planets -- unlike in many other games where any unit can conquer the city/planet/star/) or a constructor to take that nearby resource?
10. Should I build a starbase near my planet or should I extend my range with a starbase?
11. Should I upgrade my starbase or construct a new one by a different planet?
12. Should I put resources into spies and if so, how much?
13. What should I be doing with my spies? Protect my worlds or send them out? If so, which worlds should they go to?
14. If I'm sending a spy to a given world, which planet improvements should I take out that will do the most harm to them based on the strategy that I perceive they're taking? Or alternatively, which enemy agent should I nulify?

Some of these decisions are more complex than others. The one I have the most difficulty with is one of the more straight forward -- what to research and when.  I've had others I've had to struggle with -- I didn't write, for instance, the planet improvement placement code in GalCiv II, but in Dark Avatar I've rewritten it (for better or worse) to something that matches more closely the way I play the game.

In most strategy games that have computer opponents, the decision tree is kept very small.  Think through the games you've played and consider the # of actual decisions that the computer opponents have to make. And by decisions, I mean actual choices as opposed to choices that are pretty obvious.

Consider your first 20 turns of Galactic Civilizations II. What should you research? If you research the same thing (i.e. you script it) you become predictable. If you just have the computer players randomly select what it should research, it becomes pretty obvious and ineffective. 

Having computer players that don't cheat makes it tough too. I can't just tell the computer players to send a colony ship to the closest uncolonized planet. It has to know about it or at least make a reasonable guess based not on real data but based on what the map looks like.  Very often players will complain that the AI should have not done this or that without realizing that the AI made its decision because it couldn't see their ships or a planet. Sometimes players will insist that the AI must know where the good planets are because it did what most good players would do -- built a colony ship and sent it into a sector full of planets that were on the galactic sensor map (the odds were in its favor after all).

In most games with tech trees, players are pretty much expected to research every technology. In GalCiv, players are punished for doing that. The tech tree is too big. Players have to pick and choose which techs for their strategy for a particular game. That means the AI can't just randomly muddle through. It has to wisely pick.  At lower difficulty levels, that's what I have the AI do -- randomly pick technologies. But higher up, people expect their opponents to be thinking about this stuff carefully -- and they do.

And so on a variety of maps, a variety of players, I watch them play each other. What's worse, I like doing it.