Potential Topics: Here are some options for projects, in case you are looking for inspiration. This is just my wish list, you may have an even better idea of your own!
- Atropos: add an HTML version or an improved mechanical adversary.
- Matchmaker: add an HTML version or a mechanical adversary. A while back I did loads of analysis on states of this game; I would enjoy taking another look at this.
- Dictator: a 2-player voting game that desperately needs a web interface. No link, sorry!
- Football Ranker: I would like to analyze and compare this ranker to others. Is ranking teams to minimize the number of upsets NP-hard? If so, is this a good approximation algorithm?
- Fjords: How hard is it to play this game? What is the best strategy for the second phase (placing fields)?
- Tsuro: If all 8 players collude and can select whichever tiles are available on any move, can all 8 pieces survive placing all 35 tiles? How would you write a program to determine this?
- Collatz Game: What are the nimber values for different game states? How simply can you describe one state? How would you write a program to evaluate this? Can we find the nimbers for the first 100?
- Randomized Tree Searches: How well does a Monte-Carlo Tree Search algorithm work on different games? It performs well on Go, but what about Chess or Clobber or even an impartial game such as Nim?
- Something else you're more interested in than this nonsense!
What it takes: An independent project is not an easy assignment. I will expect:
- Approximately 8-10 hours of work per week. If you are replacing a course, this should be closer to 10-12 hours to make up the time missed in class.
- Self-Motivation. See the previous point! If you can't keep up with this, you will have a hard time completing your project.
- Weekly Meetings. Either once a week for one hour or twice for two half-hours.
- Brief weekly reports (emails) listing your accomplishments and road blocks.
- A written final report or user manual, if you are getting writing credit. If you are doing an Honors Project, I recommend using LaTeX.
- A presentation to the department about your project.
Getting Started: If you would like to work on a project with me, please get in touch with me. It helps to have done well in your other computer science courses. The following
suggested pre-requirements are helpful:
Note that only about half of the projects listed above actually had these prereqs! Please ask me if you have any questions!
If you are one of the students listed above and see a mistake above or want to provide extra information/material, please let me know! I'd like this to be as complete as possible, including links to your homepages!