Introduction

This page details the third year individual projects that are/have been supervised by Graham Kendall who is a lecturer in the Department of Computer Science at The University of Nottingham. This page contains details of projects supervised in the academic year 2001/02.

The main project page can be found here.

Downloadable Dissertations

Some of the projects are available for download, so that you can view them. This facility is for current third year students, being supervised by me, who can use previous dissertations for their own research and also to look at previous dissertations to see how to lay them out etc. (it also saves the inevitable requests I receive asking to see a "good" project from last year, with the risk that I never see it again!).

As such, these files are password protected and, to get the username/password you need to EMAIL me. People outside of the university will not be given access.

In addition, I cannot give access to those students outside of my tutor group. You should approach your own tutor to get copies of previous dissertations they have supervised.

Note : I cannot make the files available in formats other than those already supplied.

3rd Year Projects Supervised in 2000/01

Towards a General Purpose Artificial Life Engine by James Davis (PDF)
Abstract : Artificial life (A-Life) is concerned with the creation and study of human built systems that exhibit lifelike behaviour. The field of A-Life encompasses disciplines such as computer science, mathematics and biology. Although there have been many studies conducted in the field of A-Life concerned with many of the diverse aspects of living systems, to date these studies have required the development of an A-Life engine/simulation specifically for use within a particular study.

The main aim of this project is to take steps towards the development of a general purpose A-Life engine that can be easily altered and/or extended for use in the study of a variety of A-Life issues. This would then enable those conducting a particular A-Life investigation to focus their efforts more upon the issues they are concerned with, without them having to go to the trouble of developing an A-Life simulation from scratch specifically for use with their study.

The A-Life engine itself is comprised of a two dimensional world inhabited by artificial flora and populations of artificial heterotrophic organisms (organisms that feed on other organisms) that are henceforth referred to as critters. The behaviour of these critters is controlled by an artificial neural network brain. New critters are created using artificial evolution which combines the genetic makeup of two critters into the genetic makeup of novel child critters. Therefore critter evolution mimics real life natural evolution, with the critters most adapted to their environment surviving longer than those that are less well adapted, giving them more opportunity to contribute genetically to future generations of critters. No learning occurs within a critter's neural network brain during that critter's lifetime. Instead, the connection weightings of the neural network are altered as part of the evolutionary process. This is so as the majority of living species act solely upon instinct, rather than exhibiting a degree of learned behaviour, as seen in the higher species of real life animals.

Many aspects of the simulation are customisable by the user, which gives rise to the general purpose nature of the A-Life engine. It is hoped that this generality will make the simulator useful in such diverse applications as the study of creature senses, evolutionary dynamics, the study of artificial ecosystems, and the study of collective behaviour amongst others.

The A-Life engine has been developed using the Java programming language, as this gives the project cross-platform portability, and hence is the ideal tool for taking steps towards the goal of creating a general purpose A-Life simulator. This is so because Java allows the easy exchange of ideas between people working within a field without the developer having to worry about the targeted users' choice of operating system.

Both a graphical and a text-only version of the simulation have been developed. The graphical simulator allows the study of collective behaviour whereas this is not the case with the text-only version. However, if one is concerned primarily with areas of study such as population dynamics, where there is less need of a graphical view of the world, the text-only version of the simulator yields results faster, as it does not have the computational overhead of a graphical display of the virtual environment.

This was an ambitious project, and although a large step towards the ideal of a general purpose A-Life engine has been taken, there is still a large scope for future development.
Investigating Distance Distribution Complexity and its Aplication for the Optimisation of Genetic Algorithms by Christopher Sheffield (Word) (PDF)
Abstract : Genetic Algoritms are an important mechanism used during studies into Artificial Life. There are many ways of measuring the optimisation of individual algorithms, but few measure the diversification of the population they are contained in. Jan T Kim introduced Distance Distributed Complexity (DDC) as a way of quantifying the diversity of a population. A measure for the diversity of a population is particulaly useful in the study of open-ended genetic algorithms. Kim hypothesized that as diversity is tentatively correlated to genetic algorithm efficiency, DDC could be used as a dynamic controller of the parameters concerned with genetic algorithm optimisation. In this paper I have reproduced the results confirming that DDC as a measure of diversity within the population, using a different genetic algorithm in a more complicated environment. I have also shown that introducing the mechanism of "crossing over" to the genetic algorithm increases the speed at which diversification takes place, but has no positive overall effect on the level of diversification. I also investigated the possibility of using DDC as a dynamic genetic algorithm controller. My results demonstarted that this was not an area to which DDC can be put to use.
An Evolving Poker Player by Mark Dimelow (PDF)
Abstract : Research into how computers play games is a big research topic. Some games such as chess are well researched, and AI players are now capable of beating the best human players. Other games such as poker are not as well researched, and human players can always out perform AI players. Recent research has shown that AI players can be greatly improved using adaptive learning techniques in order to change their playing style to counteract their opponents playing style. This project carefully studies this recent research and shows how this can be built upon in order to develop a new evolving poker player using a population based approach and a genetic algorithm. The resulting poker player was then tested against various different playing styles, and in each case the player evolved its strategy in order to maximize potential winnings. The poker player builds on previous work and successfully demonstrates how effective the evolutionary techniques truly are.
Ant Colony System for the Travelling Salesman Problem by Russell Bentley (Word)
Abstract : Ants and other social insects have an uncanny ability to find their way to and from sources of food and building materials. They operate in large colonies with great efficiency, yet no single ant gives instructions. The complex patterns that are seen are an example of emergent behaviour.

The actions of ants were used as inspiration for the development of ant algorithms to solve Travelling Salesman Problems.

A system was developed by Marco Dorigo that emulated the behaviour of ant colonies. This proved to be the fastest algorithm available for solving travelling salesman problems.

This work looks to produce and test this algorithm and then to optimise it's already formidable problem solving power.
ANTZ: Artificial Ant Research by Matthew Tester (Word)
Abstract : The ANTZ system uses independent ant agents to try and produce co-operative behaviour as a colony. The colony aims to efficiently collect food from a grid-based environment. The behaviour of the ants is determined by the colony's characteristics set as a genetic code of parameters (or gene). The colony has a fixed time limit in which the ants will move about the environment to try to collect as much food as possible. The more food collected, the fitter that colony is deemed to be. The Artificial Intelligence technique of Evolutionary Strategies is used to compare two colonies fitness and so to evolve a colony of ant agents that can efficiently find food in the environment. With the agents being almost blind and there being no central control, the technique of stigmergy is used. The ANTZ system is experimented with using different parameters so to test its capabilities.
Evolving Ant Colony: Optimisation by Distinct, Evolving Ant Agents by William Ratcliffe (PDF)
Abstract : There is an increasing interest in computing methods that are inspired by natural systems to solve complex search problems. Ant System (AS), developed by Dorigo et. al., is such a system. Using a population of agents whose behaviour is inspired by ants solutions are formed by the aid of heuristics that are used by, and modified by, the agents. The use and modification of the heuristics allows cooperation between agents.
This project won the prize for the most outstanding project of the year (across all of computer science, not just those I supervised)
Developing an Adaptive Cribbage Player by Stephen Shaw (PDF)
Abstract : This study focuses on the concept of evolutionary strategies as applied to games, in order to produce an 'evolving' cribbage agent. It contains a discussion pertaining to the current crop of cribbage-playing computer games, as well as the way in which similar 'artificial intelligence' techniques have been previously applied to other games. It was shown that by applying evolutionary strategies during the discard phase of the game of cribbage, a marked autonomous improvement in the performance of the agent could be observed. The resulting cribbage-playing program performed to a fairly "good" standard - and can be shown to comprehensively outplay an undeveloped agent.

This report details areas such as the motivation for this project, the design and implementation of the project, a discussion of the results obtained and a discussion of the further work which could be carried out in this area.
A paper arising from this project was accepted by CG'02

Kendall G. and Shaw S. An Investigation of an Adaptive Cribbage Player. Accepted for Computers and Games 2002 (CG'02), Edmonton, Canada, July 24-27, Edmonton, Canada. This paper will appear in the LNCS, Springer-Verlag volume that will follow this conference.
Evolving Blackjack Player by Lewis Hardwick (PDF)
Abstract : The title of my dissertation is Evolving Blackjack Player. The aim of the dissertation was to produce a virtual computer blackjack player which evolved the more blackjack it played.
This document is divided into a number of sections. Firstly the Motivation (page 3) behind the undertaking is covered. In this section issues such as why this problem was chosen, why the work has been done and a description of the exact problem at hand.
The second main section is the Description of the work (page 4). The description section begins by highlighting some of the background of the game and a ‘whistlestop tour’ of the rules. This section details what the dissertation is meant to achieve in terms of results gained. It also outlines how the software is supposed to function.
There is then a section devoted to Related Work (page 6). Details of other work in this field are explained and the methods used. The related work section also covers why this piece of work is new and how it relates to other work previously carried out.
The Design section (page 11) gives an in-depth description of the design decisions made and what factors influenced those decisions. It also states why the design chosen addresses the problem.
The next section is the Implementation (page 17). This gives details of how the solution was implemented including details of the language chosen, how the issues of actually making a working piece of software were addressed and also pseudo code showing how this implementation worked in reality.
Evaluation (page 29) of the software covers how the software performed during a number of trials. It includes graphical representations of the software during these trials. Conclusions are also drawn as to the success of the undertaking in relation to hands won/lost and also compared to the statistical finding of other work using different methods of playing better blackjack.
There is then a Discussion section (page 33) outlining areas of the software which could be improved/done differently. It also suggests some further work that would extend the work undertaken here and how that might be structured.
There follows a Bibliography (page 36) which lists all publications explicitly mentioned within the document. Finally there are the Appendices (page 37) which include various data which may be of further interest. For example sample results of the trials are here in tabular format as well as a code listing.
Customer Charters and Complaint Letters by Shonali Pluck (Word)
Abstract : This project develops a customer complaints service that uses a website and a database. The database holds details of customer charters for various different companies. Users are able to access and interrogate the database through the website. The website is used primarily to validate complaints against the customer charter for the particular company the user is interested in. If the complaint is valid then the user has the option of creating a letter automatically to send to the company involved.

The database contains contact name and addresses as well as details of the various companies. The user is able to find out contact information for companies, without having to create a letter.
Evolution of a Blackjack Player by Luke Thompson (PDF)
Abstract : Evolutionary Algorithms can be used as a form of Adaptive Learning in order to generate or improve the Artificial Intelligence used in a variety of areas.

This dissertation explores using Evolutionary Algorithms to enable a computer program to learn its own set of rules for playing Blackjack. After much iteration, the choices that should be made in each situation would have been calculated, and the results compared with those stated in the optimal mathematically formulated models.
Implementing Chinese Chess by Andrew Tang (PDF)
Abstract : Chess has always been one of the most popular games in history dating back from as early as the 6th century. Although chess of today is different to what it was then, the main objective of the game remains the same. To win in a game of chess, the player must capture the leading chess piece in the opponent’s army. Each player must try to use each chess piece to both attack and defend from the opposing army.

Even though there are many variations of chess from different parts of the world, they all stem from the same source and origin. Today, the most well known version of chess is International chess (sometimes European chess). The rules for International chess have spread around the entire world and are known by almost everyone. Therefore, when someone mentions chess, usually it refers to the rules and chess pieces set by International chess.

The first computer chess program was created in 1960. Although this was primitive and easily beaten, its birth paved the way for more advance Chess programs which later defeated the undisputed best player in the world at that time. Most of the implementation of Chess, especially those created in the beginning, used the rules and chess pieces of International chess.

This project deals with implementing Chinese Chess with an artificial intelligence. The AI side of in Chinese Chess is explored and the success in creating a Chinese Chess program with suitable advance intelligence to beat most people.

EMAIL : gxk@cs.nott.ac.uk

Home page

Last Updated 15th June 2001