Often we invent games by taking an existing game that works and adding a twist to it, or changing some aspect of its behaviour or theme to something different. But how would we create a game from nothing, without using an existing game as a framework? In particular, how do we make the game complex enough that it’s not trivially ‘solved’? (Set aside any game where the physical skill aspect is a significant component, or games with few or no choices where strategy is typically not intended to be a factor such as Candyland or Snakes and Ladders.) I find this a very difficult problem, but to make a start on it requires some appreciation of what makes a game interestingly complex in the first place, and the tools we typically use to create this complexity.

Generally it would seem that most games we play can be described using the extensive form notation from game theory. It’s not as intuitive a representation for individual or simultaneous decisions as normal form notation is, but extensive form captures the important notion of each move opening up a new game state and new possibilities. For example, in Chess there is a single starting state, but that branches out to 20 possible successor states, and from there, the tree branches further to 400 states, and so on. I would suggest that the complexity of the game in terms of how easy it is to ‘solve’ it or to come up with the best strategy is closely correlated with a player’s ability to understand this abstract tree of game states. If “a game is a series of interesting choices” as Sid Meier has said, it’s the player’s ability to understand the ramifications of those choices that matter, which is to say that they need to be able to predict to a certain degree the effect that they will have on the tree of game states. If the choices are too easy to make, they’re not interesting, and if you can’t see that some choices are clearly better than others, again it is uninteresting.

With that in mind, it seems that we embody this essential complexity in our games in a small number of ways:

• A combinatorial explosion of discrete state spaces. As noted above, the game state tree for Chess has 400 possible positions on turn 2, and a branching factor of of about 35 on average for successive moves, making an exhaustive study of the possibilities impractical. Therefore you have to plan more generally, making an estimate of which moves are good and which ones are bad and deciding which part of the tree to look at and which ones not to. The high branching factor means that even Chess computers need to do this via something like alpha-beta pruning. A common way in which we can create this large number of possible states while keeping the game easy to understand is to use an abstract game board, as in Chess. A 2D grid gives you an easier way to describe and reason about the state changes while keeping the quantity of options high. Compare the rule “Rooks can move vertically or horizontally as many squares as you want without jumping over another piece” with “A rook at position 1 can move to positions 2, 3, 4, 5, 6, 7, 8, 9, 17, 25, 33, 41, 49, 57. However it cannot move to position 3 if position 2 is occupied, nor position 4 if positions 2 or 3 are occupied, nor… (etc)” Being able to bring prior knowledge of Cartesian coordinates and the notion of adjacency and straight lines helps simplify many possible state transitions into a much simpler rule.
• Hidden information. Typically this takes the form of a player’s hand of cards, or the fog-of-war in a real time strategy game, or even the act of forcing players to move simultaneously and thus having to estimate what the other person will do. This doesn’t make the state tree branch out any further, but it does make it much harder for a player to know which branches can be safely ignored. Compare the choice to leave your Queen under attack by a Pawn in Chess against advancing one of your middle-ranked pieces into enemy territory in Stratego. In Chess you will almost always benefit from taking a Queen with a pawn unless moving the pawn puts you at risk, which is quite easy to check for, so it’s reasonable to assume that is the move you should examine first and in most detail, making the decision quite easy. In Stratego however you simply don’t know whether it’s worth attacking that piece unless you have managed to build up some information about it, so you will need to consider all your other potential moves in roughly equal detail.
• Random factors. Randomness is like adding a 3rd player to the mix – whereas you can predict the actions of the 2nd player (your opponent) as he will always make the best move that he can given the limits of his capabilities, the 3rd player (luck) will play unpredictably, increasing the number of possibilities you must consider, in a similar way to the hidden information above. Indeed, randomness is really just a subset of hidden information, but it’s worth drawing a distinction between the two because hidden information can be potentially knowable whereas random factors cannot. (Though keep in mind the middle ground, eg. of a shuffled deck of cards – towards the end of the game it becomes more deterministic.) Some people disparage random factors as bringing ‘luck’ into the game but really it’s just about risk management. For example, Civilization would be a much less interesting game if you knew that your Phalanx unit would always defeat an attacking Militia unit. Instead you have to balance the probabilities out. You have 66% chance of beating one, 44% of beating two in a row, 30% of beating three, so how many Phalanxes do you need to defend against 3 or 4 Barbarians, given that it’s mathematically impossible to mount a perfect defence? This poses an interesting dilemma for players which again forces them to consider a wider range of options as there is no obvious solution. Greg Costikyan has a great presentation here which shows the different benefits a random factor can bring to a game and it’s well worth a read.
• Continuous state space. Games that utilise physics engines and real-world simulations exploit this to create a wide range of possible situations from a simple set of mechanics. Arguably this is the most popular method used by games today to introduce elements of strategy and tactics to what are otherwise computer-based sports relying on reflexes. It is similar to the Chess rule system in that people have an inherent basic knowledge of geographical space and direction and indeed the laws of physics which they can bring to the game to help them reason about it. Yet the continuous and almost infinite domain in which entities can move makes predicting the exact results a difficult endeavour requiring skill and expertise. You can point a gun in an FPS in an infinite number of different directions, and can stand in an almost infinite number of positions when you do it, and the best combination of these two factors at any one time depends on your opponents (and maybe your team mates) who are constantly moving within that continuous space, as well as your understanding of the implications of the relative positions and orientations. These considerations may not immediately seem relevant to the typical turn-based strategy game, but they are – the same positioning and aiming mechanics, albeit on a simpler scale, exist in games like Scorched Earth or Worms, for example. You obviously no longer have a simple tree of discrete game states here, but from the near-infinite set of possibilities you have to mentally build your own game tree, and select your tactics based on that. When you examine a continuous domain you can pick out discrete areas within it which you can reason about – for example, in FPS games you might mentally divide the area up into rooms, areas in cover vs. areas in the open, paths between weapons or power-ups, and so on. Then you plot a route from one point of interest to another and also use such points of interest when deciding how to maximise your ability to attack someone and minimise their ability to attack you.

The end result of all these approaches is that instead of calculating the whole game tree in your head and calculating the correct flow through it, you have to look for patterns and use those to guide your judgement. Your basic skill at the game is essentially your knowledge of the game’s patterns, and the depth of the game is proportional to how hard it makes it for you to understand the full game state tree.

But there’s an interesting meta-game here too, because since you know it’s impossible to know the whole game tree, you know that your opponent is in the same position, and must therefore also be formulating his own patterns to judge the game and formulate his move. This means it’s worth trying to guess your player’s patterns also, and often that is of more use than to attempt (usually in vain) to find the optimal approach – after all, in any one situation you only have to do enough to beat your opponent, not to beat all possible opponents that could exist. (“Remember, when you and a halfling are being chased by a hungry dragon, you don’t need to outrun the dragon…”)