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
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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