oh github pages

I didn't realize it, but the little webpage http://dglittle.github.com/smiley-slider on github that shows the smiley-slider in action had been broken. Whenever people would go to dglittle.github.com/smiley-slider, they would be redirected to glittle.org/smiley-slider, which was nothing -- a 404.

This redirection happened as a result of me setting up my homepage glittle.org to be served from github, which involved having github redirect dglittle.github.com to glittle.org. Apparently this breaks all my project pages.

This behavior is apparently foretold in a tip at the bottom of this article. Paraphrasing, it says: project pages like dglittle.github.com/smiley-slider will be redirected to things like glittle.org/smiley-slider unless they have a file telling them to redirect somewhere else. Of course, the very next tip says that they won't actually be redirected anywhere if there is such a file.

Which is strange. But great. It means that maybe I can fix my problem by adding a file to the smiley-slider repo telling it to redirect to some bogus domain, like example.com (except specifically not example.com, since github knows that that domain is bogus), which would cause it not to redirect anywhere. In particular, causing it to not redirect to glittle.org/smiley-slider, which is nothing -- a 404.

This did work. Sortof. I thought the behavior would be that it wouldn't redirect dglittle.github.com/smiley-slider anywhere, but the actual behavior is that it does redirect dglittle.github.com/smiley-slider to glittle.org/smiley-slider just like before, except that miraculously, glittle.org/smiley-slider shows the content held in the smiley-slider repo. And I have no idea what it would show if the homepage repo happened to have a directory called smiley-slider.

Anyway, I'm confused, but it seems to work. However, this means I need to put a bogus file in all my projects telling github that they are being served on some domain that they are not being served on. I suppose one alternative is to have my homepage in a regular project, so it doesn't cause dglittle.github.com to redirect, but that would mean having my homepage it a github branch called gh-pages, rather than master, which seems confusing, but maybe less confusing.

[update: now I do have my homepage in a regular project so it doesn't cause dglittle.github.com to redirect]

DotTracker

..going through old crap, I found this "DotTracker" program. It's something I wrote in undergrad for, um, tracking colored dots in video. Here's a description of the algorithm I found in a file appropriately labeled "writeup of algorithm.txt", though I can tell it's a rough draft, because the file has above it some text where I was obviously writing a new/better description, but never finished:

Orange Dot Tracking Algorithm

Consider a "tracker" to be an object capable of tracking a moving dot in a video sequence.

The tracker is defined by a center, a color, and a size:

center - the x,y position of the tracker within a frame of video; this variable is updated every frame

color - the color that the tracker is tracking; this variable is initialized to the color of the pixel that the user clicks on when "placing" a tracker. This variable NEVER CHANGES once it is initialized.

size - the algorithm essentially examines a square set of pixels centered around the "center" of the tracker; the "size" variable defines the size of this square.

The crux of the tracking algorithm is an update function which centers the tracker on a splotch of color.

Here's an image in that directory that I used for testing. Note that the dots on my arm are not orange, but green. Apparently the algorithm could track any color, not just orange ;)

The code is now on github: https://github.com/dglittle/DotTracker

near

Summary: Answer the question to the right, and see how other turkers and blog readers answered similar questions. After you answer the question, the red dots will show where people answered "yes".

This is just for fun. Stuff like this has been done before. For instance, this CrowdFlower post shows what names people give to different colors.

I had originally wanted to ask if the dot was "above" the bar, but I feared the result might look to boring, like a rectangle.

Technical tid-bits:

The url in the iframe is exactly the same url I posted on MTurk. The JavaScript detects if it is being viewed on MTurk and does two things. First, if it is being viewed in preview mode, it overlays a grey rectangle with the word "preview" to prevent people from accidentally answering the question before they accept the HIT. Second, it makes it so that answering the question submits the HIT, rather than showing the results. The utility function for submitting the HIT creates a form with the necessary elements, including a dummy result so that MTurk doesn't feel left-out -- this is necessary, since MTurk considers it an error to submit no results. Of course, the actual result is submitted to my server via ajax before submitting the HIT.

I only use one API call to MTurk, and that is to create the HIT. I don't get results, and I don't approve people. I don't get results because they have already been submitted to my server, and I don't approve people because they will automatically be approved after one hour -- this is a parameter when creating the HIT. But Greg, doesn't that mean people can cheat? Well, yes, but I find that people typically don't cheat on questions like this, because they're simple and kindof fun. Also, I wouldn't know if they did cheat. Each person is only allowed to answer the question once, so I can't even see if their results are statistically improbable.

Another tidbit is that I sometimes have unrealistic scalability fears, like "what if lots of people read this post and answer the question, endlessly increasing the size of the data structure until it takes forever for people to download?" So, I made this data structure have a maximum size: there are a finite number of points it will ask about (you can see them arranged on a grid after you answer the question), and it just records the number of yesses and noes for each location. But Greg, that doesn't really limit the size of the data structure, since the number of yesses or noes can grow infinitely. True, but first, that is a scalability issue I'm willing to sleep at night with, and second, JavaScript numbers cannot actually be infinitely large, like Python numbers can. I think JavaScript uses 64-bit floating point numbers under the hood. So at some point, the data structure would just be wrong, rather than too big...

screen

problem: I created an EC2 machine, and I want to start some long running script, and I want the script to keep running even after I close my terminal session.

solution: A friend introduced me to "screen". I type "screen", which opens a sort of virtual terminal, and I run my command within that, and then I press Ctrl-A and then D to "detach" from the session but keep it running. I can reattach with the command "screen -R". Apparently it is just the nature of screen itself to keep running even if I close my terminal session, so I can "exit", log in again, type "screen -R" and I'm back to the command I ran, and I can even see all its output.

perl vs grep

A friend at work claimed that perl uses NFAs and grep uses DFAs. He gave this example regular expression: (a?){30}a{30}. Then he ran the following command:

echo "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" | grep -E "(a?){30}a{30}"

which found a match instantaneously. Then he ran the following command:

perl -e "print \"match\\n\" if 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' =~ /(a?){30}a{30}/"

About 5 minutes later it printed "match".

I get the impression that grep really does convert a regular expression into a DFA, which is cool, though I seem to recall that DFAs can get pretty big for some evil regular expressions. I'll have to try giving it such an expression.

I get the impression that perl is a bit more ad-hoc than using NFAs -- I think perl can do more powerful things than NFAs support. However, it does appear that perl is not converting regular expressions into DFAs.

note to self: scrollbars in HTML

getting scrollbars to work inside of divs in HTML seems difficult sometimes. A trick to get around this is to put that stuff in an iFrame. Of course, iFrames seem like they'd take a while to load, and separate the code, BUT, we can really load a dummy iFrame with nothing in it (as long as it's in the same domain), and programmatically place stuff into it from the outside frame.

stories about programming

First Program

When I was 8 or so, my dad taught me how to program. We didn't have a computer, but he told me some BASIC commands. I was captivated by the idea. I wrote my first program on graph paper. Each square had space for exactly 2 letters. This seemed very computerish to me.

The program was a math game. You could choose which sort of problems you wanted to do: addition, subtraction, multiplication or division. Once you chose, it would give you a random math problem of that sort, and ask for your answer. Then it would tell you if you were right or wrong.

That week, I got the opportunity to type my program into an Apple 2e at my uncles house. I typed in all the commands, and it ran perfectly the first time. I was hooked.

The Idea of a Model

I was impressed by a 3d maze game I played. You could only look exactly north, south, east or west, and the maze was designed such that no matter where you were or where you looked, it always looked like you were looking down a hallway with passages branching off like open doors.

I decided to recreate this game. The first thing I did was draw a maze on graph paper. I designed it such that the view from any position would have the same property of looking like a hallway with passages leading off at various points.

Then I started manually drawing the view from each location in each direction, with the idea that I would add code after each view to take you to the appropriate next viewport depending on which direction you pressed.

This turned out to be a lot of work, and I was about to give up when my dad gave me an idea: "instead of drawing the views manually, why don't you store the location of all the walls in some variable, and then have the program figure out what the view should look like from where you're standing?" This insight was like magic, flipping a huge switch in my brain. This may be one of the most important lessons I ever learned in programming.

mturk blunder

Ugg.. so I created a hit using mturk's own designer interface with the following HTML:


<h1>Please make this sketch look good.</h1>
<p><img src="http://example.com/my_sketch.png" alt="" /></p>
<p>Upload your version when you're done. Thanks!</p>
<p><input type="file" name="drawing" value="" /></p>

This does not work. Apparently.

The results have a "drawing" field, but it just shows the filename of the file that was uploaded. The actual file is irretrievable.

My mistake is a repeat of a mistake made by someone on this stack overflow question.

Alas.

UPDATE: so, I was able to get a couple of these images using the NotifyWorkers API call, telling my workers that the drawing was lost, and asking them to e-mail it to me.

penrose tiling

penrose tiling using canvas

bluffing

question: is bluffing ever a mathematically optimal strategy?

answer: I think yes, for some definition of optimal.

let's define 'optimal strategy' as the best strategy to have if your opponent knows what strategy you have. That is, they know what algorithm you will use to make decisions.

By this definition, the optimal strategy in rock-paper-scissors is to choose randomly. If you don't choose randomly, and your opponent knows the distribution over your choises, then they'll choose the thing that beats the thing you are most likely to pick.

Now consider a simple betting game. The deck has only four cards: the jack, queen, king and ace of ❤'s. Each player is dealt a card randomly, which they can look at. Both players begin the betting by putting 1 gold into a pot. One player goes first. They can either 'call' or 'raise'. If they 'call', betting stops, and the player with the higher card wins. If they 'raise', they add 2 gold to the pot. The other player can then 'fold' -- automatically forfeiting the pot -- or 'call', adding 2 gold and giving the pot to whoever has the higher card. The game alternates who goes first each round.

You can play against the computer (nemesis), by pressing 'play' to the right. I'll tell you nemesis's strategy:

If nemesis goes first, it will only raise if it has the ace -- unless it has the jack and decides to bluff, which it will do with 50% probability.

If nemesis goes second, it will usually only call a raise if it has the ace, but there is a 25% chance that it will also call a raise with either a queen or king.

I believe that this strategy is optimal. That is, I don't think you can win all of nemesis's gold no matter how you play (unless you are genuinly lucky, or read nemesis's mind using the Javascript console, or.. I'm wrong ;)

Why do I think this strategy is optimal?

Short answer: it involves Linear Programming.

Longer answer: well, we usually play games by reacting to each bit of information we receive when we receive it, but we could, if we wanted, decide before the game even begins how we will react to each possible thing that can happen. For instance, if we are going first, we can decide before the cards are dealt how to react to each card, e.g., 'only raise if we get an ace'. If we want to bluff, we can make that decision before the game begins too, e.g., 'raise if we get an ace or a jack'.

Now there are four possible cards, and one decision to make given each card (call or raise), which gives us 2⁴ or 16 possible ways to play. If we go second, there are also 16 possible ways to play (there is only one choice to make for each card, namely: if they raise, will we call?). If we want to incorporate randomness, we can do so by choosing randomly from among the 16 options.

This lets us build a 16x16 matrix, where each row represents a way to play when going first, and each column represents a way to play when going second. The cells hold the expected transfer of gold given two ways of playing against each other (where positive amounts favor player one, and negative amounts favor player two).

Each player needs to choose a strategy. We can represent each player's choice as a 16 element vector: each element represents the probability of chosing one of the 16 possible strategies, so the elements must sum to 1. If player one's vector is A, and player two's vector is B, and the 16x16 matrix of expected winnings is W, then the expected winnings of player one versus player two is A * W * B^T, which will be a single number.

Now imagine that we're player one. We have some control over what A * W will look like. Note that it will be a 16 element vector. Note also that player two, being evil, knows what our strategy is. That is, they can look at that 16 element vector, and find the most favorable element of it for them, and adjust B so it has a 1 corresponding to that element, and a 0 everywhere else. Hence, we want to adjsut A so as to maximize the minimal element of A * W. This can be done with a linear program. We can also use the same technique, transposing everything, to find the optimal strategy as player two.

I generated such a Linear Program in JavaScript, combining both problems into a single program. You can see it by pressing the button below (and you can inspect the JavaScript of the frame to see how it works). The variables look like 'p1s0'. This represents player one -- the player going first -- strategy 0, which is the strategy of never raising.

It turns out there is a Linear Program solver written in JavaScript too: http://www.zweigmedia.com/RealWorld/simplex.html.

It tickles me to see an LP solver in JavaScript, though it does have a couple nuances: first, it requires each variable to appear in the objective function, even if we're just multiplying it by 0. Also, it implicitly adds the constraint that each variable be positive. This was a problem for my program, and is why you'll see the magic number 10, which effectively allows p1 and p2 to be 'negative', i.e., as low as -10.

The solution is p1s8 = 0.5, p1s9 = 0.5, p2s8 = 0.75, p2s14 = 0.25. This means that player one should choose strategy 8 half the time, and strategy 9 half the time. Strategy 8 is 'only raise with the ace', and strategy 9 is 'raise with either the ace or jack'. Likewise, player two should choose strategy 8 with 75% probability, otherwise strategy 14. Strategy 8 for player two is 'only call a raise with the ace', and strategy 14 is 'call a raise with anything but the jack'. (Note: this is not the only solution. p2s8 = 0.5, p2s12 = 0.5 also works, where strategy 12 is 'call a raise with a king or ace'.)

cyclic json

I think it's useful sometimes to serialize cyclic data structures as JSON. Douglas Crockford wrote a nifty way of doing it here. The basic idea is to "decycle" a data structure before serializing it as JSON, replacing redundant references to an object with string-paths pointing to a single version of that object within the data structure. When deserializing such an object, the original links are restored with a "recycle" function.

I had two concerns with Crockford's implementation: First, I was afraid it would be too slow. Crockford's comments point out that each time the algorithm processes an object, it does a linear search to see if it has processed the object already, i.e., O(n²) running time. My solution (premature optimization?) is to add a tag to objects in the original data structure, and just check for this tag when processing new objects. These tags are removed before the method returns.

Second, Crockford marked cyclic references with an object that looks like this: { "$ref" : "$[\"path\"][2][\"object\"]" }. This breaks if an object happens to contain "$ref" as a key. My solution is to find a unique key, which means I need to say somewhere what that key is. (update 1/30/12) I do this by adding a wrapper object with a property called "cycle_root". The wrapper object has another property where the key is the cycle_root, and the value is the decycled data structure. Press "run me" above to see what this looks like. You can also play with the code to see how different data structures are handled.

(update 1/4/12) Third, the original algorithm processes the objects depth first. Now it processes the objects breadth first. To see why this might be useful, consider an array where each element contains a pointer to the next element in the array:

depth-first (old)

{
    "cycle_root": "root_0",
    "root_0": [
        {
            "next": {
                "next": {
                    "next": {
                        "next": "root_0[0]"
                    }
                }
            }
        },
        "root_0[0][\"next\"]",
        "root_0[0][\"next\"][\"next\"]",
        "root_0[0][\"next\"][\"next\"][\"next\"]"
    ]
}

breadth-first (new)

{
    "cycle_root": "root_0",
    "root_0": [
        {
            "next": "root_0[1]"
        },
        {
            "next": "root_0[2]"
        },
        {
            "next": "root_0[3]"
        },
        {
            "next": "root_0[0]"
        }
    ]
}

glicko rating

I've been using the Elo rating system for talent court. I like that the update rules are very simple. However, people come into the system with a score of 1500, and if they lose, then their score drops below 1500, meaning that they are listed below people who have never played. I feel like this can be discouraging: "I'd be doing better if I never played." One hack I've seen for dealing with this is to only give people a score after they've played a few games, which is what I currently do.

More recently, I read a bit about TrueSkill, and saw a clever trick to deal with this problem. First, TrueSkill represents each player's skill with a gaussian distribution (mean and standard deviation) rather than a single number. If a player wins, their mean will increase, and their standard deviation will generally decrease, since more is known about their skill.

Now here's the trick: instead of showing people their mean skill, we show them their mean skill minus a few standard deviations. Conceptually, we show them a score that we are ~99% sure they are better than. This does something a little counter-intuitive -- if you play your first game, and lose, your score will increase. Actually, your mean score decreased, but your standard deviation decreased more, such that the mean minus three standard deviations actually increased. This has the emotionally pleasing property that people's scores generally always increase the more they play, where better players' scores increase faster.

This system also has a nice way to reduce people's scores over time. Why would we do that? The cynical reason is that we want to keep people playing, by making their score go down if they don't. A more diplomatic reason is something like: because the scores are only meaningful when compared to other people's scores, and because new people are coming into the system all the time, we want to keep people's scores up-to-date. Another way of saying this is that we become less and less sure of a person's score over time. This way of looking at the problem suggests a clever solution: we can represent this decrease in certainty by increasing a player's standard deviation, which has the side-effect we want of reducing the score that they see.

So why is this post titled "glicko rating" instead of "TrueSkill"? Well, TrueSkill is sortof an extension of the Glicko rating system, where the main contribution of TrueSkill seems to be adding support for teams. I don't care about teams for now, and the glicko system is simpler to implement, i.e., the update rules are on wikipedia.

Up above is a widget you can use to see what happens to two player's scores (labeled r, for rating) and standard deviations (labeled RD, for rating deviation, I think). Press one of the "win" buttons to see what happens when that player wins. You can also modify the r's and RD's directly. Note that I show gaussian distributions to represent red's and blue's skill, whereas I've read here that the Glicko system actually uses a logistic distribution.

Up above is also a JavaScript function that implements the update rules. You're free to take this. The glicko system itself is public domain, and so is this function. Note: don't go looking for the "actual" source code for that function in the html. What I "actually" do is call eval on the html pre element that you see above.

smiley slider

John Horton commissioned this thing on oDesk.. I need to get the name of the developer. It uses an html5 canvas and bezier curves to create a continuum of emotions as you slide it. Here is the source code.

etherpad-lite ec2 ubuntu

To install etherpad-lite on an EC2 Ubuntu instance, log into it and do:

sudo apt-get install gzip git-core curl python libssl-dev pkg-config
sudo apt-get install build-essential mysql-server

mysql -u root -p
create database `store`;
grant all privileges on `store`.* to 'root'@'localhost' identified by '';
exit

git clone git://github.com/joyent/node.git
cd node
git checkout v0.6.18
./configure
make
sudo make install
cd ..

git clone 'git://github.com/Pita/etherpad-lite.git'
cd etherpad-lite
bin/installDeps.sh
vi settings.json
    comment out the section that sets the database to 'dirty',
and uncomment the default mysql section that is commented out bin/run.sh press Ctrl-C mysql -u root -p ALTER DATABASE `store` CHARACTER SET utf8 COLLATE utf8_bin; USE `store`; ALTER TABLE `store` CONVERT TO CHARACTER SET utf8 COLLATE utf8_bin; exit bin/run.sh & 

my first jsonp

Just saying that jsonP is amazing. That P stands for padding, but I think of it as standing for procedure.

So I had my own server with a webpage that would show me music that I listend to. It did this with a server-side request to last.fm to get my listening history.

However, then I moved my site to github, and I couldn't run any server-side code. So now I need the client to make a request to last.fm to get my listening history. AJAX you say? But our betters have decided that making AJAX requests to other domains is bad, and last.fm is on another domain.

But, it's ok for the src attribute in a <script> tag to reference any domain. So you can dynamically add a <script> tag with a src attribute that effectively makes an API call to last.fm. The only issue now is, how do you see the results? If last.fm just fills the script with JSON, it will be parsed by the client, and promptly forgotten. So instead of getting a script like {"some" : "json"}, you instead want doSomethingWith({"some" : "json"}), where the doSomethingWith(...) is padding, or a procedure. Now if you implement doSomething, and then add the <script> tag, then doSomething will be called with the JSON data you want. Horray.

To see this in action, see: http://glittle.org/#music