From Pixels to Symbols - January 25, 2020

Simulate a Game - Like a Brain Models the World

I talked about my plans to simulate games in a previous post, Game Simulation. I’d like to clarify that I’m using the term “simulate” to be analogous to what the brain is doing when modeling the world around us. The brain has constant input from the world, and that input is used to keep our internal model consistent with the world around us. If we were to shut off all of our sensory input, the model in our heads would start to diverge from reality.

In the same way, my simulations of video games are intended to have constant pixel input from the game. Consider a sidescrolling game like Super Mario World. There might be many things happening off-screen. It would be great to have simulated knowledge of the entire level structure, as well as off-screen objects, but that doesn’t come easily to our brains. It’s also completely impossible if we are playing a level we’ve never seen before. Even when we do have off-screen knowledge, it’s usually a fuzzy representation and prone to diverging from reality. The real computation is spent keeping our mental model up to date with reality so that we can reason about the current state of things, solve problems, take actions, and learn new concepts.

Model Structure

Right now, I’m focussed on constructing the simulation model manually, starting with just pixel data and gradually building up the components of the game. I took a step back to think about how the model should be composed and operate in terms of a final solution, and here’s where I’ve landed. (Building this data up from scratch is a different problem that I’m not going to discuss in this post.)

1. Objects: Detect discrete objects, positions, orientations, and sizes from the pixel data with an assumption of spacial consistency from frame to frame. Predict the next state of the object using the Behaviors, Interactions, and Hidden States listed below.
2. Behaviors: Detect discrete object behaviors across frames (like movement arcs, velocities, image sequences, etc) with an assumption that a single behavior conforms to a single linear function. Predict the next object behaviors using the Interactions and Hidden States listed below.
3. Hidden States: Detect object hidden states from the set of current object behaviors. We can also retroactively detect object hidden states from mis-predicted Interactions listed below. Predict the next object hidden states using the Interactions listed below.
4. Interactions: Detect that an interaction has taken place when object Behaviors change. Interactions typically involve preconditional rules between objects and states and result in postconditional changes to objects and states. Predict the next object interactions by finding interactions which fully satisfy preconditional rules.

Note how each component of the model needs a way to detect the state of that component using the states of the other components and ultimately the latest pixel input data from the game. Each component also needs to be able to predict the next state of that component. Otherwise, it will be difficult to evaluate the model and the model will be unusable for search and action planning.

I’m sure there will be complications in every single area when constructing the model. I can predict some of them, but many more might only be discovered when I try to build it. It’s also possible that I’m missing one or more key ideas and that my entire strategy might change as a result. Whatever solution I finally land on, my hope is that creating a model of a game will become a straightforward process which can be applied to many types of games.

Game Simulation - January 4, 2020

Projects

I have a small set of projects that I’m working on in my spare time. I tend to get easily burned out by projects, so I have to be careful to create simple milestones and avoid open-ended tasks and original research. It’s easy for me to get stuck thinking about grand issues and end up never writing any code. In the long run, I think I’m much better off solving small problems. My hope is that all these small problems will add up to something bigger in the long run.

Game Simulation

One of the topics that I’m interested in is simulating video games using just the available pixel data. There’s a lot of grandiose challenges related to this, like creating an AI agent that can learn to play games using just the pixel data. I’d like to eventually tackle these types of problems - but it’s not the right time yet for me, given my current abilities. And honestly, I’m more interested in making an AI that can understand the structure of a video game, rather than one that learns to play well without any symbolic reasoning for its actions.

To that end, I’ve made a simple game to help me work on this topic. The game itself is not particularly important. There are blocks that move around and interact with one another. They have visible attributes, like position and size, and they have hidden attributes, like velocity, and behavior type. There are actually no user actions for this “game” because that’s not particularly important yet. I’ll add actions in once there’s something to be gained by it.

The goal now is to create a simulation of the game that can set its state using only the pixel data available from each frame. Imagine that you’re playing in a sports game. You’re brain has a model - a set of expectations about how things work in this sport. As you see actions unfold, you anticipate behaviors from the players. As you go to take an action yourself, you anticipate the results of that action. If you mess up the action, you have to adjust your mental model to match the real state of the world instead of what you thought it would be. That’s how I think a simulation of a game should work too.

Now, a game that has no randomness and no hidden state could be simulated with 100% accuracy - but that’s not really the goal. The goal isn’t to recreate all the pixels, but rather to maintain a reasonable representation of the game that is useful for analysis and taking actions. “Reasonable representation” is a bit vague. In truth everyone’s mental model of a game is different, and some may be more useful in particular scenarios. I’d like to come up with a good way to evaluate a simulation based on self-consistency, complexity, coverage, applicability towards goals, etc; but I think I can focus on that later.

As for the simulation itself, here’s a rough outline of how I think it should proceed from frame to frame:

• Assume that we have a set of objects from previous frames which have visible attributes (like position, size, orientation, etc) and hidden attributes (like velocity, type, behavior, etc) - or assume that we have no state if this is the first frame.
  1. Predict: the next set of objects and their states that we expect to see on the next frame of the game - both visible states and hidden states. One way to do this is to use a large set of rules about the results of interactions between objects.
  2. Detect: the next set of objects and their visible states using the pixels in the next frame of the game. Hidden state cannot be detected using only the new pixel date. One way to do this is to use a trained neural net that can recognize objects and their visual state from a single frame.
  3. Resolve: our Prediction with our Detection. Update the visible states with what was detected. Update the hidden states using knowledge from past frames. One way to update the hidden states might be to use our set of prediction rules in reverse over a period of time. Set the hidden states according to what would cause those rules to be applicable.

I’ve listed three steps, Predict, Detect, and Resolve, that we cycle through for every frame. Each step has its own problem that needs to be solved in order to have a simulation run smoothly over a range of inputs. One possible way to create these three functions is to use different machine learning techniques for each step. That may be my end goal, but that’s much too ambitious for now.

Instead, I’m building a program that will help me manually create and evaluate these functions so that I can explore various ways to solve them. The framework allows me to move forward and backwards through the simulation and it shows me all of the current simulated state using a treeview. I still need to add support for modifying the functionality in real-time, without needing to restart the program. And I think I need to add an evaluation score or graph so I can quickly tell how the simulation is performing.

Benefits of a Simulation

For completeness, I’d like to list some of the benefits to having a simulation of a game:

• Add information to help a player make better decisions. A heads-up-display indicating possible enemy hiding locations.
• Determine which actions are good or bad based on simulating into the future. Go this way, not that way.
• Take quick actions for the player in dangerous situations. Break now so you don’t run into the car in front of you.
• Dissect the mechanics of the game to learn new techniques. Running in a particular way helps you move faster.

And of course, I believe I will learn things during the development of this project that will help me down the road. I’d love to end up with a framework that lets me quickly create a simulation from an existing game. And maybe that will require using Machine Learning techniques to speed up that process.

Mutable Thoughts - December 28, 2019

A New URL

Up until now, the address of this site has always been IsaiahHines.com. I bought the address years ago, and I’ve been using my github repository to host the content so that I have full control to experiment with layouts, navigation, and content. And the only real expense is the $15 a year to renew the URL from ionos.com… And my time - that’s an expense too, but it’s worth the enjoyment I’ve gained and the things I’ve learned.

I was having a conversation about URLs yesterday and it got me thinking that most people don’t use their name as their website address. I think this is for several reasons:

1. It can be hard to reserve your name as a URL, either because someone else may already be using it or because it is being treated as a premium address in anticipation of somebody willing to shell out big bucks to purchase it.
2. A name is often less catchy than a two or three word phrase and it’s fun to come up with a nickname to use as an online persona.
3. The things we write about often have a theme to them. It’s more convenient from a reader’s POV if the address relates to that theme in some way.

Given these above reasons, and in the spirit of mixing things up, I’ve changed my URL to MutableThoughts.com. There are a couple reasons I chose this name. The first dozen or so reasons are because the other names I came up with were already taken or were too expensive. :) That being said, I’m pretty happy with where I’ve landed. Right now this website mostly contains posts with content of whatever I was feeling like writing about at the time. These ideas are not immutable - they can and will change as time goes on. And so Mutable Thoughts seems an appropriate description of what this website contains.

Mutable

Mutability and immutability is a common programming concept that is of great importance in several languages. In Python, numbers, strings, tuples, and ranges are immutable and therefore code can rely on values of these types to remain unchanged. And, in c++, there’s a special mutable keyword that is used to indicate that a class member value can be modified, even in cases where the class itself is advertizing that it is constant and immutable. The mutable keyword also shows up in c++ lambdas if you want to be able to change the value of captured variables from within the lambda.

Life Is An Adventure - December 21, 2019

New York, New York

In the 4 years since my previous post, I’ve had 2 amazing children, sold our house and vehicles in Washington, and got an apartment and software development job in the middle of Manhattan, New York City. I’ll say that it’s nice living in the same time zone as the rest of my family, and it’s a bit easier to have visitors here because of the closer distance. In the span of 1 year, I think we’ve had 5 different sets of visitors join us in new york for a few days. I suppose that the touristy feeling of New York city probably helps out with this too. :D

Programming With Python

For my job I’ve had to learn a new programming language, Python, and I’ve been having a bunch of fun with it. I think the statement, “Programming is fun again!”, is an appropriate description for how it makes me feel. I’ve got several Python projects that I’m working on, and it’s pure joy to jump back and forth between them. They are all related to video game simulations in some way - visualization of data, decision optimization, and using AI to build the simulation from only the image data available. I’m confident I will make separate web posts on these topics - probably with multiple parts as I slowly make progress on them.

Reprogramming Myself

On a personal level I’ve also been working hard to try to build better habits on a daily and weekly basis. In the past I’ve tried one-off techniques, like requiring myself to think for 30 seconds before reading news on my phone or navigating to youtube or netflix. It works for a while, but I inevitably forget about my rules and fall back into old habits after a week or two. Well, not anymore! I’ve got a new framework for making and enforcing simple rules for myself that has worked surprisingly well so far. I’ll say that I’ve gone about a month and a half with this new approach and I honestly feel that it is transformative on a weekly basis. I hope to eventually write about it in more detail - perhaps after a longer period of use.

Excitement - February 28, 2016

Time for a new post I think… My last post was more than 2 years ago and I haven’t really touched this website since. I’m hoping that will change.

There’s a lot of exciting things going on in my life right now - Sarah and I (and our puppy!) will start moving into our recently purchased house just two weeks from now. I am ridiculously excited. It’s in good condition, pretty large, and in decent proximity to both work and general stores. It will make for a very exciting blog post once we move in! ;)

Oh, and we’re gonna have a baby… Which is like new-house excitement times a kajillion. We’ll have a few months to get the house all set for the new arrival, but I don’t think there’s really any amount of time that will prepare me for all the excitement and ridiculous amount of responsibility that’s about to happen. I’m happy, excited, thankful, and nervous (terrified?) all concealed within my currently calm outwardly demeanor… That may change.

And along those lines, I’d like to start posting some pictures on here of exciting and fun things that are happening. I’m a little apprehensive about posting pictures here publicly - as anyone could steel them (but really, is that a problem?). I suppose I’ll just be picky about which pictures I post. :)

Codility - January 30, 2014

So I was recently introduced to the service Codility which provides programming challenges for people looking for a job in the industry. I’m not looking for a job, but I do like interesting programming challenges, so I thought I’d try it out.

Apparently, once a month they release a new algorithmic problem to solve and test your solution for correctness and good time complexity. You can get a “silver” award if your program is correct and a “gold” award if it also has good time complexity. They give you a time limit of 2 hours, but I’ve figured out first hand that you can simply retake the test as many times as you like.

After three tries I got my shiny gold medal. My first attempt was almost completely correct if it wasn’t for a very small edge case that they specified in the problem. I only had to change one line of code to make it correct.

Anyway, in short the problem statement is to find the number of ranges within an array where the Max(range) - Min(range) <= K.

I’m not sure If I’m allowed to post my solution online - so I’m sorry if this is bad form…

#include <set>
#include <vector>

using namespace std;

// Target space complexity: O(n)  Actual O(n)
// Target time complexity:  O(n)  Actual O(nlogn) due to multiset
int solution( int K, vector<int> &A )
{
    int left = 0;
    int right = 0;
    int count = 0;
    multiset<int> values;

    // Prime our sorted range with the first value
    values.insert( A[0] );

    // Stop once our left edge has exceeded the input values
    while( left < A.size() )
    {
        // While the range we are looking at is a legal span,
        // try to increase our right edge
        while( values.empty() || *values.rbegin() - *values.begin() <= K )
        {
            // Don't increase it if we're at the right edge of the input
            if( right == A.size() - 1 )
            {
                break;
            }

            // The new value that we're concidering to insert into our sorted range
            int newVal = A[ right + 1 ];

            // If this value would cause us to exceed the spanning limit K,
            // don't add it to the range
            if( !values.empty() )
            {
                if( ( newVal > *values.rbegin() && newVal - *values.begin() > K ) ||
                    ( newVal < *values.begin()  && *values.rbegin() - newVal > K ) )
                {
                   break;
                }
            }

            //
            values.insert( A[ ++right ] );
        }
        
        // We can no longer increase the spanning range

        // Add to our count the number of spans that start with our left edge
        count += right - left + 1;

        // Edge case... Report at most 1000000000 spans
        if( count >= 1000000000 )
        {
            return 1000000000;
        }

        // Move our left edge to the right
        // and remove the left value from our sorted range
        values.erase( values.find( A[ left++ ] ) );
    }

    return count;
}

So apparently this code was good enough to get a gold sticker, but I don’t think it’s actually O(n) time complexity. In the worst case I could create a multiset of size n. Since erasing a single value takes O(logn) time, then erasing them all one by one should take O(nlogn). But since sets and maps are so awesome, maybe they don’t always have a good way of judging the time complexity.

Either way, it was a pretty fun challenge and I’d like to complete more of them. They appear to have a whole set of training challenges at codility.com/demo/train/.

Initial Thoughts - January 30, 2014

Lots to say, but not sure if I’ll have time for it all. For a long time I’ve wanted to own a website with my own url (like this one). I’ve finally gotten my wish, because github supplies free hosting via a specially named git project and I was able to mess with some DNS settings such that the url that I own will show up in its place.

Anyway, the mechanics behind this website are pretty cool because of a tool called jekyll that provides some post-processing to my ramblings - creating lists and things like that.

So now my big question is what exactly to put on this site. Roughly speaking, I’d like it to contain projects I’ve completed, like games and small coding solutions. I also want to post some of my thoughts concerning larger projects that I’ve been mulling over but haven’t made much progress in. Finally, it might also be fun to make more posts like this one that just contain some random thoughts (like a normal blog).

I think it’s important for me to note that a big part of what I want to do with this site involves considerable infrastructure to how content is organized and displayed, so it won’t be as simple as just writing a few posts right away. Though after the infrastructure is in place I’d like it to be easy to write whenever I feel like it.

Also, code snippets:

#include <iostream>

int main()
{
    std::cout << "Hello World!" << std::endl;
    return 0;
}

Now that looks nice after tweaking the layout a bit. This should be fun! :)