6 replies to this topic

[snarles2]

Introduction

Games like Dwarf Fortress have had great success in employing algorithms to generate much of the game content. I would like to push the technique of procedural generation to the next level--having algorithms which design content like characters, weapons, quests, etc. and perhaps even some of the rules of the game. Yet a naive attempt at having a game that is extensively randomly generated will frequently result in game worlds which are seriously unbalanced or unplayable. One solution is to carefully structure the random generation scheme to ensure that the product will have good gameplay properties. However, I am interested in how artificial intelligence-driven "automated playtesting" can be used to build up an interesting game even given a relatively unrestricted randomization scheme.

Iterative design strategy

An iterative scheme is natural for procedural design of this kind. One starts with a small design which is made almost completely at random, removes strategically superfluous elements, and then starts adding elements selected to have maximal impact on the depth of gameplay.

Computational Issues

It can be expected that this type of extreme procedural design would require immense amounts of computing time, since balancing the game might require the simulated player to play the game literally billions of times. A simulated player might require a million playthroughs of a fixed design simply to learn the strategies. But once the game is rebalanced, or new content is added, the process will have to start anew. Therefore, even if the algorithmic issues are solved, we may have to depend on Moore's law to be able to hope that this kind of game will one day become practically viable.

The experiment: "Starship"

Therefore, for a proof-of-concept, it is important to start small, and design the game to be simple enough to be "solvable" for AI yet to still possess some strategic depth for a human player.

The game I propose, "Starship" is as follows:

• Turn-based, single player, menu-based
• The objective is to amass as much gold as possible in a limited number of turns
• Each turn, the player can choose to fight one enemy types, chosen from a list of enemy types
• The player earns gold from winning fights, but must spend gold to repair damage from fights
• In between turns, the player can use gold to upgrade the ship

Combat details

• Combat is based on four attributes: HP, ATK, DEF, and SPD
• Combat consists of alternating rounds of the player and enemy exchanging attacks
• The combatant which higher SPD moves first (random tiebreaker)
• If the attacker's SPD is greater or equal than the target's SPD, then the attack has a guaranteed hit, and there is an additional chance of critical hit, which is (attacker's SPD-target's SPD)/(target's SPD)
• If the attacker's SPD is lower than the target's SPD, then the chance of hitting is (attacker's SPD)/(target's SPD), with no chance of critical hit
• A normal hit does damage equal to (attacker's ATK-target's DEF), or zero if the attacker has less ATK than the target's DEF
• A critical hit does damage equal to (2 times attacker's ATK-target's DEF), or zero if the attacker has less ATK than half of the target's DEF
• Combat ends when one combatant is reduced to zero HP (the minimum amount), and the survivor is the winner
• There is also a combat round limit, at which point the combat ends and neither combatant

Shop/gold details

• You win a set amount of gold from each enemy type
• It costs 1 gold to repair 1 HP; this happens automatically
• If your ship has X maximum HP, it costs X gold to increase the maximum HP by 1
• The same applies to the other three attributes of the ship: ATK, DEF, and SPD
• If you have less gold than you need to fully repair your ship, you lose the game

Basic game strategy

• The strategy in this game consists of finding the optimal way to build your ship, and which enemies to farm
• Some builds are stronger against certain enemies
• You may be able to kill a high gold-granting enemy, but because of the damage taken, it may be more profitable to farm a weaker enemy which gives less gold
• At some point, you may want to stop upgrading your ship and simply collect gold. But initially, you would spend as much gold as possible on upgrades (saving enough for repairs, of course)

Additional strategic elements

• If the basic gameplay is insufficiently deep, more elements can be incorporated
• Different characters (ships) which can be chosen at the start, with differing upgrade and repair costs
• Addition of "boss" enemies which grant one-time rewards in the form of gold, ship upgrades, or unlocking of more enemy types. For further depth, the specific type of reward may be chosen
• "Buffs"--temporary stat increases (or other effects) which last a number of turns, bought with gold or obtained as rewards for defeating certain enemies

Procedural Design Goals

The goal in the procedural design of "Starship" is to design the enemies so that the optimal strategy of progressing through the game is not completely obvious. For this to happen, one requirement is that two or more distinct build strategies which are close in estimated value. Yet, one easy way to satisfy this requirement is to create two mutually distinct paths of enemies which force the player to specialize in one direction or another, which doesn't actually produce interesting gameplay. Thus we add an additional requirement that, from a graph-theoretic perspective, if enemies are nodes linked by the existence of a strong farming strategy utilizing both of them, that the set of all enemies should have weak clusters, but should not be completely separable into multiple components.

AI implementation

The simulated player in this game simply consists of an optimization algorithm to find a good build/farm strategy. Obviously, there needs to be a function for evaluating the effectiveness of a build/farm strategy. While the final measure of effectiveness may be gold gained, in the beginning stages of the game, the amount of gold is a poor measure of progress since all the gold should be being spent on upgrades, anyways. So for evaluating early-game strategies, the total amount of gold spent on upgrades (which are effectively "experience points") is a better measure of the effectiveness of a build/farm strategy. When an optimal experience-gaining strategy is identified, optimizing the final score (in terms of gold) is simply a matter of identifying the best point to stop upgrading.

A fully specified build/farm strategy would consist of which enemies to visit each turn and which turns to buy each upgrade. But given the simplicity of the game, it probably makes little difference to represent a build as simply a sequence of "target" builds to attain, leaving the intermediate steps to be approximated by linear interpolation by the evaluation function. Given a build order, the optimal farming strategy for that particular build order follows, as a matter of determining which enemy is the most profitable in terms of gold gained minus expenses incurred by repairs.

Still, the space of possible build orders is vast. Holding the total cost fixed, a build has three degrees of freedom; this space can be reasonably discretized into anywhere from 12 to 100 different configurations. Yet, a build order containing multiple builds increases the space to be searched exponentially. Finding a truly optimal build is therefore difficult; however, if one is willing to settle for slightly less, a "greedy" approach of building up a build order piece-by-piece is quite feasible; and indeed, has great synergy with an iterative design strategy.

Project Code

I am currently using R (www.cran.org) for this project simply because I have the most experience with the language, and because of the wealth of mathematical and plotting functions publicly available for the platform. I finished running a test to check that the combat system was sufficiently deep. Now working on the implementation of the evaluation function for build orders.

Edited by snarles2, 21 June 2012 - 06:59 AM.

[IADaveMark]

Have you looked at any/all of the existing work in procedural generation of worlds, units, gameplay, etc.?

[snarles2]

Just started reading the literature. I learned that the term for what I'm trying to do is http://pcg.wikidot.com/pcg-algorithm:automatic-game-design

[snarles2]

Solving Resource Conversion Problems

Summary:
In the interest of obtaining a useful tool for designing "Starship", we consider how it might be possible to "solve" a strategic role-playing game by using a simplified representation of such a game, as a "resource conversion problem."

Section 1. What is a strategic role-playing game?

In role-playing games (RPGs), the player-controlled character explores the world for the purpose of becoming strong enough to complete various challenges. These challenges, which may include defeating enemies, farming items, beating mini-games and (in multiplayer RPGs) defeating other players often provide rewards: additional power-ups for the player character which help surmount future challenges. Most role-playing games are developed primarily for the purpose of exploring a lavish fantasy setting complete with multiple story arcs.

However, a number of role-playing games also offer enhanced replay value even for players who have already experienced all of the content the game has to offer, due to the existence of additional competitive challenges specified by the creators of the game or the players themselves. For multi-player games, a popular challenge is player versus player (PvP) combat. For single player games, challenges include "challenge paths": completion of the game under severe restrictions, and also "speed runs": completion of the game in the lowest amount of time (for real-time games) or lowest number of turns.

In popular RPGs, high-level PvP play can effectively be considered seperate from the main game. The process of acquiring PvP-relevant tools requires RPG gameplay, but usually of the less strategic variety. Thus the "interesting part" of the game belongs more to the strategy game genre than the RPG genre.

In contrast, path challenges and speed runs, which are generally single-player challenges, often depend on intimate knowledge of the quest structure and detailed statistics of relevant game content. Therefore we find it appropriate to use the term "strategic RPG" to describe RPGs with deep speed run or challange path play.

Another variant of RPG with similarly deep single-player gameplay is the "puzzle RPG", characterized by abscence of chance elements. One example of such a game is Tower of the Sorcerer (freeware). While such games can be extremely skill-testing, their deterministic nature and severe difficulty often mean that there exists very limited number of strategies for beating the game--and indeed, this is often the intention of the creator. As such, in common with other puzzle games, such deterministic RPGs reward precise thinking. RPGs with chance elements, on the other hand, demand less precision from the player, but on the other hand may reward adaptability and intuitive grasp of strategy. Thus, from the perspective of "tactical" versus "strategic" thinking, it is appropriate to stipulate that "strategic RPG" refer specifically to RPGs with deep gameplay but also significant chance elements.

Section 2. Strategic RPG games as resource conversion problems

A general element common to all strategic RPGs is a set of areas from which the player can obtain needed experience points (EXP), money, and loot; stores and other means for converting one type of resource (money, items) into another (health restoration, items, unlocked abilities); and obstacles which must be surpassed to obtain these resources (enemies, bosses.) Taking an abstract point of view, the game consists of a number of devices for converting certain (possibly random) amounts of certain resources (time/turns, money, health) into certain (possibly random) amounts of other resources (experience points, items, money, quest progress).

However, in addition, the outputs of these resource-conversion-devices may be conditional on how many resources of each type the player currently possesses. In some cases, such as combat, these conditions can be complex. Whether a combat returns an output of money and EXP (a "win") depends on whether the player posseses the combat attributes necessary for deating the enemy. But there may be many different configurations of combat statistics which allow a player to defeat a certain enemy: for example: medium health and high attack power, OR high health and medium attack power. Thus the resource requirement for defeating an enemy may take the form of a multidimensional lower bound on player attributes. In rare cases, output conditions may also impose multidimensional upper bounds. For example, in certain versions of the Kingdom of Loathing from 2006-2007, it was possible for the player to "milk" enemies for resources; however, this process required the enemy to be able to hit the player. Therefore a device representing milking a certain enemy would require an upper bound on the player's dodging capability.

Formally, then, we define such a "resource conversion problem" as follows. One has an initial collection of resources R. The goal is to convert the initial collection of resources to obtain a "win condition" resource. There exist a number of devices D₁(R ), D₂(R ), ... which transform R to a new collection of resources R'. The problem is to find a way to compose a sequence of finite number of these device functions (possibly with repeats) to transform R into a pool of resources R' with at least one "win condition" resource.
In the case of real-time games, one can specify the devices to also have a positive, real-valued "duration" argument t, so that the devices is written D(R,t). The argument t could, for example, represents the duration of time spent in a particular area. Similarly, one could also specify that some resources (like time) exist in continuous-valued quantities. Computationally then, it would make sense to represent the pool of resources using a real-valued vector.

Section 3 (technical). Solving simple resource conversion problems

The general problem of solving a resource-conversion problem is certainly NP-hard, since the travelling salesman problem can be represented as a resource acquisition problem. But perhaps some restricted class of problems could be have efficiently computable solutions.

(Condition 1.) Firstly, we work in the continuous (or "real time") case to avoid difficulties associated with discrete optimization, and also require all devices to be deterministic. Two special classes of resources must exist: a TIME resource and a WIN resource. A solution consists of a sequence of conversions which results in having 1 or more quantities of WIN. All devices must use a duration argument, D(R,t), and using a device must increase TIME by that exact value, t. For convenience, we consider TIME separately from the rest of the resources, R. Thus, the complete resource state is a pair (R, TIME).

(Condition 2.) We also impose the condition of monotonicity, which stipulates two properties. (1) "You can only gain": for all devices D, D(R,t) >= R. (2) More is always better: for all devices D and for all resource vectors R, Q with R >= Q, we have D(R,t) >= D(Q,t). [Notation explanation: >= means greater-or-equal-to. For vectors R, Q, we say that R >= Q if and only if every component of R is greater or equal to Q. If I(x) and J(x) are vector valued functions, we say I <= J if and only if I(x) <= J(x) for every valid argument x. ]

Note that monotonic problems are easy to solve: whenever the problem is solvable, an infinite sequence of random device usages with random durations constitutes a solution. More interesting is the question of finding the "fastest path": a solution with an optimally minimal final value for TIME. We impose another condition to increase the feasibility of finding the fastest path.

(Condition 3.) We require every device to be expressible as D(R,t)=I(R )*V*t, where I is an indicator function (that is, it only takes values 1 or 0), and V represents a constant resource gain per time. If the devices are D₁, D₂,..., we write the respective indicator functions are I₁, I₂, ... and similarly, the respective resource gain rates are V₁, V₂,... And, we require the indicator functions to be "timeless" in the sense that there is no dependence on the TIME resource.

Under this last condition, each device has a "minimal usage" requirement represented by its indicator function. It never makes sense to use a device when you fail meet its minimal requirements, since you'll gain nothing for the time spent. Provided you follow this rule, it follows that you never need to use the same device more than once. If you use device 1 for duration t, use some other devices, and then use device 1 again for duration t', you gain a total of V₁ * (t+t') resource from device 1. You get the same gain by using used device 1 for duration t+t' in the first place--except at an earlier point in time, which can only help due to monotonicity (condition 2.)

Given an ordering, we consider the fastest path obtainable by using those devices in order. For convenience's sake, we append an additional device to the end of the list, which requires 1 WIN. Then the fastest path is simply the fastest path for meeting the requirements of the devices in order. One suspects that an efficient method exists in the operations research literature for doing this. But, it will still be necessary to search through a number of orderings exponential in the number of devices.

This may be alleviated by an additional condition of "sparsity."

(Condition 4.) We require that the devices D₁,D₂,... must satisfy a "k-sparse class" condition. That is, there must exist a partitioning of the devices (and corresponding indicator functions and resource gain rates) into n device classes numbered 1, 2, ...,n such that each class contains at most k devices, and so that whenever indicator I is of a lower device class than indicator J, then I < J; and for every resource gain rate V, in any higher device class there is a resource gain rate W so that V < W. By assumption, we can find monotonic indicator functions K₁, K₂, ... such that K_i(R ) > max I(R ) for indicator I in class i for for which K_i( R )< I( R ) for indicator J in class i+1; it follows that K₁ < K₂ < .... Define the psuedocone of K_i as the set of minimal R for which K_i(R )=1 (where R is minimal in the sense that Q < R implies K_i(Q)=0).

Using the cones of K₁, K₂, ..., K_n we can define a build order. If n is the number of sets S₁,...,S_n, then a build order consists of the n-tuple of points R₁,...,R_n, where each R_i lies on the psuedocone of K_i. It follows from the definition that R₁ < R₂ < ... < R_n.

A build order determines a solution path in the following piecewise manner. First, determine the fastest path starting from the initial vector which will lead to a point R' > R₁. Determining this path segment is "easy" since only the devices in the first device class are relevant to finding this path. From R', find the fastest path segment which will lead to R'' > R₂. For the second path segment, only the devices in the first and second class need be considered. In general, for determining the ith path segment, at most 2k devices need be considered. One stops early if the win condition is reached. Otherwise, if at end of the nth segment the win condition is not yet reached, determination of the optimal path to winning again only involves at most k devices. Thus, the computational cost of each path segment is exponential in k; for a total cost of at most O((n+1)e^k) for a fixed build order.

The key property of build orders is this: there must exist a build order which leads to the optimal solution path. After all, the resource vector of the solution path must intersect each cone of K₁, ..., K_n at some point in TIME. Let R₁ be the resource vector at the earliest time that the psuedocone of K₁ is reached, and define R₂, ..., R_n in the same way. Then, it logically follows that the optimal solution path is the solution path determined by the build order R₁, ..., R_n, because to assume otherwise implies the existence of an even faster path determined by R₁,..., R_n.

Therefore, finding the optimal solution path is a matter of searching the space of all possible (R₁,...,R_n), which can be done using nonlinear optimization techniques such as simulated annealing, which are roughly speaking, of complexity exponential in the dimensionality, n. As a result, the complexity is exponential in (n+k), which is somewhat better than the non-sparse case, when the complexity can be exponential in (nk).

Section 4 (speculative, technical). Solving stochastic resource conversion problems

to be continued

Edited by snarles2, 23 June 2012 - 07:44 AM.

[IADaveMark]

Perhaps this is better suited to a blog or a journal? Or an academic paper? Just seems kind of odd here.

[snarles2]

@IADaveMark: I am new to the forums, so I didn't know what kind of audience I would find here. If there is no interest in discussing my posts then perhaps I will save any additional material for an arXiv paper.

[IADaveMark]

It's just that I can't imagine that there is much to "discuss". You are honestly writing a technical paper here based on premises and theories that you, by your own admission, have just started looking into existing work on. If you had come to use asking for material on the existing work, there would have been answers. If you had come to us asking for its usefulness in games, there would have been discussion. Instead, you just started writing massive blobs of text which isn't very conducive to public scrutiny or commentary. *shrug*

On a simply procedural note, I would recommend that you look into the work others before you write your own. That tends to keep from wheel re-invention.