In the 4X TBS genre it's typical to have a tech tree. In the RPG genre it's typical to have a bunch of stats that you level up. In both cases, fascists like myself spend a lot of time thinking about how to optimally minimax the tech tree, so as to ramp up productivity / military power the fastest and thereby dominate the globe / the dungeon / whatever. I call this the "Reinvestment" problem, although perhaps others know it by a different name. I find myself quite baffled as to how to analyze complex Reinvestment problems. Usually a given investment is a tradeoff between costs now and benefits later. Occasionally there's a straightforward solution, i.e. some action is always profitable. But usually, the interactions of game state are so complicated, that I really can't tell whether a given course of action is more profitable or not. And so I end up iterating through 4X TBSes over and over again, looking for the Golden Paths through the game. (Current whipping boy is C-Evo.) I'm chagrined to find that even as a smart human, I discover things upon long, repeated iterations through such games. I have wondered if an AI could do a better job of accounting than I can, i.e. not get tired after playing for 5 hours, be more disciplined about comparing the exact ongoing profitabilities of different games. But it seems that such an AI would rely on a massive database of previously played games. So often, the Reinvestment problem can be decided only by trial and error. Is there any better way to tackle such problems than to recognize them as NP-complete?

For what I understand...., what you're trying to do is find the best way of "walk through" the tech...., wouldn't a GA properly done help you with that????

Difficult to say, as IIUC, a GA is little more than a random walk through the problem space anyways. I would still have to collect the huge database of game results. I suppose when I was wondering about a "better analytical framework," if there was any mathematical treatment of Reinvestment problems that I had overlooked. I suppose I should think about whether tech tree selections have an expressable fitness function.

The only thing I've been able to come up with is to create ad hoc metrics for various kinds of "progress," and then do a search over the cross product of all such notions of "progress." In other words, use my human judgement to decide what kinds of things are to be searched, and then search everything. Perhaps it can work if the metrics are reasonably compressed / compact representations of complex data. It may not matter, for instance, what's happening on most of the squares of the board. If I subsample the game phenomena in some drastic way, perhaps I will have ad hoc heuristics that are good enough. I am wondering if the human mind works somewhat like this, in the way it compresses data for long term memory.

I don't think the spontaneous, random generation of new ad hoc metrics is going to work, because the game state is so complex that it's probably like throwing darts at infinity. Small wonder evolution has taken so long.

What a coincidence, someone is talking about game theory in relation to video games...

I'm guessing that tech trees aren't NP-complete and a mathematical solution could be determined for the best and fastest way to climb a tech tree, but if it couldn't, you could just remove a few factors until you can write a function and hope that the answer doesn't change too much. However, there are so many variables involved, and accounting for your opponents actions is so incredibly difficult, that I don't even know where to start in writing such an equation.

For example, for Starcraft (never played C-Evo, so can't use it as an example), you could start with a score for each unit's military strength that you define yourself (I'll explain why in a bit). From this score and the cost of each unit, a production score could be given to each building. The production score would also have to take into account buildings that are now buildable on the tech tree. With the production score, a 'course' up the tech tree could be plotted that gains the highest production score with the least expenditure of resources and time. But this all depends on the initial military score of each unit being correct. So, isn't there a function that could calculate the military score? The problem here is that certain units are good for certain situations, and I personally don't know where to begin coming up with an equation to describe each unit's strength in relation to a particular situation.

Of course, I could be completely wrong. I've always been too daunted by this task to try it, especially given that if I gave a unit an incorrect score, the entire procram would be rendered useless...

The problem you are trying to address is quite hard to solve.

Basically, you are looking at a decision tree.
Unfortunately you really do need some metric to evaluate the final results of your upgrades (leaf nodes). The cost for every upgrade can easily be computed. You will just need to devise some function to combine the value of different resources into a single cost metric.
Estimate the value of all desired ends (this has to be done by hand). Then propagate their value/cost ratio up the tree replacing the value of a node with the maximum of its children's' ratios.
The biggest ratio wins.
However, the problem with this approach is that it does not catch the advantage of having a certain technology before the enemy has developed it except that you can give time a high scaling factor in your cost function.
Still, if you do not get the metrics right it is quite useless. I fear that without a lot of experimentation you won't be able to get anything useful out of it.

Cheers,
nils