Ants AI Challenge

December 19, 2011

The AI Challenge is Ants this time around. The goal is make your your ants collect food, explore, raze opponent ant hills, and protect their own hill. New ants are earned by harvesting food, and there is a combat system. Here is a video of a game. For a better view, go to the main site to watch some games!

From the past contests, I knew I could easily spend too much time competing. I also knew that I didn’t want to spend most of my free time tweaking weights and settings. So, I decided to work on this for a short while, try to get a respectable bot, then quit. I succeeded at quitting, though maybe not soon enough.

Unlike the previous contests (Tron and Planet Wars), in this version the bots have imperfect information. Like the previous contests, the game is text based, making it very easy for contestants to use their language of choice, subject only to getting the language running on the contest server. This was one of the reasons I entered the Tron contest, besides how awesome it looked. Often these kind of games require players to compile or link their bot into the game engine.

My goal was to create a bot that made only local decisions for each ant because there were too many possibilities to consider every possible set of moves. With any luck, good behavior could emerge from such a bot. I also hoped to only use very simple features for these local decisions, but the features in the bot are lacking in several respects.

So, again, I wanted to treat each ant independently. That makes searching their moves easy, but also makes the bot dumb. The first bot I submitted searched for food, enemy hills, and unknown territory, It avoided enemies, but had no combat code. The bot was pretty dumb.

The second version had some simple combat code. I tried making each ant move as aggressively as possible, and then backed off any move that didn’t seem safe enough. This bot also had some code to push ants away from their own hill. The second version was much stronger than the first, but it timed out on some big maps.

The timeouts occurred because the bot does a few breadth-first searches to find out the distances from the various targets. One BFS starts at each known food, one at each known enemy hill, and another at all of the grid cells that haven’t been seen for a while. The way I wrote the BFS in Python was almost fast enough, but could take too long on larger maps.

The scoring function for ants that are not in combat is just a weighted combination of the inverse distance squared from each of the interesting targets. This makes the ants go towards food, but if they have a choice between close food and close enemy hill, they charge the hill. They also are attracted to enemy ants, which helps the bot get the numbers needed for attacking.

The third version was a rewrite of the second, but in C++. This made the BFS searches about 50 times faster. I tried making the combat code more aggressive, but it went too far, often walking right into an attack.

The third version is my official version. Some weaknesses it has are

  • no defense of the home base
  • no overall global decision making. (it will send every ant to battle at one hill, and leave another that is only)
  • the combat is pretty bad
  • there is no coordination at all between ants

I spend some time on the code after my official entry, but made no progress that was worth submitting. I wrote code to discover the symmetry of the map to predict where other hills would be, though it wasn’t very helpful. The math was fun, though. I tried using logistic regression to tune the weights of my evaluation function. That failed, and I think it was because I was trying to predict the wrong thing, and my features did not account for any global information.

Some of the other competitors are far beyond the rest of us, and I look forward to learning how they did it. Overall though, I am happy with the time I spent, and what I have learned. With the Stanford Online classes, work, and other activities, spending more time on the AI contest was just going to happen for me.

Congratulations to the winners!

Stanford Online Classes

December 18, 2011

The ML Class and AI Class from Stanford are nearly over, and they have been a lot of fun. I have not had formal classes in either of these topics, but have seen similar ideas over the years of doing numerical programming and signal processing.

There were some technical glitches, but I learned a lot. The pace was good… unlike reading a book where I just skim through pretending to understand. The quizzes and homework encouraged active learning is more efficient than passive learning.

Many of the topics were things I had heard of, but never learned anything about. Some of the topics were completely new. I really enjoyed the ML class progression from linear regression to logistic to neural networks. NN are a simple idea, until you start thinking of how to train it. The jump from logistic regression to NN made a big difference in understanding.

In the AI class, much of the material was from Norvig’s book, which I have been using as a paperweight for a while. The book is extremely dense with information, so it was nice to see explanations of even a sample of the material. (That isn’t meant as a slight against the book either… just a challenge with reading it.)

Again, these classes were a lot of fun, and I learned a lot. Watching these world-class lecturers, and getting quick feedback on my understand would have been worth paying for. Getting the classes for free was amazing.

IPython on the mac

December 18, 2011

What has worked for me:

  • setup a virtualenv
  • easy_install readline
  • easy_install ipython

If python gets updated by MacPorts, remove the old virtualenv, and re-run.

Old blog

November 20, 2011

Old blog. Posting to WordPress from emacs is so much easier right now. Plus, \LaTeX just works here!

A simple Octave tip

November 19, 2011

Matlab and Octave are both great for quickly trying out numeric code, especially code that uses linear algebra. Many times, code can be written to use the built in matrix operators instead of for loops. This makes the code faster, higher level, and clearer. Here, I will use Octave as I no longer have access to Matlab.

First, lets consider this formula

S = \sum_{i=1}^n x_i * y_i.

Since x and y are one dimensional vectors in Octave, we can find S like this

S = 0;
N = length(x);
for i = 1:N
  S += x(i) * y(i);
end

That was pretty straight forward. Octave can let us do more, though. The .* operator does an element by element multiplication over matrices, and sum adds up the elements in a matrix. Since our matrices are one-dimensional, we can use these two functions together to get our result, at the cost of creating a temporary matrix.

S = sum(x .* y)

Finally, Octave has a function that does what we want. The formula we are working with is the dot product of two vectors, so in octave, we can do

S = dot(x, y)

The first attempt is the clearest when you do not know what .*, sum, and dot do. But, the intent of the sum and dot examples is clearer. As a plus, in Octave, they are much faster.

fprintf("\n||||\n| method | size| result | time |\n")
for SIZE = [100, 1000,10000,100000,1000000]
    x = rand(SIZE, 1);
    y = rand(SIZE, 1);

    fprintf("|---\n")

    tic
    S = 0;
    for i = 1:SIZE
      S += x(i) * y(i);
    end
    t1 = toc;
    fmt = "| %s | %d | %f | %f |\n";

    fprintf(fmt, "for", SIZE, S, t1);

    tic
    S = sum(x .* y);
    t1 = toc;
    fprintf(fmt, "sum", SIZE, S, t1);

    tic
    S = dot(x, y);
    t1 = toc;
    fprintf(fmt, "dot", SIZE, S, t1);

  end

Give the following results. (extra formatting was for making this table in org-mode…)

 
method size result time
for 100 24.266291 0.000744
sum 100 24.266291 0.000055
dot 100 24.266291 0.000018
for 1000 247.065638 0.007198
sum 1000 247.065638 0.000016
dot 1000 247.065638 0.000017
for 10000 2507.387623 0.074163
sum 10000 2507.387623 0.000083
dot 10000 2507.387623 0.000029
for 100000 25090.247927 0.736105
sum 100000 25090.247927 0.000656
dot 100000 25090.247927 0.000095
for 1000000 249863.296971 7.334975
sum 1000000 249863.296971 0.006773
dot 1000000 249863.296971 0.001246

As a general rule, we should always try to use the language and tools, instead of doing things ourselves. Often, this is mostly a matter of learning what is available.

Of course there are times when we don’t want to, or we want to do something ourselves to learn how to do it, so that rule has plenty of exceptions.

Posting from emacs with org2blog/wp

November 3, 2011

I don’t blog very often for several reasons. A technical excuse was that blogging from emacs to one of the hosted services was too painful. This is my experiment to see if I can get around it.

org2blog allows you to post from an org mode file in emacs, which is pretty nice. The only prerequisites are org mode and xml-rpc.el. The setup is pretty straightforward, as described in the README.org file.

Speaking of org and github, github appears to render README.org files in the main directory when you are viewing a repository. That is pretty awesome.

Code and latex snippets show up too from org2blog! I am fine with the default formatting, but I imagine this stuff could be tweaked to look however I wanted.

A quote I like

September 1, 2008

From Pensees, by Blaise Pascal:

171. Misery. — The only thing which consoles us for our miseries is diversion, and yet this is the greatest of our miseries. For it is this which principally hinders us from reflecting upon ourselves and which makes us insensibly ruin ourselves. Without this we should be in a state of weariness, and this weariness would spur us to seek a more solid means of escaping from it. But diversion amuses us, and leads us unconsciously to death.