Posts

Recformer is a simple platformer. To beat a level, the player has to collect every coin in the level. Recformer is implemented in Typescript. I built it for the web because I am planning to run a player study with it, and it is a lot easier for people to open up a webpage than to install an executable. Another reason I made it is because I wanted to, and because of that, I want the game to be good; at the very least, I want Recformer to be decent. An image I have had in my mind for a while now is a main menu where you can watch an agent that plays the game. This blog post is going to show you how I accomplished exactly that. ...

A* is an algorithm that is so well covered that I won’t be wasting my time to add to the noise in this blog post, but if you are unfamiliar with A*, I recommend reading an introduction from Red Blob Games and then coming back here.1 Alright, assuming you are familiar with A*, the question you may be having is: “How can we make A* faster?” There are, in fact, a lot of ways. If you don’t care about finding an optimal path, you can use an inadmissable heuristic.2 If you wish to reduce resources required, you can cache common path requests. If you have a problem where the path is constantly being recalculated, then you can migrate to D*. If you want every search possible to be less costly to compute while still being optimal, you have to do something different. Specifically, you need to reduce the search space.3 ...

In my most recent post, I showed how to implement Conway’s Game of Life in C++ and visualize it with raylib. This post is of the same kind, except we are going to visualize Hilbert Curves with raylib. However, this post will only have an example of the final result and the code.1 I am of the opinion that that the two sources below are of a high enough quality that I don’t have anything more to add. ...

Introduction Conway’s Game of Life was created by John Horton Conway. The idea is simple: you have a grid of cells that can either be alive or dead. In every iteration, a new grid is made from the current grid by following a set of rules based on a cell’s neighbors. Since this is a grid, there are 8 possible neighbors when diagonals are included. The rules are the following: Any live cell with less than two neighbors dies. Any live cell with two or three neighbors stays alive. Any live cell with more than three neighbors dies. Any dead cell with three live neighbors becomes a live cell. The rules are simple, but the results can be mesmerizing. However, there are more reasons to care about Conway’s Game of Life than the fact that it is nice to look at. For example, it has been shown that a turing machine can be simulated with it. It is also proof of how seemingly incredibly complex phenomena can appear from straightforward rules. ...

Introduction This is related to an earlier post which was on panning and scaling a node graph visualized with Tkinter. In this post, the goal is to implement a level preview function where when the user hovers over a node they can see the associated file in a rectangle that appears. When they stop hovering over the node, the preview should go away. Additionally, there is a section on writing an update_node function that simplified the codebase. ...

Motivation As part of the work for my dissertation, I am building a tool that allows users to edit a Markov Decision Process (MDP). This relates to my paper, Level Assembly as a Markov Decision Process. This work is different because I am representing the MDP as a graph. Every node in the graph is a state, and a state is a level segment. Every edge represents an action. Levels are formed by connecting states together. I also have some metadata in the edges, which are links between level segments. ...

It’s been over two years since I last made a post, and a lot has happened. One of the most minor of these is the change to my website: I’m now using Hugo to build the whole thing. Before Hugo, I was using a home-brewed tool I built in Python. It worked with HTML, but there were re-writable portions marked by {{ FILE_LOCATION }}. The tool would go to that file location and replace the line with whatever it found in that file. I also had a blog post system with a meta file with information like the title and the data of the blog post, and more features. However, it was a pain to work with. ...

In this post I’m going to be covering two active reinforcement learning methods: q-learning and SARSA. Both methods do not depend on an MDP. Meaning, we are not guaranteed the presence of P. Instead, we learn which actions can be taken in a state during playthroughs. This is represented by a q-table, which is a table of states and actions that yield a q-value, which represents expected utility when taking an action in a given state. We can say that the expected utility of a state is the best action associated with that state. See the equation below. ...

This post is on temporal difference learning (TDL). TDL does not rely on a a Markov Decision Process (MDP). Instead, it traditionally uses a table where each state has a row and column so that the table represents the utility of all possible transitions. TDL uses observations to learn which transitions are valid. \[ \begin{align} U^{\pi}(s) \leftarrow U^{\pi} + \alpha (R(s) + \gamma U^{\pi}(s') - U^{\pi}(s)) \end{align} \]This is a very similar to the Bellman equation that we’ve seen in the past posts, but we aren’t using neighbors because temporal difference learning does not assume a model. Instead, an agent plays through the game, and returns a set of states that were taken along the path. So, the utility of a state s is determined by itself plus the reward of that state plus the utility of the state next in the path minus its own utility all multiplied by a learning rate alpha, which is typically a small number between 0 and 1. ...

In this post I’ll be covering policy iteration. As a brief reminder, here is the bellman equation that value iteration optimizes: \[ \begin{align} U(s) = R(s) + \gamma \max_{s \in S} \sum_{s'} P(s'|s, a)U(s') \end{align} \]In policy iteration, the goal is not to find the perfectly optimal utility of states like value iteration. If one state is clearly better than another, then the precise difference isn’t that important. After all, we care most about an agent making the correct decisions. This idea is how we come to policy iteration, which is broken into two steps: (1) policy evaluation and (2) policy improvement. Before going into each of these ideas, I want to give you the pseudo-code for the algorithm. ...