cat /proc/claus

Two days ago I went to this Nomikai (work-related drinking “parties”) with some industry contacts of my lab. While the nomikai itself was not very exciting (I don’t really like this kind of Japanese event, but that’s for another post), I had a nice little neat idea while chatting there.

One of the research topics addressed in my laboratory is the use of Evolutionary Computation to assist in music composition. Basically, a EC algorithm generates multiple small pieces of music, which are evaluated by the human composer, and those evaluation scores are sent back to the computer, which try to generate a new generation of pieces similar to those which received a high score. This particular framework of evolutionary computation is called “Interactive Evolutionary Computation” (IEC) [1], because the fitness function is a human operator, and not a algorithmic function.

A big issue IEC is “user burden”. Evolutionary computation is based on scoring multiple candidate solutions, many times - when this evaluation is done by a human, instead of a computer program, the user may get tired after scoring too many individuals. To avoid that, it is important to either use the least amount of evaluations as possible, or make the evaluation as quick and painless to the user as possible - a lot of research has been done in both areas.

Now, the idea - how about using the concept of crowd sourcing to IEC? Instead of having one user evaluating the songs, we would have multiple users evaluating them in a asynchronous manner. The example we thought up would be a website where, say, mobile ring tones are generated by EC, with downloads and user evaluation being used as scores. Every few days(?), these values would be used to generate new tones, which would replace the old ones. This could not only generate more interesting tones, but also be able to “track” or “follow” fashions or memes of users.

A quick google search on the above keywords seemed to reveal that this is still a new idea (nothing relevant shows up on the first page for “crowd-sourcing IEC” and “crowd-sourcing composition” only show non-EC approaches [2]). Try it while it is fresh. Brainstorming in the comments is welcome

Links
[1] IEC on Wikipedia
[2] Crowdsourcing Composition

Today in the University meeting my professor told me that my pre-thesis defense will consist of an one hour presentation, followed by an one hour Q&A session. Since my Master Thesis presentation 2 years ago here in Tokyo university was a paltry 20 minutes, I was both relieved and a bit apprehensive. I was thinking that maybe one hour was a bit too much (I was expecting more like 40 minutes), but talking to Y I realized that among the three techniques and two problem I will have to explain and discuss at length, one hour might even be too little. Anyway, I’m breathing a little easier now that I know exactly how much time I have available - now I just need to do the work. I just wished they would give me the damn deadline already so I could prepare my schedule better.

Also, In today’s meeting we had visitors from another laboratory which presented to us their research on DNA computing. DNA computing is a sort of wet computing where you use the chemical reactions between DNA strands as the processing units. They were explaining their work in developing an AND gate with DNA. To be honest, I was not very impressed. I had heard before of wet computing before (maybe chemical computing?), and in my mind the state of art in this was a bit more evolved. But in their presentation, one AND operation would take more than one hour to complete, and they would need to do the experiment from scratch to change the data inputs. I wasn’t very convinced (although the rain might have made me grumpier than usual). Either you try to emulate electro-mechanical computing, but do it faster, or you get some new operators to do different stuff (like quantum computing). Could someone enlighten me about what I’m missing here?

In other news, RPG game tomorrow, and I got a pretty neat series of encounters for my players. Report coming from Sunday on

They say that for every problem there is a solution which is simple, elegant, and wrong. I found mine today while working on ETD, and I also find the correct solution (which is also elegant, although a bit less simple).

One of the rules of the “Tower Defense” games is that you cannot completely lock the path that the enemies take from the entrance to the exit of your maze. This path may be as long as it takes, but it must exist. In my implementation, I’m writing in each cell of the path the cost to go to the exit, so that each enemy does not need to calculate their exit paths all the time. Then I have to have a “locking detection” routine that detects if placing an aditional tower in a given location will lock down the maze or not, to prevent that tower from being put.

My first idea was to see what are the distance values of the cells the new tower is going to occupy. If those values were not repeated anywhere else in the maze, that means that that path is a bottleneck, and cannot be blocked. Thinking this solution for a bit while showed that it was wrong (exercise to the reader :-P). The new solution is thus: The entrance and the exit of the maze bissect the surrounding walls into two groups. I give each of this group a flag, and I check each tower when it is put down to see if it connects to one of the groups. If it does, I give it the same flag as the group. If a tower connects BOTH groups, then it means that it blocks the path from the entrance to the exit. I only have to deal with the special case of “island” towers, by giving them a third, “neutral”, group flag, which is painted 1 or 2 when one of the groups reaches the island.

I have not finished implementing the above, but I have implemented most everything else that I needed from the map. I did not have as much time to program today as I had yesterday because I used the bright sunny day to walk around a little bit, clean my home (including washing the dreaded bath), and meeting my friend Dionisio. All in all, I had about 4 hours to hack away at ETD today, and I think I managed quite a bit in this time. Tomorrow I’ll finish implementing the maps, then a bit of tower logic, then link the genome with the tower and the map I hope!

I woke up 2 in the afternoon today. Even when I was staying awake for days at a time when I was writing that article last month, I never had crossed the AM/PM line for waking up. I wonder if it is the cold - today was a constant 8 degrees during the whole day, and everyone I called for a coffee out said they couldn’t go, so I end up staying the whole day at home…

Which means that I had plenty of time to keep hacking away at my Python problem :-). Today, I tried a more direct approach by try and coding directly the functions I needed, stopping to google a concept or another when I ran into something I did not understand. This worked surprisingly well, as I managed to intuitively use the list constructs and function in python to easily implement my genome, mutation, crossover operations, as well as population mechanics, like elite, sorting, tournament selection, etc. I did find my share of bizarre bugs, like once when I got confused about instance and class scopes, and that resulted in a constructor operator which generated bigger and bigger individuals in geometric progression and ate up all my computer’s memory in just 4 generations, but by the end of about 6 hours I managed to have a fully fledged evolutionary system (although with a dummy evaluation function). Tomorrow I’ll try writing the engine for my ETD game/evaluation function.

Besides that, I also read up two chapters in the new book I have started “Here Comes Everybody”, by Clay Shirky. The book talks about and tries to explain the phenomenon of the massive, loosely linked community actions, like wikipedia or flickr, based on the idea that the cost to maintaining social connections has collapsed in the past few years, which allowed non-profit actions which were too expensive for informal communities to organize, but too unprofitable for formal companies to tackle, to flourish. Reading the book I can’t help but feel that I had heard all this talk in many different blogs, forum/slashdot comments, and Free Software talks, but it is always nice to see everything put together in one cohesive, well argued text, and with plenty of interesting anecdotes to illustrate the concepts.

Talking about books, last week I also read “A Wizard of Earthsea”, by Ursula K. Le Guin, and I really really recommend this book. I devoured it in less than 2 days. This book is one of the precursors of Medieval Fantasy, and the wizards and how the magic works in Le Guin’s world is too charming. The concept that a Mage is just as powerful as he knows and understand the world around him draws you into her world. I hope I can make my own D&D world as mystical and still consistent as hers.

And that’s for a very cold and gray Sunday. I got one of my three bases covered

While finishing the paper for the ECF conference (or to put it in a more honest way, while procrastinating playing DTD in Kongregate when I should have been finishing the paper for the ECF conference), I had this idea: What if I wrote a GA that evolved a labyrinth for DTD?

After that, the flood of ideas came through (and the paper was quickly forgotten for an hour or two). I drew a quick scheme for the genome representation and for the rough simplified game to be used as the fitness function, and then I realized that this would be no fun at all if I didn’t program a small graphical front end for the program.

While thinking about this, I dreaded trying to delve into Java’s swing to program what should be a very simple cartoonish interface for a non-interactive game. I thought for a second about finally taking the time to learn the curses library, then it hit me. If I’m to learn something new, I might just as well finally get that goal of learning python off the self!

So here I am, reading a bunch of python tutorials, and some pygame examples for the Gui. Luckly, I found a half-made DTD clone in pygame which is running, so I can probably use that when I finally get to the “getting things on screen” stage, but right now I’m still struggling to write a basic GA loop in the language. More specifically, how to use the fancy tuples to implement crossover functions. Gah, things are too different, but at least I’m off to a start already. Tomorrow and Monday are Japanese Holidays, so with some luck I get a large chuck of the project started by then and can write some more precise details… but for tonight - reading, reading reading.