Graham Kendall

Individual Projects (3rd Year Undergraduates)

(Academic Year 2002/03)

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 2002/03.

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 2002/03

  1. A Visual Ant Algorithm for the Vehicle Routing Problem by Peter Southall (PDF : 398KB)
    Abstract : Ant Colony Optimisation is a relatively recently proposed metaheuristic that can be used to solve combinatorial optimisation problems. I propose to apply this methodology to benchmark instances of the travelling salesman (TSP) and vehicle routing problem (VRP) and report simulation results. Four ACO algorithms are presented in the paper. ASTSP and ASVRP are Ant Systems, capable of solving TSP and VRP instances respectively. ACSTSP and ACSVRP are Ant Colony Systems capable of solving TSP and VRP instances respectively. The results gathered from the systems proved extremely promising. A GUI through which the user can alter the parameters to the ACO is implemented, in an attempt to conglomerate recently employed methods in the field. Results from the system are compared to known good solutions in order to present the relative quality of the solution generated by the system. Furthermore, the performance of the implemented algorithms are compared and contrasted to each other in order to evaluate the relative strengths and weaknesses of the various algorithms.

  2. Collection of Real World Data for Poker Utilising a Standard Notation by Tim Perkin (Word : 783KB)
    Abstract : This dissertation describes a machine interface to gather data portraying real money poker games played at an online poker room. This is data which is currently unavailable to the academic community. Over 10,000 hands of poker data have been collected for analysis. This data should facilitate advances in the development in of an automated Poker player.
    No entirely standard notation exists for describing games of Poker. A high-level notation POKEN notation is defined in this dissertation, which facilitates the exchange of poker information between systems. An application of XML POKERML is also defined for the distribution of poker information which is intended for viewing by individuals.

  3. Interactive Ant Systems by Michael Gibbens (Word : 3667KB) (PDF : 865KB)
    Abstract : Good approximate solutions to the Travelling Salesman Problem can be produced using a variety of heuristic based approaches and optimisation techniques, among which Ant Colony Optimisation has been shown to be one of the best. This work combines Ant Colony Optimisation with various interactive techniques, allowing the user to cooperatively guide the optimisation using high-level knowledge of the problem domain.
    In comparisons to Dorigo's original results, the algorithms are shown to produce good solutions more rapidly, but are ultimately unable to match the quality of solutions found by Dorigo.
    The user is able to interact with a visualisation of the current search neighbourhood, adapting the heuristics generated by the algorithm with a number of basic tools.
    The user is also able to refine the behaviour of the algorithm through the alteration of control parameters.
    Both these techniques are shown to produce marginally better quality solutions than those produced without user interaction.
    The conclusion is that whilst small improvements can be found in either the time taken to generate good solutions, of the overall quality of solutions producible, there are fundamental limitations to the techniques applied in this work.

  4. An evolving poker-playing agent with the use of an evolutionary strategy and neural networks by Rakesh Garala (PDF : 657KB) (Word 1801KB)
    Abstract : Game playing has been used for a very long time as a test bed for artificial intelligence research. Ranging from perfect information games such as chess and checkers, where all game data is known, to imperfect information games such as poker; where competing agents must use probabilistic knowledge and risk assessment to make decisions concerning what to do next. The great challenge in artificial intelligence is to produce agents that will 'learn' as apposed to being 'told' how to play a particular game.
    Neural networks and evolutionary strategies have been found to be very successful when producing evolving game playing agents for perfect information games. I used these techniques to produce an evolving poker player that plays the pre-flop stage of a poker game, poker being a game of imperfect information.
    Poker is a very complex game and obviously too complicated to adequately develop a player that can play every stage of the game within a year, instead I decided to concentrate solely on the pre-flop stage with the aim of developing a competent pre-flop player. The autonomous poker player had no prior knowledge except the rules that govern the game and had to resort to learning tactics and strategies to play a good game of poker.
    There were many variants of poker available to investigate. However I used Texas Hold'em for my research, this is the poker variant used to decide the best poker player in the world in the World Series of Poker held annually in Las Vegas. Texas Hold'em is ideal for artificial intelligence research as it is considered to be the most strategic variant of poker but has relatively simple rules and logistics.
    The final artificial agent was very successful; the autonomous player learnt some very important strategies associated with Texas Hold'em. The player evolved over the training period to a poker-playing agent that can skilfully play the pre-flop stage of a game, demonstrating neural networks and evolutionary strategies can be used in the evolution of a poker-playing agent.
    The project could be developed in the future to accommodate all four stages of Texas Hold'em producing a high-class player.

  5. Designing Efficient Tree Searching Algorithms for Chess Variants by Michael Chadwick (PDF : 371KB)
    Abstract : This dissertation presents a new variation of Chess known as 'Chexi'. This project aims at producing an efficient system to be the underlying basis for a future commercial level computer player for this variation of Chess, to be used in industry.
    The player is based on a tree-searching algorithm, Mini-max but incorporates chance and so uses a similar search algorithm known as Expectiminimax. The main goals of the project are to write a player that runs quickly and efficiently, as it is intended that the player will eventually be used in a real life project, potentially used across the internet and also incorporated into a stand-alone version.
    Writing an effective evaluation function has not been the main goal of this project as this in itself could constitute an entire dissertation of its own. For this reason this project is based on constructing a state-of-the-art tree searching algorithm using the latest computer chess 64 bit technology known as Bitboards. The project looks into the various design considerations and goes into great detail showing the benefits of a system based on pre-computation. It then details the effectiveness of the methods used to achieve the goal. In order for the player to reach the status of being a competitive player the project would need to be further extended, however, it outlines the successful design and implementation of an efficient basis for a computer based solution to a game never before attempted.
    This project is intended to be the beginning of a commercial scale program. Chexi is a new game and currently being launched on the internet. It is intended that Chexi will be implemented as a stand-alone Windows application eventually boasting 3-D graphics and a full multimedia experience. The system is to incorporate a computer opponent. That opponent will be based on the work completed in this project.
    The website is due for launch in Summer 2003 and the Windows application later in the year. I have been very lucky to have been asked for my involvement in this project and as a result, this project is based on my work in the design and construction of the computer Chexi player.

  6. Evolving Explorer Ants: routing in telecommunications networks by Nick Fitzpatrick (PDF : 683KB) (Word : 2682KB)
    Abstract : Telecommunication networks are increasingly complex structures that require efficient routing techniques in order to cope with the growing demands of information transportation. Conventional centralised routing algorithms have many flaws and thus alternative routing methods are being investigated. One such area of investigation is based on the way ants forage for food, so called ant-based routing algorithms. Initial work has shown that this natural metaphor can outperform existing routing algorithms but much work has still to be done before such algorithms can be implemented in practice. With this in mind, we have supplemented previous work with an evolutionary strategy in an attempt to improve performance by allowing a population of routing ants to evolve over time, adapting the way in which they explore a telecommunications network. Several experiments are carried out to establish whether the addition of an evolutionary strategy improves the ability of routing ants to react to various network conditions. The results of the experiments, when compared to two existing ant-based routing algorithms, indicate that the inclusion of an evolutionary strategy improves the performance of ants when a) adapting to a given network topology and b) adapting to a given set of call statistics within a given network. The results presented are obtained from a simulation, using the British Synchronous Digital Hierarchy (SDH) network as a realistic network topology.
    The use of an evolutionary strategy, to tune network exploration parameters, has extended existing work, showing that the concepts of natural systems can be used to solve real world problems.

  7. The role of Sexual Selection in the Evolution of Communication by Mark Goldthorpe (PDF : 738KB) (Word : 1866KB)
    Abstract : Sexual selection drove the creation of the bowerbird's elaborate nest, the riflebird's riveting dance, the nightingale's haunting song and the peacock's iridescent tail. Recent theories suggest that sexually selective pressures for good imitators may have lead to the evolution of communication which in turn has lead to the unprecedented development of human intelligence. This paper investigates the development of communication in an Artificial Life simulation of sexually reproducing birds. Here we present a design to simulate the effect of female preference on adaptive male traits and demonstrate how a mutation to facilitate copying will proliferate throughout succeeding generations. We subsequently investigate the 'shielding' effect that copying has on selection of genes, and propose that sexual selection may be an element essential to prohibit system decay.

  8. The Artificial Emotion by Ryan Collins (PDF : 392KB) (Word : 602KB)
    Abstract : In order to create a machine that is truly intelligent, it would have to experience some form of emotion. To date, the possibility of emotions in computers has yet to be studied in any great depth. In this study I am first going to convince the reader that the three statements above are correct. This is followed by an examination of the research carried out on emotions in the fields of psychology, neuroscience and artificial intelligence. Finally, I will attempt to model and recreate the process of what happens when we feel an emotion in a form understandable by a machine.

  9. Genetically Programming a Tourament Poker by Tom Elkin (PDF : 345KB)
    Abstract : The game of poker poses a tough and exciting challenge to the domain of artical intelligence. Whilst there have been many successes in the field already, many poker playing systems only deal with a simplified version of the game. Also, little work has been done on developing a poker player specically for tournament play, which demands extra levels of strategy.
    Genetic programming is a fresh and exciting machine learning technique whose applications to poker have so far been limited to sub-problems of the game. This project explored new ground in considering the use of genetic programming to evolve strong tournament poker players. To facilitate this research, a system capable of simulating complete play of a Limit Texas Hold'em poker tournament was created. This was then integrated in a genetic programming system. A population of 50 players was evolved, using their performance in a poker tournament against one another to judge fitness, then applying crossover and mutation operators probablistically, based on that fitness. It was expected that over a series of generations the behaviours of the higher tness individuals would be recombined to produce better players.
    Experiments were carried out, competing players from later generations against players from earlier ones, to test for improvement. There was a positive trend between performance and the number of generations a player had been evolved over. This indicated that genetic programming certainly held potential for the development of advanced poker playing agents, and it is hoped that this work might be basis the of further investigation.

  10. Developing a Blackjack player using a Series of Neural Networks with an Evolutionary Strategy by Craig Smith (PDF : 560KB) (Word : 6609KB)
    Abstract : Since the early 1930's games having been the test bed for many ideas in the Artificial Intelligence area of computing. Over the years there has been vast improvements in the methods used, peaking in projects such as Deep Blue, which in 1997, beat the reigning world Chess Champion, Gary Kasparov. There was also the noted success of the checkers program called Blondie24, written by David Fogel, which went on to gain grand master status in the late 90's. Since then most perfect information games have been worked on and so research has generally moved onto imperfect information games such as poker, backgammon and blackjack.
    Blackjack is an ideal game to look at because of the proven mathematical work done in the past, which has produced a perfect strategy, which gives you a recommended action to take for every possible scenario. This project uses a series of neural networks along with an evolutionary strategy to adjust the synapses of the networks over a period of time. The aim is to uses these two techniques to develop a blackjack player that replicates the basic strategy as closely as possible.
    This dissertation shows how a population of random and knowledgeless blackjack players are developed to eventually derive a strategy that is close to the best strategies currently suggested for blackjack players to use. The results show that over a number of generations the players average pot of money left increases as the players learn which actions to take in different situations during the game. The project then suggests some possible extensions to the research and concludes what has been learnt during the duration of this project.

  11. Opponent Modelling in Poker by James Osbourne (PDF : 784KB)
    Abstract : Poker, a game of imperfect knowledge and deception represents an interesting challenge to artificial intelligence researchers. Unlike in games such as chess and checkers where all the information relating to the game is known, and therefore can be tackled with 'brute-force' methods, the game of poker contains a great many unknowns and the key to playing well, is to be able to make accurate estimates of these unknowns using the information available. The most difficult problem in dealing with poker and other games of imperfect knowledge is the modelling of opponents; the best real-world players attempt to gain a model as accurate as possible of their opponents through the various actions that they make during the course of the game. These methods include analysing body language and facial expressions. However, this is a job for the vision and image processing people.
    This project looks at the creation of an artificially intelligent poker player, Texem 2. The player makes use of the information made available to it during the course of a game to estimate the strengths of the opponents' hands, compares this to the strength of its own hand and attempts to make good decisions based on this information. As more information on the opponents is gathered over the course of a game the decisions made by the player improves. Various methods of opponent modelling were considered before taking this approach.
    The program utilises the public license classes produced by the research group at the University of Alberta, who created Poki and Loki generally considered as being the best poker players around. It also makes use of the ideas developed in my last project, Texem.
    The player itself has been developed to play the Texas Hold'Em variation of poker, one of the most popular in the world. With the fixed limit variation of this being the one that has been designed for.

  12. Evolving Blackjack Playing using Neural Networks by David Al-Tarafi (Word : 4999KB)
    Abstract : The idea of playing games against a machine fascinates us. This can be shown by the rapid growth of game playing consoles in the 1990's with the trend continuing to the present. From the beginnings of AI research, researchers have used game playing as a test bed for search and planning algorithms. Moving away from perfect information games such as chess, this paper focuses on Blackjack as a game of more than just chance. With existing mathematical models proven to be able to give the player an edge over the casino, this study shows how a neural network with varying knowledge of the game can play Blackjack at an expert level and achieve a profit. This report details the motivation behind the project, the design and implementation of the neural networks and the results achieved.

  13. Investigation into Prisoners Dilemma Tournaments by Oliver Jackson (PDF : 400KB) (Word : 6277KB)
    Abstract : The concept of the Prisoner's Dilemma has been around since the early 1950's. Since then several experiments and many years of research have been devoted to the subject. This paper starts by describing much of the experimenting and research performed in several different areas relating to the Prisoner's Dilemma. The paper focuses on a range of topics, varying from applications to real life, through to the theoretical aspect of the Prisoner's Dilemma as looked at by researchers such as Darwen and Yao.
    This study looks at possible methods and algorithms that could be used in order to accomplish the aim of the project; this being to see how different strategies perform amongst different populations. The paper will adopt a genetic algorithms approach to the problem being addressed and will outline the methods to be used. Genetic algorithms have been proved to be very effective at exploring a large and complex search spaces such as those presented by the prisoners dilemma problem.
    The results gained from this study highlight key factors in determining what makes a successful strategy within specific environments. The study has been very successful in achieving what was originally specified, with some quite interesting and revealing results, contrasting with previous findings gained by people such as Robert Axelrod.

  14. Computer Chess Player by Adam Bozon (PDF : 810KB) (Word : 1432)
    Abstract : The aim of this project was to write a computer Chess player that could play to an intermediate standard. Using Claude Shannon's paper "How to Program a Computer for Playing Chess" as a basis for scoring and tactical elements I managed to develop my program through hundreds of test games against opponents of various abilities to reach the target intermediate level of play.
    I wrote an opening book containing about 750 positions so that my program could play the early stages of the game well. Shannon gave a lot of scoring and tactical elements that could then be considered when evaluating moves after the opening stage. I used many of his factors and invented some of my own to encourage my program to position pieces strongly on the board, avoid weakly positioned pieces and to attack other pieces on the board. I experimented with using different values for pieces and tactical elements throughout the development of my player until I achieved what I believed were near optimal values. The scoring factors are activated and deactivated depending on the current position during a game and how far you are into the game.
    The results from my games at various stages of the development show conclusive proof that my fully developed player is a much stronger player now than it was before I developed the scoring algorithm. My test games included in this report show that the developed player has had success against both human and other computer Chess programs.My program uses the depth-first search method and the minimax algorithm to evaluate which is the best move to play. It searches every possible move to a depth of two moves for each player and uses alpha-beta pruning to stop branches when a "Checkmate" or "Stalemate" position occurred.
    In this report there is a discussion of related work, the design of a Chess program, how my program was implemented and developed, a collection of games that my program has played from various stages of its development and some ideas for future developments that I believe could improve my program's standard of play further.


EMAIL : gxk@cs.nott.ac.uk          Home page

Last Updated 15th June 2001