This is a direct follow on from ‘Modelling games with Graph Theory’ where we will explore one of the interesting ramifications of the theory described in that article. The following proof explore the fundamental limitations of game design and will hopefully be both intrinsically interesting and useful for guiding game design.
Solvability of Deterministic Full Information Systems
The proof I wish to produce is that for any deterministic full information single player system there is guaranteed to be an optimal solution or possibly multiple equally optimal solutions and that they can be found. Using the theory from last time we know these systems are represent-able as finite graphs. There is a defined start state and end states are classified by tags rating them from best to worst outcome. The goal is to find a legal walk through the graph to the highest rated end state. So how can we go about showing this can be done on any finite graph with finite edges?
To start with, a walk is just a series of sequential edges leading from one node to the next. The problem we first run into when trying to find the walk with the best end-state is that because walks allow loops there are possibly an infinite number of walks through a graph to search. Even a single loop in the graph would cause an enumeration of all walks to trail off infinitely, repeatedly enumerating walks that go through this loop some different number of times. To deal with this we can instead look at paths as they avoid this problem. There must be a finite number of paths in any graph with finite nodes and edges as paths do not allow loops. Also, any end-state capable of being reached by a walk can be reached by a path and vice versa. Enumerating all the paths in a graph is a good replacement for enumerating walks because they are of finite number and we do not miss any end-states by doing so. From this we have a simple problem of searching through this list of all enumerations looking for the one that terminates in the highest ranked end-state. This path will be the optimal path and all walks constructed by allowing loops along this path will also be optimal.
That it is possible to find these walks in any finite graph mean all single player, full information, deterministic systems are always going to be solvable, no matter how complex they are. It means that every deterministic full information system can be fully solved by using pure calculation.
How can we deal with this problem? Many writers and designers suggest adding some form of randomness will break the players ability to calculate the correct moves but I disagree. This will be the topic of the next post.