REAL TIME CONTEXT LEARNING BY SOFTWARE AGENTS

• US 20070260567A1
• Filed: 07/06/2004
• Published: 11/08/2007
• Est. Priority Date: 07/06/2004
• Status: Active Grant

• Current Assignee: Wei Yen
• Original Assignee: Ikuni, Inc.
• Inventors: Tu, Xiaoyuan, Funge, John, Wright, Ian, Yen, Wei, Dobson, Daniel, Cabral, Brian, McNally, Michael, Duffy, Nigel, Musick, Ron
• Granted Patent: US 7,296,007 B1
• Time in Patent Office: Days
• US Class Current: 706/47
• CPC Class Codes: A63F 13/67 adaptively or by learning from player actions, e.g. skill level adjustment or by storing successful combat sequences for re-use
• CPC Class Codes: A63F 2300/60 Methods for processing data by generating or executing the game program
• CPC Class Codes: A63F 2300/6027 using adaptive systems learning from user actions, e.g. for skill level adjustment
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Providing dynamic learning for software agents in a simulation. Software agents with learners are capable of learning from examples. When a non-player character queries the learner, it can provide a next action similar to the player character. The game designer provides program code, from which compile-time steps determine a set of raw features. The code might identify a function (like computing distances). At compile-time steps, determining these raw features in response to a scripting language, so the designer can specify which code should be referenced. A set of derived features, responsive to the raw features, might be relatively simple, more complex, or determined in response to a learner. The set of such raw and derived features form a context for a learner. Learners might be responsive to (more basic) learners, to results of state machines, to calculated derived features, or to raw features. The learner includes a machine learning technique.

Claims

1. A computer controlled system including

a simulation engine having a set of state variables, and having a set of rules describing permitted changes in value of those state variables, wherein substantially each collection of possible values for the set of state variables defines a context;

a stored set of behavior models, each capable of responding to a query from the simulation engine and capable of generating a response to that query;

a stored set of software agents, at least one of which being responsive to one or more behavior models, said at least one being capable of being updated in response to actions taken in a context.

2. A system as in claim 1, wherein updating of said at least one of said set of software agents occurs in real time.

3. A system as in claim 1, wherein said state variables include at least one variable for a raw feature and at least one variable for a derived feature, wherein the derived feature is responsive to at least that raw feature.

4. A system as in claim 1, wherein said state variables include substantially all raw features and substantially all features responsive thereto.

5. A system as in claim 1, wherein updating of said at least one of said set of software agents occurs without reference to any external source logically remote from the simulation engine.

6. A system as in claim 1, including a set of features, each associated with a current context or with a set of information from outside the simulation engine.

7. A system as in either of claims 1 or 6, including

a learner member capable of constructing at least one of said behavior models in response to an action taken by one or more of those software agents;

whereby a first one o those software agents is capable of learning behavior in context from a second one of those software agents.

8. A system as in claim 7, wherein said software agents include at least one of:

software agents for player characters, software agents for non-player characters.

9. A system as in claim 7, wherein the set of behavior models collectively includes at least one of:

a Bayesian classifier;

a neutral network;

an expert system;

an exponential gradient learner;

an on-line learner;

in response to a plurality of features in a context.

10. A system in any of claims 1, 6 or 7, wherein the simulation engine includes at least one of:

a self-learning mode including at least some of those behavior models and software agents having initial values, and reinforcing those behavior models and software agents which are successful according to an evaluator for the simulation engine;

a demonstration mode including at least some of those behavior models and software agents demonstrating their learning to an observer;

a real time mode including substantially all of those behavior models and software agents being updated with each change in context;

a stochastic mode including introduction of random or pseudo-random values for at least some of those state variables.

11. A system as in any of claims 1, 6 or 7, wherein the simulation engine defines a computer game including at least one player or non-player character, and wherein the learning includes at least one of:

a non-player character learning behavior from a player character;

a plurality of non-player characters learning behavior from a player character;

a plurality of non-layer characters learning behavior from a plurality of player characters;

a plurality of non-player characters each learning behavior from a distinct one of a plurality of player characters;

a first non-player character learning behavior from a second non-player character;

a non-player character learning to produce similar behavior in context as another character;

a non-player character learning to produce opposite behavior in context as another character;

a non-player character learning to produce behavior in context friendly to another character;

a non-player character learning to produce behavior in context inimical to another character.

12. A computer controlled system including

a presentation member having a sequence of states, substantially each possible such state defining a context, the presentation including a stored set of software agents operative within a set of rules for the presentation;

and

a stored set of decision models, each capable of generating a response to a query for decision;

wherein

at least one of the software agents is responsive to one or more decision models, and is capable of being updated in response to changes from a first context to a second context.

13. A system as in claim 12, wherein said software agents include at least one of:

software agents for player characters, software agents for non-player characters.

14. A system as in claim 12, wherein updating of said at least one of said set of software agents occurs in real time.

15. A system as in claim 12, wherein said context is responsive to at least one variable for a raw feature and at least one variable for a derived feature.

16. A system as in claim 12, wherein said context is responsive to substantially all raw features and substantially all features responsive thereto.

17. A system as in claim 12, wherein updating of said at least one of said set of software agents occurs without reference to any external source logically remote from the simulation engine.

18. A system as in claim 12, wherein

each decision model is responsive to either a set of game features or a set of information derived therefrom;

each decision model is capable of receiving queries from the computer game;

each decision model is capable of generating a response to those queries; and

each decision model is responsive to either statistical or logical representations of those game features or information derived therefrom.

19. A system as in claim 12, wherein

the presentation member includes a simulation engine, wherein the sequence states in the presentation are represented at least in part by a set of state variables or by a set of information from outside the simulation engine, and wherein the set of rules for the presentation include at least in part a set of rules describing permitted changes in value of those state variables, wherein substantially each collection of possible values for the set of state variables defines a context;

and

the set of decision models is responsive to a set of behavior models, each capable of responding to a query from a simulation engine and capable of generating a response to that query.

20. system as in claim 12, 18 or 19, wherein

said system has at least one decision model, the decision model being capable of generating a response to a query for decision, each decision model being responsive to either a set of game features or a set of information derived therefrom, and wherein at least one of the following is so:

each decision model is capable of being updated concurrently with operation of the computer game, whereby updates to the decision model occur while the player is using the computer game;

each decision model is capable of being updated without a history of earlier versions of that decision model;

each decision model is capable of being updated in response to a Bayesian statistical technique;

each decision model is capable of being updated in response to at least one of;

an incremental induction technique, a classification technique, a clustering technique, an artificial intelligence technique, a machine learning technique, a statistical technique;

each decision model is capable of being updated in response to at least one of;

a multiplicative update technique, a Winnow technique, a weighted majority technique, an exponential technique;

each decision model is capable of being updated in response to a graphical model including at least one of;

a hidden Markov model, a Bayesian network model, a partially observable Markov decision process model, a neural network model.

21. A computer game as in claim 20, wherein updates occur substantially in real time while play of the computer game is ongoing.

22. A system as in claim 19, including

a learner member capable of constructing at least one of said behavior models in response to an action taken by one or more of those software agents;

whereby a first one of those software agents is capable of learning behavior in context from a second one of those software agents.

23. A system as in any of claims 19 or 22, wherein the simulation engine includes at least one of:

a self-learning mode including at least some of those behavior models and software agents having initial values, and reinforcing those behavior models and software agents which are successful according to an evaluator for the simulation engine;

a demonstration mode including at least some of those behavior models and software agents demonstrating their learning to an observer;

a real-time mode including substantially all of those behavior models and software agents being updated with each change in context;

a stochastic mode including introduction of random or pseudo-random values for at least some of those state variables.

24. A system as in any of claims 19 or 22, wherein the simulation engine defines a computer game including at least one player or non-player character, and wherein the learning includes at least one of:

a non-player character learning behavior from a player character;

a plurality of non-player characters learning behavior from a player character;

a plurality of non-player characters learning behavior from a plurality of player characters;

a plurality of non-player characters each learning behavior from a distinct one of a plurality of player characters;

a first non-player character learning behavior from a second non-player character;

a non-player character learning to produce similar behavior in context as another character;

a non-player character learning to produce opposite behavior in context as another character;

a non-player character learning to produce behavior in context friendly to another character;

a non-player character learning to produce behavior in context inimical to another character.

25. In a computer controlled system including a simulation engine having a set of state variables, and wherein a collection of possible values for at least some of those state variables defines a context, a method including steps of

defining a set of behavior models, each capable of receiving queries from the simulation engine and generating responses to those queries;

and

defining a set of software agents, each being responsive to one or more of those behavior models, and each capable of being updated in response to changes from a first context to a second context.

26. A method as in claim 25, including steps of

presenting a sequence of states, substantially each possible such state defining a context, the steps presenting including operating a set of software agents within a set of rules for the steps of presenting;

and

generating a response to a query for decision by at least one of a set of decision models;

wherein

at least one of the software agents is responsive to one or more decision models, and is capable of being updated in response to changes from a first context to a second context.

27. A method as in claim 26, wherein

the steps of presenting collectively include operating a simulation engine having a set of state variables, and having a set of rules describing permitted changes in value of those state variables, wherein substantially each collection of possible values for the set of state variables defines a context;

and

the set of decision models collectively include a set of behavior models, each capable of responding to a query from the simulation engine and capable of generating a response to that query.

28. A method as in either of claims 26 or 27, wherein the simulation engine includes a set of features, each either defined by a current context or associated with a set of information from outside the simulation engine.

29. A method as in either claims 26 or 27, including steps of constructing at least one of said behavior models in response to an action taken by one or more of those software agents;

whereby a first one of those software agents is capable of learning behavior in context from a second one of those software agents.

30. A method as in either of claims 26 or 27, wherein the simulation engine includes at least one of:

a self-learning mode including at least some of those behavior models and software agents having initial values, and reinforcing those behavior models and software agents which are successful according to an evaluator for the simulation engine;

a demonstration mode including at least some of those behavior models and software agents demonstrating their learning to an observer;

a real time mode including substantially all of those behavior models and software agents being updated with each change in context;

a stochastic mode including introduction of random or pseudo-random values for at least some of those state variables.

31. A method as in either of claims 26 or 27, wherein the simulation engine defines a computer game including at least one player or non-player character, and wherein the learning includes at least one of:

a non-player character learning behavior from a player character;

a plurality of non-player characters learning behavior from a player character;

a plurality of non-player characters learning behavior from a plurality of player characters;

a plurality of non-player characters each learning behavior from a distinct one of a plurality of player characters;

a first non-player character learning behavior from a second non-player character;

a non-player character learning to produce similar behavior in context as another character;

a non-player character learning to produce opposite behavior in context as another character;

a non-player character learning to produce behavior in context friendly to another character;

a non-player character learning to produce behavior in context inimical to another character.

32. A method as in either of claims 26 or 27, including steps of

in a computer game having at least one decision model, the decision model being capable of generating a response to a query for decision, generating a query for decision including at least one of:

selecting which action to take in a selected context, the selected context being a possibly empty context;

predicting a future event;

predicting what action another game agent will take in a selected context;

ranking a set of possibilities in an order according to a selected criterion;

selecting a result from a possible distribution thereof;

determining a probability distribution for a set of possible events;

determining a set of clusters of similar objects within a selected set;

providing a set of criteria by which determining a set of clusters of similar objects within a selected set can be performed;

selecting a set of relevant factors in making a game decision;

determining how certain or uncertain the decision model is regarding its response to a selected query for decision;

determining a set of relevant factors for retrieval to make the decision model more certain or less uncertain about its response to a selected query for decision;

determining a most common result from a possible distribution thereof;

determining a least common result from a possible distribution thereof;

providing an explanation of a reason for predicting a selected possible future action;

providing a sequence of actions to advance a game agent toward a selected goal.

33. A method as in either of claims 26 or 27, including steps of

in a computer game having at least one decision model, the decision model being capable of generating a response to a query for decision, generating a response to a query for decision including at least one of:

training one or more non-player characters in real time in response to actual play by a human user of one or more player characters, whereby those one or more non-player characters learn during play;

training a group or team of non-player characters in response to an individual player character, whereby that group or team of non-player characters learn the knowledge or style of that player character during play;

training one or more non-player characters in response to decisions made by each of a plurality of player characters in context, whereby those one or more non-player characters act in response to a statistical measure of the actions taken by those player characters;

training one or more non-player characters in response to a set of game results, wherein those game results are produced by at least one of;

one or more player characters, one or more non-player characters that are already trained, one or more non-player characters being trained.

34. A method as in either of claims 26 or 27, including steps of

in a computer game having at least one decision model, the decision model being capable of generating a response to a query for decision, generating a response to a query for decision including training one or more non-player characters in response to one or more player characters, to perform at least one of:

imitating that player character;

doing an opposite of that player character;

act favorably toward that player character;

act unfavorable toward that player character;

act orthogonally to that player character;

act in a manner that is a particular transformation of how that player character acts.

35. A method as in either of claims 26 or 27, including steps of

in a computer game having at least one decision model, the decision model being capable of generating a response to a query for decision, generating a response to a query for decision including training one or more non-player characters in response to a set of game results, wherein those game results are produced by at least one or more non-player characters that are already trained, one or more non-player characters being trained;

whereby no human user is required for training, whereby training of those one or more non-player characters is effectively unsupervised training.

36. A method as in either claims 26 or 27, including steps of

in a computer game having at least one decision model, the decision model being capable of generating a response to a query for decision, generating a response to a query for decision including training one or more non-player characters in response to a set of game results, wherein those game results are produced by at least one of one or more non-player characters or at least one of one or more player characters;

whereby changes in strategy by a human user are adapted to by the one or more non-player characters in response to those changes, whereby those one or more non-player characters effectively learn from collaboration or competition with human users.

37. A method as in either of claims 26 or 27, including steps of

in a computer game having at least one decision model, the decision model being capable of generating a response to a query for decision, generating a response to a query for decision including training one or more non-player characters in response to a set of game results, wherein those game results are produced by at least on of one or more non-player characters or at least one of one or more player characters;

wherein group actions by those one or more non-player characters are responsive to the knowledge and style of at least one human user.

38. A method as in claim 37, wherein those group actions include at least one of:

business actions, military actions, political actions, social actions, sports team actions.

39. A method as in either claims 26 or 27, including steps of

in a computer game having at least one decision model, the decision model being capable of generating a response to a query for decision, generating a response to a query for decision including training one of more non-player characters in response to a set of game results, wherein those game results are produced by at least one of one or more non-player characters or at least one of one or more player characters;

wherein actions by those one or more non-player characters are responsive for at least one human user, to at least one of;

demographic information, player history, player preferences, player skill, player style.

40. A method as in claim 39, including at least two human users, wherein actions by those one or more non-player characters are responsive for at least one pair of human users, to a comparison or interaction between that at least one pair of human users, of at least one for each human user of:

demographic information, player history, player preferences, player skill, player style.

41. A method as in either of claims 26 or 27, including steps of

in a computer game having at least one decision model, the decision model being capable of generating a response to a query for decision, generating a response to a query for decision including training one or more non-player characters in response to at least one of one or more non-player characters or at least one of one or more player characters;

wherein those trained one or more non-player characters are substantially able to negotiate with human users.

42. A method as in either of claims 26 or 27, including at least one of the following steps:

supporting train by playing, whereby activities by a player character while playing the game are used to train non-player characters;

supporting train by playing, whereby activities by a player character while playing the game are used to train non-player characters, whereby non-player characters can learn at least one of (1) actions a player character tends to take, (2) at least one context in which to apply those actions, (3) continuing learning over a time duration within the game;

supporting creating teams wherein individual members of the team are trained individually by a player using train by playing;

controlling or influencing actions of non-player-entities in a game, wherein those entities include at least one of non-player characters including followers, friends or enemies;

or active control elements of the virtual game;

controlling or influencing the actions of a group of followers that learn at least one of (1) actions a player character takes, (2) at least one context in which to apply those actions are taken in 2D and 3D tactical/strategic action and fighting games;

controlling or influencing entities that recognize millions of different contexts and behave appropriate according to how they have observed the player behaving;

controlling or influencing entities that can adapt and evolve their behavior on-the-fly and over time as behavior of the player character changes;

controlling or influencing entities that can learn tactical or high-level strategic play from player characters;

controlling or influencing the actions of teammates in sports games, wherein the sport might be a depiction of a known sport, or a sport with rules conducted for the video game;

controlling or influencing entities that learn quickly and for whom learning can continue indefinitely;

controlling or influencing entities that can learn individual skills or how to cooperate in large or small groups;

controlling or influencing entities during any one of (1) a single critical decision, (2) all the time, (3) some fraction of decisions therebetween;

creating behavior for entities that can be saved, restored, replayed or traded;

controlling or influencing entities that can learn to make tactical decisions including at least one of;

timing, spacing, approach, positioning and selection of opening moves and follow-up moves for attacks, blocks, and backing off;

target selection, including double-teaming;

direction and style of movement, where and when to dodge and flee;

selection of a level of aggression;

ordering and timing of decisions;

deciding to flee or fight;

controlling or influencing target decisions including at least one of;

aiming for the heart of a cluster;

aiming at stragglers;

ignoring mobs to attack a leader or vice-versa;

selecting which power-ups to try to obtain, selecting which crates to open or with what priority;

selecting which rooms to enter or with what priority, selecting which doors to try or with what priority;

controlling or influencing entities that initially at least one of (1) no knowledge, (2) very little knowledge;

(3) lots of knowledge, or (4) some degree of knowledge therebetween, and thereafter learn from player characters;

controlling or influencing at least one of (1) a single companion, (2) a core group of followers, (3) whole armies, or (4) anything therebetween, in response to at least one player character;

controlling or influencing entities in a single player mode or in head-to-head events that show off training and leadership skills;

controlling or influencing entities whose errors can be corrected by demonstration;

controlling or influencing entities, wherein some user interface element, or pre-defined condition, specifies to which group the training signal is applied and when;

controlling or influencing entities whose behavior can evolve over multiple scenarios or multiple games;

controlling or influencing entities with regard to type of organization or formation, including at least one of;

unit shape, when a unit chooses to engage enemies, when a unit chooses to flee enemies, whether a unit involves every soldier attacking individually or holding formation or coordinating attacks;

optionally controlling or influencing entities that can learn from the player character;

creating non-player entities that can explain their behavior;

creating non-player entities that can negotiate;

sharing trained characters, whereby later selection of a choice of avatars if possible for a selected encounter;

allowing a player to create avatars as opponents for other players to compete with;

allowing a non-player character to emulate behavior of an expert or a world-champion player character;

creating and evolving a knowledge base per player, wherein that knowledge base can be loaded for a selected encounter;

training a new player character by providing hints or indicators of what other play characters or scripts designed for non-player characters would do in a similar context.