Before we begin, let me just define a few terms:
$S_t$ is the state at time $t$. $A_t$ is the action performed at time $t$. $R_t$ is the reward received at time $t$. $G_t$ is the return, that is the sum of discounted rewards received from time $t$ onwards, defined as $G_t = \sum_{i=0}^\infty \gamma^i R_{t+i+1}$. $V^\pi(s)$ is the value of a state when following a policy $\pi$, that is the expected return when starting in state $s$ and following a policy $\pi$, defined as $V^\pi(s) = E[G_t | S_t = s]$.
Read more →
Compared to the previous article where we simply used vector derivatives we’ll now try to derive the formula for least squares simply by the properties of linear transformations and the four fundamental subspaces of linear algebra. These are:
Kernel $Ker(A)$: The set of all solutions to $Ax = 0$. Sometimes we can say nullspace $N(A)$ instead of kernel. Image $Im(A)$: The set of all right sides $b$, for which there is a solution $Ax = b$.
Read more →
There are multiple ways one can arrive at the least squares solution to linear regression. I’ve always seen the one using orthogonality, but there is another way which I’d say is even simpler, especially if you’ve done any calculus. Let’s define the problem first.
Given a matrix \(N \times M\) matrix \(X\) of inputs, and a vector \(y\) of length \(N\) containing the outputs, the goal is to find a weight vector \(w\) of length \(M\) such that:
Read more →
This article is a part 3 of the Let’s Write a 2D Platformer From Scratch Using HTML5 and JavaScript series. Click here to go to the previous article (part 2: Rendering).
The previous post ended with a very ad-hoc solution to collision detection. We barely managed to get vertical movement working, and didn’t even get started on gravity. There’s a reason for that. Once the player starts moving vertically, we need something better than just checking against the top left corner we immediately run into issues such as passing through walls below the player, as shown in this image:
Read more →
As far as gamedev and HTML5 goes, there are tons of great game engines already out there. How do we pick the right one? Look at the number of stars on GitHub? The number of contributors? The number of published games? If you’ve looked at the previous articles on this blog, you probably know where this is heading (or read the title for that matter). We’re going to write our own game engine first!
Read more →
This article is a part 2 of the Let’s Write a 2D Platformer From Scratch Using HTML5 and JavaScript series. Click here to go to the previous article (part 1).
Now that we have the game loop, we can build a small wrapper around the HTML5 Canvas API. We’ll start with a simple tile based map where each tile is rendered as a colored rectangle.
The map will be specified as an array of numbers where 0 means empty and 1 means wall.
Read more →
Binary search is an extremely useful and popular algorithm used for quickly searching in a sorted array. Binary search is even used by people in real life (outside of programming) when they play the guess the number game. One person thinks a number between 1 and 100, and the other person tries to guess. The response is only less, equal or greater. If you guess 50 and get a less response, you just narrowed down the search to half the interval, 1 to 50.
Read more →
A binary heap is a simple data structure most often used for implementing priority queues. In a more general sense, a heap is a tree-based data structure which satisfies the heap property, and a binary heap is a heap which uses a binary tree to store its data. Any arbitrary binary tree which satisfies the following two properties can be considered a binary heap:
heap property: If P is a parent node of N, then P.
Read more →
Having just implemented and tested a Fibonacci heap on a large dataset I thought I’d write up a bit about it, mostly so that I can reference this post later in the future, and to help me remember things I’ve learned better. Note that this blog post is not a tutorial on how to implement a Binomial/Fibonacci heap.
First, let’s begin with a few definitions. Throughout the article we’ll be talking about min-heaps.
Read more →
This article assumes basic familiarty with bit vectors. If you’re unsure how they work or need a refresher, check out the previous article about bit vectors which goes in depth both in explaining how they work, and how to implement one.
A Bloom filter is a simple yet powerful data structure. It allows you to answer the question have you seen this before? in a very fast and memory efficient way.
Read more →