"Curiosity driven learning" in video game AI?

from Elemental Forums

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?

elemental
6,722 views 6 replies
Reply #1 from Elemental Forums Top

This is a very interesting post, at least to this coding spectator. Where are the real code monkeys? Is smakemupagus asking about things that are obvious to the AI folks inside Stardock? Is this two-competing-objectives thing possibly a way to make AIs that really do have a 'world view' that affects their decisions?

I would be beyond happy if WoM and/or FE ended up being the first Stardock TBS that had a couple of kick-ass AIs that avoided war at all costs instead of assuming that war is the only thing worth doing. Oh, to be invited into an alliance that was based on an AI's commitment to helping the helpless and smiting the wicked...

Reply #2 from Elemental Forums Top

Ièm sure they will have different ai personalitie once they are comfortable with its ability to play the game :P

 

Star Control: Origins
Reply #3 from Elemental Forums Top


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?

 

This is actually the way basic turn-based AI works - They make estimates using all the numbers they posses and assess whether or not they have a high chance of success for each consecutive action. The AI typically will have plans based on everything they have explored, and needs that if not met, are met through exploring. Sometimes you'll see the AI send out a pioneer unit towards one resource, and then suddenly high tail it towards something that was just discovered because the AI wants it more and doesn't want to wait for the new unit to appear, so each turn the AI should be re-evaluating all of its knowledge. It uses those worthless faction power numbers to determine who it should be declaring war with, though in my opinion it should use that along with its knowledge of existing units - If a faction has a medium power rating but a few super units that the AI can't hope to beat, it should use that knowledge in spite of the power rating being lower than their own.

Now the AI is faulty in which numbers it utilizes for evaluations and how it does a lot of its thinking. So the utilization of existing knowledge and evaluations using an "Internal world model" (i.e. estimates and comparisons) is there, but it's just a bit off.

 

Now if I completely misunderstood what you meant by curiosity driven learning, I'm sorry - I'm sure it's more complicated than the short original post, but this is my thought from what I know of things.

Reply #4 from Elemental Forums Top

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.

Reply #5 from Elemental Forums Top

AI for games is probably different than solving equations.

 

I would say that no game AI today actually "learns" anything, as that is too much work. Instead the programmer will just create some basic objectives and concerns for the AI and it will make decisions accordingly.

 

Now you could write an AI that is connected to the internet, monitors every game your players play, (especially in multiplayer), and have the AI look through all of the replays and figure out what all the strategies are and how to counteract them. A problem with this system is that you would need a huge database and a complex program to update and use this info, which nobody has done yet for a video game.

 

So for now, I think the way to improve AI is to make a very flexible AI that can make its own decisions. For example, in War of Magic, someone said that it relies on this "faction power" to make military decisions.

 

A smart AI would look at every unit you have and decide whether it could take on your army. So if you have lots of archers, it should factor that in. If you don't have archers, but you have the technology to make the best archers in the game, it should factor that in. If you have the technology but not the resources, it should factor that in.

 

Its not really that difficult to make a really great AI that doesn't use much CPU and memory, you just need to be smart and creative when you design the AI. I think that having a strong concept of the game is important when a programmer designs the AI, which is why having the AI learn will always lead to better AI since you don't have a human deciding what the AI should and should not do (and thus introduce human error).

Reply #6 from Elemental Forums Top

I did some research on the Watson AI that competed in Jeopardy yesterday. The basis for that AI is called "Machine Learning". Instead of basing decisions on rules and calculations, the AI learns by example. By analyzing hundreds of examples in its database, the desired result can be compared with similar situations.

"based on these historical conditions, there is an 80% chance the player will do such and such in his next turn" and the AI can take the appropriate action.