Prisoner's Dilemma.
In this multi-agent environment, one can explore
levels of cooperations and
deception between the inhabitants. The prisoner's
dilemma setup has been studied in many different areas, such as
economics, biology, sociology, and computer science. This surpisingly simple game provides interesting
insights into the overall properties of highly complex system, e.g., our global
economy. Here or here is a
description. Now, try it yourself!
As you can see, the basic setup is quite simpe.
However, one can explore arbitrarily complicated strategies (involving learning
and reasoning) in trying to win the game. Your team can build a multi-agent
visual java setup to explore different classes of agents trying to outdo each
other. If more than one team expresses interest in this project, we can have
the teams compete (in friendly manner of course).
Artificial Life. The goal of the work in
the area of Artificial Life is to study whether we can replicate some of the
key aspects of evolution within a computer program. We've discussed in class
genetic algorithms (GA) and genetic programming (GP). GA/GP techniques are used
extensively in the alife
community. Perhaps the most basic question is how exactly evolution can give
rise to highly complex (biological / artificial) systems. See here for some interesting examples of work
in this area. In particular, explore the SortNet
and Morphs links. The SortNet
problem has been studied extensively by Donald Knuth. There are still some
interesting open questions in the area, which you could try to resolve with
your program.
Games. Here is
a good collection of interesting games you might want to consider. For a
project, one could study how a learning strategy can be used to do with less search. You would have two
programs play against each other, where one searches to a smaller depth than
the other. Can a learned evaluation function
make up for the difference in performance? (Some good applets: Turnablock and
rolling cubes.) Of
course, the more traditional games, such as, chess, go, backgammon (with learning), and bridge, are
also good domains to consider.
Learning Competition. For an interesting and real learning competition, see here or here.
Theorem proving. The
challenge would be to prove an open problem in algebra or mathematics in
general. It's unlikely you
would succeed in cracking a real open problem, but a course project would give
you a better understanding of the issues and may put you on the path of solving an open problem in the
future. See McCune's page for some
background, and a view of search intensive theorem proving.
Reasoning and search. Puzzles are great for studying and developing new reasoning
and search algorithms. See here for a demo of a Latin
square completion. Issues to explore are e.g., heavy-tailed phenomena
(see also also) and backdoors. Sudoku is also a great puzzle to study. Here
is a paper
discussing research issues about the hardness of Sudoku.
Challenge: Can you generate a Spatially Balanced
Latin Square of order greater than 35? This paper started
as a student project: it proposes an approach that led to the
discover of the largest SBLS (order 35)! This paper
discusses a different approach.
Data Mining. With information age upon us almost all information is stored in some sort of database. Not only do databases grow in the number of entries stored, but also in the number of dimensions to represent an entry. We are far beyond the point where humans can coupe with the amount of data collected, thus computers are needed to pick up the slack. Data Mining concentrates on going through large amounts of data and finding a relevant information, the goals are to be as fast as possible as well as relevant as possible. Here are some pointers about the field.
Here
is a list of specific project suggestions.
NOTE: These are just some suggestions. Other project ideas are of course welcome!