U.S. Pat. No. 11,007,441

DETAILED DESCRIPTION

Disclosed herein is an algorithm for evolving game content which automatically evolves novel game content based on player behavior, as the game is played. Specifically, new content evolves based on player interaction with existing content. Application of this algorithm allows for games that generate their own content to satisfy players, which has the potential to significantly reduce the cost of content creation and to increase the replay value of games.

FIG. 1is a block diagram of a computer game100, which may be implemented on a general-purpose computer, a specialized game console, or any other computing device (e.g., mobile phone, personal digital assistant, media player, etc.). Game100includes game logic130, game world110, and evolutionary content generator120. Game world110includes the set of content items (e.g., levels, terrain, maps, models, textures, weapons, vehicles, etc.) which are available to interact with players during the game. In the example ofFIG. 1, game world110includes two types of content items—weapons and vehicles—and three instances of each. Evolutionary content generator120generates new content items and inserts the new content into game world110. Game logic130receives player inputs and processes these inputs to drive player interaction with game world110, resulting in game play.

FIGS. 2A-Cillustrate the evolution of content by evolutionary content generator120, according to some embodiments disclosed herein. During the game, players210interact with content items220that exist in world110. This interaction results in a content distribution230among players210. Thus, at any point in time, world110includes distributed content items230as well as content items240that are available for distribution to players210through their interaction with items220. Some non-limiting examples of how an item220is distributed to a player210include: a player picks up the object; a player buys the object; the player takes the object from another player; and the player is awarded the object for some action within the game. As play progresses, players210explore the game world110and discover new content that is generated by evolutionary content generator120and placed into the world110. As shown inFIG. 2B, the content distribution230changes as play progresses because some items are more popular than others: players210tend to keep content items with which they are satisfied, while discarding content items with which they are not satisfied in favor of newly discovered content. The interaction of users with content items affects the evolution of newly generated content contained within the undistributed content240as shown inFIG. 2C. Specifically, content items that players210are satisfied with become parents of new generations of content, while content that is widely disliked filters out of the game. As game play continues, additional generations are evolved. In this way, players210continually explore a succession of changing content in world110.

Thus, one embodiment of evolutionary content generator120can be described as: tracking popularity according to one or more users of at least a portion of a plurality of game content items available in a game world, where the game world is associated with the computer game; evolving an additional game content item based on the popularity of the tracked game content items, where the usage of each tracked game content item determines a reproduction availability of the tracked game content item; and inserting the additional game content item into the game world.

Another embodiment of evolutionary content generator120can be described as: tracking usage by one or more users of at least a portion of a plurality of game content items available in a game world, where the game world is associated with the computer game; selecting for reproduction a subset of the tracked game content items based on the respective usage, where the probability of selecting each of the tracked game content items for reproduction is proportional to the usage; reproducing using the selected subset of game content items to generate an additional game content item; and inserting the additional game content item into the game world; and inserting the additional game content items into the game world.

In some embodiments, a player210is allowed to collect different content items, and/or multiple instances of the same content items. That is, a player210may, at a particular point in game play, hold three weapons and one vehicle. In some of these embodiments, the total number of different items and/or total number of instances of the same item may be limited. That is, the player210may be limited to three offensive weapons and two defense mechanisms. In some embodiments, a player210is provided with information about the characteristics of a content item before that item is selected. In some embodiments, a player210is given a preview or demonstration of how the content item operates rather than simply being given information about the characteristics.

Thus, evolutionary content generator120directs evolution based on implicit information expressed by user interaction with particular items of content. In some embodiments, user interaction is captured in a fitness score for each item of content in game world110.

FIG. 3illustrates the use of a fitness score by evolutionary content generator120. In the example ofFIG. 3, game world110includes three items of content (310;320,330) and generator120tracks a corresponding fitness score (340,350,360) for each. Each fitness score340,350,360is computed based on player interaction with the respective item310,320,330. For example, if game play involves players choosing a weapon from a set of weapons available in world110, then one embodiment of generator120gives a higher score to a weapon that is chosen or used more often, or by more players, and gives a lower score to weapons that are not preferred by players. In another embodiment of generator120, lower scores are associated with items that are more preferred. Importantly, the fitness score is driven by normal player interaction with the game, and does not require specific player feedback in the form of a preference or grade for an item. Since scores are tracked on an item basis, the content generated in a multi-player game is not merely an average of all player preferences, but is instead unique content reproduced from individual items that are popular.

For some types of content items, an initial fitness score is assigned when the user selects the item, and the score increases while the user keeps the items (possibly up to a maximum value). For other types of items, an item's score increases as it is selected by more users. For still other types of items, an initial score is assigned and is then increased according to specific actions (e.g., score increases each time a weapon is fired)

Having explained how fitness is tracked, several different types of evolution will now be described. One embodiment of evolutionary content generator120breeds using items already in game world110to produce new generations of content. The content items that are chosen to be parents are selected based on fitness of the items. In some embodiments, the parents are chosen probabilistically, such that the chance of being chosen as a parent is proportional to the item's fitness.

An example of evolution from items already present in game world110is illustrated inFIG. 4. In this example, game world110includes items410,420,430, and440. Evolutionary content generator120selects items410,420,440for breeding based on fitness scores. As indicated by arrow450, item410breeds with item420to produce a next generation item460. As indicated by arrow470, item420also breeds with item440to produce next generation item480. The fitness score of item430does not qualify that item for breeding. Mutation and crossover may occur during reproduction, so that children may become more complex than their parents.

As can be seen inFIG. 4, after an initial round of breeding, game world110contains content items from the original generation (i.e.,410,420,440) as well as content items from a new generation (i.e.,460,480). The example shown inFIG. 4uses “sexual” reproduction (i.e., multiple parents, though not limited to two), but other embodiments use “asexual” reproduction (i.e., only one parent), while still others used combinations of the two. All forms of reproduction involve some form of mutation or crossover of characteristics, which distinguishes reproduction from cloning.

Thus, the process used by the embodiment of content generator120shown inFIGS. 3 and 4includes: assigning fitness scores to multiple items of game content based on player usage of the respective items; selecting a set of the items, based on the fitness scores; and adding new items of game content into the game world by spawning using the selected items as parents.

Another embodiment of evolutionary content generator120introduces new content into game world110by cloning from a separate predefined content pool rather than being reproduced from parents that already reside in the world. An example of evolution by cloning is illustrated inFIG. 5. In this example, the items residing in game world110initially include items510,520,530, and540, while a predefined pool550(outside of world110) includes items560,570, and580. Evolutionary content generator120then evolves the content by cloning item560to produce item560-1and places item560-1into the world110. Generator120also clones item580-1and places items580-1into the world. In some embodiments, the selection of items for cloning is random.

In some embodiments, designers of the game initially select items for predefined pool550. Some embodiments of evolutionary content generator120receive content descriptions from game designers and create the predefined pool550from these descriptions.

In some embodiments, the items residing in predefined pool550are items with desirable characteristics and are thus expected to be preferred by users. For example, if the items are weapons, then weapons in the predefined pool have characteristics like high accuracy, long range, high stopping power, etc. As another example, if the items are vehicles, then vehicles in the predefined pool have characteristics like high maximum speed, high acceleration, good cornering, etc.

Cloning from predefined pool550ensures that diversity is not lost and that good types of content from the past (i.e., those that users liked) might reappear. Additionally, cloning ensures an initial seed of good content when the game first starts and players' preferences are unknown.

In some games, players210are provided content items with which to start play. Some embodiments of evolutionary content generator120provide players210with randomized content at the start. Other embodiments of evolutionary content generator120start the game by distributing items to players210from a starter pool of content items. Because all players begin the game with it, content in the starter pool content does not contribute to evolution. Therefore, content in the starter pool is not actually used as a parent in the reproduction process. However, the fitness of starter pool content items does change as users interact with these items. Therefore, it is possible for a starter pool item to be selected during evolution for reproduction. In such cases, an item is randomly selected instead from predefined pool550, and this item from predefined pool550is spawned into the game world.

Some embodiments of evolutionary content generator120utilize a recently-used pool which includes content items that were recently possessed by players220who subsequently left game world110. This recently-used pool queue provides a reasonable number of content items which can be used as parents for breeding even when a small number of players is participating in the game.

Some embodiments of evolutionary content generator120utilize an archive pool which includes all content that achieves a particular level of fitness during game play. When such content reaches this level of fitness (which varies among types of games), it is automatically saved to the archive pool.

Some embodiments of evolutionary content generator120combines reproduction from parents residing in game world110with cloning from predefined pool550. In some of these embodiments, the probability of new content being introduced into game world110through reproduction is PRand the probability of new content being introduced from predefined pool550is PNE. These values are typically set by the game designer.

Creation and insertion of new content items into game world110may be triggered by various user actions. For example, destruction of an enemy, or a group of enemies, or enemies at a particular location may trigger insertion of a new weapon. Triggers for creation and insertion of new content items into game world110may be related to time, e.g., may occur at predefined intervals, at random times, etc. Triggers for creation and insertion of new content items into game world110may be related to a number of items, e.g., to maintain a predefined number of items not yet distributed to players210, to maintain a predefined number of total items in world110, to maintain a predefined number of items of each type, etc.

In some embodiments, a new content item is spawned into the game world by one of multiple methods, with the particular method chosen being based on a fixed probability. Two of the methods were discussed above: reproduction from the current content pool existing in the game world, with random selection of parent(s); and cloning from predefined pool550. A third method is random generation using a variety of item characteristics (e.g., weapon range, weapon projectile size, weapon projectile rate, etc.)

One example of the probabilities used to select these methods of item generation are as follows: random=10%; predefined pool=10%; reproduction=80%. if a starter item (i.e., from the starter pool) is selected for reproduction, then an item from predefined pool550is cloned instead. Higher fitness items have a higher chance of producing offspring, thereby enabling players to directly affect the course of evolution.

According to the content generation methods disclosed herein, the population size (i.e. those items that are eligible at any given time to reproduce) is variable and depends entirely on the number of users in the system. That is, when more users play the game, more items receive a score and are thus eligible for being chosen as parents.

Content items generated according to the methods disclosed herein are not immediately eligible to reproduce. Instead, these items are in a special temporary state (i.e., placed somewhere in game world), in which the item may join the population only if a user chooses to acquire it or interact with it.

According to the content generation methods disclosed herein, the determination as to which items leave the population (i.e., are no longer eligible for reproduction) is made by users, by simply discarding items, rather than by fitness scores.

According to the content generation methods disclosed herein, users do not explicitly communicate to the system which content they like. Instead, the preferred content is deduced by the system implicitly from natural human behavior. That is, users do not need to know that they are interacting with an evolutionary algorithm yet evolution still works anyway.

According to the content generation methods disclosed herein, the steps of the method are asynchronous. That is, players may cause content to join the population or be eliminated at any time.

In some embodiments, each game content item is represented by an artificial neural network (ANN) and reproduction as discussed inFIG. 4is performed according to the NeuroEvolution of Augmenting Topologies (NEAT) algorithm. NEAT begins evolution with a population of small, simple networks and complexities the network topology into diverse species over generations, leading to increasingly sophisticated behavior. The NEAT algorithm is further described in “Evolving neural networks through augmenting topologies”, K. O. Stanley and R. Mikkulainen, Evolutionary Computation, vol. 10, pp. 99-127, 2002, the entirety of which is incorporated herein by reference.

To keep track of which gene is which while new genes are added, NEAT uniquely assigns a historical marking to each new structural component. During crossover, NEAT aligns genes with the same historical markings, efficiently producing meaningful offspring. Traditionally, speciation in NEAT protects new structural innovations by reducing competition between differing structures and network complexities. However, in the applications described herein, the usual speciation procedure in NEAT is unnecessary because a human performs selection rather than an automated process.

The process of complexification, which resembles how genes are added over the course of natural evolution, allows NEAT to establish high-level features early in evolution and then later elaborate on them. For evolving content, complexification means that content can become more elaborate and intricate over generations.

In some embodiments, each game content item is represented by a compositional pattern-producing network (CPPN). CPPNs are a variation of artificial neural networks (ANNs) that differ in their set of activation functions and how they are applied. While ANNs often contain only sigmoid or Gaussian activation functions, CPPNs can include both such functions and many others. The choice of CPPN functions can be biased toward specific patterns or regularities. For example, periodic functions such as sine produce segmented patterns with repetitions, while symmetric functions such as Gaussian produce symmetric patterns. Linear functions can be employed to produce patterns with straight lines. In this way, CPPN-based systems can be biased toward desired types of patterns by carefully selecting the set of available activation functions.

Having described general principles, application of those principles to an example will now be described: the Galactic Arms Race (GAR) game. The goal of GAR is to pilot a space ship to defeat enemies, gain experience, earn money, and most importantly, to find advantageous new weapons that are automatically generated by the evolutionary algorithm described earlier. That is, in GAR the content items which undergo evolution are weapons.

GAR has a single-player mode, in which evolution is directed by the actions of a single player battling aliens. The aliens are controlled by scripted steering behaviors rather than players.

In one embodiment described herein, each player weapon is a particle system. Particle systems are usually defined by (1) a set of points in space and (2) a set of rules guiding their behavior and appearance, e.g. velocity, color, size, shape, transparency, rotation, etc. However, such rule sets can be complex and are usually hand-coded. In GAR, the player weapon contains a single evolved CPPN. For every frame of animation, each particle issued from the weapon inputs its current position relative to the ship (px, pz) and distance from the ship (dc) into the CPPN. There are two, rather than three, spatial inputs because the game is entirely situated on the y=0 plane. The CPPN is activated and outputs the particle's velocity (vx, vz) and color (r, g, b) for that animation frame.

Weapon fitness in GAR is automatically calculated based on player usage statistics, gathered as follows. Players possess up to N weapons at one time in an arsenal. When a player fires a weapon, that weapon (which is a unique member of the population) gains fitness at a constant rate and the other weapons in that player's arsenal lose fitness at the same rate. In some embodiments, the minimum fitness is 1 and there is no maximum value. This sort of fitness decay mechanism for unused weapons emphasizes emerging new weapon trends.

In GAR, one trigger even for spawning a new weapon is destruction of an enemy base or an enemy commander. As described earlier, methods for spawning a new weapon include reproduction within the current population present in game world110and cloning from predefined pool550, with a probabilistic method based on weapon fitness randomly deciding which weapon(s) reproduces.

In single-player GAR, the weapon population includes only the weapons the single player currently holds in his arsenal. In multi-player GAR, the weapon population includes the weapons currently held by all players. Thus single-player evolution is to some extent greedy; however, it is not equivalent to a normal evolutionary algorithm with a population of N because the player encounters a significant number of weapon previews in addition to the weapons in the ship's current arsenal. Therefore, the player is in effect judging such previews by taking them or not.

When the game begins, players have no history of weapon preference. One possible policy is to initially give players N random weapons. However, such randomization could cause new players to receive N undesirable weapons. A better solution is for players to begin the game with a predefined set of starter weapons. The starter weapons are viable: shoot only in a straight line, and not eligible to reproduce during evolution. Thus, new players are guaranteed to begin with viable weapons.

Because starter weapons cannot reproduce and players begin the game with only starter weapons, a method is needed to start evolution. For this purpose, predefined pool550includes a diverse collection of acceptable weapons generated (in some cases, evolved) by the game developers. If the weapon selected for reproduction by the evolutionary algorithm is a starter weapon (e.g., selected because the player fires that starter weapon often), the evolutionary process clones a random weapon from predefined pool550into game world110.

One advantage of predefined pool550is that it provides a jump start to evolution at the beginning of the game. Thus, developers can influence what weapons players will see early in the game. Predefined pool550can also serve as a hall of fame, to which popular weapons are retired, possibly reappearing later in the game.

In one embodiment of GAR, the content items are particle system weapons, and each player weapon contains a single evolved CPPN. In every frame of animation during game play, each particle issued from the weapon inputs its current position relative to the ship (px, pz) and distance from the ship (dc) into the CPPN. Two spatial inputs are used when the game is two-dimensional, i.e., entirely situated on the y=0 plane. The CPPN is activated and outputs the particle's velocity (vx, vz) and color (r, g, b) for that animation frame. Representing particle velocity and color in this manner produces a wide of variety of vivid patterns. Because CPPNs are a superset of ANNs, which can approximate any function, particle weapons in GAR can theoretically evolve any conceivable pattern.

Calculation of fitness based on player usage may account for different influences. As one example, certain weapons, by their nature, require more shots to be effective (e.g. wall guns for blocking incoming projectiles). As another example, players that participate in the game more often might disproportionately influence evolution (i.e. by firing their weapons more often). To address these two influences, some embodiments of the evolutionary processed disclosed herein calculate fitness as follows. When a player fires a weapon, that weapon (which is a unique member of the population) gains fitness at a constant rate and the other weapons in that player's arsenal lose fitness at the same rate. This fitness decay mechanism for unused weapons emphasizes emerging new weapon trends and ensures that weapons that require more firing do not come to dominate. Furthermore, the minimum fitness is 1 and the maximum fitness is 1,000, which means that older players do not create a disproportionate effect.

FIG. 6is a hardware block diagram of one embodiment of a computer600implementing the game100ofFIG. 1. The computer contains a number of components that are familiar to a person of ordinary skill in the art, including a processor610, memory620, non-volatile storage630(e.g., hard disk, flash RAM, flash ROM, EEPROM, etc.), a display640, and one or more input devices650. The components are coupled via one or more buses660. The input devices can include, but are not limited to: keyboard, mouse, touch pad, touch screen, motion-sensitive input device, gesture-sensitive input device, inertial input device, gyroscopic input device, joystick, game controller, etc. Omitted fromFIG. 6are a number of conventional components, known to those skilled in the art, that are not necessary to explain the operation of the computer.

The game100can be implemented by specialized hardware logic, software (i.e., instructions executing on a processor), or a combination thereof. Hardware embodiments include (but are not limited to) a programmable logic device (PLD), programmable gate array (PGA), field programmable gate array (FPGA), an application-specific integrated circuit (ASIC), a system on chip (SoC), and a system in package (SiP). In a software embodiment, memory620stores various software components which are executed by processor610, for example, an operating system620and game100.

These executable components can be embodied in any computer-readable medium for use by any processor which fetches and executes instructions. In the context of this disclosure, a “computer-readable medium” can be any means that can contain or store the program for use by, or in connection with, the processor. The computer readable medium can be based on electronic, magnetic, optical, electromagnetic, or semiconductor technology.

Specific examples of a computer-readable medium using electronic technology would include (but are not limited to) the following: a random access memory (RAM); a read-only memory (ROM); an erasable programmable read-only memory (EPROM or Flash memory). A specific example using magnetic technology includes (but is not limited to) a portable computer diskette. Specific examples using optical technology include (but are not limited to) a portable compact disk read-only memory (CD-ROM) and a digital video disc read-only memory (DVD-ROM).

The foregoing description has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Obvious modifications or variations are possible in light of the above teachings. The embodiments discussed, however, were chosen and described to illustrate the principles of the invention and its practical application to thereby enable one of ordinary skill in the art to utilize the invention in various embodiments and with various modifications as are suited to the particular use contemplated. All such modifications and variation are within the scope of the invention as determined by the appended claims when interpreted in accordance with the breadth to which they are fairly and legally entitled.