Final Project

Objectives

• to do something interesting with computational intelligence for games

Guidelines

• workload should be in the same range as the first five assignments (something that would take an average 474 student 10-15 hours)
• try to find a game that is interesting (takes some time to learn to play well) but simple enough so you don't have to spend too much time writing code to implement the rules of the game (the model)
• you should implement a relevant algorithm (so just developing the model of a game and running it through OpenAIGym is not enough)
• you may share work on the model or use existing code (with citation) if you've chosen a sufficiently complicated game (something more complex than Pig) so that you may focus on the algorithm
• if sharing work on the model then you should still implement an algorithm on your own, unless you're working on a very complicated algorithm (for example something like AlphaGo with many steps, each interesting on its own)

Project Ideas

• Backtracking
  • Backtracking (DFS) or BFS by themselves are not too interesting, but could be
    • enhanced with rules to prune branches early or to select promising branches to explore first
    • compares to A* with different heuristics
• Dynamic Programming (Backwards Induction)
  • Hoot Owl Hoot
  • Multi-player Pig (>= 3 players)
  • Variants of solitaire Yahtzee (Kismet, Yatzy, Super Yatzy, Generala)
  • Backgammon endgames
  • Small versions of Kalah
• Simultaneous Games
  • evolutionary game theory – something like Conway's Game of Life but where each cell is inhabited by something that plays the game differently; see how the population evolves over time
• Search
  • alpha-beta with transposition table, or scout, or MTD-f for some game you can find a reasonable heuristic for
  • various enhancements of MCTS for something other than Kalah
• Genetic Algorithms
  • tune the parameters of a heuristic used with minimax or alpha-beta for some game
• Reinforcement Learning
  • implement DQN
• Supervised Learning
  • Fall 2019's solitaire Yahtzee assignment (I copied the supporting code and scripts to /c/cs474/hw6)
• Content Generation
  • invent a game and tune the parameters to be hard for agents using computational intelligence for some definition of "hard" (for example, "hard to beat a greedy agent using MCTS" or "hard for Q-learning") 
• Old competitions
  • Gin Rummy EAAI Undergraduate Research Challenge (closed to submissions but the code is still available)

Videos

So that other students my comment on your approach, create a short video (~5 minutes?) describing the game you're developing an agent for and your approach (you are not expected to have completed the code for your approach yet). If you do not include an example of gameplay then provide a link to a source that describes the rules of your game. A narrated or captioned presentation exported from PowerPoint or similar presentation software will suffice.

Address the following questions as appropriate (some questions may not apply to your game/approach).

• What is interesting about your game from a strategic point of view?
• What is challenging about your game in terms of developing an agent that plays your game (high branching factor, large state space, hidden information, etc.)?
• What simplifications have you made in order to improve your probability of success in a short period of time?
• Why is your approach reasonable?
• What other approaches might be better or worse?
• What are the similarities and differences between your approach and projects and examples from class? (This should be more detailed the closer your game is to one addressed in class. For example, for a variant of Yahtzee, the algorithm will be the same and so you should focus on the differences in the implementation like what information is contained in states for Yahtzee vs. what information is in states for your variant.)
• How do you plan to evaluate your agent?

For those working in a group on the same game, questions for which the answers are the same across the group (for example, questions about the game itself) can be answered as a group. For questions for which the answers are different (for example, questions about your individual approach), those questions should be answered individually. You may either submit a single video with all answers together, or separate videos with a copies of the common answers.

In the last week of class, watch 3 (graduate students: 4) videos from the Final Project Videos folder in the Canvas Media Library or from the YouTube links provided on Canvas and write short responses to them. There are several students or groups working independently on some games, so you should choose presentations on different games (don't watch 3 videos about Hoot Owl Hoot). Indicate which presentations you watched and then write your responses. Write at least 5 (graduate students: 7) total responses across the videos you watched (so 1-3 each). Each response should be a sentence or two giving your thoughts on the project, for example:

• agreement with the approach ("you say A should work because it is similar to what worked for B; I agree because it is also similar to C, which worked");
• disagreement with the approach ("you say A should work because it is similar to what worked for B; I disagree because it is more like C, which didn't work well);
• questions about the proposed approach ("how are you going to handle X?");
• any difficulties you foresee and any ideas you might have for overcoming them ("you're probably going to run into trouble with A but you can get around that with B");
• alternative approaches that you think might work ("you could also try C, which might work because of D"); or
• anything else interesting that comes to mind.

Course staff will not be able to collect, collate, and distribute your responses, so if you want the project authors to see them, please enter them as comments on Canvas or YouTube (optional).

Deliverables and Submissions

• Videos and Responses
  • upload videos to Canvas by Dec. 6 11:59pm
  • upload responses to Canvas by Dec. 10 11:59pm
• Code and Results
  • use the Zoo submission system, assignment number 6; due Dec. 16 5:00pm (no late days per University policy)
  • include a build script/makefile and a test script so I don't have to figure out how to run your code; the test script should include a brief description of your game, what your code is doing, and the results (for example, "I'm using Q-learning to play NFL Strategy.  Here's my winning percentage over 250000 games" or "I'm using MCTS to play Kalah.  Here's my winning percentage over 100 games when playing with a minimax player with a simple heuristic searching to depth 4, with both sides making random moves 10% of the time:")