Playlist Synchronisation for Portable Devices

I have recently been attempting to properly set up synchronisation between Windows Media Player and my portable music player (which happens to be my phone). Though I found that the Windows Media Player synchronisation tool does the job pretty well, it does fail in one respect: it cannot copy over playlist (WPL) files. For me, this was a bit of a nuisance, since I rely very much on playlists to categorise my music collection.

The solution for me was to write my own tool that synchronises a given set of playlists with a portable device that is compatible with WMP (Windows Media Player) – as I believe many devices tend to be. The tool works simply by finding the appropiate place on the device to which to copy the playlist files (a known XML descriptor file on the device should specify this), and then copying over these files, with the locations of the media files updated to point to those on the device.

Naturally, my choice of technology with which to write the thing was .NET/C# – this does mean that it’s not a fully standalone application, though it does only consist of a single EXE. However, thanks to a few particularly convenient features of the language/framework (primarily LINQ to XML), the code was largely trivial to write, and the majority of the ~200 lines is in fact error handling.

You can download the program here. As mentioned, it requires the Microsoft .NET Framework 3.5 (SP1) to run, which is not installed on any current version of Windows by default, so it will need to be downloaded and installed firstly if you don’t yet have it. Also, if anyone is curious to see the code, I may be able to upload that at some point.

The tool should be run from the command line, and would seem to be very straightforward to use. (Run the program with no arguments to see the help information.) An example command line to syncrhonise the playlists in the standard location of your user profile with a portable device on drive F might be:

pps F “C:\Users\username\Music\Playlists”

That’s all it takes. The task should finish within a matter of seconds  and then report some general information about the playlists it found and what it managed to successfully synchronised; else return an error message.

NB: If you’re wondering how the synchroniser matches the media files on the device with those in the playlist, I have a small admission to make. Because the directory structure is not guaranteed to be the same on the device as at the location of the source media, the current version simply matches media items by file name. This works perfectly well for me, though there is clearly a caveat. I am looking for an improvement on this method, and while I have a few ideas, I haven’t finalised my decision yet. Any recommendations by someone more knowledgeable on the subject would be appreciated.

Now, this program was designed primarily for my own use, but I did consciously attempt to make it usable with any WMP-compatible portable device, so hopefully people shouldn’t have any major problems using it.

Finally, it would be nice to hear any feedback regarding this little tool of mine, so please feel free to drop me a message (even if it’s just to say you’re using it). If I hear any suggestion for a worthwhile feature to add (or of course a valid bug report), I will gladly update the program.

Numerical Analysis for .NET

During my ongoing work on a computational project for university, I recently discovered the need to perform some serious numerical analysis from my C# code.  Unfortunately, I must admit that the .NET world only now seems to be catching up in terms of the free and open source libraries it offers for various tasks, and initially I was disheartened to find that there seemed to be nothing available for doing calculations on large (sparse) matrices. After a fair deal of searching, only a couple of somewhat incomplete and no longer maintained matrix libraries turned up. Being an avid user of StackOverflow, however, I decided that if anyone was aware of some library that could do what I needed, I would most likely find them there.

The result was much better than for what I was even hoping. dnAnalytics is a general-purpose package for numerical analysis in .NET that does almost everything for which I might possibly ask – and from my first impressions, does it very well indeed. This wonderful find is a well-maintained, fully open-source, library with great API documentation (not a wholly unexpected thing, but surprisingly uncommon among so many open source projects). There are several features that stand out as particularly impressive. One undoubtedly is I/O classes for Matlab and delimited files (among other formats). What is more, the library seems to offer both a fully managed version and one that wraps the Intel® Math Kernel Library. I’m not sure how the performance compares between the two (I haven’t yet tried the latter), but it is surely nice to have the pair of options available, quite similarly to how you have alternatives of cryptographic algorithms in the .NET BCL, that is to say, a) a fully managed version, v) a version based on top of the Windows Crypto API, c) a version that uses the CNG (Next Generation) API introduced with Vista. Perhaps what appeals to me the greatest about this library is that the developers have clearly gone to an effort to make it user-friendly, not only with regards to the documentation, but also by adding an interface friendly to F# coders (likely to be a language of choice for future mathematical/scientific programming), and even visual debuggers for Visual Studio (possibly the only library to date I’ve seen include them).

My particular usage of the library requires me to use the linear algebra (specifically, sparse matrix) classes. Although I must point out that the specific algorithm that I was intending to employ for the project was not available (see my later discussion), it did include a host of other ones, primarily focusing on direct and iterative matrix decomposition, which would appear to be quite handy in many circumstances. I haven’t yet had a chance to play with the other areas of the library, but I have noticed that it offers some statistical functions and methods as well as a number of modern pseudo-RNG algorithms such as the Mersenne Twister.

To conclude, I should come back to the point that the most important part of the analysis I require was not (at least direclty) contained by the library – finding the eigenvalues or eigendecomposition of large (1000s of rows/columns) matrices, which happens to be in relation to spectral theory, in case you’re curious. Even so, being such a complex field and one fraught with difficulties when it comes to implementation (numerical instability is a huge problem), I was not surprised to find that an implementation of the Arnoldi or Lanczos algorithm was not present. Fortunately, after a bit more searching around (by this point I knew specifically what I was looking for), I came across the ARPACK library, written in the archaic Fortran77 language. It did however seem to be exactly what I was looking for: a set of fast routines to find the eigenvalues of large (either dense or sparse) matrices of various types. After only a small amount of pain messing about with MinGW, I managed to get the code compiled nicely into a DLL. At this point, I am of course perfectly able just to use the P/Invoke capabilities of .NET and do some hackery to integrate the ARPACK stuff with my existing code and dnAnalytics. Yet, I am also inclined to do this whole task properly and basically write a managed wrapper for ARPACK that is tightly conforms with dnAnalytics. I could then perhaps submit these wrapper types (along with a few unit tests?) as a repository patch to the dnAnalytics team in the hope that they’ll take it and add it to the next release. As with most other projects at this time, I will have to see what time permits me, though I would certainly hope to contribute something substantial to what truly is a terrific project that I would love to see expand further.

LINQ to YAML

LINQ to XML is one of the many technologies introduced with the .NET Framework 3.5, and one that is certainly a step forward in terms of usability. It allows querying in both the functional style (using LINQ and lambda expressions) and the more traditional imperative one, meaning that it’s a great tool for concisely working with XML data in any sort of application, and undoubtedly a significant improvement over the old XML DOM that resides in the System.Xml namespace.

In the spirit of LINQ, and with the advent of YAML, I recntly decided it was about time that this new “markup language” were integrated with LINQ. Surprisingly, there does not already exist anything akin to LINQ to YAML out there (though there are a couple of fairly usable implementations of a YAML reader/writer for .NET). This seemed to me like a good chance to potentially create something that might be used by more than the odd .NET developer or two. My plans are to implement a LINQ to YAML provider either from scratch or on top of one of the existing YAML libraries. (Which option I choose will depend on the state of the existing projects, which I haven’t yet investigated properly. I am however suspecting that it might be worthwhile writing my own, since it would a) teach me all the intricacies of YAML, and b) allow me to support the latest version [1.2], which the existing libraries do not.)

Before I launch into an overview of my intended implementation, here is a little bit about YAML itself, for those who aren’t already familiar with it. Although technically YAML isn’t a markup language (after all, the recursive acronym stands for YAML Ain’t Markup Language) – it is rather a serialisation format – it does essentially fulfill the the role that XML  traditionally has, in a variety of common situations. I’m not going to try to sell the format to you right now, but it should suffice to say that you wouldn’t have reached this far in the post if you weren’t already at least intrigued! Without doubt, the format is actively gaining popularity because of it’s ultra-lightweight syntax and suitability for hand editing, perhaps the two points that summarise its advantages over XML.

Anyway, here’s a short example of a YAML document (taken straight from the Wikipedia page), so you can see precisely how pleasant it is to work with (at least for humans).

—

receipt:     Oz-Ware Purchase Invoice
date:        2007-08-06
customer:
    given:   Dorothy
    family:  Gale

items:
    - part_no:   A4786
      descrip:   Water Bucket (Filled)
      price:     1.47
      quantity:  4

    - part_no:   E1628
      descrip:   High Heeled "Ruby" Slippers
      price:     100.27
      quantity:  1

bill-to:  &id001
    street: |
            123 Tornado Alley
            Suite 16
    city:   East Westville
    state:  KS

ship-to:  *id001

specialDelivery:  >
    Follow the Yellow Brick
    Road to the Emerald City.
    Pay no attention to the
    man behind the curtain.
...

Of course, the great thing about YAML, which is demonstrated clearly by this example, is that you don’t have to have any real knowledge about YAML to understand exactly and immediately what the data represents, and as a bonus it doesn’t hurt your eyes to stare at for too long! Even the referencing syntax should be fairly self evident. (&id00 and *id001 would surely be nothing new to C programmers.)

The semantics as well as the syntax of YAML obviously differ to those of XML greatly, although there is almost always some sort of correspondence between the features and possibilities that the two formats offer. The only notable missing feature when contrasted to XML is attributes, yet their usefulness is questionable anyway.

Right, so now I ought to explain a bit about how I actually plan to design this library. The basic framework will be virtually equivalent to that of LINQ to XML. In other words, the hierarchy will be largely based around an abstract YamlObject (YObject?) class, and will look very much like the one contained within System.Xml.Linq.

LINQ to XML class hierarchy

Though LINQ to YAML must of course accomodate for the unique nature of the format, I would initially aim for minimal difference and only significantly adjust the hierarchy when it is found to be necessary. Classes such as XCData and XDocumentType would not apply at all to YAML, yet there would need to be a place for a YReference or such somewhere in the hierarchy. The referencing aspect of YAML will likely prove to be one of the more interesting challenges; while YAML’s lists, maps (dictionaries), and combinations thereof would seem relatively straightforward with regards to emulation of the LINQ to XML design, references would introduce a substantially novel concept. Some sort of implementation of lazy evaluation followed by concrete referencing should be able to solve the problem, but there’s no way to predict how well this might work in practice at this moment.

What I realised only after deciding to create a LINQ to YAML library is that among LINQ providers, LINQ to XML is somewhat special in that the LINQ aspect of it is built on top of LINQ to Objects (i.e. LINQ using IEnumerable<T> objects), with only a relatively small number of extension methods specific to LINQ to XML. Indeed, most LINQ providers (LINQ to Objects and LINQ to SQL among others) require you to implement the IQueryable and IQueryProvider interfaces to provide complex logic for interpreting and returning the results of expressions, as well as evaluating complex expression trees.  All this means that I can pretty much just design a DOM  to a certain style (i.e. one suited to functional code, like LINQ to XML), and let LINQ to Objects to everything else for me.

As I can’t think of anything more worth mentioning about my project at this time, I shall leave any more specific and complex details to a future post. Still, do by all means feel free to query me about my plans – I would be glad to answer any questions, and even gladder to receive some suggestions as how you think I might design LINQ to YAML, or simply a nod that you might find this useful at some point. I don’t anticipate this project to be a very long one, though I must say that both my work and free-time schedule are likely to be fairly messed up for the next month or two, therefore I’m not going to promise when I’ll get around to my initial release. Whenever it so happens, I will duly post the link to the project page on Launchpad (or wherever I decide to host it).

Strongly-Typed CSV Reader in C#

As part of a project on which I’ve recently started working, I found it necessary to write a class that reads entries from CSV files. Such a simple format, you might think, so why would I bother sharing such trivial code? Indeed, it is a relatively short class, but I thought I’d post it here nonetheless, primarily because I believe its usage promotes a design practice of which I am particularly fond, and I suspect (hope) other people may appreciate as well. There are also a few bits of code that might be considered interesting (and unusual) from a language/design perspective.

When I decided to formalise the logic for reading from CSV files, I firstly thought it would be nice to write something in the spirit of .NET 3.5 – in this case, easily compatible with LINQ, fully generic (strongly-typed), and attribute-oriented (as seems to be the trend in APIs nowadays). Before I launch into any further discussion, here’s the code for the class in full.

using System;
using System.ComponentModel;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Text;

namespace NetworkAnalyser
{
    public class CsvReader<TEntry> : IDisposable where TEntry : struct
    {
        private StreamReader streamReader;
        private FieldTypeInfo[] fieldTypeInfos;

        private bool isDisposed = false;

        public CsvReader(string path)
        {
            streamReader = new StreamReader(path);
            Initialize();
        }

        public CsvReader(Stream stream)
        {
            streamReader = new StreamReader(stream);
            Initialize();
        }

        ~CsvReader()
        {
            Dispose(false);
        }

        public void Dispose()
        {
            Dispose(true);
            GC.SuppressFinalize(this);
        }

        protected virtual void Dispose(bool disposing)
        {
            if (!isDisposed)
            {
                if (disposing)
                {
                    if (streamReader != null)
                        streamReader.Dispose();
                }
            }

            isDisposed = true;
        }

        public IEnumerable<TEntry> ReadAllEntries()
        {
            TEntry? entry;
            while ((entry = ReadEntry()).HasValue)
                yield return entry.Value;
        }

        public TEntry? ReadEntry()
        {
            var line = streamReader.ReadLine();
            if (line == null)
                return null;

            var entry = new TEntry();
            var fields = line.Split(new char[] { ',' }, StringSplitOptions.None);
            FieldTypeInfo fieldTypeInfo;
            object fieldValue;

            for (int i = 0; i < fields.Length; i++)
            {
                fieldTypeInfo = fieldTypeInfos[i];
                fieldValue = fieldTypeInfo.TypeConverter.ConvertFromString(fields[i].Trim());
                fieldTypeInfo.FieldInfo.SetValueDirect(__makeref(entry), fieldValue);
            }

            return entry;
        }

        private void Initialize()
        {
            var entryType = typeof(TEntry);
            fieldTypeInfos = (from fieldInfo in entryType.GetFields(BindingFlags.Instance |
                                  BindingFlags.Public)
                              let fieldTypeConverterAttrib = fieldInfo.GetCustomAttributes(
                                  typeof(TypeConverterAttribute), true).SingleOrDefault()
                                  as TypeConverterAttribute
                              let fieldTypeConverter = (fieldTypeConverterAttrib == null) ? null :
                                  Activator.CreateInstance(Type.GetType(
                                      fieldTypeConverterAttrib.ConverterTypeName))
                                  as TypeConverter
                              select new FieldTypeInfo()
                              {
                                  FieldInfo = fieldInfo,
                                  TypeConverter = fieldTypeConverter ??
                                      TypeDescriptor.GetConverter(fieldInfo.FieldType)
                              }).ToArray();
        }

        private struct FieldTypeInfo
        {
            public FieldInfo FieldInfo;
            public TypeConverter TypeConverter;
        }
    }
}

(Please excuse the utter lack of comments in the code. Most of it is self-explanatory, but admittedly some parts are probably not. I put it together pretty quickly, but I may get around to commenting it some time soon. Some basic error handling might also be nice.)

At this point it may seem rather excessive just to read data from a CSV file, but I hope you’ll agree that it’s worthwhile once you see an example of typical usage.

The first step is to define a structure (struct) that holds each entry in memory. Here we’re going to define one that holds some basic information about a programming language.

public struct LanguageEntry
{
    public string Name;
    public string[] Paradigms;
    public string LatestVersion;
    [TypeConverter(typeof(CustomDateTimeConverter))]
    public DateTime InitialRelease;
    [TypeConverter(typeof(CustomDateTimeConverter))]
    public DateTime LatestRelease;
    public float Popularity;
}

The TypeConverter attributes are completely optional, and are only required when you’re reading some fields that have unusual formats and whose values you would like to convert to something simpler/more accessible (e.g. a string “Jun2002″ to a DateTime object in this case). For any field of a type recognisable by the default type converter, you don’t need to bother, as is shown for the double type. (This actually applies to a very large range of types within the BCL, including System.Drawing.Color, which can be specified in any format that you might use in the propeprty editor of Visual Studio, such as “DarkRed”.)

Finally, here’s a snippet to show how you might actually use the CsvReader<TEntry> class to read from a CSV file. This example reads all entries from the languages.csv file and prints out to the console the names of all functional languages.

using (var languagesReader = new CsvReader<LanguageEntry>("language.csv"))
{
    var languages = from lang in languagesReader.ReadAllEntries()
                    where lang.Paradigms.Contains("Functional")
                    select lang;
    foreach (var lang in languages)
        Console.WriteLine(lang.Name);
}

Hopefully that’s now convinced you that this is the right way to go about reading data entries from files. What this class provides is completely strongly-typed I/O (reading in this case, though it wouldn’t be very hard to create a similar CsvWriter class), and a declarative manner to defining entry types (or records, to use database termninology).

I’m not going to delve too deeply into the implementation of the class, but I think it’s worth highlighting a few specifics. Going back to the code for the class, the first thing to notice is the Initialize method – this is where much of the interesting stuff is happening. To summarise: it loops over all the public fields of the type specified by TEntry, gets the default type converter for the type of each field (or the one given by TypeConverterAttribute, if it exists), and then stores the FieldInfo along with the TypeConverter in a simple struct. The only other noteworthy point is the call to SetValueDirect in the ReadEntry method. This uses a keyword that’s almost wholly unknown (and undocumented!) to C# developers by the name of __makeref (there are other related ones by the names of __reftype and __refvalue) – I was certainly unaware of it before today. The problem that I initially encountered was one of using the SetValue method, which works perfectly well on classes, but presents a unique problem with structs: namely, because they are value-types, and the obj parameter is of type object, the argument must be boxed (wrapped into a reference type) and placed on the heap rather than the stack, meaning that the heap-based copy gets altered, and not the one you passed to the method (which is on the stack)! What the __makeref keyword does is create a TypeReference that directly references the stack-based object and thus allows SetValueDirect to set the field accordingly.

That’s enough explanation, I think. If you still aren’t sure about how it works precisely, then feel free to comment on this post. I’d also be quite happy to hear what anyone thinks of the general design and implementation, too.

Evolutionary Algorithms

Genetic algorithms (or more generally evolutionary algorithms) is an aspect of programming that has interested me for quite a while now. The concept of using natural selection and simulating (in an abstract sense) the process of evolution of biological species with computational algorithms may not seem to useful upon first thought, but has in fact created a whole field of research in recent years. It turns out that genetic algorithms (GAs for short) are extremely useful and relatively efficient to throw at a problem about which you typically know quite little. (However. they are not terribly good at finding perfect solutions, which is why they are often used along with another late-stage optimisation algorithm.) They can be summarised as being essentially optimisation techniques that work in virtually any search space (though with varying degrees of success). Just to list a few examples of problems at which GAs tend to do well:

• Travelling Salesman Problem
• Model fitting and prediction (This is used with some degree of success to forecast stock markets.)
• Evolving artificial neural networks (These two nature-inspired AI algorithms work together quite well indeed.)
• Parameter/weight optimisation (in any system where there are large number of free parameters and complex inter-relationships)

I will point out the last one in particular, as it could potentially be used rather effectively with a game AI such as the Stratego one I am currently writing – more to come in a future post.

Unsurprisingly, many online articles have been written about evolutionary programming, ranging from basic introductions to scientific papers. If you’re curious about the topic and fancy learning a few things about it, I can recommend these articles, all written in plain understandable language:

1. Genetic Algorithms Overview by Michael Skinner on Genetic Algorithms Warehouse/AI Depot
2. Genetic Algorithms by Marek Obitko
3. Genetic Algorithms in Plain English by Mat Buckland on AI-Junkie

Finally, to the main purpose of this post: I have recently finished coding the beta version of my Darwin.NET project and released it on Launchpad. It is a library for generic evolutionary algorithms, with direct support for genetic algorithms and also an extension for gene expression programming (GEP). The ideas presented for GEP are what initially inspired me to create this library. A comparatively recent idea (traditional GAs were first designed in the 1950s), it was originally proposed in a 2001 paper that can be found here, and is well worth the read. Despite being published for a scientific journal, it is surprisingly straightforward to comprehend and should offer anyone a good understanding of why GEP is so special (and a huge improvement over traditional GAs). The end part clearly details how it can be used to solve several complex problems – according to the author’s statistics, significantly (orders of magnitude) quicker than GAs.

Now, the library that I have just released provides reasonably complete implementations of both GAs and GEP, though I must point out that it has not been extensively tested. (There are currently only two samples included with the source code, though they ought to at least help you get started. Before I attempt to write crazy extensions like a GEP-based algorithm to evolve neural network structure, my priority is to write a few more samples as I gradually improve upon the library. Oh, and I’ll begin to write up some proper documentation too.) I would also be very glad to hear feedback of any sort about the library (here or on Launchpad), or even a simple note that you are using it for a project! Any overlooked bugs are the first things I would like to get resolved of course, but design and feature suggestions are equally welcome…

Stratego Computer World Championships

The Computer Stratego World Championships is something of which I’ve been aware for a while now (since before its second event in 2008 in fact), but this year I’ve made my mind up to actually compete. Contrary to what its name suggests, it is a rather small competition (though indeed international and the only one of it sort), with only 5 individuals taking part last year. (Now I slightly regret not entering then while I at least had a statistically better chance, despite the lack of time and even experience.) This year there may be as many as twice as that number, and it appears as if there is even some academic interest from various places as well. Also, it seems that I will be submitting the first bot (computer player) written in .NET, thanks to a web service interface provided by Sven, one of the current and last year’s participants. (The standard interfaces provided with the SDK are only for Java and C++, requiring some form of IPC to get the client working with other languages.) Given that I have almost a full year to write, test, and improve upon my submission, I very much hope to submit a competitive bot by the time of the competition in December.

One of the great things about this tournament is the opportunity to test the bot you have coded at any time within a sizable online Stratego community at Metaforge (the host of the actual event), whose admin was nice enough to provide all participants with free testing accounts. If I’m lucky I may be able to get some useful feedback from some of the experts. The main method of testing and learning (perhaps automated learning if I’m feeling adventerous) will be offline, running marginally different versions of the bot against each other.

To me this competition is especially attractive because it deals with a largely unstudied area of game AI (hence the recent attraction of academic interest). Although it could be in vain, I’m hoping that my lack of formal education in this area may not serve as too big a disadvantage to me. It also means I can experiment with some really interesting theories without feeling I’m wasting time or reinventing the wheel. Until now, the most complex of the very few AI-related projects that I’ve worked on are a basic (though surprisingly skillful!) four-in-a-row player and an automatic solver for the Herbert challenge (part of Microsoft Imagine Cup in previous years – see my Herbert.NET project for more information). In fact, the AI that I ended up coding for a four-in-a-row game was quite overkill, since I implemented it primarily based on descriptions out of articles for advanced chess AI – now I hope to actually put it to good use.

Of course, programming a decent Stratego player is going to require quite unique algorithms and tactics. I will try and summarise a few of my theories here in brief, but don’t expect me to give too much away. (Admittedly, my ideas are currently little more developed than what I write here.) My plan is essentially to use something based on the alpha-beta search algorithm for traversing the tree of all possible future moves, almost identically to chess AIs. A transposition table and a few other traditional methods should come in handy, but that’s about where it ends and the statistical nature of the game requires its own approach. Clearly, considering an unknown opponent piece to be anything would allow the tree to branch far too quickly for any useful results, and would in many situations be near-pointless anyway. Very basically, my proposed solution is to use Bayesian probability and inference to calculate the likelihood of certain outcomes and thus assess the risk of different moves and strategies. Maintaining a list of probabilities of each opponent piece being of a certain type (for all nodes within the tree) is therefore a fundamental requirement, though with all liklihood not enough. In addition, it is perhaps equally important to keep track of what the opponent might guess its own pieces to be.  Now, simply choosing the move with the statistically best expected outcome would however produce a very poor player, since a good (human or computer) player does not base their moves purely on probabilitic calculations. For this reason, the program must have some understanding of the concept of bluffing among other things; it is generally not wise to attack an unknown piece with the potential of a large loss despite it being relatively likely that that it will defeat it anyway. In summary, I expect the design of the cost function for the search algorithm will be crucial in that it needs to account for movement behaviour of pieces as well as macro-decisions made by the opponent, apart from the usual point counts and piece positions. I cannot yet tell whether it will be more effective to simulate the human decision-making process when playing Stratego or that of existing AIs for board games (or quite possibly a hybrid of the two).

So that concludes the first of my posts on the subject. Look out for a follow-up post as I begin serious work on the bot and get some interesting results to show. For the meanwhile there is a rather long list of post ideas to keep me going.

Update

Imer Satz, the creator of Probe (the reigning AI of the Stratego Computer World Championships),  has kindly pointed out that there does in fact exist a host of files (roughly 75,000) of recorded classic Stratego games. The are available for download  from the gravon.de website. Imer has stated that he might be willing to put up an archive of all these games; I will update the post again if there is any success in this respect.

RoboChamps World Finals

About a month ago now I happened to receive a rather surprising email from Microsoft. Having read that I was invited to the Microsoft RoboChamps World Finals in Barcelona, I quite nearly dismissed it as spam until I read a bit further. It soon became obvious that it was in fact a real event for four “world finalists” to compete by programming robots to fight in a “Sumo ring” (essentially a physical version of the online Sumo challenge from the same competition). My disbelief was mainly due to the fact that RoboChamps wasn’t something I had devoted a huge amount of time to before then. I had watched some videos on MSDN Channel 9 and played around with a couple of the challenges downloaded from the website, but that was about it. Not before long I had encountered various bugs and issues in the SDK/challenges, quickly making me lose interest and move on to something completely new, as is often my tendency. (I might have anticipated the problems given that it was Microsoft beta software). Admittedly, the idea of programming robots in a simulated environment using the .NET framework sounded pretty cool, but I was busy enough at the time to (temporarily) forget about it. Back to my point: I soon found out that I had gained a wildcard place by my (comparatively) active participation in the forums, which at least clarified matters. So it came down to a free week-long holiday in the middle of the university term, simply to play around with robots (and win a guaranteed prize!) – how could I not accept such an opportunity?

I arrived in Spain late on Sunday after far too many hours travelling by aeroplane/train (and then getting lost and having to rely on my paltry knowledge of Spanish for directions to the hotel in the dark). Still, I did manage to arrive at the conference centre on time for the keynote (opening) speech of the yearly EMEA TechEd developer conference, which was acting as host to the RoboChamps finals. Unfortunately I wasn’t able to attend any of the other talks given at the conference during the week. (The ones on the new F# language [see this post] and the future of C# looked reasonably interesting, but as contestants we were coding and testing literally from sunrise to sunset some days!) The keynote itself was all about the next version of Visual Studio (VS 2010), including a few live demos, which overall looked very promising. I haven’t actually downloaded the CTP for it yet, so I won’t go into the details here. I may however wait for the next release, given that the IDE crashed within about 30 seconds after startup on the first demo – quite unsurprising really, but still rather amusing in what was essentially a big promotional talk.

The competition proper started that afternoon, when I met the three other contestants as well as the guy from Microsoft who was organising everything for us. They were Jackson, a professor of robotics from Brazil, David, and Doug, both two American engineers with many years of experience… I thought it would be difficult simply not to embarrass myself, but contrary to expectations the contest turned out to be surprisingly close (possibly due to the severe time constraints). We were firstly given our individual robots, two shared practice rings on which to test, a reference book for Microsoft Robotics Studio, and a brief explanation of how the event would be run before we then set to work. The robots were in fact just iRobot Create models (very similar to do the Roomba vacuum cleaner) with an embedded box running Windows CE and a webcam attached. In addition, since I was without a laptop, I was kindly given one to use throughout the course of the event, with nothing less than a pre-released version of Windows 7 installed. This ought to be the topic of another (short) post, but suffice to say now that I was quite impressed with some of the updates from Vista. I even hear that a slimmed-down version is being developed, which means people may have rather more luck running it on EEE PCs and other less powerful machines.

There were initially (that is the whole of the first two days) some horrible issues trying to run even the sample program on the robots. To start I had the bad fortune of being unable to deploy my program to the embedded box (which took rather long to realise and resolve with Visual Studio displaying a “Deploy Successful” message, despite my wondering why my program was still behaving like the sample one). Still, it seemed that everyone had their fair share of problems over the week, both hardware and software related. The fact that half of the robots were originally broken in some way (and some never fixed), together with the low charge on all the battery packs meant that I spent the first two days doing all too little. I should however mention that we did have plenty of assistance in trying to fix everything as soon as possible. (Microsoft did want a good contest after all, especially since the fight on Thursday was being publicised to any conference-goer who walked near.)

Eventually when I did get my program running, things turned out to be a lot of fun and it the challenge became one of strategy rather than debugging. I started by tweaking the code for the sample program and improving upon the vision processing, with a limited degree of success. My hopes to use the SIFT algorithm (its virtues preached to me by David [my aforementioned friend, not opponent]) for feature detection and estimating the location of the robot’s self/opponent immediately vanished once I had run a few speed tests on the embedded device, showing about a 100x slowdown compared to my moderately fast desktop. Noticing that my opponents were using relatively straightforward algorithms for machine vision was however a big relief. (SIFT was largely magic to me anyway, having tried to learn it only the previous week from Wikipedia and some of David’s old lecture notes.) I ended up taking the general structure and motor-control code from the sample program (as I believe the others did too) and using my own code for handling the sensor data, in particular the camera frames. The essence of my vision processing algorithm was some fine-tuned colour segmentation (using a flood fill function I ported from a previous project). I also updated the motor control code to use proportional feedback. Most else was quite trivial.

We finally came to the afternoon of the competition, with barely a day and a half of serious development behind me (and little more, if any, for the others). Despite the evidently enormous amount of work everyone put into the competition, it was great to be with such casual, open, and friendly competitors, and we were sharing ideas even until the last few hours. The format of the rounds was very simple: the winners of the two semi-finals progressed to the finals, and the losers played for 3rd place, where each round was the best of three 60 second bouts. The first semi-final between Jackson and Doug began at 1:00pm (see the video recording of it here) and I was beginning to panic slightly, realising that the recent versions of my program were strangely intent on running the robot out of the ring by itself and not easily resolvable. (I had recently done some 3 or 4 hours coding without any testing, which would explain…) A bit foolishly, I also had no sort of version control on my code (unless you count the poor man’s version control of copying/pasting the source directory every so often). When it came to my semi-final round against David, his robot needed only to watch mine drive full speed out of the ring after about 15 seconds. Fail, indeed. Crucially I had a couple of hours before the 3rd place play-off, which meant I could at least revert to a backed-up version (of unknown behaviour in the ring) and do some tweaking/testing. This somehow won me the round against Doug (though my robot only succeeded in avoiding being pushed off) to finish 3rd overall. I did get the feeling that perhaps I would have faired rather much better on first round had I only been less intent on using my latest version, but I was nonetheless happy to settle for 3rd given the overall situation.

We had all agreed earlier in week that we would let the winner choose first whichever prize he wishes, followed by the others in rank order. (This was mainly due to the lack of fondness for the RoboDog, which was originally going to be the 1st place prize.) When it came to decision time Jackson was very generous in deferring his choice to the rest of us, which means I was lucky enough to receive one of the two laptops. I still am not aware of its precise specs, but hearing that it was a high-end Alienware gaming laptop was enough to sell me. The Corobot ended up going to Jackson and the RoboDog to Doug, but everyone seemed reasonably pleased (the robots were . In the end I don’t think I could have hoped for a better experience (minus the hardware issues perhaps). Now that it’s apparent this was both the first and last RoboChamps competition (it has already been merged with the Imagine Cup), I feel particularly fortunate to have been invited. (The Imagine Cup, inspite of being for students, seems to attract far too many Eastern European hackers to give many people a chance.)

On a final note to this absurdly long post, Microsoft Robotics Developer Studio 2008 has just been released. You can download the Express version here for free, but there’s now also a commercial Standard version. I suppose the focus on hobbyists had to come to an end at some point, although the free version still looks quite capable. Also, I should point out that the release of the Mars Rover challenge (an especially interesting one) is now imminent in case anyone fancies giving RoboChamps a go – there will most likely be some pretty nice prizes for the winner/runners-up too, as with the previous challenges.

Windows SSH Server

This is a notice to anyone who might be interested in my open-source Windows SSH Server project. Windows SSH Server is a project I started earlier this year as an attempt to fully implement an SSH2 server using the .NET 3.5 framework (primarily C# with a bit of C++ for interfacing with Windows Console). The project is currently hosted on Launchpad. I have maintained a Bazaar repository of the entire source code.

It has grown to become just about usable now, providing a shell interface to any Windows Console application (e.g. cmd, PowerShell), though not yet programs such as edit. The protocol library SSH.NET has been written from scratch and is probably about 90% complete (minus extra features such as TCP port forwarding) and all the necessary cryptographic algorithms have been implemented/integrated in full. The main task in order to make it fully usable is finishing the Windows Console scanner (also very nearly usable) and then create a proper user-interface for authentication, which is currently hard-coded.  Of course, there are other aspects to the project such as the Windows Service (which is already working) and the admin interface, though they are not so important for the first release. I am also considering splitting the development into two seperate projects, one of them being the SSH server and the other an xterm shell for Windows Console applications (which would be utilised by the server). The main purpose of this is so that the xterm shell can be completed (or at least made stable) much sooner than the SSH server and can serve as a useful program by itself.

Unfortunately, although the project has come along very well I likely won’t be able to find the time to work much on such a large project in the near future. (A one-man team was never going to finish the job!) I am nonetheless keen to maintain the project and see it become mature with the help of other experienced coders. If you’re interested in contributing to Windows SSH Server (or the Windows Console xterm shell) in any way, please contact me via Launchpad and I’ll be glad to answer any questions and possibly set you up as a developer.

Querying the Semantic Web

Although the Semantic Web is yet in its infancy and has a long way to go before widespread adoption, the evolution of some of its projects is finally starting to enable some interesting applications. DBpedia now provides a semantic framework for accessing much (though far from all) of the data in the 2.5 million articles currently on Wikipedia. Other projects are attemping to create semantic databases of music, books, geography, and photos, to name some of the larger ones. If you’re not very familiar with the concept of the Semantic Web, I recommend the Wikipedia article as a good introduction, though for the purposes of this post you won’t need to know the details. In summary, the eventual goal of the Semantic Web is to create a huge interlinked web of knowledge that can be accessed and utilised by computers for all sorts of tasks. This would ultimately enable a computer to perform most of the actions humans can currently perform on the WWW, such as researching knowledge, making bookings, or ordering products from online companies.

Having done some research into the current state of the Semantic Web, I have recently been considering the (admittedly rather ambitious) idea of querying the semantic web with human-language questions. The plan is to make use of two great sources of semantic data, DBPedia and WordNet (a lexical database of the English language) to give precise answers to advanced questions, similar to the Ask.com service but much more “intelligent”. The former allows a program to access an enormous amount of encyclopaedic information while the latter provides detailed specific information about the meanings of words and expressions in the English language. The data is accessible in RDF format and can be queried via SPARQL (an SQL-like language). RDF is the standard model for representing semantic data, consisting of simple statements called triples (see the RDF link for a detailed explanation). Combined with the appropiate AI, a computer could (at least in theory) answer any question contained, either explicitly or implicitly, by the contents of Wikipedia. The aim is to allow a person to enter a complex question in English and receive an accurate response (or set of ranked responses) from the system, displayed in whichever way is most appropiate. Examples of such questions are:

• “When was Microsoft founded and where are its current headquarters?”
• “Who succeeded Octavian as Emporer of Rome and when was he born?”
• “List all of the papers published by Albert Einstein in 1905.”
• “Through which countries do the Alps pass?”
• “Give me a list of all the computers costing more than £1000 manufactured by Dell between 1998 and 2000.”

It is clear that translating queries like these into computer-understandable ones is far from a simple process and will require a significant level of AI. Some can be directly queried against RDF with hardly any further processing but others will need some form of machine logic (to perform simple numerical or set operations, for example).

It is important to note that there are a few major obstacles to creating such a system and allowing it to achieve high accuracy, though some of them can be at least partially resolved by human training. Such training or evolution of the system could be accomplished effectively by making question askers utilise a user-interface that provides feedback.

1. Human languages are inherently ambiguous methods of communication. Any algorithm used to interpret queries will necessarily involve a probabilistic model to resolve ambiguities. Also, more intricately phrased questions can be very difficult for AI to comprehend. A user would ideally use as simple and direct language as possible.
2. DBpedia in its current form does not express in a semantic form a very large proportion of the information contained by Wikipedia since much of it is given in continuous prose. However, improvements in the quantity and density of information in DBpedia articles are likely to come in the near future as Wikipedia and the Semantic Web continue their growth. The system could additionally be expanded to search within other databases of knowledge apart from Wikipedia, such as Geonames and MusicBrainz.
3. Similarly, WordNet is an incomplete lexical database of the English language; some words/expressions and links between them will inevitably be missing or poorly defined.
4. There is no easy way to link the objects and concepts defined by WordNet to those in Wikipedia/DBpedia. In fact, it could prove all but impossible to do so without the aid of humans (or a very advanced and currently infeasable level of AI.) Still, there are various solutions to this issue and the topic will be a main focus point in upcoming posts.
5. The processing or even actual intelligence required to accurately answer certain questions may be too great in certain cases. This does not present as big a problem as some of the other points, though it is desirable that either the human questioner or the AI recognises when a question is obviously unanswerable. An example of such a question would be:
   “What was the mean average speed of computer processors between 1990 and 1995?”
   Although there is a possibility that Wikipedia or other databases of knowledge implicitly contain the answer to such a query, it would require a very high degree of intelligence to answer it, which goes far beyond the purpose of the system. It should also be noted that this condition may not be differentiable to that where the information is not contained by the knowledge base. Questions which require opinionated replies however ought to be recognisable upon querying WordNet but before searching the knowledge base.

This post is only meant to be an introduction to my currently half-formed project idea of querying the semantic web for encyclopaedic information. I plan to discuss the details of high-level implementation in a series of following posts as I begin and continue work on this project. These posts ought to mainly include conceptual diagrams and images with explanations, plus some rare short snippets of code. I firmly believe that getting bogged down in low-level implementation details will not offer a good understanding of the system and should only serve to clarify key ideas. Explaining the architecture will be the focus of the series and certainly ought to fill enough posts! The project will become open-source once it (with  with any luck) reaches the first development milestone, which I will define at a later date. Current plans are to carry out development in C#/.NET 3.5 using LinqToRDF to query RDF data.

Well, that’s all for now, but hopefully you now have a general understanding of the the core ideas. Comments on any aspect of the project are welcome.