This assignment allows students to gain experience with AI game-playing algorithms, implementing minimax and alpha-beta pruningand designing a utility function for measuring game states. The assignment uses Connect Four, a relatively simple fully-observable and deterministic game that students are likely to have seen before. Students are responsible only for developing an agent to play the game; the game itself is already implemented and given as part of the student-facing materials. The assignment breaks down the requirements for the two algorithms into smaller chunks in order to make the whole assignment more approachable. We also provide code for Tic-Tac-Toe so that students can apply their code for minimax and alpha-beta pruning to a simpler game where sub-optimal moves will be more obvious, indicating potential bugs in their implementation. The assignment allows for a tournament to be played among all student submissions, potentially awarding extra credit to the winner of the class tournament.
This assignment was developed for an upper-level AI class, with Data Structures as the prerequisite. Game-playing is the second major topic covered in the course, following heuristic search. We announce the assignment after covering minimax and alpha-beta pruning, allowing two to three weeks to complete the assignment.
The assignment contains starter code for both Python and Java. We include both because most of our students have experience in both languages and we want to encourage them to use their preferred language. Adopters could choose to offer only one language without impacting the merits of the assignment.
Faculty adopting this assignment may be tempted to have students implement the game rules, in addition to the AI algorithms. This would substantially increase the scope of the assignment and the time required. Doing so would also mean that students implementing functions to evaluate board state as part of the alpha-beta algorithm would not be able to reference the existing functions
to determine winning or losing states.
Adopters looking to replace Connect Four as the game would need to either build a model for their preferred game, such as the model included in this assignment, or require students to build the model, as noted above. In order to keep the assignment at the same level of difficulty, we recommend using another game that is both fully-observable and deterministic, like Connect Four.
This assignment uses Meaningful and Relevant Content. When teaching minimax and alpha-beta pruning, it is common to use toy games without a real-world analog (particularly as examples to explain the two algorithms), very simple real-world games (e.g. Tic-tac-toe), or complex games whose rules and strategies are not commonly understood without extensive experience (e.g. chess, go). Tic-tac-toe is too simple for students to find relevant, while chess may be too difficult for students not previously familiar with the game. Using Connect Four splits the difference between these two games – the game and basic strategy are commonly known, and the rules are relatively simple. The complexity of the game (branching factor, maximum depth) falls between Tic-tac-toe and chess.
This assignment also Encourages Student Interaction, suggesting that students test their agents against each other. While establishing a tournament for extra credit may inspire competition and discourage students from playing each other, we actually try to encourage students to play-test their agents against each other in order to see how well the agents are doing. Many students focus on playing against their agents themselves, but find that they are not as strong of a Connect Four player as they thought, losing frequently to agents that are reasonably well-designed. By pitting agents against classmates’ agents, students get the chance to integrate their code and discuss the outcomes of their games, potentially strengthening the strategies used in the alpha-betapruning heuristics.