Further Project Suggestions for CS-4701

Scientific visualizations of AI methods In class, we have seen various demos of AI techniques (e.g. local search for the N-Queens problem and the GA walker). These demos came out of course projects. The visualizations are very useful in demonstrating key algorithmic and other concepts. Other web-based visualizations of AI concepts,  e.g., game tree search or different machine learning methods, would make for great projects.

 

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 surprisingly simple game provides interesting insights into the overall properties of highly complex system, e.g., our global economy. Here is a description. Now, try it yourself!  As you can see, the basic setup is quite simple. 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 (A-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 A-Life community. Check out some of the demos  Perhaps the most basic question is how exactly evolution can give rise to highly complex (biological / artificial) systems. Cellular automata provide a common framework for A-Life simulations. The basic patterns are here here. There are many directions for possible projects. For example, can you evolve “the most complex” cellular automata rules? 

Games   Here is a good site discussing various games in the context of AI. 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.) Consider your own favorite game or go with more traditional games, such as, chess, go, backgammon, and bridge.

Games and the Turing test Here is an interesting project on game programming to beat a version of the Turing test. Consider other games or domains for this.

Twitter / WWW For a fun twitter style project, see here. There is still room for many variations.   

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 (Here  and here.) For a demo on randomized backtrack search, see here. There is room for improvement and experimentation. This is a more research oriented direction. 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!