Undergraduate Work
Here you can find links to the various projects I've undertaken at UWA. Click here to see my postgraduate work.
BSc Dissertation
SEE: Source repository for further work on the Symbibots framework.
↑ Symbibots game screen, click to enlarge.
"Is a Genetic Algorithm appropriate for use in making adaptive and quality real-time-game playing opponents, within a human time frame of play?"
The following dissertation outlines one possible answer to this question, including an example game-like problem and a Genetic Algorithm (GA) inspired solution.
The Genetic Algorithm described acts upon a population of game playing computer agents. Each agent contains a set of expressible instructions, composed of simple axiomatic behaviours representative of the games world model. The instruction lists are evolved through an iterative process of game playing in opposition to a human. The game played is called Symbibots, a simple two-dimensional shooting game. The human player uses the same genetic mechanism as the GA to co-evolve their own game-playing agent. Both the computer and the player are required to try to shoot each other with missiles, collect energy to stay active, and outlive one another to the next game round. Any "intelligent" and adaptive behaviour seen in the computer agent population is a result of evolution and the emergent complexity of their instruction set.
↑ Graph showing how symbiogenesis rate alters fitness as epochs progress, click to enlarge.
The idea for this dissertation came from background reading over the period of my degree and work placement (2003-2006) in topics including Retroviruses, Endosymbiotic Theory, Symbiogenesis, Genetics, Quorum Sensing, Artificial Life, Genetic Algorithms and Cellular Automata. Originally, I had the ambitious idea of bringing all of these concepts together: modelling cell interaction including models of molecules crossing virtual membranes, leading to higher-level effects like quorum sensing. Obviously, this early idea was way out of the scope of my knowledge and ability; let alone what I could accomplish in one year for a Bachelors degree. However, I still wanted to do a project that incorporated all of the biology, artificial life and artificial intelligence topics I was passionate about. I thought carefully on how I could relate these ideas to a Computer Science and Artificial Intelligence specific project. The concepts I found of interest in biology were all genetic and evolutionary operations. It seemed appropriate to try to wed these concepts from Biology with a Genetic Algorithm of some kind, since this is the analogous paradigm within the field of Artificial Intelligence.
↑ UML design for the Symbibots GA package, click to enlarge.
The result of this idea was Symbibots, a single player two-dimensional shooting game with the look and feel of a dirty puddle of Zooplankton. Symbibots attempts to be an expandable, general platform for investigating the use of Genetic Algorithms with agent based computer simulations. Currently Symbibots has not quite achieved this, but the program design and user interface allows for future development towards this goal.
Original Disease Model Idea (Discarded)
To create an artificial life simulation to investigate the propagation of retro-viral genomes within a population, and conditions required for the rise of sex based reproduction apposed to vegetative or a-sexual reproduction. Taking ideas from genetic algorithms, cellular automata and machine learning; I hope to have a world populated by various life-like agents that simulate the reproduction of life on Earth, along with the idea of retro viral disease (such as HIV). To accomplish this I plan to create a virtual machine capable of 'executing' or 'expressing' the genome of each agent. With a 'header' used to represent overall agent functionality similar to the differentiation between sets of chromosomes and the actual genes in real organisms on Earth. This is to reduce the complexity of the model so that an agent can be said to be male/female or a child of a previous ancestor etc. Then the actual genetic string is used to express behaviour at any given event or tick of the simulation. So movement, reproduction, feeding etc. will all be governed by functions acting on the inherited genetic like strings. I will also have the concept of a world environment that the agents are in which will change through a set simulation governed by starting parameters similar to the rules used when creating models using cellular automata. This will hopefully add another dimension to my investigation allowing controlled stresses to be placed on the population to investigate the parameters for the rise of sex. Another thing I would like to see is the possibility of stable 'retro-viral' genomes being expressed by a family of agents, this virus might add functionality facilitating reproduction or other beneficial symbiotic input. A notable portion of the human genome is made up of defunct retro viral genes, it is not clear as to the relationship life has on Earth with these simple organisms and whether there has ever been any beneficial relationships in the past. HIV is an obvious example of retroviruses effecting human life, however it is not always the case that retroviruses are pathogenic although none have been found in humans to date, this might only be because they are not of any noticeable importance. It might also be possible for dormant retroviruses which are currently part of our stable genome to become activated later as the result of a mutation, causing the rise of an ancient virus. Although none of this can be investigated in real life, a computer simulation provides the time scale required. My simulation will be biased towards the specifics of propagation of retroviruses; I hope none the less that it will be an interesting look at the possible complexities of this biological relationship.
Solo & Group Projects I've Worked On.
ulted (Solo Project 2005)
A simple command-line line editor.
In my second year I took a module on C & UNIX systems programming, one of the courseworks was to write a line editor similar to ed on UNIX operating systems. After I had met the coursework specifications I went a little bit further so that what I had created was almost useful: ulted. Not all the features are quite there yet, and there are a lot of bugs! However, the simple code design using a line iterator and per line action functions, means this might be useful code for someone to extend.
Grobbits1.1.jar (Group Project 2005 9 Person Team)
COMING SOON! When I finish getting rid of some bugs.
A 2D strategy/puzzle game written in Java using Java2D and SWING. The aim of the game is to keep a little character called a Grobbit alive for as long as possible. The game is turn based and has original animated-artwork and music. The game is very buggy and although I designed most of the game, I don't have any experience of the backend code since I only coded the GUI and graphics engine. The only thing im proud of in this whole program is the use of a crazy generic arraylist of hashtables I used to animate a set of graphics :D
Credit goes to:
Steve Davies (http://www.steev.me.uk/) Technical design, input and feedback; also implemented all of the backend classes (big job). Andy Williams (link coming soon) Kept quality to the max, made nice docs/website, and most of all: made the digital versions of the original artwork and muzak.
Further thanks goes to the rest of the team for: documentation (all), testing (Neil Brough, Steven Roberts), and giving input on the conceptual design (Ed Spencer, Elgan Jones). Finally Ruth Palmer for organising the work-load and doing some documentation when no one else could be bothered.
No thanks goes to the 9th member of the team who dropped out, except possibly for a small amount of a testing doc :S
WordFrequency.jar (Solo Project 2005 for Algorithm Design)
This is a command line program, an example execution: java -jar WordFrequency.jar -g The 1000 mystory.txt
A program that outputs word and trailing word frequency information for a given input file. A trailing word is any word that follows immediately after another in the text. The program can also be used to generate text of a certain format/style from a given starting word, based on the original input text. It should be of a similar format and fairly readable thanks to the frequency analysis. Some inputs work well with this program, such as giving lots of rhyming poetry often results in new nonsense poetry that rhymes. This could be useful for english students :D
WordLadders.jar (Solo Project 2004 for Algorithm Design)
This is a command line program, an example execution: java -jar WordLadders.jar -d girl ball dict.txt
This program can be used to try and find the optimum "ladder" of words between a given start and end word. So in the example execution above assuming the dictionary file included was used (dict.txt) the optimum ladder would be [girl, gill, gall, ball]. Where one letter was changed in turn to reach the end word in the shortest amount of changes. No words are repeated, and the shortest ladder is nearly always discovered. However the algorithm I designed doesn't appear to always get the optimal ladder some are lost when searching thanks to the heuristic I used. The search algorithm is quite fast and uses a heuristically guided (sort of iterative) depth first search. This was supposed to be an algorithm design project but I got crazed about making the search as fast as possible for huge amounts of words, so it all got a bit hacked and im not overly sure how the details work :S plus I found some optimisations whilst randomly fiddling and I don't even know why they work. As well as getting a ladder between two words, the program can generate a ladder from a start word to a depth you specify. No words will be repeated and if your goal can't be reached the longest ladder is returned. I don't know if this generating algorithm is complete but it's basically a depth first search where it's trying to reach the deepest part of a graph based on the wordladder rules. But from comparing my program with other students I think it's probably a fair attempt.
CarPark.jar (Group Project 2003 4 Person Team)
You might need to extract the car an lorry images out of the jar for them to be displayed.
A simple simulation of a multi-storey car park. This was my first attempt at writing a GUI with Java, I came up with the conceptual GUI design and wrote the majority of the Swing code, with the exception of the JTable and TableInterface which was put together by Andrew Jarrett. Andrew Jarrett with Matthew Bennett wrote up the simulation backend, apart from the timing component which I wrote into the Swing side of the program. Unfortunately due to illness Jonathan Stahlhacke towards the end of the project could only take a go at testing and documentation.
Useful & Reusable Java Classes I've Slung Together.
ImagePanel.java
Extends the Swing JPanel component, but allows you to have a neat image in the background of all the components. If the panel is bigger than the image, the image gets stretched to fit. This is a bit buggy and doesn't appear to display properly with some implementations of Java. All JPanel constructors available with the addition of taking a string representation of the path or URL to the image.
MusicButton.java
Extends the Swing JToggleButton component, automatically plays music when depressed. Handles all IO and events itself. Constructor takes string representation of the path or URL to the sound file.
RSS
Facebook
Stumbleupon
Delicious
Digg
gmail.com
