Author: Usman Mohammad Siddiqui

The process of making a professional video game is a complex task that involves people from many backgrounds to join together and work on something creative. We can examine the ways game theory is used to help make decisions when designing the gameplay as high level decision trees can be made to model the flow and pathways and use payoff matrices to model skill or level change.

There are many methods for design approaches which include flowcharts, storyboards, topological maps, UML and decision trees. Decision trees can be used to model gameplay where different paths in the decision tree relate to different paths that can be chosen by the player or the different outcomes that can arise from the actions of the player. A decision tree is a branching tree style diagram that can show the set of possible actions and decisions that can be made by the player. It can overall model the way the player moves through all the possibilities of the game.

When creating decision trees it is based on the main game interactions of most interest. We can use fixed inanimate objects that will be represented as boxes in the decision tree. The tree will show the likelihood of events occuring, for example for a coin toss game it would show the likelihood of getting heads or tails. In more complex games it would show the probability of getting a success. It would seem too large and out of scale to make a decision tree for the whole game and so instead we can break it into segments or per mission.

The figure represents the design of a simple example of a very small segment of a hypothetical game scenario. It shows the game objects with which the player may interact on how fast and how accurately opponents 1 and 2 will respond.

A payoff matrix can be used to model the player’s decision making the process into a grid structure in order to analyze,document and communicate the skill or challenge levels within the parts of the game. One axis will represent the player’s decision and the other axis of the payoff matrix will represent the opponent’s decisions. It is unfeasible to have a payoff matrix for every possible decision in the game however it’s practical to make one model more generic level decisions made by players given in segments of a game. For example in the video game pong, the accuracy of the movements made by the player affects the game. This is because the ball’s contact with the ping-pong rectangle (bat) returned the ball at smaller angles which made it harder to hit the next time. A payoff matrix can model high and low player accuracy outcomes as generic player decisions. For multiplayer games, statistical analysis of the strategies used by a large number of players via payoff matrices can be used to understand the strategies of the players which will inform us more about the game design. This ultimately can help balance different elements in the game.

Table 1 shows a payoff matrix that could be proposed by a game designer to determine what skill level would be required regarded to the gameplay involving either of the two software-based opponents from Figure 1. In terms of skill level, the matrices could be used to apply Nash equilibrium.

Table 2 shows a payoff matrix based upon an analysis of different games played during playtesting for a given section of a video game. The first number in each cell is the payoff (or probability of success) to the opponent and the second number is the success probability for the player. If they use the same strategy, then the player will win 50% of the time. However if the player chooses a high accuracy/low speed strategy and the opponent chooses a high speed/low accuracy strategy, the player will win 80% of the time. Overall high level payoff matrices can help design the skill and challenge level for different sections of the game.

References

https://journals-sagepub-com.myaccess.library.utoronto.ca/doi/pdf/10.1177/1555412017740497

Gossip is something that is really common between schools around the world. Students love to spread this type of information to their peers of the partial stories they know which ends up spreading to other groups of people like wildfire. To find out the true story, the students would need to tell each other the partial bits they know about it which would combine into the full story. This course comes in to play as we can use graph theory to determine how many conversions would need to take place in a group for every person to know the full story.

We can assume that everyone knows one part of the story and we want everyone to know the full story. Let people be vertices in a graph and the edges between them be the number of calls they make. To simplify this problem, we can assume that their will only be 2 ways calls (no group calls). In this blog post, I will answer the question of: How many calls must be made for n people to allow everyone to know the full story?

The numbers on the edges between the vertices represent the order in which the calls take place. This means the lowest number has the highest priority and so the paths taken will choose the highest priority edges first.

Consider the following graph:

There is a problem in this graph as B never hears D information. As you let information pass through D, D’s last call with A is also A’s last call and the same goes for C. Thus there is never a call to B telling D’s information.

We can try fixing this graph by defining the following.

“A gossip scheme is an ordered graph where there is an increasing path from any vertex to any other.” – Nate Gildersleeve

An example of this would be:

In this graph of 4 people, information can be passed around to anyone. We can see that C’s call to B happens after C’s call to D and thus B hears D’s information so the problem in the first graph has been solved here.

A method that can be used to find out how many calls it takes is that everyone calls one person in turn and then that same person calls everyone back. This would mean that the first person everyone called knows the whole story now and then he would be able to call everyone back to tell them the whole story. 

For this approach, there would be

Let n be the number of people

=> n – 1 call’s going into that person  [exclude the person being called]

=> n – 1 – 1 call’s going out    [last call-in doesn’t need to be called again]

=  (n – 1) + (n – 1 – 1) 

=  2n – 3

For a group of 5 people this would look like:

We can actually improve this slightly by the following approach.

“If every person calls one of four people, then have those people share their information with each other and finally call everyone back”- Nate Gildersleeve

The following graph is more efficient than the one mentioned earlier.

This will improve our formula to 2n – 4.

In the world of gossip that we live in today, you now know how many conversions it will take to clear it up efficiently from the teachings of graph theory and deriving an undirected weighted graph for it.

References:

http://web.pdx.edu/~caughman/Gossip.pdf