**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 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

- 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

- 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)

- 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.**