JMoe: The Mastermind

About a year ago I said I would make a post about LinQ. Now that Visual Studio 2008 is out, and LinQ is a released technology, I think I can get around to it. I still haven’t built a project that makes a good use of LinQ, but I’ve got a fairly good understanding of it, and found some interesting ways to use it.

Now, you may be wonder what LinQ is, and what it stands for. The answer is that it stands for Language INtegrated Query. It is an extension to C# and VB.NET that allows you to use a SQL-like syntax for constructing queries against a wide variety of data sources. The most obvious example is XML, but you can also use most of the built in data structures in the .NET framework as well.

With that out of the way, on to an example or two of how I’ve managed to use LinQ, and what the challenges that I’ve run into are.
Read the rest of this entry »

I realize I’m rather off the schedule I had planned. I blame the holiday weekend, my laziness, and Robocup. The international qualification deadline is at midnight on February 22nd. For those of you unaware of what the date is, that is in less than 24 hours (it’s 2:15am at the moment). That means it is somewhere close to crunch time, which means that I’ve been working. The new look for the RFC Cambridge site was rolled out tonight, and I’ve been helping with the team description paper (both writing sections, and proofreading it). With that out of the way, on to the actual topic of this post…

C# is one of the primary languages supported with the .NET Framework. C# is a strongly typed, managed language. This means that the language runtime is responsible for memory allocation and deallocation (garbage collection is the technical term). This saves a lot of hassles and helps to reduce (but not eliminate) memory leaks (memory that has been allocated, but is no longer pointed to, but not deleted). The .NET Framework is also important, as it provides C# with a powerful class library.

C# also has the capability of using essentially the entire power of C++ through something called Platform Invoke (or PInvoke for short). PInvoke allows you to call essentially arbitrary C++ (with a few requirements for how it is written) from within C#. This is hugely powerful, as you can access unmanaged memory, and do operations that are inherently more efficient in C++ than in C#. There are also a few features of C++ that aren’t available in C# (such as memory mapped files) which are useful.

Another powerful capability of C# is called reflection. Reflection is essentially the ability to examine and modify objects at runtime. This allows you to determine the capability of an object, and even to extend it programmatically, at run time, rather than at compile time. C# can also programmatically invoke a C# compiler (through the .NET framework) which can allow for things like dynamically compiled modules, and other interesting features. With Reflection, you can then discern properties of the runtime compiled code, and integrate it into an existing system. This allows for a theoretically powerful plugin system, which can at the same time be limited for security purposes. When compiling code at runtime you can specify the assemblies (code components more or less, some of these terms are almost another post in themselves). This can lead to some very interesting ideas (an XML Parsing system based solely on object structures, or an easily extensible editor are a couple that I’ve had), and allows for very powerful capabilities.

The last, and one of my favorite features of C# (well, more correctly Visual Studio) is the GUI (Graphical User Interface, ie what you see) designer. I originally began programming with Visual Basic (save the hate, I’ve moved on to “better” languages), and I always enjoyed the ease of building a GUI with Visual Basic, even if the language behind it was a little quirky. It was actually common to use Visual Basic to build a GUI, and use COM (Component Object Model, a rather nasty complicated Microsoft technology) to hook up C++ code for the actual program component. With C# you don’t have to go that far, as the GUI designer is part of C# as well.

This is getting long enough, even though there is a lot more to cover. I guess this will have to become a multiple part series (to be continued on Friday I suppose). I’ll close with a link to Visual C# Express Edition, which is a free fully featured C# IDE (Integrated Development Environment, I need a little extension to let me just link to wiki pages for these) for Windows. It’s fun to play with, and gives you most of the power of Visual Studio 2005 for free.

RFC Cambridge is a Robocup team that is a joint effort between the MIT Competitive Robotics Club, and the Harvard College Engineering Society. We’re in our second year competing, with the international deadline coming up soon. For RFC, I’ve done a variety of different things. Last year, my largest single contribution was the refbox. Robocup uses a serial connection to send referee commands to each team. I developed a drop in component for our AI system that could read the commands from a serial port asynchronously. To avoid reinventing the wheel, it was composed of two subsystems. One was the serial reader, which read from the serial port, and placed any received values into a memory mapped file used as a buffer. The serial reader was in Managed C++, and used the Microsoft .NET serial reader class. Inside the actual AI was an unmanaged C++ component which read from the same memory mapped file buffer to read the commands.

Strictly speaking, the design was non-thread safe, and avoided issues mainly by having a guarantee that the input data could not exceed the size of the buffer, to cause a wrap-around race condition, and that each thread would never be in the same area. While not the best design, it was sufficient for our needs. Since the AI was reading the buffer every 33ms (or so), and there was no way possible that more than 255 commands would arrive in that 30ms, there was never an issue.

Another major unused contribution was a new pattern recognition system that was part of the vision module. This was to have been used to detect the location and orientation of each robot, using a “butterfly” pattern, rather than the much simpler two dot pattern that our team used. However, because of time constraints (it was written about 3 days before the competition, and fully integrated the day before the team left) it was not used at the international competition.

I also developed a small control system that allowed users to drive our robots with an Xbox 360 gamepad. This was useful for non-autonomous demos, as it allowed more effective control of the robot. It was done over the course of about two days, using C#, and a third party wrapper for the XInput technology with the Xbox 360 Gamepad for PC. It worked quite well, and was rather popular with people when we were doing demos at the MIT Activities Midway, as we could allow students to drive the robots, without any real training (one thumbstick to drive, the triggers to rotate), and it was fairly intuitive.

This year, I’ve been doing bits here and there, and will probably redevelop the 360 control system for our new platform (which is quite a change, but I’m not sure I can post about it just yet). Otherwise, I’ve mostly become the web guy. This is mostly because I know how to get at the servers (I didn’t make it complicated, that was someone else), and I’m one of the few people who has a lot of web development experience (4 years, including 2 years profesionally). This is the latest page I’ve done, which uses Lightbox, a rather neat little set of Javascript to display full size images as an overlay on the current page. I also redid the HTML for the main site, to replace a mess of tables from Dreamweaver with a CSS version of the same thing. It reduced the page size by about 50%, and also makes it much easier to read. I’m planning to port the existing content into some sort of script, so that changing one link doesn’t require editing every page, but that is a bit off yet (I need to sort out what the web server actually runs).

iFind, a project of the SENSEable City Lab is an application designed for “Friendspotting”. It uses the ubiquitous Wifi coverage around the MIT campus to allow you to locate where you are pretty much anywhere on campus (minus a few buildings that we don’t have access point information for yet). The application then allows you to share it with whatever friends you want via an encrypted peer to peer link. This means that the information is shared only with who you want it to be shared with, and we as the operators of the iFind service have no information about your location (we can use a couple properties of the MIT network to guess which building you are in, but that’s it).
There are two parts to iFind. The shiny GPL licensed Java client, and the proprietary (sorta) PHP server. I was responsible for about 98% of the server code, and that’s what I’ll focus on, right after a pretty picture….

(yes, they were taken on a Mac. No, it’s not mine, the primary client developer uses it).
The iFind server is a relatively uncomplicated piece of code (around 25 files, and 35KB as a RAR archive), but there are a few interesting aspects. The biggest is that all communication with the server is done via XML. This creates what you could call an XML-RPC (Remote Procedure Call) system, although it isn’t nearly as flexible (aka complex) as other XML-RPC implementations. It is simply a custom defined protocol with a variety of messages that use XML to transfer the data and return the result. The entire protocol documentation is a 71KB Microsoft Word document (it does compress to 14KB as a RAR file though), which we keep somewhat private (it is available on request by sending a message to senseable-ifind [at] mit [dot] edu) to gauge interest. The server code will also be available on request for private use (pending a few agreements on release and such) for research and use at other institutions.
The other interesting aspect is the handling of requests. Once the server does some basic processing, and determines that the request is valid (well-formed XML, and including the expected method field), it passes off the request to an input handler. Input handlers extend a base class using the object oriented nature of PHP, which gives access to a variety of predefined methods and fields, such as an XML class for the output functionality. The advantage to this process is that adding a new method is as simple as adding a properly named file (the method name with no spaces and a .php extension) to the proper folder, and the server will handle requests. Any invalid requests will receive a generic error (either 100 Service Unavailable, or 104 Service Unimplemented) although the behavior is technically undefined (although it has no side-effects, and should not cause any problems or malformed output).
There are probably a few other interesting bits in the server code that I will run across while preparing it for the consumption of others (have to put in some comments and document how to extend it I suppose).

This is again a rather quick note. The developers (and sponsors) of Battlecode award a variety of prizes to teams for many different things. One was a prize for the most merciless (ie the team that hunted down and killed a defenseless, move and turn only) archon the fastest, while another was for the best team name. Blooregard Q Kazoo didn’t win either of those. We did however win the best formation award. This award was for our arrow formation which we would form above our archons to defend against EMP and air attacks. We also had the ability to fire out the center of the arrow, rather like a crossbow, or bow and arrow. We disabled this for the tournament, but it was coded and working. This earned us the best formation award, which was $200 and an iPod Shuffle.

The next post about Battlecode will likely be the last, and will contain our strategy document and descriptions of our matches (it may need to be two posts to avoid being too long). I will also hopefully have our final ranking from the tournament, so we can see if we improved (somewhat unlikely), stayed the same, or fell from our ranking in the seeding tournament. I feel that it is likely that we lost some ground, but probably not a lot. I know we didn’t finish in the top 16, which doesn’t leave a large margin to have improved, but it is probably possible.

I feel compelled to at least write a quick post noting that I am not in fact dead, but have been busy with Battlecode (see a couple posts down) for the past several days. Although the final seedings aren’t out yet, my team did reasonably well in the qualifying tournament, losing to two quality teams. We managed to win our first match against team General RAAM (after a bye), lose our second match against team Battletoads (the top ranked scrimmage team, seeded 9th), win our third match against team Global Warming, and lose our fourth match against team Little (to the third ranked scrimmage team, seeded 8th, beat us in seeding tournament). Battletoads was also one of the teams that finished in the top 8, so I don’t feel too bad about losing to them at all. After the final tournament (on Saturday) I will post our teams strategy writeup, and also hopefully go through our four matches, with some commentary on why we lost, and why the other team deserved to win.

With the basics out of the way, it’s time to delve a little bit deeper into some strategies for Battlecode. These are a few that have all been used by multiple teams, so I’m not giving away anything top secret here (especially after the seeding tournament).

• The Scout Tanker: With a low upkeep cost, scouts can be used to provide Energon to other units with a higher upkeep (EMP’s especially) to keep them alive longer. This can help to greatly extend the range of EMP’s. One of the most interesting applications of this could be called the Scout Railroad. It was a line of 10 scouts with one end anchored over the archons to pass up energon, who would feed any EMP that traveled along the rail to keep it alive. It wasn’t terribly effective, but looked impressive.
• The Archon Trap: Archons are a very difficult unit to destroy. Their health regeneration is able to match the damage output of a soldier with no problem, and can even survive two attackers with no difficulty if it is moving. The trick is to trap an Archon so that at least two, preferrably 3 soldiers are able to attack it. This can be done in corners, or with a large group of scouts along a wall.
• The EMP Wave: EMP’s are a dangerous offensive unit, and some teams simply used them as their only major unit. They would use Scout Tankers to keep the EMP’s alive, and send wave after wave of them at the enemy, hoping to cripple their energon production, and win that way.
• The Tank Assault: Tanks are a powerful ground unit, dealing major damage, plus splash damage. A pair of them can take down even Archons with little difficulty if they have a spotter. Teams that can move their archons, and locate the enemy without taking too much damage, and can get in range of a tank strike can be deadly.

There are of course many other tactics and strategies, but I don’t want to give away everything (as I do have a few ideas that I didn’t see implemented at the seeding tournament). Our team did quite well, being seeded 24th out of 137 teams. Hopefully that number can be improved in the final tournament.

Battlecode (also known as 6.370, or in past years, Robocraft), is an annual AI programming competition that occurs every year during IAP (Independent Activities Period). It centers around writing a program that will control a variety of different robots to achieve a certain goal. In previous years it has ranged from kill the queen, to capture the flag, to king of the hill. There are a variety of different robots, which change every year. The robots this year are:

• Archons: The most important units, the only unit with positive energon production
• Soldiers: The basic ground unit. Attacks other ground units adjacent
• SAMs: The anti-air ground unit. Attacks only air units with a range
• Tanks: The ranged attack ground unit.
• Scouts: The basic air unit. Attacks other ground units adjacent
• EMPs: An evolved air unit. Has a suicide ability that reduces the energon production of Archons in a radius. Can also attack air units.

Each of the units that isn’t an Archon has an upkeep cost in energon. Energon is the energy of the game, and it allows your units to live. Attacks reduce energon, and EMPs reduce the energon production of Archons. The goal of this year is to kill the 4 enemy archons, or to satisfy one of the other victory conditions. The victory conditions are:

1. Largest number of surviving Archons
2. Largest total energon production among Archons
3. Largest total energon among surviving units
4. Lowest team number (so earliest registered)

There are, of course, a few complications to make writing the AI more complicated than simply that of programming a basic game AI. There is no overaching player. In Battlecode, each robot runs a copy of your code, and must work together with the limited information available to each unit. This includes their sensor information (which varies based on robot type). They also can message robots in a limited radius to share information. There is no overarching “super” player that can see the entire map. You have to determine what the map looks like, how to pathfind, and everything on the fly with limited information.

With the basics of Battlecode out of the way, you can expect another post tomorrow explaining a few ideas for strategies (some I might use, some I probably won’t), and any details that I realized that I missed. The full game is of course more complicated, but this should be a sufficient overview for what I explain tomorrow.