27 Sep 2009

Under Gavin's suggestion, I've been watching The Prisoner, a 1960's British television show. The main character is an ex-spy held prisoner in "the Village", an Orwellian, isolated, enclosed town. No one in the Village has a name, but is instead assigned a number. The main character's number is 6.

As far as I can tell, after number 2 the order of the numbers is not important. Number 56 is no more important than number 12. By using numbers to name things there is an implied ordering, even if the the ordering is insignificant. It could be misleading to a newcomer.

Is there an unordered set could be used to name things? More specifically, is there a set that cannot be ordered? If it is unorderable then there is no implicit ordering to cause confusion. It's easy to have an unorderable set in theory, but I think it is difficult to have in practice.

Using letters is obviously out, as the alphabet has an order. Words and names made of letters can be sorted according to the alphabet. However, the ability to order words is almost never used outside of indexing. If words are used to name things, a newcomer is unlikely to assume relationships based on ordering. No one will assume Alan is more important than Bob.

Large numbers also tend to lack an assumed order. I don't think anyone assumes a larger or smaller social security number has meaning, or a larger or smaller phone number. However, these values are also known to be handed out in some semi-random way.

But can we do better? For at least English speakers, is it possible to create an unorderable set? If the items in the set have a vocal pronunciation, then they can probably be ordered by their phonetics. That could be avoided by using non-standard phonetic components, like clicks and pops, which won't have a standard ordering (in English, anyway).

A set has an order if there is a total, transitive, relational operator for the set. If such an operator does not exist then the set isn't linearly ordered. I want a set that can't easily have such an operator.

If a set of symbols was created, how might they be presented as to show no ordering. The order of the symbols in the original presentation might be considered the ordering, like how the alphabet is always presented in order. A circle could be used, but this is circularly ordered. I think there is also the issue of memorization. A human will have a much better time memorizing the symbols if memorized in some order. For example, try naming all the letters of the alphabet at random, without repeats. Or US states.

Thanks to modern day technology, with dynamic content, the set could be displayed in a random order each time it is viewed. For a web page, the server could select a random order, or a JavaScript program could reorder the images at random.

There could be partially ordered sets, like hierarchies and DAGs. The ordering in The Prisoner is one of these. There is number 1, then number 2, then everyone else. Is there a partially ordered set in use that has unique names at the same level?

The penalties incurred by intentionally prohibiting order would likely outweigh the benefit of the set. If it's not orderable, we can't index it, and it's difficult to deal with. I expect it's much easer to just use numbers and tell people that the order isn't important, or just use an obviously unordered set.

02 Sep 2009

In the summer of 2007 my friend, Michael Abraham, and I wrote a robot programming game in Matlab. The idea came out of a little demo he wrote where one circle was chasing another circle. Eventually the circles could be run by their own functions, then they were shooting at each other, then dropping mines, and so on. It was dubbed "Matbots".

It turned into a little programming competition among several of us at work. Someone would invent a new feature, like cooperative bots or bullet dodging, that would allow it to dominate for awhile. Then someone else would build on that and come up with some other killer feature. At one point we even hooked up a joystick so we could control our own bot live against our creations.

I never shared that here. Someday I will.

Anyway, Mike took a little bit of the Matbots code and design and came up with a new, similar game called SumoBots. Programmable bots are in a frictionless circular playing area with the ability to accelerate in any direction. Collisions between bots are governed by a spring force dynamics. Bots are out of the game when they leave the circular area. The goal is to knock out all the other bots. Here's a video,

I like how smooth and natural that looks.

He got a number of people at his lab to code up some bots to compete. I threw the code up over at bitbucket, a Mercurial host, which you can checkout with,

hg clone http://bitbucket.org/skeeto/sumobots/

(I haven't convinced anyone else over there to use a version control repository, let alone this one, but here's hoping!)

You can use either Matlab or Octave to program your bot. It works in both, with Octave being on the slow side. For Octave, you'll need to define a cla function as a call to clf (they don't define it for some reason). To start coding a bot, just look at the samplebot bot for information on programming a bot. Edit the players in player_list.txt, then launch it by running engine (engine.m).

I wrote one bot so far called bully. It charges at the nearest bot, being careful to cancel out its own velocity. In the video above this bot is red.

The other bots so far is kyleBot, blue in the video, which passively runs circles around the outside of the surface hoping to trick aggressive bots, like mine, into running out. The bot2fun bot, black in the video, is like bully, but tries to keep safely near the center of the playing area. The brick bot, green in the video, is a dummy, practice bot that just gets knocked around.

The tricky part in writing a bot is managing the frictionless surface. Acceleration can't just be in the direction you want to travel, but also against the current velocity. You might want to set up some kind of process control for this.

Right now I think there is a balance issue. Passive bots have an advantage, but the game won't progress if everyone takes this advantage and writes passive bots. It's like camping in a first-person shooter. As a partial solution to these stalemates, Mike has proposed that the playing surface should shrink over time.

If you want to join in, grab the code and start coding.

01 Sep 2009

This website/blog turns two years old today. That's right, the first post was on September 1, 2007. This also happens to be the 100th post! Woo! Which means I have nearly kept up with my original one post per week planned average (104 would put me on schedule).

The site has evolved a bit in that time. Two years ago I was using vanilla blosxom (I've since hacked it up), no comments, no portrait (portraits increase reader trust), simpler logo, no color, no RSS (it was there, but I wasn't linking it), crappy index, no features but this blog and the "projects" section, no Creative Commons license (but I've always had the other simple copyleft statement), no lisp, and only one permalink per post. Since I started this site I lived in three different US states, had two different jobs, bought two computers, bought a car, adopted a cat, learned several programming languages, graduated with a bachelor's degree, had major surgery, and got married.

I've tried to make all my posts more than a trivial "hey, check this link out", and instead have some real content for each one. Thanks to this, if you concatenate all the posts together it's long enough to be a short book (about 170 pages). And, this blog is 100% Free Culture. All text and images are public domain or under a Free license (and none of that non-commercial-only crap). So I -- or anyone -- could easily publish it as a book. (Ha! As if anyone would buy it!) And I do maintain another completely separate blog, with a (currently) higher post frequency, under a pseudonym (so I don't get myself into trouble), which is why I won't tell you what it is. :-)

I'm really happy I kept kept this "log" of my activities. I've had some real misconceptions about my previous self, which the log has cleared up. I often think I came up with ideas or had viewpoints much more recently than I really did ("Oh, learning Scheme really was that long ago."). I wish it went back further, because, for example, I really am not sure at which point I became an atheist (early 2003?) or a libertarian (summer 2003?). I tend to think of my previous self as more stupid than I really was, which gives me this false impression of intellectual progress, when really I am as dumb as I ever was! I know one one thing for sure, my writing hasn't really improved!

So, thanks for reading! If you don't already have a blog, start one today. Keep up with it, and at two years I'm sure you'll be really glad you have it.

Here's to another two years!