AMazeBot 2011

It’s time again for another AMazeBot competition! What exciting new changes do we have in store this year?

Well, actually nothing significant in terms of the rules. There is a small addition to the API but this isn’t a major new feature. The addition of recharging last year was quite significant, and we want to allow more time for students to get used to it, and for us to see if it needs balancing. I may still add another maze type before the competition event, but that would be the extent of the changes for this year.

Instead, our focus this year is on opening the competition to other colleges! We feel this is the obvious next step in growing the competition.

For a couple years the prize money was provided by Mohawk, and under that situation we were understandably restricted to Mohawk students. But since last year we have independent sponsorship, and so we are now able to accept submissions from students at any Ontario college. For this first time we don’t expect to get many outside submissions, but we are hoping for a few at least. We’d like to set up a friendly rivalry among the colleges, to see who has the most dedicated and talented programmers!

What we are trying to do is create a snowball effect: by increasing our visibility and number of participants, we are hoping to attract more sponsors. With more sponsors we can offer a larger prize pool, which will then attract more participants and increase our visibility.

We are now in the process of communicating with some other colleges to spread the word. Promotion in general is a large task, one best undertaken by specialists. Professor Yendt and I aren’t particularly good at this; our field is mainly the technical side of things. So this is an opportunity to bring in some other volunteers to complement our efforts.

I’m not sure what we’ll do in upcoming years regarding new features in the rules/API. There was some discussion of possibly having multiple rechargers, and that seemed the only practical idea we had. Everything else seemed to be overly complicated, compromising our primary design criterion (keep it beginner-friendly). It may be that we have reached a plateau, or it may only be that we lack good ideas! If the latter is the case then perhaps our nascent community will direct us.

I do have a number of ideas for new features in the development tools, but they would require major rearchitecting of the code. I reckon we’ll tackle it eventually, but that’s beyond the horizon at the moment. Small steps!

AMazeBot 2010: Recharging

Every year we try to introduce some variation to AMazeBot, partly just to keep it interesting but also to force returning students to do at least some new work. In the past most changes have been fairly minor, such as adjustments to scoring, different maze types, and the like. There have been a couple of moderately significant changes, such as having 2 goal rooms that must both be visited (only done for one year) and the ability to scan all the empty cells ahead of the bot (the standard scan can only check adjacent cells). But the new feature for this year is definitely the biggest variation introduced so far—recharging.

AMazeBot 2010: Improvements to Batch Mode

The release date for the 2010 version of AMazeBot is quickly approaching; I expect that in 2 to 3 weeks the website will be updated and the devkits available for download. We who are developing it are quite excited, and we’ve heard that a number of students are also eager to get started on their new bots. I can’t yet announce any new features or changes we’ve made in the ruleset, but I can reveal some improvements to the batch testing system.

When I first wrote the Batch Module for 2008 I didn’t have much time to polish it. As a result, although it was functional it was somewhat unfriendly. It’s an important tool for the students however, perhaps used more often than the Developer Module. I had always intended to make a number of improvements, but failed to do so for 2009.  Now for the upcoming 2010 competition I have finally given it the attention it deserves. Here are a few things that I’ve changed.

I Am Not a Teacher

…anymore. Specifically, I’m not teaching the game programming course again this autumn, as I had hoped. I was interested to do it, but Mohawk was a bit tight on funding for sessional instructors this year, so one of the regular professors took over.

It is unfortunate for me, as I had a number of ideas for improving the course and my framework that I wanted to try. On the other hand, it means I still have my free time—teaching required me to go to Mohawk twice a week for 4 hours in total (and transportation and preparation time on top of that) while still maintaining full hours at my primary job at Mac, which was draining. Not that I’m making much productive use of my free time, but still… it’s nice to have.

I think this may be the last time this course is taught at Mohawk, at least using the current platform (OpenGL via C++). I know that Mohawk is restructuring its Software Engineering program (for one thing I believe it’s going to be renamed to “Software Development” which is just as well; I don’t think we had much actual engineering discipline taught) and as part of that C++ is being phased out. Depending on when that happens (or happened) this course may yet be taught once more, but once only. After that, it will either have to change (perhaps to C#/XNA?) or be retired.

Incidentally, I taught Assembly Language the previous year and that too was phased out. I’m not sure if these changes are good or not. Although I feel C++ and even Assembly are important and worthwhile to learn (and I’m sure quality university programs will continue to teach them), Mohawk is focused very much on catering to the broad needs of Industry, and getting their graduates jobs. And the bulk of the jobs these days seem to be in Java or C#, and typically on a web platform. So perhaps overall it is the correct direction for the college.

I am not a programmer

… but I wish I were.

Well ok, actually I am a programmer, in that I am employed to (among other things) write programs. But it’s not in the professional sense that I wish to be a programmer, it’s in the amateur sense. That is, the original meaning of “amateur”, one who does something for love, not money. (However I certainly am an “amateur” programmer in the more common sense, “novice” rather than “expert”–sometimes words can be so difficult.) I say this because although I love programming in the abstract, I just don’t do a lot of it! Ergo the conspicuous absence of posts about my programming projects, which is what this blog was ostensibly for.

I just haven’t been greatly motivated to do anything for quite some time, and I’ve been struggling to figure out why that is. I’ve identified a couple reasons:

Programming at work makes me disinclined to do programming at home. This is a feeling that a number of my programmer friends have reported also. For some it goes even further–they don’t even want to be on the computer at home. I don’t seem to have that problem; I’ve no difficulty spending much (and probably too much) of my time at home playing games, browsing the web, whatever. But focusing on projects, even when they are fun stuff compared to the boring stuff at work, is often difficult.

Programming alone is dull. When I was younger I learned programming by myself, and most of my early experiments and projects were done solo. It wasn’t a problem then, though I would have liked working with other programmers. I just hadn’t had many friends who were interested in it. But I find now that my disposition has changed, and I more strongly crave the interaction with others. I had the opportunity for it in college, and now prefer it. This is a major thing lacking from my job actually, the fact that I am not on a team of programmers.

Fortunately these factors don’t always prevail; sometimes I can manage to overcome them and get stuff done. Sometimes I can even reach the mood described by Nikola Tesla:

“I do not think there is any thrill that can go through the human heart like that felt by the inventor as he sees some creation of the brain unfolding to success… Such emotions make a man forget food, sleep, friends, love, everything.”

All summer I did no programming at all, but when September came and I realized I had a lot of work on AMazeBot yet to be done, I managed to slowly get back into it. I’m not yet in the Tesla state, but I’m gaining some momentum.

Now if I can only find the motivation to write blog posts more frequently…

AMazeBot 2009 Completed

The 7^th annual AMazeBot competition was held yesterday (April 1), and I declare it a success, with much fun had by all. There were 17 bots submitted by 23 students this year, which is the highest turnout yet. All bots managed to solve at least 1 maze, earning their authors a 5% bonus in one of their courses. In fact, every bot solved at least 3 mazes—very well done!

The notorious Conficker.C even made an appearance, and though the worm was ineligible to win prize money, it did put in a respectable performance, possibly frightening some of the other bots in the process. But in the end it was vanquished by a sleepy kitten, a Dalek, and a mouse.

I can now reveal a couple of the things I had been working on: the new design for T-shirts which were given to all competitors, and the title screen used in the show. Also, this was the first year in which a custom (i.e. hand-drawn instead of procedurally generated) maze was used, and it proved to be the most difficult of the 5, exhausting an astonishing 13 bots.

T-shirt design.

Title screen.

Concentric maze.

The complete final results are posted on the official website, and soon (eventually?) there will also be photos from the event.

Some of the competitors will be graduating this year, but  many will be able to enter again next year, including the current champion who has taken 1st place for 2 years. Will he be able to claim the title a third time, or will he be dethroned? Will some mutation of the worm or another of its ilk arise again to threaten all good hard-working bots? Will there be a custom maze so insanely convoluted as to foil every single bot? All shall be discovered in a year’s time!

As for what new features might appear in 2010, I cannot at this time make any comments, other than to dispel rumours that there will be a minotaur.

Evolution of AMazeBot

The AMazeBot is less than a week away! The deadline for students to submit their bots is tomorrow, and the competition takes place on Wednesday. Even at this late stage I’ve been making some minor tweaks to the system, which has delayed me from describing all the major changes I made when I rewrote it last year. I’ll attempt to do so now.

The original Amazebot system consisted of only a single module that was used both for writing bots and in the competition show. This module was contained in a library that could not be run independently, instead relying on students’ code for the main function. A compiled Amazebot program would create a window with a maze, run the bot through it while drawing its path, and then exit writing the results to a log file. The mazes were procedurally generated based on a seed value which was obtained from an ini file. For the show, a script was prepared which, for each of the 5 rounds, did the following: modify the ini file to specify the seed for the round, execute each bot program in turn, and process the log file to create an HTML file showing the bot rankings.

This system worked adequately, but there were a number of deficiencies. The solutions to these resulted in the system being split into 3 modules, each described below.

My Kingdom for an Ergonomic Left-handed Keyboard!

I’m not sinistral; I use a mouse with my right hand. A standard keyboard has arrows keys to the right of the alphabetic keys, and a numeric keypad to the right of those. The result of this arrangement is that a mouse to be used by the right hand must be placed very far from the most commonly used keys. A keyboard with this awkward layout (for right-handers) may sometimes be referred to as a “right-handed” keyboard.

There is an alternative layout in which the arrows keys are placed to the left of the alphabetic keys, and the number pad to the left of those. Besides moving the mouse closer to the most commonly used keys, this also provides an enter key for both hands, and allows one to rapidly type numbers while continuing to use the mouse. A keyboard with this sensible layout (for right-handers) is referred to as a “left-handed” keyboard. The world is, in case you have not noticed, largely insane.

An ergonomic keyboard is one in which the keys are arranged in a curve rather than linearly, and usually have a gap between the left and right alphabetic keys. The intention is to allow the wrists to be kept at a more natural posture while typing. There may be some additional niceties, such as a pad for the wrists or heels of the hands.

Ergonomic keyboards are quite common these days, and a left-handed keyboard can also be had without much difficulty. Sadly it seems that these sets do not intersect, for it is nigh impossible to find an ergonomic left-handed keyboard (or, equivalently, a left-handed ergonomic keyboard). The closest ones I’ve been able to find are made by Fentek and Evoluent, neither of which particularly appeal to me. The good people at Evoluent seem to understand the absurdity of this problem; they even describe their keyboard as “mouse-friendly” rather than “left-handed”. If only the layout more closely matched the usual ergonomic style, such as in the keyboard I currently use made by Adesso or my previous Microsoft Natural Keyboard 4000 (which drowned in a tragic accident).

Actually even these ergonomic keyboards have various problems inherited from their primitive ancestors (truly, it’s like these things had evolved rather than been intelligently designed). I refer to the physical positioning of the keys rather than their logical labeling–a Dvorak layout still exhibits asymmetries that confound human hands. But it’s too much to expect all this tradition to be thrown out and an ideal keyboard produced from scratch. I would settle for an ergonomic keyboard with the arrows and numpad on the left.

In the meantime, I suppose I should learn to mouse with my left hand.

Hash your passwords!

At my place of work we use a certain program. It’s a multi-user client/server program, with authenticated user accounts. Recently while I was logging in something unexpected happened. After providing my credentials and hitting enter I realized I’d inadvertently typed one extra character at the end of my password. I expected to have to retype it, but to my surprise the program granted me access. To be sure I logged out and tried it again, this time purposely appending an extra character, and again I was granted access. A few more experiments revealed that my password would be accepted with any number of characters added at the end, whereas any other change was properly rejected.

This peculiarity baffles me; I can’t fathom why anyone would program a password check in such a way. But leaving that aside, what are the implications of this behaviour? Minimally, that the program must know the length of my password. Without that information it couldn’t know how many characters to ignore, were I to type too many. (Well, actually that isn’t strictly true—there is a way to do it without knowing the length of my password, but it’s a silly trick.) Now, there are basically 2 ways in which the program could know the length of my password. The most direct and obvious way is to store my password in its database and thus be able to simply count the characters. Alternatively, it could store only the length as a number but not the password itself.

But how could the program possibly be not storing my password? How can it check whether the right password has been supplied, if it doesn’t know what the right password is? By using a form of encryption known as hashing. A hash function takes plaintext (original, readable text) of arbitrary length and converts it into a ciphertext (encrypted, unreadable text) of fixed length, which is called the hash. The important property of this function, that differentiates it from other kinds of encryption, is that the reverse operation can’t be done. This means the function is “one-way” only: you can turn any plaintext into a hash, but given a hash it’s practically impossible to reconstruct the plaintext.

Using this scheme then, instead of storing the password as plaintext, the program could store just the hash. To authenticate a user, the program need only hash whatever the user has typed in, and compare the result against what’s in the database. Thus, without even knowing what the password actually is, it could ensure that the correct one was given. Because all hashes produced by a particular function are the same size, even the length of the original password is obscured. That’s why if the program were using hashing to avoid storing the password itself, it would have to store the length of the password separately. Unless, that is, it used the silly trick I mentioned—which I’ll not reveal here, as it should be fairly trivial to figure out (feel free to ask in the comments if you’re stuck though).

So what is the program actually doing? Well, the observed behaviour is most straightforwardly explained by the storing of plaintext passwords. In fact I jumped to that conclusion when I discovered the peculiarity, and it was only after analyzing the situation in depth for this post that I realized that it wasn’t quite certain. But anyway what does it matter whether it’s storing plaintext or hashed passwords? In a word, security.

Consider what would happen if an attacker were to compromise the database and obtain read access. If the passwords are stored in plaintext, then it’s a disaster; but if only hashes are stored, then the passwords themselves are still (for the moment) secret. Even under normal circumstances there is a benefit—hashed passwords are secret also to the administrators of the system. Users commonly use the same password for many services, so they are better protected if they don’t have to risk placing undue trust in admins; and if something does go wrong, an admin is under less suspicion if they could not possibly have known a user’s password.

This is a very basic security technique, but the knowledge of it seems depressingly uncommon in the software engineering field. A major part of the blame lies with educational institutions; I was not taught this in college, having instead to learn it on my own (fortunately not the hard way). Hashing is only the beginning though, as there are still ways an attacker could defeat such a system. The second line of defense is to add salt, which I’ll cover in a future post.

AMazeBot

It’s been over 2 months since my last post! In that time my attention has mostly been devoted to the Amazebot programming competition. I’ve been doing several activities related to it: updating the software, running workshops for beginners, and designing a promotional T-shirt. When I discovered that I had a few hits from people searching for “amazebot” I felt I should capitalize on this. The competition takes place just a month from now, so perhaps it’s a bit late for that but at least this will all be in place and ready for next year!

The Amazebot is an annual competition run at Mohawk College, open to all students (though most entrants are from Software Engineering). Competitors must write a program that will navigate a virtual robot through given mazes as efficiently as possible. It was started in 2003 by Professor Mark Yendt, in an effort to show students a fun side of programming. The first 2 competitions were done in C++, and thereafter switched to Java.

While I was in college I entered 3 times, and (I must beg pardon for this boasting) I won first place all 3 times. It wasn’t all just talent though–I put a lot more time into it than most, and I believe that effort is what really paid off. Back then the system was rather primitive, both in terms of the tools provided for students to develop their bots, and the quality of the visual presentation during the competition itself. I had several ideas for improvement, and after I graduated Professor Yendt graciously allowed me to rewrite the software from scratch. My version was first used in the 2008 competition and was well received by both entrants and spectators. You can see the evolution of the system in these 3 screenshots:

2003

2005

2008

The basic concept has remained the same over the years though. The maze is constructed on a grid of 44 × 44 cells, each of which can be either open (floor) or closed (a wall). This is simpler to deal with than some other types of mazes, in which walls are drawn only between cells. Instead of escaping the maze, bots must attempt to reach a 4 × 4 cell goal room. A bot can perform a few different actions: it can move forward or backward, turn left or right, and look into the cell ahead or to either side of it. Each action costs a certain number of points–this represents energy that a real bot would have to expend to do anything. The challenge is that bots start out without any information about where the walls are–they are given only the location of the goal room. They must explore and discover the layout of the maze as they go along in order to find a path to the goal. There are 5 rounds in the competition (each a different maze) and bots with the lowest overall scores win.

I’m planning a series of posts to discuss in detail how the system works, new features I’ve introduced, and the competition itself. I’ll also offer tips and tutorials for students getting started.