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.