Modelling Games using Graph Theory

This is a follow on piece from the ‘Modelling Puzzles using Graph Theory’ article. Here I want to revise the theory so as it can be extended to a greater range of interactive computer systems. We will use graphs to represent game-states and their transitions. This will give us the foundation to prove some interesting things in the future like the solvability of all full information games and look into some interesting implications of randomness.


Deterministic Systems

For this first part we will be talking about only deterministic, full information, single player or single agent systems. The very first assumption I will make is to assume a finite number of legal game states. For all modern computer software this assumption is perfectly safe as machines do in fact use a finite number of binary bits to represent their state and each bit can only take a finite number of different values, either a 1 or a 0.

Remembering from the puzzles article we will model each state as vertices on a graph. The edges of the graph are defined by the rules of the system. In the rules of checkers a piece can move forward to a diagonally adjacent square if that square is empty. In our formal system this would be represented by having every state where there is a free space diagonally in front of some piece connected to the state where there is a piece in that position, no piece in the previous position and everything else the same.

State Transition.PNG

Two edges are distinct if they do not join the same two game states in the same order. This is important as it lets us prove that given there are a finite number of states, there will also be a finite number of distinct edges, namely all possible pairs of states.

edges in complete graph.PNG

An important thing to note is that these graphs are not necessarily trees. In most games there are multiple paths through the graph, multiple series of choices, which will leave the player in the same state. Using the Checkers example we could have the following,

State Transition Not Tree.PNG

There are two distinct paths from state 1 to state 2 which proves this is not a tree but a graph. The other important feature of these graphs is that there is no guarantee they are acyclic. Acyclic graphs are ones where there are no loops, once leaving a state you cannot re-enter it. There are many games where you can ‘undo’ a previous move and return to an earlier state. These two properties will be important things to keep in mind for future proofs.

The final thing we need to model before we can start creating proofs is our games goals. Most systems have an ending. We can easily work that into the model by saying any state that has no child vertices is an end state. If a state has no child vertices that means that once the game has entered this state there are no further moves that can be made, thus it is an end state. However this doesn’t capture the value of certain endings. Although putting your opponent in check-mate and getting put in check-mate are both chess states where no further moves can be made they are not equally desirable outcomes. Because of this we must add to the model a classification for every end state. We could simply use a win and loss tag attached to each end state which works fine for many games but we want a more general classification method that will work for any conceivable game. To this end I suggest we use an ordered set of arbitrary but finite size of tags to classify our end states. This would enable us to represent games like chess and checkers which have simple win and loss conditions but also to represent the different end states of racing games where there could be multiple different classes of end state, all of different value. It would also enable us to represent the meaningful difference between end states in games like Tetris which use a scoring system. Having this property will be very useful in future for creating proofs.

So we can represent every deterministic, full information, single agent computer system as a graph with a finite number of vertices, a finite number of distinct edges and a finite number of meaningfully different classifications of end states. Can we relax some of these descriptors in any way? First lets take a stab at removing that requirement for determinism.

Non-Deterministic Systems.

Firstly, computers do not use real random number generators but pseudo random number generators but for our purposes we will assume they are practically indistinguishable to the agents. In the previous system, at each state the player would be able to chose from the connected edges which state they wish to transition to with certainty. Each edge represented a possible decision in totality. What if a game’s rules called for some simple randomness?

Lets imagine a simple game. You are a hero fighting an orc. On your turn you may attack the orc with either a bow or a sword. Your bow has a 60% chance to hit and deal 10 damage while your sword has an 80% chance to hit and deal 8 damage. From our start state where the orc is healthy there are three possible future states, the orc takes 10, 8 or 0 damage. We could try and represent it using the old model as follows,

Orc Battle Old.PNG

but we can see this doesn’t capture the non-deterministic properties of the system. This model says the player can directly choose what state they want to move to; it loses the non-deterministic properties of the rules. Simply adding percentages to each of the edges doesn’t work either,

Orc Battle 2.PNG

This model loses the deterministic elements of the rules, suggesting that from the start point the player has no choice over which state they end up in. The solution is fairly simple, make a new intermediary state, splitting the deterministic and non-deterministic elements apart.

Orc Battle Non-deterministic.PNG

In this model, edges with no probabilities attached are deterministic edges, the player has full choice over the state transitions. Intermediary states are always fully non-deterministic, the player has no control over the state transitions from an intermediary state and the state transitions are labelled with their respective probabilities.


 

Now that we have this theory we will be able to use it in later articles as the basis for some fundamental proofs in design. Further extensions of the framework will be introduced to deal with multi-agent and partial information games which will then enable us to investigate them further. Thanks for reading, if you have any thoughts let me know in the comments below.

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s