Week 4: Markov Chains / by Valzorra

Building the World

After our introduction to matrices from last week, which can be found in Week 3: The Matrix, we moved on to the rather fascinating Markov Chains in our Building the World Session. In short, Markov Chains express transitions from one state to another based on certain probabilities. They answer the question, after a certain event has occurred, what is the next most likely event to take place? Markov Chains are all about predictions based on what has already happened and on a set of actions and events we can choose from. This ties in quite nicely with our previous work on Chance and Probability with James, as well as my own research into that field of mathematics, which can be found in Week 3: Research on Mathematics. This transitioning data is represented in the form of matrices, which is why it was crucial to have an understanding of what a matrix is before moving on to the Markov Chains. Traditionally, Markov Chains have been utilised in the field of Marketing as they provide an excellent way of structuring data and making estimations about the success of certain marketing strategies, which I will be taking a closer look at shortly.

maxresdefault.jpg

As games designers, Markov Chains can be rather fascinating as they are key components in making NPCs and AI with individual personalities and changing behaviours based on those personalities. For example, if an enemy NPC has been wounded by the player then a tank NPC might choose to engage, while a more squishy one may opt to gain range and attack from afar. The same event occurs, which is that an NPC has been wounded, however, responses vary and behaviours change based on what data is within our State and Transition Matrices. Through these values and probabilities we have the opportunity to create an exciting and unique gameplay experience, which would excite players as it would be difficult to predict and take advantage of. In the session itself, we calculated how the Safety Index of certain sniper positions would change, if an NPC were to shoot from one. This is another example of how gameplay and AI within video games could gain variety and become more fun, making better and more unpredictable decisions about how to react to players. Below I have attached my work on Markov Chains from the class, their basic definitions and examples of how they operate.

Markov1.JPG
Markov2.JPG
Exploration of Markov Chains through analysis of the Pokemon Battle System.

Exploration of Markov Chains through analysis of the Pokemon Battle System.

In addition to dissecting the example related to sniper positioning, we also took a look at the popular Pokemon Battle System and came up with our own Pokemon, exploring how they would react based on certain probabilities we inputted. After crunching the numbers, we realised that if our Pokemon starts off with their strongest attacks, then based on the probabilities we chose together, they are most likely to attack with the same ability again. Now, this opens up a variety of possibilities in terms of design, because we have the option of estimate all of our probabilities on paper and complete the entire design of a sophisticated AI, all without writing a line of code. This is absolutely amazing, because not only do Markov Chains allow us to make accurate predictions of probability based on data we input, but they also enable us to change and manipulate that data based on the results we desire. This is an exceptionally interesting idea to me, because it gives users the power to learn from their mistakes and to change data based on the results they would like without any excessively complicated or time-consuming processes.

Board Games with Dice can be entirely represented by Matrices and Markov Chains. What matters in those games is the current state of the board, which is then changed to the next state by the dice. The next state is entirely dependant on the current one.

Board Games with Dice can be entirely represented by Matrices and Markov Chains. What matters in those games is the current state of the board, which is then changed to the next state by the dice. The next state is entirely dependant on the current one.

After our detailed examination into Markov Chains and why they are freaking awesome, we proceeded to explore some more principles in Calculus. We had a brief overview of all of the principles and rules we had covered up until that point and then James proceeded to explain the wondrous and mystical powers of the number e or Euler’s Number. This is an irrational number, approximately equal to 2.7182818284590452353, that spans across multiple areas of mathematics. The reason e is such an amazing number is that it allows us to solve seemingly unsolvable mathematical problems. It offers a solution where none seem apparent, which makes it incredibly useful. Below I have attached my work in relation to this number and how we essentially proved its value.

Euler's Number.JPG
Euler's Number 2.JPG

Tech Workshop

After our Markov and Calculus extravaganza in the morning, we went over to Studio 16 for individual one to one sessions with James in relation to mechanics we may be interested in developing. As I am very much focused on Mathematics, Chance, and Probability, I was interested in how one could go about manipulating certain probabilities. I wondered if I had three standard six-sided die, A, B, and C, and if I threw them all one after the other, how could I go about changing the order in which the values appeared. For example, if I tossed a 1, another 1, and a 6, how could I manipulate my result to become in the order of 1, 6, and 1. The reason I was interested in this concept was primarily the idea of data and chance manipulation based on certain knowledge.

dice-gambling-1024x768-wallpaper.jpg

After James gave me a nice and clean method for achieving the task, I went to one of the computers to try and code it. However, as I was setting up, I realised that it would be a great exercise to try and craft my own random number generator to give me the values for my three die. Additionally, as this is Probability at its purest, I thought it would be an excellent application of my research on the topic and of the things we have covered in previous Tech Workshop sessions. For this piece of code, I referred to my handout on Linear Congregational Generation and applied the same method for obtaining a truly random number within a limit. The code, which I am happy to confirm does in fact work, is attached below. I should note that as the computer I was on did not have Unity installed, I coded this in an online compiler in C#. But anyway, who cares, the thing works!

using System;           
public class Program{

    //Getting the current time which will be used as our seed value
    public static String GetTimestamp(DateTime value){
        return value.ToString("ssffff");
    }
    public static void Main(){
        
        //Initialising variables
        string inputM;
        int x, m, s;
        
        //Inputting m
        Console.WriteLine("Enter Value for m: ");
        inputM = Console.ReadLine();
        m = Convert.ToInt32(inputM);
        
        //Ensuring m is greater than 0
        if (m<0){
            do{
                Console.WriteLine("The value of m must be greater than 0.
                Please enter a different value for m: ");
                inputM = Console.ReadLine();
                m = Convert.ToInt32(inputM);
            }while(m<0);
        };
        Console.WriteLine("Your value for m is {0} ", m);
        
        //Getting the seed value based on time
        String timeStamp = GetTimestamp(DateTime.Now);
        s = Convert.ToInt32(timeStamp);
        
        //Ensuring that s<m based on seconds;
        if (m<s){ 
            do{
            s = s/10;
            }while(m<s);
        };
        
        //Outputting the accurate seed value
        Console.WriteLine("Seconds right now: {0}", timeStamp);
        Console.WriteLine("The value of s is: {0}", s);
        
        //Arbitrarily choosing t and u
        Random rnd = new Random();
        int t = rnd.Next(0, m);
        int u = rnd.Next(0, m);
        
        //Outputting t and u
        Console.WriteLine("The value of t: {0}", t);
        Console.WriteLine("The value of u: {0}", u);
        
        //Calculating x
        x = ((t*s) + u)%m;
        Console.WriteLine("Your random number is: {0}", x);
        
    } 
}

Unfortunately, although I had successfully coded a random number generator based on the Linear Congregational Generation method, by the time I had finished this task the session had concluded, so I wasn’t able to incorporate the swapping mechanic fully. However, I did have the time to consider how to approach the process and what I intend to do is to simply add three random numbers from my generator in an array, and then swap the elements in the array to the desired positions based on the algorithm James showed me at the start of the session.

Thoughts and Reflection

I found the material we covered this Tuesday incredibly useful to my personal research into Mathematics and specifically Probability and Chance. I am fascinated by the idea of being able to make predictions of certain probabilities and then to be able to change the data in order to obtain the results we desire. This is an excellent method for manipulating chance and probability and an be extremely applicable not only in games design and AI, but also in fields such as Marketing and Training. Markov Chains have excessive power as they can essentially predict the future and all possible outcomes based on a set of collected data, which is absolutely fascinating to me. I’m also incredibly interested in figuring out how to actually visualise this data in a digestible format, which anyone could understand, even without the knowledge of matrices. More on Markov Chains and their applications will follow soon as a continuation of my research into this field of Mathematics.