Wednesday, May 22, 2013

Unlabeled Object Recognition in Google+

Google+ released an amazing feature that uses object recognition to tag photos. Here is a Reddit thread discussing it. Generalized object recognition is an incredibly difficult problem - this is the first product that I have seen which supports it. This isn't a gimmick - it can recognize objects in pictures without *any* corresponding text information (such as in the filename, title, comments, etc). Here are some examples on my photos (none of these photos contain any corresponding text data to help):


At first I thought this last one was a misclassification, until I zoomed in further and saw a tiny plane:


Of course, there are also many misclassifications since this is such a hard problem:

This squirrel came up for [cat]:

This train came up for [car]:

This goat came up for [dog]:

These fireworks came up for [flower]:

This millipede came up for [snake]:

Sunday, May 19, 2013

PAQclass

I have released an open source classification algorithm called PAQclass: https://code.google.com/p/paqclass/. I originally created PAQclass when I was working on my master's thesis but I never got around to releasing it until now. PAQclass does classification via data compression. It uses one of the best compression programs available: PAQ8. Although it is very slow, I think PAQclass is probably close to state of the art for text categorization tasks.

Friday, May 17, 2013

Fathauer Fractal Tessellation



I have implemented a fractal in HTML5 canvas: http://www.byronknoll.com/kites.html. It is based on a fractal discovered by Robert Fathauer. Here is a zoomed-in view of the top of my fractal:



The fractal seems to have some interesting properties. Near the center of the zoomed-in image above you can see a "tunnel" of consecutively smaller triangles. There are an infinite number of these tunnels (and I think they exist in every direction). Along the vertical you can see there is pattern to the location of the tunnels. The distance between the tunnels is a geometric sequence with a common ratio of 1/3. As you travel into a tunnel, the hypotenuse length of consecutive triangles is also a geometric sequence with the same common ratio of 1/3.

Friday, May 10, 2013

O(n log n)

I have released a new version of my visibility polygon library. I improved the time complexity from O(n^2) to O(n log n) (where n is the number of vertices). O(n log n) is actually the *optimal* time complexity for this problem (since this problem can be reduced to sorting, and we know sorting is O(n log n)).

A high level description of the algorithm: First, sort all vertices according to their angle to the observer. Now iterate (angle sweep) through the sorted vertices. For each vertex imagine a ray projecting outwards from the observer towards that vertex - all we need to compute is the closest "active" line segment in order to construct the visibility polygon. The closest active line segment must be computed in O(log n) time (for each vertex). I used a special type of heap to accomplish this. The heap keeps track of all active line segments (arranged by distance to the observer). The closest line segment is at the root of the heap. Since line segments don't intersect (a constraint in the problem definition), the heap remains consistent. This property is essential - if the distance ordering between two line segments could change depending on the angle, then a heap would no longer work. So, we can find the closest segment in O(1) time and insert new segments in O(log n) time. The reason the heap I used is "special" is because it also allows removing line segments (when they are no longer active) in O(log n) time. Inactive line segments can't just be ignored and left in the heap - they need to be removed to maintain a consistent distance ordering. In a standard heap, removing an arbitrary element takes O(n) time (since it takes linear time just to find the element). My heap contains an additional map structure from element value to heap index, so elements can be found in O(1) time. Once an element is found, we swap in the last element in the tree and propagate it either up or down (which takes O(log n) time) to maintain heap correctness. Hooray!

Wednesday, May 01, 2013

Visibility Polygons



I have released an open source JavaScript library for computing visibility polygons: https://code.google.com/p/visibility-polygon-js/

Demo: http://www.byronknoll.com/visibility.html

I don't think there are any other JavaScript libraries which compute visibility polygons. A few years ago I released a Java game that used visibility polygons.

Thursday, April 25, 2013

Google Bikes


An article about Google Bikes is currently on the homepage of wired.com. If you watch the video about conference bikes, I am one of the riders (facing backwards).

Saturday, April 20, 2013

Canvas Demo

http://www.byronknoll.com/geb.html

I didn't use webgl for this demo - just canvas polygons. This is actually the first time I have made a 3D rendering engine. For the simple model in this demo the framerate appears to be high (even on my phone).

Sunday, April 14, 2013

3D Prints

Here are some more 3D prints I ordered from Shapeways:







So, the second version of my monostatic body actually works! You can order the design from Shapeways.

Saturday, March 30, 2013

Monostatic Body

I received the 3D print of the one-sided die that I designed. Unfortunately it sometimes gets stuck upside-down on the unstable equilibrium. I have designed a new version which I think should fix the problem: http://www.shapeways.com/model/979729/monostatic-body.html. This version has a ridge on top which should make the unstable equilibrium... less stable:


The ridge causes the center of mass to raise a bit (to 0.9mm below the cylinder's center). I feel confident that this version of the shape should work - it will take about two weeks until I get the printed copy from Shapeways.

Sunday, March 17, 2013

One-sided die


Today I designed a one-sided die: http://www.shapeways.com/model/979729/one-sided-die.html

I have ordered a 3D print of the model.

A sphere does not make a very good one-sided die because it takes a long time to stabilize after rolling. The shape I designed has some interesting properties. It has only one stable equilibrium, so it will always rest in the same position on a flat surface. It is also homogeneous and convex. A gömböc is another shape with these properties. Unlike a gömböc, my shape has multiple unstable equilibrium points.

My shape is similar to a monostatic polytope described in 1969 by J.H. Conway, M. Goldberg and R.K. Guy. Here is a video demonstrating their shape:



Unlike Conway's shape, my design is smooth everywhere except a flat surface on the bottom. I added the flat surface to help it stabilize faster. It is actually very easy to construct my shape - it is the intersection of a sphere with a cylinder (ignoring the flat bottom). For the design I uploaded to Shapeways, the cylinder has a radius of 10mm and the sphere has a radius of 30mm. It was modeled using Rhino:


The highlighted point in the screenshot is the center of mass - it is 1.059mm below the cylinder's center. I am hoping that the center of mass is low enough so that the actual physical object always reaches the same resting point. Theoretically any center of mass below the cyclinder's center would work, but in practice inaccuracies in the 3D printing process could cause problems.

Friday, March 15, 2013

Gyroid



I ordered a 3D print of a gyroid from Shapeways. The material is alumide. I am very impressed with the quality of the print - I plan to create some of my own models soon.

Wednesday, March 13, 2013

RIP Google Reader


Google has announced that they are shutting down Google Reader. This is a sad day.

Wednesday, February 20, 2013

Rocket Launch

This weekend I launched a low-powered rocket at NASA Ames. The event was organized by the local rocketry club. My rocket was designed by my older brother. Here are some pictures:



NASA is definitely the coolest venue imaginable for launching rockets :). I am guessing there were 50-100 people at the event, with about one rocket launching every minute. One rocket actually fell on me while I was setting up my rocket. Its parachute didn't deploy due to a malfunction. Luckily its terminal velocity was not very fast, so it didn't hurt me. Here is a video of my first launch:

We determined that fire/ember from the engine traveled up the body of the rocket, burning the parachute and snapping the rubber cable which connects the two rocket segments. So the bottom rocket segment crashed without any parachute, causing the four fins to break off. After repairing the rocket with super glue we made a second launch attempt. The second launch was slightly better, but the parachute got tangled and did not fully deploy.

Sunday, February 10, 2013

Blob Balance

I have created a simple game based on the blob demo I made yesterday: http://www.byronknoll.com/balance.html

The blob will become harder to control as your score increases (caused by changes to a "fluidity" parameter).

Saturday, February 09, 2013

HTML5 Blob

Today I made a blob in HTML5 canvas: http://www.byronknoll.com/blob.html

You can interact with the demo by moving your cursor. This is the second time I have made a blob. My first blob was for a game I made called Time Stop. Since Box2D has a JavaScript port, I was planning to use Box2D for this project (here is a Box2D demo in HTML5 canvas).

However, I decided not to use Box2D when I stumbled across this amazing demo: http://www.ewjordan.com/processing/VolumeBlob/. ewjordan discovered a technique for simulating blob physics that is computationally efficient (much faster than Box2D), realistic, and extremely simple to implement. My demo is basically just a port of ewjordan's Processing code to JavaScript.

Saturday, February 02, 2013

Smooth Voronoi Diagrams

The paper.js project has a cool demo with polygon smoothing on a Voronoi diagram. For fun I decided to implement my own version from scratch.
The first step was to implement a system for polygon smoothing using Bézier splines. Here is a demo of the technique (you can click/drag to interact with the demo). The blue points are the original polygon vertices. For the Bézier spline, the midpoints become the vertices and the original vertices become the control points (making this a quadratic Bézier spline).

To compute the Voronoi diagram polygons I used this excellent JavaScript library. Next, I computed polygon centroids using this formula. To create the gap between polygons I scaled the vertices towards each centroid. Here is the final demo: http://www.byronknoll.com/cells.html. The blue dots are the Voronoi seeds and the green dots are the polygon centroids. You can click to create new Voronoi seeds (or drag to move seeds).

I am not completely happy with the demo since there are some "jumps" in the animation when new vertices are added to a polygon. I tried several ideas to make the polygon smoothing more robust to adding vertices, but couldn't find anything I was happy with. Imagine adding a new polygon vertex exactly on top of an existing one. It doesn't change the shape of the original polygon, but it significantly changes the shape of the smoothed version using my algorithm. Intuitively it seems like something that would be easy to overcome, but I haven't been able to figure it out.

Thursday, January 24, 2013

Response

In response to my last post, Jackie asks:
Not sure I understand your point about selling in as short a time window as possible. The day-to-day fluctuations of a stock's price is greater than its fluctuation over a week or so, right? But it might not be worth the extra transaction costs to sell over a time window.
I am replying here so the response is more widely visible. I claim that a stock should have much greater fluctuation at the end of a week than a day. In order to have less variance after a week, the stock would have to revert towards some sort of mean after the daily fluctuation. If this was true, I could use a simple strategy to make huge amounts of money in a short amount of time. I would look at a rolling average of one day for all stocks on the market. I would then buy the lowest stocks relative to their mean and then sell when their price hits the mean. The reason this strategy won't work is because stocks will not revert to a mean in the short-term. The reason they don't revert to a mean is because other investors in the market (especially high-frequency traders) would pick up on such an obvious pattern and take advantage of it. These traders would have a smoothing effect on stock price, ensuring that the price never reverts from the mean. Therefore I think it is necessary that variance increases the further into the future you consider.

Wednesday, January 23, 2013

Optimal Investment Strategies

I have recently become interested in the topic of investment. More specifically, I want to know:
  1. When should I sell my Google stock? Should I sell it all in one chunk or spread out the sales over a time window?
  2. How should I invest money that I currently have sitting in a bank?
I have been reading The Four Pillars of Investment for advice (as recommended by this post).

I was surprised to learn that there are actually provably optimal strategies when making these investment decisions. If you had asked me about this a month ago, I would have shrugged and said that it would be too complex to calculate an optimal strategy and that different experts in the field would probably give different answers. However, now I can say:
If you currently own stock in a single company (or a small set of companies), the optimal strategy is to sell immediately. The sale should be made as a single lump sum instead of spread out over a time window. You should then consider investing that money in an index fund.
The goal of investing money is to maximize expected profit for a given level of risk. The function of expected profit vs risk is monotonically increasing: with more risk you can always find an investment with higher expected profit. This fact can be used to make optimal investment decisions. If one investment has lower risk and higher expected reward than another investment, the optimal choice is clear. So, how can you calculate risk and reward?

It turns out that when investing in stocks, there is one fact that makes computing risk and expected reward much easier: regardless of how smart you are, you can not predict what a stock will do in the immediate future. You have zero information that is not already reflected in the stock price of a company. A company's stock price is a weighted average of a large number of expert investors. As with ensemble methods in machine learning, an individual can not compete with a weighted average of many expert predictors. Any investor who claims to be good at actively choosing a small set of stocks to invest in is wrong - even if they have an incredibly profitable investment history. In a room full of monkeys choosing to invest in random stocks, some of those monkeys would become rich due to natural variance in the profit distribution. I find this fact comforting - I am as good at predicting stock values as the best wall street investors (i.e. I can't).

There are certain exceptions to this:
  • When new public information is released, you can try racing other investors to take advantage of the information (i.e. high-frequency trading) using an algorithm.
  • In the long term, you know that the stock market as a whole will tend to revert to a mean value. It is profitable to invest more heavily during a bear market and sell during a bull market. Reverting to a mean does not apply to individual stocks in the short-term (otherwise it would be very easy to make money in the stock market).
  • In the very long term, you know that all stocks eventually go to zero (i.e. all companies eventually go bankrupt).
It is known that different classes of stock have different levels of risk. A company on the brink of bankruptcy has high risk. As expected, riskier stocks tend to have higher expected profit (this can be verified by analyzing historical data, as done in The Four Pillars). So, let's assume you are interested in investing in a particular "class" of stocks (i.e. a set risk level). Within this class, you do not have the ability to pick out good stocks - the expected profit of all these stocks is the same. So, should you invest in a small set of stocks or a large set? Well, given a set expected profit, you should try to minimize risk. You can do this by decreasing the variance of your investment - splitting your investment among many companies has a lower profit variance than investing in few. So, the optimal strategy here is always to invest in a large number of companies (i.e. index funds).

So, back to my problem of selling stock in a single company. The optimal decision is to sell immediately since I can get the same expected profit with lower risk using an index fund. Now the question of whether to sell in a lump sum or to sell over a time window. Once again, the expected profit of these options is roughly the same since I can't predict what the stock will do in the future. Which option has lower risk? I conducted a poll among some friends and most of them argued that spreading the sale over a time window has lower risk since it will smooth out fluctuations in the stock price. However, I argue that a lump sum payment has much lower risk. The "fluctuations" in a stock price are not centered about some short-term mean - if they were it would be easy to take advantage of this to predict stock price. Instead, the longer your time window, the more variance there is in the expected stock price distribution (which has an expected value equal to the current stock price). This means the longer your time window, the more risk you incur. Therefore the optimal strategy is to minimize the time window (i.e. make a single lump-sum payment).

Now on to my second question of what to do with money in a bank. Even if I am completely risk averse, there exist investments with a higher expected value and lower risk than storing money in an account without interest rate. Due to inflation, I think most bank accounts actually have a negative expected value. As for my level of risk-aversion, I will probably work on constructing a portfolio with a mix of different classes of index funds and bonds. Once I have constructed a portfolio, the only maintenance it needs over time is rebalancing.

So, does anything here sound controversial to you? If so, please let me know - I am still new to this and could be completely wrong. But as far as I can tell, I can compute the optimal investment strategy when comparing a small set of options.

Tuesday, January 22, 2013

Space-Saving Algorithm

Peter Norvig recently posted an interesting article about the frequency of different ngrams in a massive data set. A few months ago I worked on a similar problem.

Inspired by Peter Norvig's post, I decided to release my code for the space-saving algorithm as an open source project: http://code.google.com/p/space-saving/

I optimized the speed of the program and tried testing it on Wikipedia. The file I used was a XML dump of Wikipedia which is 42,544,528,073 bytes (39.6 GiB). I used k=100,000,000 (100 million internal buckets). Here are the results: Unlike last time, the counts reported here are exact. After an initial pass with the space-saving algorithm my program makes a second pass to compute the exact counts for the top buckets.

I ended up implementing my own hash table from scratch for this project. I figure that since this problem has some unique properties (such as a constant number of elements in the hash table), it would be easier to optimize my own hash table rather than using something more generic. I used linear probing to resolve hash collisions.

I found a way to improve upon one aspect of the standard linear probing approach. Typically deleted entries are marked with a special label, so a large number of <delete,insert> swaps would eventually fill the table up with useless deletion entries (requiring an expensive resize). My implementation doesn't use deletion labels and never needs to be resized. Instead, when an entry is removed I propagate the empty spot down until it reaches a free slot. Performing this propagation operation requires computing the desired position of subsequent elements (to know whether the element can be moved) to maintain consistency. This can be done efficiently in my hash table since the elements are integers - computing the desired position just requires a mod operation.

Wednesday, December 05, 2012

Laservex Updates

Since the original Laservex launch I have been fixing many bugs and adding features. I recently added the most commonly request feature: dragging the center of a mirror. There are also now over 50 levels (mostly thanks to dllu and GuiltyBystander). So, if you haven't tried Laservex since the initial launch, I encourage you to try it again.

The site had a nice initial traffic spike from Reddit and Hacker News but traffic has been dropping recently. I regret launching/announcing the site so early in development, since during the traffic spike the game was buggier and harder to interact with (which probably lost many potential users).

Saturday, November 24, 2012

Laservex Released!

I have finished implementing the game I have been working on for the last few weeks. Try it out at www.laservex.com.

Thursday, November 15, 2012

Saturday, October 20, 2012

laservex

I have started working on a new project: www.laservex.com. This will be a remake of a Java game I made a few years ago: http://byronknoll.com/lasers.html. This time I will implement it in HTML5 and support user-generated levels.

Wednesday, October 10, 2012

The Top-k Element Problem

I have been working on the problem of efficiently finding the most common items in a large stream of data. This problem shows up in many applications - I am working on it for a data compression project. One example application: given a stream of user queries to a search engine, find the top k queries which occur most often. Some Google employees published a fascinating algorithm for this problem called count sketch.

After reading through papers on the problem, I decided to use an algorithm called space-saving. I implemented it in C++ and have been testing it on the following task:

Problem: find the k most common substrings of length N in the Wikipedia database.

I haven't fully optimized my program yet, so I estimate it would currently take 4-5 days to process the 38GiB Wikipedia file I downloaded. I have some preliminary results on a subset of Wikipedia though - here is the output for k=1000 and N=1...30: Each row has two columns (tab separated). The first column is the substring and the second column is the count.

Since the time complexity of this algorithm is completely independent of k, I actually chose k=1 million and then took the top 1000 from the million buckets. The heuristic I used for choosing k was to use the largest value possible such that the memory used by the program did not exceed the available RAM on my computer.

Tuesday, October 02, 2012

Five Player Go First Dice

In a previous post I proposed a challenge to come up with a set of go first dice for five players. I thought my prize would be safe since this seems like a difficult unsolved problem. Paul Vanetti has successfully won the challenge with the following solution:
  • 0, 1, 2, 3, 4, 5, 6, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 259, 260, 261, 262, 263, 264, 265
  • 7, 20, 21, 22, 35, 36, 37, 50, 83, 96, 97, 98, 111, 112, 113, 126, 139, 152, 153, 154, 167, 168, 169, 182, 215, 228, 229, 230, 243, 244, 245, 258
  • 8, 12, 13, 14, 15, 19, 23, 27, 28, 29, 30, 34, 38, 42, 43, 44, 45, 49, 84, 88, 89, 90, 91, 95, 99, 103, 104, 105, 106, 110, 114, 118, 119, 120, 121, 125, 140, 144, 145, 146, 147, 151, 155, 159, 160, 161, 162, 166, 170, 174, 175, 176, 177, 181, 216, 220, 221, 222, 223, 227, 231, 235, 236, 237, 238, 242, 246, 250, 251, 252, 253, 257
  • 9, 11, 16, 18, 24, 26, 31, 33, 39, 41, 46, 48, 85, 87, 92, 94, 100, 102, 107, 109, 115, 117, 122, 124, 141, 143, 148, 150, 156, 158, 163, 165, 171, 173, 178, 180, 217, 219, 224, 226, 232, 234, 239, 241, 247, 249, 254, 256
  • 10, 17, 25, 32, 40, 47, 86, 93, 101, 108, 116, 123, 142, 149, 157, 164, 172, 179, 218, 225, 233, 240, 248, 255
These dice have the following number of faces:
  • 90
  • 32
  • 72
  • 48
  • 24
When I described the problem in my original blog post I did not specify any constraint specifying that the dice need to have the same number of faces. This constraint is unnecessary because:

Conjecture: Given any valid set of N go first dice with number of faces x1, x2, ..., xN, it is always possible to generate a new set of go first dice with exactly LCM(x1, x2, ..., xN) faces per die.

This can be done using the following algorithm:

Suppose you have go first dice with the following labels:
  • a1, a2, ..., aQ
  • b1, b2, ..., bR
  • ...
  • y1, y2, ..., yZ
Let m = LCM(Q, R, ..., Z). The following should be a set of go first dice with m faces:
  • m*a1, m*a1 + 1, ..., m*a1 + (m/Q) - 1, m*a2, m*a2 + 1, ..., m*a2 + (m/Q) - 1, m*aQ, m*aQ + 1, ..., m*aQ + (m/Q) - 1
  • m*b1, m*b1 + 1, ..., m*b1 + (m/R) - 1, m*b2, m*b2 + 1, ..., m*b2 + (m/R) - 1, m*bR, m*bR + 1, ..., m*bR + (m/R) - 1
  • ...
  • m*y1, m*y1 + 1, ..., m*y1 + (m/Z) - 1, m*y2, m*y2 + 1, ..., m*y2 + (m/Z) - 1, m*yZ, m*yZ + 1, ..., m*yZ + (m/Z) - 1
Example of how to apply the algorithm to a simple set of dice (which are not go first dice):
  • 1,2,4
  • 3,5
LCM(3,2) = 6, so the merged dice are:
  • 6*1, 6*1 + 1, 6*2, 6*2 + 1, 6*4, 6*4 + 1
  • 6*3, 6*3 + 1, 6*3 + 2, 6*5, 6*5 + 1, 6*5 + 2
Which becomes:
  • 6, 7, 12, 13, 24, 25
  • 18, 19, 20, 30, 31, 32
Empty regions can be removed to form:
  • 1, 2, 3, 4, 8, 9
  • 5, 6, 7, 10, 11, 12
Since LCM(90, 32, 72, 48, 24) = 1440, Paul's solution can be used to generate a set of 5 go first dice with 1440 faces. Paul says he found a technique to use a solution for N-1 to generate N go first dice (I do not know how this is done). His technique can be used to quickly generate solutions for any N. The solutions generated by his algorithm are not optimal in terms of minimizing the number of faces on the dice.

Tuesday, September 25, 2012

Go First Dice Problem

The Problem:

I encountered an interesting riddle recently called the "go first dice problem". The challenge is to come up with a set of dice (one per player) such that:
  • No two faces share the same label.
  • The dice can be used to determine a fair turn order for the players after a single roll. That is, the player with the highest roll goes first, the second highest goes second, etc. A set of dice is fair if and only if every possible turn ordering is equally likely given random rolls.

More Information:

There are some stack exchange threads discussing the problem: Eric Harshbarger (puzzle designer/Lego sculptor/programmer/mathematician/Scrabble player) sells a set of 12 sided dice that solve the go first problem for four players: http://www.ericharshbarger.org/dice/#gofirst_4d12. As far as I know there is no known solution for five players. For fewer than five players:
  • 2 players: minimum 2 faces
  • 3 players: minimum 6 faces
  • 4 players: minimum 12 faces

The Challenge:

Find a set of go first dice for five players. This will require at least 30 faces per die.

I have been working on trying to solve this (with a computer) for a few days. The search space is too large for a naïve brute-force search, so I think to make this computationally feasible you need to either:
  • find a clever way to constrain the solution space (to make it small enough to exhaustively search), or
  • come up with a heuristic so that your program is more likely to search in regions where a solution exists.

The Prize:

I will offer a small prize to whoever solves this challenge first. The prize will be a set of Eric's go first dice for four players - shipping paid by me to anywhere in the world. To claim the prize just email me with the solution and I will run a program to validate it. You can only claim the prize if you are actually the person who found the solution (e.g. don't copy it from someone). There is no set end date to this offer (as long as Eric continues selling the dice).

Sunday, September 09, 2012

Metamoku

The first release of Metamoku is ready! Try it out at: www.metamoku.com

Metamoku should work across different browsers, operating systems, and devices (including smart phones and tablets). Let me know if you encounter problems on any platform. Note that you can also play team games if multiple people choose the same color. When I was developing the game I was unsure whether it would actually be fun or contain non-trivial strategies. After playing some test matches with friends I think the game does have some interesting strategic components (especially the team matches). I currently don't have any major features/tasks left to implement. I will probably continue tweaking gameplay parameters as I get more experience playing games.

Saturday, September 08, 2012

Dark Souls PvP

I recently started my second playthrough of Dark Souls. Dark Souls is the best game I have ever played. I originally played Dark Souls on the PS3 - this time I am playing the PC port ("Prepare to Die" edition). That means now I can take screenshots!
Notice that the dragon's tail is missing - I did that.

Unhappy dragon.

This hallway is where I had an unforgettable experience. Another player had invaded my world to assassinate me (1v1 PvP). This is a pretty rare event when I play, so it is exciting when it happens. Luckily, this was the perfect place and time for him to invade - I had full health and the location could not be better. This narrow hallway leads to a dead-end, which means there is only one way in or out. That prevents my opponent from sneaking up with a surprise attack. My character is a pyromancer, which means that I am most effective at mid-range attacks. This hallway was perfect for my character because it forces the other player to walk directly into my spell range. So I waited in the hallway for him to attack. He spotted me from the end of the hallway and tried to lure me out - he can see my Pyromancy Flame so he knows that I have the advantage here. His weapon is some sort of dagger. Since I refuse to leave the hallway, eventually he cautiously approaches. When it looks like he is in my spell range, I start casting fire orbs at him. Impressively, he manages to stay far enough back to narrowly avoid my spells. When I advance he moves back, and when I move back he advances. So I continue casting the spell since I have plenty to spare. My spell is powerful enough that a single hit would make it very difficult for him to recover. Suddenly after one of my fire orbs misses him, he starts sprinting towards me. I cast another orb and it is headed directly at him. At the perfect time he does a dive roll under the orb and it narrowly misses him. He rolls past my side and stands up directly behind me. Before I have a chance to react he backstabs me and kills me with a single attack. The backstab attack is that powerful because it is so difficult to get directly behind a player. I was astounded at how perfect his sequence of moves was. As he was fading away to return to his world, he turned towards my corpse and bowed. I wish the battle had been recorded - it would have been fun to be able to watch it again.

Sunday, August 19, 2012

Metamoku

I have started working on a new game! HTML5 canvas! Network multiplayer! Turn-based strategy! Metaballs!

The name of the game will be Metamoku. A combination of metaball and moku (which is territory in Go).

I have been putting together various demos to experiment with rendering metaballs. It is actually a difficult problem to render them fast+smooth+accurate. I have tried three approaches:

Approach Speed Smoothness Accuracy
pair-wise Bézier curves Fast Good Bad
pixel rendering Variable Bad Good
border following Slow Good Good

Pixel rendering is the most common rendering approach. However, it can get very slow on large displays. Also, making the edges smooth is difficult. dllu made a two color demo.

Here are a couple demos I made with the pair-wise approach. These are just an approximation to the actual metaball function and are therefore not "accurate".

I found a great article about the border following approach here. This is the most complex of the three approaches. I implemented a demo here. Here is another demo where you can see some of the path-finding internals (red is border misses, blue is border hits). These demos don't have real-time rendering or drag-and-drop because it is too slow. However, this approach might be feasible for a turn-based game with one frame per turn.

Saturday, July 21, 2012

Password Management

The Problem:

  • Using the same password on multiple websites is known to be insecure.
  • Creating and remembering a different password for every website is difficult.

Solution:

My solution requires remembering two pieces of information:
  1. A single secure key.
  2. A simple string hashing function.
When registering for a website, generate your password by applying your hashing function to the domain name of the website (ignoring the top level domain) and append the output of that to your secure key. Voilà, you now only need to remember O(1) bits of information instead of O(N) to register N websites.

Example:

Step 1: generate and remember a single secure key. Let's say my key is now "0vDga5"
Step 2: generate and remember a string hashing function. Here is an example of a function to create a three character hash:
  • Character 1: The first letter of the string.
  • Character 2: The length of the string.
  • Character 3: The last letter of the string.
Now when registering an account on the following websites, my password would be:

gmail.com: 0vDga5g5l
imdb.com: 0vDga5i4b
a.ca: 0vDga5a1a
subdomain.domain.xyz: 0vDga5d6n

Thursday, July 19, 2012

Lossy Video Compression



Using a three dimensional DCT I can drop components from both the temporal and spatial dimensions. Here is what dropping high frequency temporal components looks like:

Sunday, July 15, 2012

Lossy Audio Compression

Here is an experiment I ran performing lossy audio compression with DCT:


[link]

Audio Spectrogram

Using FFTW I made a program to visualize audio spectrograms. The song "Windowlicker" contains an image hidden in its spectrogram - here is the output from my program:

Discrete Cosine Transform

Today I spent a few hours playing with discrete cosine transforms using the FFTW library. I have been experimenting using DCT for lossy compression in different domains. Here is a visualization I made of lossy image compression using an increasing number of frequency components:


[link]

Saturday, May 05, 2012

Elian Ambigram

Today I attempted to find an Elian ambigram. I wrote a small program to do a brute-force search through dictionary words to help. Out of all possible English words/phrases, it turns out only a handful of combinations are valid. The reason they are so rare is because Elian script has high rotational symmetry. The rotational symmetry adds constraints on how the ambigram can be constructed - standard Latin characters have far fewer constraints.

Sunday, March 25, 2012

symbols

This is a follow-up on my last post. Here are some comparisons of two symbols generated from the same class and displayed at the same orientation. I can adjust parameters on how much variance there is between symbols within a class - the parameters I chose are fairly conservative so that most symbols should appear very similar:

A New Kind of CAPTCHA

My goal for today was to create my own CAPTCHA system. I find CAPTCHAs fascinating because of their goal of distinguishing human intelligence from machines. Surprisingly, most major CAPTCHA systems (currently used by companies such as Google, Microsoft, Facebook, etc.) are routinely solved by computers with over 15% success rates (at least according to the brief research I did on the topic today).

Most CAPTCHA systems provide an image of a sequence of characters and ask the user to type in the text. Software that attempts to solve these typically first segment the image into characters and then classify each character individually. Character classification is a solved problem - so the only security behind current CAPTCHAs relies on the fact that character segmentation is difficult. In my attempt at creating a CAPTCHA system I will try to make both the segmentation and classification tasks as difficult as possible.

One of the reasons English letter classification is so easy is because there is a massive amount of training data available for each letter. In my CAPTCHA system, I will create my own symbols and provide only *one* training example for each symbol class. My hypothesis is that humans are better than computers at extrapolating from tiny training sets. Another benefit of creating new symbols from scratch is that it makes the system internationalizable (i.e. not dependent on the character set of a particular language).

Here is an example output from my CAPTCHA program:

The answer in this case is "1428736". First, I create 10 symbol classes and present one example from each class to the user. I then generate 7 symbols from random classes (no repetition) and arrange them from left to right (allowing overlaps). The user has to enter the symbol classes in the right order. There is a 1 in 604,800 chance of guessing correct randomly, or a 1 in 10,000,000 chance if symbol repetition is allowed. The symbols are displayed in random orientation.

The symbol from a particular class will look different between the training example and the main CAPTCHA. Each class is defined by a small set random parameters. These parameters determine features such as branching factor, curviness, length, etc. Once I have generated the random class parameters, each symbol is also created via a stochastic process - but its general appearance will remain visually similar to the other symbols in its class due to the class parameters.

Well, I suspect that this CAPTCHA system will not work well in practice because it is too tedious for humans to solve. On first impression I think this task seems more difficult to solve with a computer than typical CAPTCHA systems. It would be easy to evaluate the time/precision of humans solving these CAPTCHAs with a user-study. However, evaluating the performance of software solvers is more difficult. One idea I had for evaluating software solvers is to host a contest (say on TopCoder or Kaggle) and offer a big cash prize as incentive to make competitive AIs (I won't actually do this :P).

Here are a few more random CAPTCHAs from the program. I have posted the answers at the end of this post - how many can you solve without looking at the answers?

The answers are: 0718936, 9467251, 0197283, and 7634290 respectively.

Sunday, March 11, 2012

An API for Intelligence

Over the last few years I have made many attempts at creating artificial intelligence. By "artificial intelligence" I mean a general purpose system that can recognise and predict patterns in spatio-temporal data. I have written about this topic in some previous posts.

Spatio-temporal data is any data that has a temporal dimension and one or more spatial dimensions. Everything your brain perceives is a stream of spatial data over time. Any type of sensor (e.g. microphone, camera, thermometer) can create a stream of spatial data over time. The goal of artificial intelligence/machine learning/data compression is to look for patterns in this type of data and predict what the data will be in the future.

All of my AI projects have had essentially the same API. For those of you who speak Java: "double[][] perceive (double[][] inputs)". That is, a single function that takes a matrix of floating point numbers and returns another matrix of floating point numbers. The input represents spatial data at a particular moment in time and the return value from the function represents a prediction for the next input (the next time step).

A magic black box:

Let us imagine that I have a magic black box that does a great job at implementing this function. What could I do with it? Well the most obvious thing I can do is use it to predict the future. Let's use it to find out what the stock prices will be five years from now:

// Training.
double[][] stockPrices;
for (Time t = TimeOfFirstData(); t < Now(); ++t) {
  stockPrices = GetHistoricalStock(t);
  stockPrices = blackBox.perceive(data);
}
// Predict the future.
for (Time t = Now(); t <= FiveYearsFromNow(); ++t) {
  stockPrices = blackBox.perceive(stockPrices);
}
return stockPrices;


Of course, these estimates wouldn't be very accurate because in reality stock prices depend on a vast number of different types of data (which I didn't give to the black box as input). If I gave the black box additional data in the input matrix (such as local news stories, earning reports, weather sensors, etc.) it would do a better job at predicting stock prices.

What else could I do with the black box? If I want to have a conversation with it or make it control a robot, I would need to give it some mechanism to perform actions. Let's imagine I naively plug a light bulb into a random cell in the output matrix of the black box (and the light bulb turns on/off depending on the value of that prediction). This light bulb is now an actuator - it gives the black box a mechanism to interact with the environment. There is now a feedback loop where the black box can influence the value of future sensor readings by changing the light bulb prediction. How would the black box choose which action to take? Well, the only "goal" of the box is to minimise the difference between its predictions and what actually happens in the future. Maybe turning on the light bulb allows the black box to make more accurate predictions of future sensor values, so it "decides" to keep the light on. If I hook up a speaker and microphone to the black box, maybe it will decide that having a conversation with me will also allow it to make more accurate predictions about the future (which is probably true).

The Magic Number:

Hopefully in the previous section I convinced you that if this one function was implemented correctly, it would result in something most people would consider true AI. So, why did I choose a matrix of floating point numbers? Why not simplify the API by just making it a single array instead? Why not a higher dimensional matrix? The answer is because I think that two (as in a two-dimensional matrix) is the magic number that makes a reasonable trade-off between competing factors. Using a higher dimensional space would make implementing the function infeasible due to computational complexity. Using a lower dimensional space loses critical information about the spatial relationships between sensors. As evidence of this information loss, imagine converting a two-dimensional image into a one-dimensional array of pixels. The image would become meaningless to you because you have lost the information of how the pixels are spatially arranged.

Let us consider the most intelligent system we know of today: the human brain. I think that the human brain is complying to the same API I described above. In fact, we only need to look at a part of the brain known as the neocortex. The neocortex is a thin sheet of neurons on the outer surface of the brain. It is responsible for essentially all higher-level thought and what makes humans intelligent. Since the neocortex is fundamentally a two-dimensional surface, it uses topographic maps to project higher-dimensional signals onto a two-dimensional space. For example, the three-dimensional touch sensors on your body are mapped onto a two-dimensional homunculus on your neocortex, where regions that are neighbouring in 3D space are also neighbouring on the homunculus (and regions which are more important are mapped to larger regions on the homunculus).

So, how close are we to being able to implement AI? I think so far the most successful efforts come from the field of data compression. A compression algorithm called PAQ8 does an amazing job of implementing "boolean perceive (boolean input)". However, it doesn't scale well to continuous numbers or higher-dimensional spaces. Another promising attempt at creating AI is coming from Numenta in the form of hierarchical temporal memory. So far their attempts have been unsuccessful, but I think at a higher level their approach to the problem is the best I have seen.

Saturday, February 25, 2012

Project Euler

Over the last few months I have been solving programming problems on Project Euler. I currently have solved 140 out of 373 problems. Since I have been solving the problems in order of increasing difficulty, my progress will probably slow down now that I have finished solving all of the easy problems. There is a great range in the difficulty of the problems - there are probably some problems that I couldn't solve even if I spent weeks working on them. If you have a Project Euler account, feel free to add me as a friend: 13166529170291_2172f964a0c5e4a2e5a4d6e690c97cb8

Game Playtime

Today I beat The Legend of Zelda: Skyward Sword. It was an amazing game - better than The Legend of Zelda: Ocarina of Time in my opinion. I noticed at the end of the game that my total playtime was recorded as 41 hours. Out of curiosity, I have gone through some of my save files from other games and compiled a list of how long it took me to beat each game. Unfortunately the game that I probably spent the most time playing, Baldur's Gate II, doesn't record total playtime.

Title Playtime (rounded to the nearest hour)
Dark Souls 57
The Legend of Zelda: Skyward Sword 41
Demon's Souls 40
Valkyria Chronicles 24
The Elder Scrolls V: Skyrim 21
Red Dead Redemption 15
Mass Effect 2 15
Heavy Rain 14
Dead Space 11
Uncharted 2: Among Thieves 11
Super Smash Bros. Brawl 10
ICO 7
The Secret of Monkey Island: Special Edition 5

See this post for a list of my favorite games (four years ago).

Monday, November 21, 2011

InnoCentive

I found a cool website called InnoCentive. They currently host 116 active competitions - some of them with million dollar prizes. Most of the contests seem to be about solving open-ended problems in science/engineering. I have made a submission to the "Strategy to Assimilate Unstructured Information" contest (which ends in four days). There is a similar website that hosts competitions for machine learning problems called Kaggle.

Facebook Removes RSS Importing

When I logged into Facebook today I was greeted with this message:
That's right, Facebook is removing the ability to import RSS feeds. I am not very active on Facebook, so people commenting on my automatically imported blog posts is one of the few ways I still use the service. Now that this functionality is removed, my usage of Facebook will drop significantly. I have the suspicion they are removing it for a bad reason. I have noticed that the amount of time it takes for RSS feed items to be imported to Facebook can sometimes take several days. Why would it be so slow? Google Reader updates my feeds in a matter of minutes. I think the only reason Facebook would be so slow at importing feeds is if it is an expensive process and they don't want to spend the resources to update more often. The feature is obviously good for users, so the only reason Facebook would have to remove it is to reduce costs.

Sunday, November 20, 2011

e-sports

I spent the day watching the MLG Starcraft 2 championship. This is by far the most entertaining sport I have watched. I bet it would be fun to watch even for people who have never heard of Starcraft. It is definitely attracting a growing audience in the US and should start showing up on TV networks soon. I started cheering for the South Korean player Leenock while he was in the losers bracket, several rounds before the finals. I was thrilled when he continued winning round after round, making his way out of the losers bracket to eventually win the competition and a $50,000 prize. Incredibly he is only 16 years old! Before this contest almost nobody had heard of Leenock, so it was exciting to watch him defeat world-famous sc2 players one after another.

Leenock's rise to fame reminds me of another young e-sport competitor: tourist. tourist is only 17 years old but has proven himself to be one of the world's best competitive programmers. I find it shocking that tourist/Leenock can become the best at their respective fields at such a young age. It shows how genetics and innate intelligence/talent plays a crucial role in these sports, since their age obviously limits the number of years they have spent practising. I think since competitive programming is a pretty good measurement of human intelligence, tourist may also be one of the smartest people in the world. It will be interesting to keep track of what he eventually accomplishes in his career.

Monday, November 07, 2011

rpscontest.com is down!

A while ago I created the site rpscontest.com - a rock-paper-scissors programming competition hosted by Google App Engine. The site is currently down due to exceeding its quota. This is because today App Engine introduced a new pricing model. With the old pricing model my quota usage was $0 per day. With the new model it is about $13 per day, or about $4,750 per year. Seriously? That is a ridiculous increase in price. Of course this basically forces me to shut down the site or redesign how it works. For now I have disabled all automatic ranked matches which should bring it back into the free quota (at the same time making the site completely useless because the rankings will no longer update). I can only assume that the price increase has a larger impact on me than typical users (possibly due to the type of resources I use to run matches). The only reason I make this assumption is because if everyone is hit by the price increase as badly as me, nobody would continue using App Engine. I am not happy.