A friend of mine recently introduced to me an optimization method called "Curiosity driven learning". We use it to solve complex multi-parameter parameter problems that come up in materials physics. The great thing about this method is that as it iterates, it balances two competing objectives: (1) to try to find the best solution with the info on hand right now and (2) to satisfy curiosity by constructing a consistent internal model of the world. Much like evaluating a complicated game board state, our forward problem can be computationally expensive like a solution in a large space of Maxwell or Schrodinger eqs. So this is a nice approach because it lets you leverage your internal model of the world to quickly get a good solution while evaluating the "forward problem" as small number of times as possible.
In the journal literature some people refer to the tradeoff in this type of optimization as "Explore" vs "Exploit", so, as you can imagine it got me thinking about the connection to "2X/3X/4X" strategy game AI. But, I don't know anything about how game AI is contructed. Is this kind of approach used already? Are there standard test problems available? Are there Journals of Game AI or something out there?
To understand video game AI in relation to more traditional AI applications, you have to take a second to consider the fundamental differences in the problems being addressed. Let's take a look at a more traditional AI application, a natural language interpreter. A natural language, such as English, French, or Japanese, contain a finite amount of base symbol, phones, which make up their respective phonetic alphabets. These symbols can be combined in such a way to make a countably infinite set of possible strings. Yet, every natural language contains only a finite set of acceptable strings, which make up the syllable set for acceptable words. Thus, the total amount of acceptable words in a natural language is a finite set. Now, a natural language interpreter might take in a string which we will define as an acceptable sentence of some language. It then processes the words and the grammar to attempt to create acceptable model of the sentence's meaning. As the interpreter runs, it uses the various sentences to create an ontology, a model of the relations of various words, which it then uses to better interpret future sentences. This type of learning is very similar to your curiosity driven learning, in so much as the interpreter balances trying to interpret the single sentence or piece of text and also trying to create a comprehensive ontology to derive meaning. This process is incredibly computationally complex and requires large amounts of time to complete.
Now, looking at a game AI, the traditional thought is to look at games such as chess which have a small amount of well defined moves and to create systems which are capable of creating an optimal strategy for any particular game instance. Yet, these game systems are still computationally complex and require time to complete their vast computations. If you consider X3D-Fritz v. Kasparov game, the computer was given 2 hours to make around 40 total moves. A normal video game, however, does not have such luxury, as there are several key limitations which handled. These AIs must be capable of near real time calculation and must ultimately not be invincible. If we consider Elemental's AI, each AI faction can have more units than a standard chess board has pieces and each unit has more possible actions per turn than any single chess piece. On top of this, even if the AI is given full vision of the board, the AI must also calculate again a fairly large amount of unknowns. Thus, attempting a set of computations designed for making optimal moves is more or less impossible. The traditional work around is the use of a scripted AI, that is, an AI that is given hints as to what actions to do given a certain situation. Many FPS games use heavily scripted AI to control the various units since time and CPU cycles are at a premium, where as TBS games can use a mixed scripted reactive AI since time of the player's turn and the time between turns can be fairly large.
