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.
WWW Based. If
your interested in a WWW project, take a look at the ReferralWeb
project. I can get you the basic
code but there is still a lot of room for improvement!
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, planning, and search.
See
here
for a paper with challenge problems. The code for GSAT / Walksat / SATPLAN
is available. There is room for improvement and experimentation. See also
GRAPHPLAN.
This is a more research oriented direction. See here
for a demo of a stochastic search procedure. Issues to explore are fractal
phenomena and chaotic
behavior in the search space. Drop me an email
for more details.
NOTE: These are just some suggestions. Other project ideas are of course welcome!