City building strategy algorithms

Question

I'm looking for some papers on finding an infrastructure development strategy in games like Starcraft / Age of Empires. Basic facts characterising those games are:

1. continuous time (well - it could be split into 10s periods, or something like that)
2. many variables describing growth (many resources, buildings levels, etc.)
3. many variables influencing growth (technology upgrades, levels, etc.)

Most of what I could find is basically either:

1. tree search minimising time to get to a given condition (building/technology at level X)
2. tree search maximising value = each game variable*bias
3. genetic algorithms... obvious doing either of the above

Are there any better algorithms that can be tuned to look for a perfect solution of the early phase?

Answer 1

You might find some information on one or more of these books: http://www.gamedev.net/columns/books/books.asp?CategoryID=7

Answer 2

I do not know of any specific algorithm but this does sound like a traveling salesman problem. It does look like you have your base rules so you are already on your way. If you know what end condition you want to reach then it shouldn't be to hard to build a heuristic algorithm for the above rules. Then you could just run a simulation of the build outs and then measure them against each other. Each time you do that you would have a better idea of how to get where you want. Check out this to learn about heuristic algorithms.

Answer 3

There is no "perfect solution" for the early phase (if your game is complex enough). If you've played these games online, you'll see players using various strategies and all of these working depending on the other player's strategy. Some try to attack very early, some are more defensive, some prefer developing economically rather than having lots of unprepared soldiers.

Given this, I believe you must try to figure out a good value function to be maximized.