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.

Machine Consciousness

This post is the result of a discussion between David (a friend of mine and engineering student) and myself. It ought to be read alongside his post on the same topic, which takes a quite different perspective on many of the matters. As he states, it is quite unlikely that (even between us) we will cover all the points made by the both of us, though I will certainly make an effort to do so.

I now forget how the debate arose, but its main theme ended up as follows: Are modern computers conscious/self-conscious to any degree and what is it exactly that makes them so, or indeed differentiates them from humans in this respect? It began as a rather scientific/technological discussion but turned out to involve a good deal of metaphysics (in which neither of us can claim to be well versed, though we certainly learnt much in the process).

To start I should note that where David refers to intelligence, I more often that not mean consciousness. In my opinion, intelligence of certain kinds is something already possesed by computers to varying degrees; their ability to perform calculations and analysis of some forms of data far surpasses that of humans whereas they are not nearly so adept at holistic analysis or creative thinking for example.

Before I get to the core of the discussion, it is important to firstly (try to) define a few terms. There is no general consensus on the exact meaning of consciousness but the introduction of the Wikipedia article offers a good idea of what I refer to when using the word. Self-consciousness (or self-awareness more accurately) is a much easier to define concept, if still not a concrete one: if anything can actively identify itself in a mirror (whether it be a physical or conceptual one), then it can be deemed self-aware. Several animals other than humans have been labelled as such on the basis of this test, such as chimpanzees, dolphins, and elephants. Now the question is whether computers can currently demonstrate this. An example given by David was a computer recognising its existence within a network by pinging itself via a remote device (if I remember correctly). His argument is that if the computer receives a successful reply, then it can clearly determine that it exists (the remote device would act as the mirror in this example) and is therefore self-aware. I dispute this argument primarily by asking whether the computer actively/explicitly realises that it exists. Firstly consider that it would be easy enough to fool the computer into believing that it does not exist on the network by returning a fake reply (or none at all). Also, in effect the programmer is telling the computer that it exists if it receives a successful reply, which fails to meet my criteria for self-awareness. In a way, the programmer is imparting his own realisation of the computer’s existence into it. Humans on the other hand can actively come to the conclusion that they exist (even without sensory information). They need not be told that they exist, but rather only to think about it. The famous statement by Rene Descartes, “Cogito, ergo sum” (“I think, therefore I am”) can be seen as proof of this. The same argument applies to the mirror test for self awareness in animals, although the difference there is that observers have to make the decision (albeit with very high probability) that the animal has shown signs of self-awareness. David refuted this explanation, suggesting that a person raised without any contact with others would not have the ability to come to the conclusion of their own existence. However the situation in fact then becomes similar to that of other intelligent self-aware animals which have not been trained in any meaningful way. I do concede that it is theoretically impossible to be sure of self-awareness in anything other than yourself on the basis of “Cogito, ergo sum”, though the fact that humans and animals have not been explicitly/consciously programmed gives a good indication that self-awareness arose independently.

This whole argument leads onto the (wholly philosophical and non-empirical) issue of from where consciousness is derived. It is believed (or has at least been proposed) by some that all biological organisms have a certain level of consciousness (though not necessarily self-awareness). For example, the cells that compose an organism could be seen to have a certain level of conciousness (by the definition given earlier), while the whole organism could be seen to have a greater one. Similarly, the Gaia hypothesis (especially that presented by Isaac Asimov in his Foundation series) proposes that the Earth has a supreme level of consciousness, which is greater than the sum of its component consciousnesses (including humans and other organisms). It goes as far as to suggest innanimate matter has a minute amount of consciousness, though I suspect this was a unique idea for the sake of fiction. This theory can be summarised by the statement “the whole is greater that the sum of its parts”, which comes up in various places but I feel is perhaps most appropiate here. As I warned, the topic has now diverged completely from empirical science, since no-one currently knows a way to measure consciousness quantatively (or even define it in a concrete way). Continuing nonetheless; a computer may be said to derive its consciousness from either its programmers, internally, or from a combination of both. Humans may be considered to derive their consciousness internally (the neural networks of the brain are created from innanimite matter via biological growth and are developed with learning). Whether an entity derives its consciousness from a few other highly conscious entities (such as the prorgammers) or a multitude of entities with very low consciousnesses (such as cells and micro-organisms) could perhaps define what is to be considered independantly conscious (though there is clearly a grayscale here). We did not discuss this particular area too far as it was becoming horrifically abstract, though I think we both agreed that it was an interesting idea.

The final point made by David in his post is regarding the increase in the complexity (again another loosely defined concept) of an entity (system) in order to completely understand itself. His point is that the complexity will eventually converge to a finite value as a system grows indefinitely in order to understand itself. (See his post for a proper explanation.) A solely hypothetical question, but nonetheless intriguing. This view seems intuitively wrong to me, but specifically it would seem necessary that the system would have to recomprehend its entire self as it increases its complexity (and therefore level of consciousnes), since fully understanding the original system and the additional parts of it would not imply an understanding of the overall system (if you subscribe to the view that “the whole is greater that the sum of its parts”).

I don’t think I can comment very well on my general philosophical views as David has (though take what has been offered already). Looking briefly at some of the terminology however, I seem to largely subscribe to the philosophies of Holism and Emergentism, which appear to contradict with his views, as I might expect. (Why else would I be writing a post on the same topics?) Still, I subscribe very much to empiricism, with the small caveat that our knowledge of metaphysics is too small and basic to yet apply it to that too. (As a student of physics, I would be worried if I didn’t!)

Now that I’ve finally made this post (after much goading to fulfill my promise) and David has likewise made his own, I’m hoping that this debate is ended for the time being but that these posts stand well as records of our philosophical views.

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.