Friday, March 25, 2011

Cursor-10 Clojure bot

Usually when I say I love using programs to solve problems for me, I'm referring to some kind of machine learning. Today, I mean I'm using the raw power of automated mouse control beat a flash game that was pissing me off.

Cursor-10 is a strange and unpolished Japanese game. Try it out here.

Since its been my latest toy, I decided to write the bot in Clojure. I could have chosen Python, but manipulating the mouse is much easier in Clojure due to Java's Robot class. To be honest, the entire thing could have been written in something like AutoIt, but I wanted to take advantage of the abstractions available with Clojure's Lisp syntax to make everything as clean as possible.

Like I said, my choice of Clojure meant that I could take advantage of Java's Robot class- awesome. However, mouse-click actions are a side effect in Clojure land, meaning that its lazy evaluation made my Robot calls never happen. I needed to sprinkle doseq and dorun calls all over the place to force the side effects to actually be resolved. Not a huge deal, but it was the source of most of my debugging headaches.

So now I know how I'm going to play this game- clicking using Clojure/Java's Robot class. Next I need to know where to click. For some rapid prototyping, I started by manually entering coordinates for interesting game elements: crystals, ladders and boxes. This quickly proved an inadaquite solution... there must be a better way!

The better way was to use ImageMagick to programmatically find the coordinates of elements. Check out this blog post to see the details of how I did that.

It would have been awesome to use ImageMagick in real time to make my program more dynamic, but the computation took WAY too long for that to be possible. So I created lists in Clojure of everything I wanted to click on on each floor. These lists are currently contained inside the main module of the project, but it may have been cleaner to put them in their own text file and load that file on program startup.

After all that, I had a working bot. Check it out:

I win! The video starts at the final cursor (the only one that grabs crystals and gets points), but start at the beginning to see them all in action.

Note that I did give the bot some manual interaction; I started each cursor at the appropriate time. I could figure out the time between each level and make the bot fully autonomous, but that sounds like a lot of headache that I could devote to something more deserving.

The project source is available on github. There's a helpful README to get you started.

Thursday, March 24, 2011

ImageMagick subimage search

As part of a larger project, I needed to find the coordinates of any instances of a small image inside a larger image. Here are the two images:

I think you can guess out what my project was. Anyway, using ImageMagick's subimage-search to get the desired coordinates (all those pyramid shaped crystal things) was pretty easy. Here is the command I used to analyze floor #11:

This outputs a new grey image, with a white spot corresponding to the location of every match. Check it out:
Note the white spot in the center of each crystal- those are the matches we're looking for! If we tell ImageMagick to output a text file, we get a list of coordinates:

Note the coordinate with the color of "white." Now we're getting somewhere- a numerical coordinate corresponding to a match. Here is a quick one-liner I used to parse the coordinates out of the file:

This grabs all the lines of the file that contain 'white.' It then uses awk to parse the raw output into something more useable in Clojure:

Done! Now we have a coordinate list of all the crystals in the image. Check out how I used it in a future blog post.

Tuesday, March 22, 2011

Inno Setup checkedonce flag in Code section

When using Inno Setup, you can set flags to any of the optional [Tasks] your installer might be preforming. We were using the 'checkedonce' flag for one of our tasks at work to make sure the Task was set by default only the first time we ran the installer on a machine. When we brought this Task into our [Code] section to be run by a custom Wizard page, we lost our checkedonce functionality.

The issue at hand is that we want to set the flag to be True if we are installing for the first time on a user's machine, and set to False if we are performing an upgrade. If we are preforming an upgrade on a machine, we should be able to find the Inno Setup app ID in the registry, stored here:
If we find this key, we know the installer has been run before, and we are preforming an upgrade. If we can't find it, it's a new install. Here's the code to check if it exists:

Note that we check both HKLM and HKCU, because [I think] the application install information could live in either one.


Sunday, March 13, 2011

Genetic "Hello World"- Clojure Edition

Last post I talked about implementing the Genetic Algorithm equivalent of "Hello World" in Python. Since I was learning Clojure around the same time, I decided to implement the algorithm the newer language as well.

Already having the iterative Python program written, it was strange to move to the functional Clojure. I made a point not to write a port of my previous program; I used the knowledge and experience from writing the algorithm in Python, but made sure to "think" in Clojure while I was writing.

In Python, my script's main logic was contained in one large function with a while loop.

In Clojure, this became a small recursive function which called started a chain of calls to other small functions.

While the Python script could have been written with more helper functions like the ones used in Clojure, the language does not push you in that direction the same way you get with functional languages (obviously). Therefore, the large function with the while loop seems natural in Python, just like how lots of small functions seems completely natural in Clojure.

One of the major benefits I've realized while playing with Clojure is how easy unit testing becomes when the language pushes you to write small functions with no side effects. Every function has a suite of obvious tests. This concept mostly failed for this particular project however, since the reliance on using random selection in many functions made unit testing mostly impossible for them. I tested every function when it seemed natural to do so, but my experiments on testing functions with regular but randomized output were too convoluted to actually use.

There is one problem I have with my Clojure solution that I have been unable to solve. It runs much slower than the equivalent Python version. I have hooked it up to Java's VisualVM to do some profiling, but I was unable to get helpful results. It showed (I think) that most of my time was spent sorting the solution set. While this does make sense, the algorithm is much cleaner with the sort- and in any case, the Python version has the same sort in the same spot. I plan to look in to this issue more (following these suggestions) once I have more experience with Clojure.

The full source is available on github. It includes a README to help you get started playing around, and explains more about the algorithm. 

Friday, March 11, 2011

Python Genetic "Hello World"

I've always enjoyed using computers to solve problems I'm too lazy to solve myself (see my Monte Carlo attack on an old math joke). That's why I got really excited when I read Howard Yeend's post on Genetic Algorithms, which made everything seem complex but accessible. My proven method for trying to understand something to write a program to do it for me (this dates back to learning the quadratic formula by writing a program for the TI-83 in high school), I figured I'd try my own Genetic "Hello World."
Here we can see the output from running the Genetic Hello World program. It took 76 generations to reach the target string.
There's many great resources for Genetic Algorithms, but here's a high level overview. A random sample of chromosomes is created. These chromosomes are combined, and the ones that score the best on a fitness function are kept for the next round of breeding. If you have a good fitness function, your solutions get better and better until you have an acceptable answer.

The source for this project is available on github. There's a README included that explains how to get set up and how to modify it to play with it yourself. I'm embedding the main script here so you can take a look: 

Thursday, March 10, 2011

Boids Sandbox

In an effort to discuss past projects that I've enjoyed working on, I'm going to start with one from my senior year of college. As part of my elective Artificial Intelligence course, we had to end the semester with a demonstration project from any area of AI. Having a double threat of recently reading about Boids as well as learning Python in my internship, my path was clear. I was going to develop my own bird flocking simulator.
Boids operate as an autonomous group, flying together in flocks without a defined "leader." Each boid is affected by neighboring boids according to three rules:

  1. Separation- ensures the boids don't get too close together and collide
  2. Cohesion- keeps the boids together in a loose flock
  3. Alignment- makes the boids point in the same direction as their neighbors, making the flock head the same way
As you can tell, the forces of Separation and Cohesion are direct opposites. However, each force is given a operation distance as well as a weight during calculation. Here are the values my model currently uses:
  separation_distance = 20**2
  cohesion_distance = 50**2
  alignment_distance = 50**2
  separation_weight = 2
  cohesion_weight = 1.5
  alignment_weight = 1.5
The Separation force doesn't kick in until a closer distance than Cohesion, but it operates with a greater weight.

You can check out the complete source code (and images) from Bitbucket (this project was before I discovered the wonder of git). It has a README to help you get set up (it's easy!), and start manipulating parameters to play with the sandbox yourself. The main module is embedded here so you can take a look:

Sunday, March 6, 2011

An infinite number of mathematicians walk into a bar...

The first one orders a beer. The second orders half a beer. The third, a quarter of a beer. Before the fourth mathematician can place his order, the bartender says "You're all idiots", and pours two beers. 
Yes, dumb math joke. But how easy is this to prove? We could form a mathematical proof that shows this must be true (I think I did this in class at one point), but where's the fun in that? Monte Carlo methods don't really prove much, but I think they're a fun way to solve1 this kind of math riddle.

So, how fast can we write a Clojure function that figures this out for us? Pretty fast- it's a one liner2.
(reduce + (pmap #(/ 1 (Math/pow 2 %)) (take 200000 (iterate inc 0))))
I'm going to use this post to telly you how this works. It's best to try to read Clojure code from the inside out. Let's start with
(take 20000 (iterate inc 0))
This will generate a lazy sequence of the numbers 0 - 19999. The (iterate inc 0) part is actually an infinite (but luckily, lazy) sequence. Pretty cool, huh?

The next block is the map function
(pmap #(/ 1 (Math/pow 2 %)) (take 200000 (iterate inc 0)))
The map documentation shows that it takes a function and a sequence of numbers. We've already generated our vector, so what about this function? 

The #( syntax means we will be using an anonymous function. The % becomes the variable we pass in to the function; in this case we're passing in each number from 1-19999. This uses Java's pow function from java.lang.Math to raise 2 to that power, then divide into 1. Notice how easy it is to use Java libraries within Clojure code.

So now we have our two arguments to pmap. As the documentation says, this function is exactly equivalent to map, but has the added benefit of the map tasks in parallel. Since our functions are pure and don't depend on each other for computation, we can parallelize them. So, we use pmap instead of map, and boom3! Instant parallelization. I love this game.

Now we have a 20000 element long sequence kinda like this
[1 1/2 1/4 1/8 1/16 1/32 ...]
Each of these corresponds to a drink that one of our infinite mathematicians ordered back in our joke4. The last thing we need to do is sum all of these fractions up.
(reduce + (pmap #(/ 1 (Math/pow 2 %)) (take 200000 (iterate inc 0))))
And that brings us back to our original one liner. Now that we understand the inside, we can see that reduce takes a function (yes, + is just a function) and a sequence. It returns whatever it gets by "folding" the answer from each call of the function to the next one (check the docs or Wikipedia for a real explanation), leading us to get a single number from our sequence. 

The answer is 2 by the way. Probably could have saved you a bunch of time if I just said that in the beginning.

How could this be made cooler? By using 20000 elements, we're ensuring that we reach a point where the rounding inaccuracies of floating point numbers show us an answer of 2. Of course, the actual answer never reaches two. However, we could write our own recursive function (which would replace the reduce call) that stopped execution when it noticed that the input sum hadn't changed after calculation, meaning we'd reached our maximum precision.

1 Using "solve" in the loosest sense of the word.
2 Blogs have magical properties that turn amazing one liners into ugly multi-line messes. At one point it was one line, and in a 80 character window too.
3 This is the one and only time this blog will link to Steve Jobs. Get your fill while it lasts.
4 Were you aware that analyzing a bad joke to death doesn't make me like it any more?