Das doofe Fischlied

February 26th, 2010

This remarkably silly song demonstrates how case and gender affect article, attributive adjective, and noun suffixes in German.

Das doofe Fischlied

Der guter Mann, Ein guter Mann
Der guter Mann, Ein guter Mann

Schlag den guten Mann nicht!
Schlag einen guten Mann nicht!
Schlag den guten Mann nicht!

Der guter Mann, Ein guter Mann
Der guter Mann, Ein guter Mann

Schlag den guten Mann nicht!

Gib’ dem guten Mann einen Fisch!
Gib’ einem guten Mann einen Fisch!

Das schöne Haus, Ein schönes Haus
Das schöne Haus, Ein schönes Haus

Schlag das schöne Haus nicht!
Schlag ein schönes Haus nicht!
Schlag das schöne Haus nicht!

Das schöne Haus, Ein schönes Haus
Das schöne Haus, Ein schönes Haus

Schlag das schöne Haus nicht!

Gib’ dem schönen Haus einen Tisch!
Gib’ einem schönen Haus einen Tisch!

Die kleine Maus, Eine kleine Maus
Die kleine Maus, Eine kleine Maus

Schlag die kleine Maus nicht!
Schlag eine kleine Maus nicht!
Schlag die kleine Maus nicht!

Die kleine Maus, Eine kleine Maus
Die kleine Maus, Eine kleine Maus

Schlag die kleine Maus nicht!

Gib’ der kleiner Maus einen Fisch!
Gib’ einer kleiner Maus einen Fisch!

Die gute Freunde, Meine gute Freunde
Die gute Freunde, Meine gute Freunde

Schlag den guten Freunde nicht!
Schlag meinen guten Freunde nicht!
Schlag den guten Freunde nicht!

Die gute Freunde, Meine gute Freunde
Die gute Freunde, Meine gute Freunde

Schlag den guten Freunde nicht!

Gib’ den guten Freunden einen Fisch!
Gib’ meinen guten Freunden einen Fisch!

This song really helped me learn the somewhat messy attributive adjective suffixes. It gives you a handy way to practice them. (One pattern from here that never escaped me is that of the nominative and accusative forms of neuter: “There’s always exactly one ’s’,” meaning that das is followed by schöne but ein is followed by schönes.)

Solving the Rubik’s Cube? There’s an app for that.

February 25th, 2010

image

I’ve long been enamored of robotic Rubik’s Cube solvers. There are many of these out there (most built of Legos) that typically feature everything necessary to complete the solution autonomously. These pieces are as follows:

  1. Read the cube pattern (generally by taking a picture of each side of the cube and analyzing it).
  2. Generate an efficient solution.
  3. Execute each step mechanically.

Recently it struck me that a sufficiently hackable mobile phone could be used to provide everything from the camera to the control via USB or Bluetooth. “That would be a fun application to write,” I thought, for my Android phone, a Google Nexus One. Alas, I haven’t the funds, knowledge, or time necessary to build the robotic component of that.

My dreams dwindled a bit.

But then I thought of something else, something so incredibly obvious that I figured it had to already exist. Some searching around, however, revealed nothing of the sort, so I’m going to announce the idea here:

ARCS, the Augmented Reality Cube Solver.

See, generally augmented reality works when you have markers to track, as otherwise you’re basically limited to geolocational stuff and have to collect all kinds of information to make it work. With visual tags, the problem is much simpler, and a Rubik’s Cube already has 54 visual tags on it: the color-coded stickers.

By detecting the stickers and tracking movement, the application could not only orient the cube in 3D space, but also read each face’s state as the user turns the cube before the camera. Once the entire cube state had been recorded, the application could generate a solution and (here’s the really cool part) overlay the solution step-by-step on the image of the cube itself! Imagine 3D arrows flowing along the layers of the cube, indicating which to turn. As the cube is solved, the application recognizes the new state and shows the next step. If at any time the cube diverges from the expected next state, the app can figure out what the user did wrong and show a correction step.

Now that OpenCV has been successfully implemented on Android, I think this is well within the range of possibility. I don’t know if I could do it myself, but I know someone could, and I think it would be a fantastic app.

Got any other cool augmented reality or general Android app ideas? Sound off in the comments!

Infinite Whiteboard

February 5th, 2010

infinite whiteboard logo

Infinite Whiteboard is the unassuming title I’m applying to this project of mine. The goal is to create a project planning tool that does what it says on the box. It’s a whiteboard on which the user can simply start drawing objects anywhere. Image files can be uploaded and dropped onto the board, vector drawings can be annotated with notes, chunks of the board can be clipped and saved to doodles, links can be made from one area to another. Imagine a whiteboard that you can zoom, pan, save, annotate, and search, and you have the Infinite Whiteboard project.

I’ve mentioned this before. It’s what I want Cogspace to be. While WordPress is great for what it is intended for, it falls somewhat short as a freeform idea foundry, so that’s what I want to create.

Data & Dice

February 4th, 2010

The need for truly random data is quite common, but as any engineer can tell you, true random data is hard to come by. Computers are incapable of generating truly random data. Although some systems do a pretty good job of it, e.g. by collecting entropy from chaotic processes like keyboard and mouse usage, disk access, error corrections, etc., even these methods often fall short of cryptographic randomness.

There is, however, one class of number generator that is rather easy to come by and is about as close to truly random as one can come without using quantum events like radioactive decay. That device is the humble die.

Dice have been used for thousands of years to provide entropy for games, and they can also be used to provide entropy for computational needs. One particular task I often have is to generate a PIN for Second Life scripts to be used for security. This PIN is in the space of all 32-bit integers, meaning it is in the domain [-2^{32} \cdots 2^{32}-1].

The easiest way I have found to do this is using four eight-sided (octohedral) dice, commonly used for Dungeons & Dragons, in which they are referred to as “d8″. The d8 I have are, as are most, number from 1 to 8, so I just treat 8 as 0 and use the other digits as they are, meaning each d8 gives me one octal digit. Four of these then give me twelve bits, which is three nibbles, so if I roll these 4d8 three times, I’ll get 36 bits, giving me the 32 bits I need plus four extra, which I just cut off the end.

In order to guarantee good random rolls, I keep the dice in a clear plastic tub (previously used for almonds) and just give it a good shake, then hold it at an angle so the dice line up along one of the bottom edges, then read them off left-to-right. Here’s an example:

Roll 1 Roll 2 Roll 3
0 3 4 1 0 1 4 7 1 1 1 2
0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 0
0 E 1 0 6 7 2 4 A

Note that the last four bits are discarded, meaning onle the two most significant bits of the second-to-last d8 only count, and the entire last bit doesn’t count. The output value, in this case 0×0E106724, represents a full 32 bits of random data. I also use this method to generate chat channels, which are typically kept negative to prevent client eavesdropping. In these cases, I just force the most significant bit to 1, since that will guarantee a negative number.

That’s all there is to it! I have also seen 16-sided dice, which would generate 4 bits of data, so you could just roll 8d16 (or 4d16 twice (or 2d16 four times (or 1d16 eight times))) to generate the 32-bit integer, but d16 are an awful lot harder to find than d8.

If you’re stuck with six-sided dice, you can get two bits out of them by assigning 6 to 00 and re-rolling on 4 or 5. This would require twice as many dice (or rolls) as using d8, and could also be done with d4 (where 4 would be 0 and all other values would be their normal values). This does not skew results as the chance of landing on each of the valid sides is equal (1/6). d6 would be less efficient than d4, though, since 1/3 of rolls would be invalid (4 or 5). The reason there’s no way to make use of 4 or 5 is it would introduce skew, e.g. using the values directly would mean 6 and 7 would never be possible, and trying to do something like use the 1/3 bit of entropy provided by the extra faces would be more work than it would be worth, and I’m not certain it’s probabalistically even either.

Stay tuned for more random crap!

(pun very much intended)

On the Busting of Moves

February 2nd, 2010

Growing up, I spent many a weekend in the Family Fun Zone, a local arcade known for its apparently custom-built massive Ghostbusters game and convenient proximity to Shakey’s. Most of my fondest memories involve the familiar cadence of tokens vanishing into loud, imposing arcade cabinets and hasty trips to the aforementioned eatery to beg Dad for more fiat. I still get that fluttery feeling of potential when I trade paper for coin to pry repast from a mechanical vendor. Those percussive plinks – one, two, three, four – may well have been my primary mathematical educator. What value has a five-dollar bill beyond its facility to conversion to twenty tokens? I haven’t a clue.

There were many familiar haunts in those days: Golden Axe was a favorite, as were the fast classics. Pac-Man. Dig-Dug. Donkey Kong. Centipede. Being the youngest person in the pinball aisle seemed a badge of honor. It was an homage to the true progenitors of the medium. I’m going to go play the pinball games, I’d think. Why? Out of reverence.

Every trip concluded with at least a few rounds of air hockey. Dad almost always won, but over time, my brother became the true master of compressed air and plastic pucks. The sound of the puck entering the goal slot is as satisfying a sensory memory as the plinking of tokens in the change machines, those dutiful money-changers of the realm of the arcade, converting your hard-earned greenbacks into worthless metal slugs. One-way foreign exchange. No cash value. But as long as Arcadia stood, those embossed metal rounds were good as gold.

One game above all others captured me deeply, though – deeper even than the Western-themed side-scrolling shooter in the Shakey’s that formed a sort of cathartic ritual after the post-gaming Bunch of Lunch – and that game was Puzzle Bobble, a.k.a. Bust-a-Move.

Bust-a-Move is one of those rare games that is so perfectly designed that it can truly stand as a monolith of the industry. It’s trivial to learn, exciting and addictive, and the potential for racking up truly monstrous scores (the theoretical maximum being somewhere around thirty million) affords near-infinite replay value. Whoever AAA is, one would think, their 16,000,000 cannot stand forever! This game continues to be one of my favorite games of all time. The music’s familiarity is right up there with Tetris and Mario Bros.

Fast-forward to modern times, and the arcade has gone the way of deinonychus. That once-powerful fraternity of flashing, blaring audiovisual gods has been deftly deposed by the gaming console trinity, and the somewhat shamanic realm of the personal computer. The plaza-mall which once held, in addition to a fabulous snow cone shop and a Crown Books, that doomed Shakey’s and the Family Fun Zone is now all but vacant. Only the Edwards 10 remains, under new management as a three-dollar theater clinging to life on razor-thin margins, if life it can be called.

Taito’s legendary bubble busting puzzle game is now the property of Square Enix, by whatever sorcery has led to this being the case, and it is a good case for it to be. As it has been in countless other fashions, Bust-a-Move has now been remade on the Android platform, and I could not be happier. Sure, the graphics are a little  different, the music doesn’t speed up as the ceiling falls, and the fact that it’s on a mobile phone instead of a massive cabinet, while convenient, is also somewhat disingenuous to the original experience, but for $4.99, and at this level of polish, I am utterly thrilled. I feel as though I’ve been given the opportunity to enjoy a lifetime of Bust-a-Move for a mere score of tokens, which once I would have squandered in a single Sunday session. Besides, nostalgia is a bargain at any price.

Speaking of which, I wonder where I put that Family Fun Zone token. I located one – who knows how it escaped that vortex – but seem to have misplaced it. A damn shame, too. That token is, to me, like a Japanese occupation peso. Coin of a realm that no longer is, it has no worth, and yet for me, a former citizen of that land, it holds fast to emotional – I’d go so far as to say cultural – significance. It is the currency of my homeland, whose national sport might well be Skee-Ball, and for me, at least, is as priceless as it is worthless.

In close, and, if I may myself so indulge, in verse, let me an anthem propose:

Rest Ye Well, Arcadia

Rest ye well, Arcadia,

Though thy temples fold,

Thy gods dismissed, thy roads untread,

Thy halls vacant and cold,

Rest ye well, Arcadia,

Thy people prosper yet,

And ne’er will they thy memory

Nor thy fair games forget.

Rest ye well, Arcadia,

Thy purpose doth endure.

Although thy sovereignty is past,

Thy legacy is sure.

Strip Iterated Prisoner’s Dilemma

February 1st, 2010

In light of this, I’m going to propose a rule set for strip iterated prisoner’s dilemma.

For those unfamiliar, the Prisoner’s Dilemma is a standard example in game theory. The setup goes thus:

Two prisoners (who acted together) are accused of a crime. Each is given the following deal: Betray the other prisoner, and they can walk free while the other serves 10 years in prison. The catch is that if both betray, both serve 5 years instead of one going free and the other serving 10 years. If they both remain silent (“cooperate” with each other), then they each receive a brief 6-month sentence for the only thing the cops have enough evidence to pin on them.

So to make this a strip game, we just need to change the rules a bit:

  • Alice defects, Bob defects: Each player removes two articles of clothing.
  • Alice defects, Bob cooperates: Bob removes three articles of clothing.
  • Alice cooperates, Bob defects: Alice removes three articles of clothing.
  • Alice cooperates, Bob cooperates: Each player removes one article of clothing.

It’s unfortunate that articles of clothing are such coarse score units. I’m thinking a system whereby players accumulate points and every time they pass n points they have to remove an article of clothing might work better, but hey, it’s Strip Iterated Prisoner’s Dilemma. How polished need it be?

ZEN

January 27th, 2010

ZEN

On Intellectual Property in Virtual Worlds

January 24th, 2010

Consider, if you will, the problem of a virtual world whose participants retain intellectual property rights over their creations. How can such a world keep its residents honest in their dealings? How can people do business in a space where copying someone’s property is trivial?

To illustrate the problem, let’s imagine a virtual world in which Alice, Bob, Eve, and Charlie are participants.

Alice is a content creator. She designs objects that people might like to decorate their worlds with. She works hard at it, and feels she deserves to get paid for her work, so she sets up a store in her world that sells the objects for her. The store accepts micropayments from a major online payment processing service and delivers a copy of the object to the purchaser in return.

Now let’s meet Bob. Bob is a musician. He does live streamed concerts in his world and needs some high-quality decorations to wow his fans. His friend Charlie tells him that Alice has designed some awesome stage lights that would really spice up the performances. Bob goes to Alice’s world and buys a set of the lights. Alice makes a few bucks, and Bob has new lights for his stage. All is well with the (virtual) world.

But now Eve enters the picture. Eve doesn’t care about Alice’s intellectual property rights. Maybe she disagrees with them on philosophical grounds, or maybe she’s just broke but still wants stage lights. Either way, she decides she just has to have a copy of those lights. Now, most world browsers prevent people from copying other people’s stuff in the UI, but that’s just to keep honest people honest. There’s no way for the object not to get downloaded to Eve’s computer. How else is it going to be rendered when she gets to Bob’s concert? Eve sees those lights at Bob’s next concert and, talented coder that she is, simply copies the object right out of her cache and into the directory where her own objects are kept. She places the lights in her own world, and since Alice doesn’t keep careful track of who has bought her lights, there’s no way to know anything is amiss.

The solution to this problem is quite simple. Let’s re-imagine the situation with the following modifications:

Each user is assigned a unique cryptographic keypair for security reasons: They use these keys to log into the system securely. It’s exactly the same security used by banks to secure transactions and by secure software distribution channels to sign packages that have been vetted to be free of malware.

Whenever a user creates a new object, it is signed with his or her private key. The user’s public key is kept on file by the registrar and used to verify objects. What the signature contains is the owner of the object, their basic rights (whether the object is allowed to be copied or modified, used in derivative works, etc.), an optional license reference to specify what licensing the object is provided under, the creator of the object, and other information that is to be protected from forgery.

Now, when Bob buys a copy of Alice’s lights, he gets a set of lights that says that Bob is the owner and is signed by Alice’s private key. In essence, this is a license provided by Alice to Bob describing the agreement under which the object was furnished. The server can then check that when Bob places an object in his world, it really belongs to him. And even if Bob were to maliciously modify his server to disregard the discrepancy, other users connected to Bob’s world would be able to see it (since there’s no way for the server to show a certificate deeding the object to Bob if no such certificate exists – Alice’s private key guarantees that.

Now when Eve goes to copy Bob’s lights, she has a problem. If she copies the lights without changing them, she’ll have a set of lights that says “property of Bob.” Clients connecting to her server would be able to recognize the discrepancy and Alice would have solid evidence to invoke a DMCA takedown if she so desired. Everyone would know Eve had stolen the lights – and perhaps even worse, they would know from whom she had stolen them.

Eve could copy it and strip the signature, then resign it under her own name, saying “property of Eve,” but then anyone who saw the lights in her world would see that Eve had supposedly created it, and so anyone who recognized they were actually Alice’s design would know of the fraud.

Of course, this system is not perfect. It’s simply not possible for such a system to be perfect. Even if the graphics were rendered on a server somewhere and streamed to clients so that the object data never had to be sent to the client, anyone determined to steal content could take images of the object from various angles and reconstruct it using computer vision software like CCV. Sure, it would be harder, but the performance penalties would outweigh those gains completely.

Not to mention, someone would be paying an awful lot for their super beefy server rendering graphics for every user. What a mess.

One further addition must be made to handle open content, so let’s consider Charlie. Charlie’s a big believer in open licenses. He uses an open-source operating system, writes a column under a Creative Commons license, and generally dislikes DRM and such. So when Charlie finishes a desk he’s worked hard on and wants to share it with the world, he simply places a copy in his world and deeds it to *, a special reference that indicates that the object belongs to everyone, and anyone can then copy it and place it in their own worlds.

Note: it is important to realize that servers still keep track of who placed what in the world. This is to prevent (at the world owner’s discretion, of course) people from moving objects placed by other people. This dialogue has been concerned with the asset itself. When a copy of it is placed in a world, that is more accurately called an “instance” of that asset, just as the desk you are probably sitting at right now is not desk. It is not the concept of desk. It is a particular desk, with its own set of unique traits (where it is, whether it is clean, what is on it, etc.)

An asset is the combination of a copy of the object data and a license for it. An instance of an asset is the combination of a reference to the asset and a set of information particular to the instance – who placed it, where it is, which direction it is facing, etc.

I think I’d very much like to build a world on these principles and others, but I’m starting to realize that I just don’t have that kind of free time.

Delgar Ambigram

January 14th, 2010

I’ve been doodling a lot more ambigrams lately. I would love to find a good design for a Delgar logo, and I think this is pretty good, but it still needs some work. It took a while to get the E/G looking good, but the D/AR still needs a little tweaking and the L needs lots of help before it’ll satisfy me:Delgar AmbigramIt’s not a bad start, though. I should get those oddities smoothed away soon.

What do we think?

A Badge of Honor

January 12th, 2010

Last night I was looking at ambigrams, which are typographical creations which can be read multiple ways. The most common form is one which looks the same after a 180 degree rotation. I decided to mess around a bit with it, and came up with this, inspired by the Abbadon font:

QA ambgigramIt could use some polish, but it’s quite readable as “QA” from either perspective. It’s a good symbol for a profession so often turned on its head.

I think I’m going to make more of these.