Tron AI

I have spent much of the past few days competing in a AI contest hosted by the University of Waterloo and sponsored by google. I have been having tons of fun with the contest and figured others would be interested in participating or reading how the contest has been going. I encourage anyone who finds this interesting to participate as it takes less than 5 minutes to get started and your first bot competing.

Here is a play of me beating the #1 ranked bot. I got lucky here, but be sure to watch other matches of mybot against others

The contest is to write an AI to play the game of Tron. It is played on a grid with each player moving one spacer per turn and each space moved from leaves an impassible wall. If you are not familiar with the classic film tron, it is easiest to think of the game as two player snake, where each players snake continues to grow every move. The goal of the game is to outlast your opponent before crashing into a wall.

On the day the contest launched I was already able to jump up to the top 20 in the rankings. I started off with something very basic. Every turn there are only three possible moves (the first turn there are 4) and so I just tried to narrow it down from there. I would decide which direction to move by looking in all three directions (forward left right) and choose the direction farthest from a well. This end up having the bot move to the center of the space and then run around in the middle. After watching a few rounds I decided this would work best if I first cut off some options to the enemy. So I would first run to the nearest edge and then follow the above strategy hoping to first block off their path. Lastly I would avoid draws by preferring not to move to squares the enemy could move to. This worked surprisingly well for being so simple and just avoiding walls,and I was ranked pretty well.

This did not last long, as more and more people submitted or improved their bots I had to get smarter. My first major improvement was to mark the open space in continuous regions. So my bot would scan the map, and color in every continuous space, each group a different color, and then count the number of squares of each color there were. This was a huge advantage, first it allowed me to not move into dead ends. If the head of my snake bordered two different colors, move into the one with more space available. Worked great. Now my bot would not do stupid things like move down obvious dead ends. If there was ever a choice between two regions I would end up in the larger one. This alone coupled with my old strategy bumped me up back into the top 20.

The way I stored my colors gave me an added benefit, if there was a color that bordered both me and the enemy I knew that there was some path between us. So I could use this and if there was no possible path between us, go into space saving mode. This meant to not do anything fancy just follow the wall since all that was needed now was to out last him, and hope we have more space than them. My space saving ideas still could use a lot of work since this situation comes up all the time once the board has been divided.

Next I added an attack routine. I just based this off of common cases I saw while watching my bot. Since my bot would race to the middle I could then move towards and edge and hopefully cut them off. I did this based on quadrants. I divided the map like so:

|1|2|
|3|4|

Then if I started in 1 and the enemy started in 4 the game would proceed as fallows. I would find a wall, then move to the middle. I would check what quadrant the enemy was in, if they were in 2 or 3 make a dash for the wall. If they are not in 2 or 3, just stick with evasive maneuvers. Works really well against certain bots like this


My bot still has a long way to go before beating some of the top ranked bots. I have some ideas in the works still though. This contest has been tons of fun and goes till the end of the month so check it out!

Message to my future self

So currently I am studying for the physics GRE exam. I hope to apply to physics PhD programs this year so this is my last chance. This is my second time taking it, but still redoing all of the practice tests.

So my process is to take the practice tests and grade them as if they were the real test. Then go through and figure out what I did wrong on any problem that I didn't get. This is aided immensity by grephysics.net which has typed out solutions to each problem and lets users contribute their own solutions.

This time through I got stuck on the following problem: http://grephysics.net/ans/9677/82

I read the answers and I still did not really understand it. I read the users solutions to see if those made more sense to me but they didn't. The first comment I read 3 or 4 times and still had no idea what the author was saying. Then I glanced at the name of the poster, IT WAS ME.

About one year ago, I knew how to solve the problem, and knew well enough to post a solution for others. Now I can not solve the problem and don't even understand my OWN solution. Such a strange feeling to read something many times, not understand it, and only later find out I wrote it. I need to start writing more things to myself since some day what I think now will be unintelligible to myself in the future.

Social networking

Almost weekly I hear someone or read something by to the effect of complete lack of understanding of why anyone would use a service like twitter. "Do you really want to know that your friend is eating a sandwich?" Of course not. The truth of matter is most people really suck at online social networking. Blogs, Facebook, twitter, most people write things that are useful to no one. This becomes amplified by a site like twitter which has no intrinsic usefulness and the utility is completely based on what you say and who you follow, so the media is baffled why it is so popular.

Let me start with Facebook. When Facebook was first released it was a site for university students so they could connect with other people in their classes. Over time it has evolved and has lost the utility to students and has become a more general networking site which aims to simply keep people connected. This is the general trend of web services for a while now. Being social creatures, everyone wants to be connected with people, and the web is an amazing tool for this purpose, however most people are clueless about it.

When Facebook first started the transition over to general purpose networking, the first effect was USELESS applications. Everyone could not wait to send everyone they knew an egg that would hatch into a puppy 10 days later, or super poke, or any other of the countless annoyances. Why did this happen? Sending someone an egg that hatches into a puppy is not particularly useful to anyone! It does however initiate and continue social contact with the recipient. These new facebook applications allowed people to seek attention from their friends in a new way, and that is all people want.

This is the problem with all new social media. People want attention. So if there is a way to get attention from friends or strangers people will use the service to accomplish that, even if it has no other utility. Yet even though most of the applications are useless there are plenty of features on facebook that are genuinely useful to me and so I continue to use the service.

Blogs. There are countless blogs that meaningless to me. I do not care about the life updates about everyone I have ever met. However I do care about what is going on in my friends close friends lives. Anything my closest friends and family choose to write about I care about, because I care about them. This is great because I can choose to follow my friends with an RSS feed and read their thoughts, but I am only going to read blogs about topics I care about.

Enter twitter. I genuinely care about what is happening in my friends lives and want to see their twitter updates. Even if only a small percentage of their tweets are something that I care about, I am happy to know what is going on in my friends lives. Just like facebook it seems the majority of people are idiots and think everyone will care about everything they do. This is what the media picks up on and why everyone is clueless what purpose twitter poses. For the people who use twitter like a game and see how many people they can get to follow them, twitter is not going to be of much usefulness. Directly analogous to the people who try to set a record for the largest facebook group. However both services have utility if used to keep connected with the people you actually care about.

Most people suck at twitter, and all social media. Just ignore them. These user driven sites work if you interact with users you care about, and not morons.

Functional Programming

I have recently fell in love with functional programming. I am learning Haskell and loving it and would like to share the story.

Recently I made some real progress on my Chinese Chess application which I will eventually put on Facebook. It is written in python and the rules of the game are pretty much complete and so I can run through a bunch of simulated games where each side makes a random move each time. I now have to design and create an interface for it so the game can actually be played. I am making a web app for it and going to use jQuery to help me out with it.

In learning jQuery and implementing my python I started to fall in love with functional programming. To generate the legal moves for a piece I used map and filter. These are functions which take a list and another function as their input. Then they go through the list applying the function to each element on the list. While this can be done with a loop its is much cleaner with these higher order functions. It took me a while to realize how passing a function as an argument to another function is amazing, it is like magic.

This came up again in jQuery. jQuery is a javascript library that makes doing useful things with JavaScript much easier. The amazing part is that it takes advantage of passing functions around as well. While I am still learning javascript I already am loving the functional parts of it.

All these functions prompted me to take the plunge into Haskell. Haskell is a pure, functional, and lazy programming language. It is a whole new way of thinking about programming for me, and so far I am in love with it. As an example let me show this piece of code I wrote which still blows my mind:

derivative f = (\x -> (f (x+dx) - (f x) ) / dx)
where dx = 0.0001


This is a function, that takes another function and returns the derivative of that function! What?! To show you what it does

Main> (derivative sin) 4
-0.6536057796480144
Main> cos 4
-0.6536436208636119


the inaccuracy is only because dx is set to be 0.0001 rather than an infinitesimal but that is all it takes to create calculus!

While I am certainly not proficient in Haskell yet I am having tons of fun reading through http://learnyouahaskell.com. After just the first few chapters my head exploded a few times but I was able to solve the first 10 project euler problems with Haskell.

The only problem I have with learning functional programming is the frustration when first class functions are taken away from me. In my parallel computing class I have to write MPI programs in C or FORTRAN. I do not think MPI supports first class functions, but I keep wanting to pass functions to other functions! I will be posting more about my progress with my chess application and functional programming progress shortly. I feel I am progressing quite a bit as a programmer which feels nice.

Birthday

So it is about to become my 23 birthday. This is the first age where I would had preferred to live another year whilst staying the same age rather than gaining a year.

So for the occasion I am having friends come by and go out to dinner and beer. I have chosen the yard house for their beer selection and onion rings. Unfortunately for my free time I recently discovered both ratebeer.com and beeradvocate.com. This caused me to take the beer list at the yard house and put it into a spreadsheet, take data from ratebeer.com to get an order list of their beers by rating. Yardhouse beer list

It is interesting to note that while going through this list I found that stronger beers such as IPA's or Quads tend to have higher over all ratings from equal quality beers of other types. For example sorting the list by percentile within the style of beer puts the wheat beers like Hoegaarden and the hefewiezens much higher than other beers with much higher ratings.

Milage may vary

I have come to the end of my crazy road trip. After 2300 miles I am back in San Diego as the semester starts tomorrow. The trip was fun I got to see a bunch of friends and travel all of the place. Probably a better use of time over anything else I would have done over my break.

During the entire trip I had my eyes glued to my dash which displays my gas mileage. Since it was such a long trip I felt it would be good to track my mileage and see if my display is accurate. I ended up with a grand total of traveling 2300 miles, burning 44 gallons of gasoline, paying $86.80 at prices ranging from 1.899-2.079 dollars/gallon, while getting an overall 54 MPG. The price came to a bit more than I had originally estimated but I ended up traveling more miles as I drove around a bit at most of my stops.

I drive a Honda insight which is the first hybrid sold in America. The dash displays the instantaneous MPG as well as the MPG for the current trip. I tracked the entire journey with one trip while used the other two trip settings to give me estimates for each leg of the journey. My mileage was much different depending on how I was driving and my driving conditions. During the first leg of the trip I got mileage in the low 60s. I was driving at about the speed limit the whole way and very conscious of my driving to try to get better mileage. Unfortunately that did not keep up the whole time. I did quite a bit of city driving at various points which hurt my mileage quite a bit.

The insight does get very good mileage on surface streets due to the regenerative breaking but it only gets up in the 50's if one is careful with their driving habits, and on unfamiliar streets and with traffic it is difficult. At many points of the drive I was in a hurry either because I needed to get to my next destination quickly and speed makes a huge difference in mileage. The best mileage I got was the long flat straight of the 5 interstate in northern California. On that section I slowed down to about 55-60 and drafted behind semi trucks. By driving like that I was able to get MPG in the high 70's for hours of driving. The worst mileage part was in Oregon. I was driving faster there as I was more in a hurry, but also found that I couldn't get the same mileage up there as I could for similar speeds, and I believe because the roads are rougher in Oregon, but it might have all been in my head.

A successful trip to Portland and back without having to ford any rivers, no deaths due to dysentery and round trip for a fraction of the cost of a plane ticket.

象棋

On my trip I hung out with Geoff in Berkeley. Berkeley ends up closing up pretty early when school is not in session so we spent the evening playing Chinese chess. Chinese chess is a strategy game with many similarities to western chess and may be just as complex. It is pretty quick to learn but takes a long time to master and we played a few games of it over beers.

The next day we ended up going to SF for lunch and to see some sights. I had never seen Chinatown so I wanted to check it out. It was pretty cool to check out Chinatown with Geoff since he is fluent in Cantonese and could communicate with people in the shops if we were looking for things. While wandering around we came by a open park area and saw groups of old Chinese men huddled around small tables playing and observing Chinese chess! It was great since we had just played and had refreshed the rules so we could watch them play and understand the game (although I was unable to understand the discussion/debate over strategies which they were yelling at each other.) It was really cool, and so I decided a great souvenir would be to buy a Chinese chess set. I found one for about $3 which was pretty cool.

We ended up walking back to the park, sitting down at a table and playing a game together. At first I was worried that I would be offending them as I would be seen as a scruffy white guy mocking their past time. After just a few moves a few men started to stand around and watching our game. First they were giving me weird looks and seemed confused or maybe just curious about what we were doing, I think a few chuckled a bit. It was really embarrassing because neither of us are good at the game but a bunch of guys who watch the game played all day long were certainly aware of our lack of strategy. After a while they began to give me tips by pointing at squares on the board or moving my pieces for me, while of course giving me instructions in Chinese. It was frustrating as I did not even know how to say thank you for the tips they gave me. At some point they were basically just playing for me and debating with each other over the merits of various moves. It was amazing, but all very surreal. Was not at all what we were planing to do in SF but I cant imagine anything better.

The game of Chinese chess or 象棋 (xiàngqí) is extremely popular in China. The scene in chinatown of groups of men playing it in public is apparently seen in cities all over china. While playing it I decided it would be a unique and fun project to program, and something that is within my abilities. So I have decided to create a Chinese chess Facebook application. There already are successful western chess applications so I have something to model it after. I currently do not see an Chinese chess application out there and who knows maybe Facebook will one day become popular in china and I will get a ton of users. I think it will be a great learning experience for me to actually write code with users other than myself, and will be great to put on a resume if it ever became popular!