Category Archives: Programming

2014 reboot

I've been looking for a project to take on in my personal time and have been extremely indecisive about it for some time now, but I think I've got an idea now.

Over the Christmas holidays I spent some time playing a wonderful iOS game called QuestLord which has gotten me interested in iOS/graphics and C++ programming again. So I've dusted off my old C++ vector math library and started hacking things around a bit.

Some of my goals for this project:

1. Extremely fast compile time. Aside from simply working, this is the most important thing to me.

2. Processor and memory efficiency. These are also very important to me from a technical stand point except when they conflict with #1. I suspect this might happen when using say, header files for implementing inline types such as vectors and matrices but I'm not sure yet.

3. Elegant design of classes and function APIs with minimal code. Also very important except when conflicting with 1 or 2 above. One possible case I can think of where there might be a conflict with #1 is over reliance on templates, but I'll just have to see.

4. Achieve mastery of C++11 and refresh knowledge of C++ in general. This is not necessarily the least important thing on my list.

Hmmm.... well that's a lot of technical goals and no goals relating to algorithms or math yet, but I'm sure I'll think of some.

Finally gitting it

I decided to take a day off from work today and turn the 3 day memorial day weekend into a 4 day one in order to take care of some house keeping. One of the things that's been on my to do list has been to open source the code from my Master's project and thesis from a few years back. It's now available on git-hub under the MIT license. I probably should have done this a long time ago, but at the time, I wasn't sure how, or whether I wanted to continue development of it after graduation. Since I haven't done anything productive with it since, maybe it will be useful to someone as open source and I figure this way it's also a lot less likely to get lost/forgotten. This article on open source scientific research was also quite persuasive.

I'm looking into releasing a couple more of my home brew projects on git-hub - namely my 2012 Google AI Challenge entry and also my graphics programming "framework", so stay tuned.

Post Mortem of a Google AI bot

The submission phase of this years Google AI Challenge is over and final bot rankings are being established. I have to admit that the competition was (to me at least) very, very tough. It looks like Heron's performance is going to be much less than what I was hoping for.

But the good news is that I learned a great deal during these past two months. Here are some of the lessons I've learned:

1. Don't converge on an 'optimal' solution too quickly. This is basically just restating Don Knuth's view on pre-mature optimization being the root of all evil. I think more than anything this is what hurt me. I have a strong tendency to be a perfectionist in the things that I do and sometimes this comes back to bite me. Maybe you, gentle reader, can relate. The problem is that this makes me spend too much time trying to perfect things that maybe aren't as important and when in fact combined with other components of the system in fact turn out to be very much sub-optimal. So, in the future I need to give myself more time to experiment with various ideas before polishing a single one down to perfection.

2. Prefer simpler algorithms when the performance difference is not too great. Again, this is pretty much following along the lines of number 1 above. Now that other contestants are starting to talk about their bot designs its becoming clear to me that I seriously over engineered a number of things, particularly with choice of algorithms. For example, I wrote an A* implementation using binary heaps and an indexed array. This is one approach suggested by Amit Patel in his path finding notes. And it is a very efficient implementation but in hindsight might have been over kill for this problem as I've noticed some of the top contestants used a breadth first search to both find paths and handle task assignment. So while, BFS is theoretically sub optimal, the side effect that it also allows you to handle task assignment among several ants actually appears to make it better.

3. Maybe it's time to start seriously thinking about dynamic languages. OK, I admit it. I've always secretly been a bit of a language snob. I've always felt smugly superior as a C/C++ programmer to folks that use things like JavaScript and Python. But now that I really think about it, that feeling was probably more due to my own resentment about how productive these languages seem to make people. In any case, with a competition like this I really would have liked a language that would have more easily facilitated rapid development. And again this ties back to lesson 1. Don't optimize prematurely. I really think it would be helpful to have a dynamic language so that I could have tried many more ideas. While I love the speed and power of C++, it's kind of bad to get one month into a contest like this and realize that you've made all these mistakes and now have to go back and redesign your class types. Apparently Python has a fairly good foreign function interface to C, so that might be a good way to optimize cpu bound code portions. Also I noticed some of the contestants using something called "PyPy" which apparently is a JIT compiler for Python that can give the language a substantial performance boost.

Lastly, lesson #4 is "Never give up!". While very little in this contest went my way, I think I can at least claim a moral victory in the fact that I kept at it during the whole two months, even though, I was very, very tempted to quit so that I could start playing in the SWTOR head start. I really think that not giving up is probably the most important thing to do in programming, or anything for that matter.

Oh, I almost forgot. Actually there is a lesson 5. And it is "Aim high." I admit very often I tend to be overly exuberant and unrealistic in my optimism when starting a new project. I've heard this is fairly common among programmers. While it certainly can be disappointing to have one's hopes dashed, on the other hand it would be much worse to never try to begin with. After all, how many people enter a contest like this with the though "Oh, I just want to be average". Answer: nobody. So, don't be afraid to aim for the stars - otherwise you may never even get off the ground.

Let slip the ants of war!

So the Google AI challenge is back with a vengeance as of yesterday, and for better or worse I've decided to participate this year. I say "or worse" because it could end up being a bit of a personal obsession for the next few weeks, and given the calibre of the competition I'm not sure how well I'll be able to do but it should be a fun learning experience regardless. Naturally this means my current reworking of my vector and matrix math code will be on the back burner while this thing is going on.

I've already signed up and downloaded the C++ starter pack and then uploaded the default bot which is pretty mindless but at least it's something until I've had a chance to submit a bot with a reasonable amount of capability. I'm scared to look at my ranking at the moment since its the default bot, but my handle is "Heron" if anyone is interested in tracking my progress in the rankings. I'll update this blog as soon as I've had a chance to upload a revised bot.

Anyway, this year's competition involves the simulation of an ant colony. The goal for the bot is to collect food, grow the colony, and exterminate opposing ant colonies controlled by other players' bots. I've got an idea for a fairly simple bot that I'm currently researching. I thought I might find a possible algorithm to implement it in Donald Knuth's Art of Computer Programming but unfortunately he hasn't published that chapter yet. I'm devastated.