Homework 2: Reversi Agents

Greedy search, minimax, and alpha-beta pruning

Implement and compare Reversi agents in the PySide6 game from Spring 2025.
Adversarial searchPython + PySide6
Your goal: implement the four required functions in ai.py, run all 16 AI match types in the PySide6 Reversi game, and report the final piece counts and a board screenshot for each trial.
Submithw2submission.pdf
AnnouncedMon, Sep 21, 2026after Lecture 10: Alpha-Beta Pruning
DueMon, Oct 5, 202611:59 PM Eastern · 14 days
StarterDownload below
Starter packagePySide6 Reversi game

The original Spring 2025 graphical game, with player settings, an animated board, piece counts, move history, and unfinished ai.py.

Homework Submission Instructions

  • Due Date: October 5, 2026, at 11:59 PM Eastern. Late submissions will incur a penalty, as detailed in the syllabus.
  • Please submit only one file named hw2submission.pdf through Canvas.
  • Paste your code in ai.py into hw2submission.pdf. Don’t paste other codes.
  • Scoring: The completeness of the homework will account for 80% of its score, while correctness will contribute the remaining 20%.
  • Grade Contribution: This homework contributes 10% to the overall course grade, as specified in the syllabus.

Background

Reversi is a strategy board game for two players, played on an \(8 \times 8\) board. Players take turns placing discs of their color (black or white) on the board, with the goal of capturing and flipping the opponent’s discs by trapping them between two of their own. The game continues until the board is full or no valid moves remain, and the player with the most pieces on the board wins. For more details, refer to the Wikipedia article: Reversi on Wikipedia.

When implementing Reversi in code, special attention should be given to situations where a player has no valid moves. In such cases, the turn must be passed to the opponent, and if neither player has a valid move, the game ends. Properly handling these scenarios ensures that the game logic remains correct and adheres to the official rules.

Task

  1. Download and extract the starter package and install the necessary Python libraries, such as PySide6.

    From a terminal in the extracted starter folder, install PySide6 and launch the game:

    python -m pip install PySide6
    python main.py

    In the Settings window, select the black and white players, then click Save Settings. You can try human or random before completing the remaining AI methods. Use Game → New Game to select another match.

  2. Implement the required functions in ai.py. Do not import any libraries in ai.py except for import random. Specifically, implement the following four functions:

    def utility(board, player):
        # Utility function used in the following search methods
    
    def greedy_ai(board, player):
        # Greedy search algorithm
    
    def minimax_ai(board, player, depth):
        # Minimax search without pruning
    
    def alpha_beta_ai(board, player, depth):
        # Minimax search with alpha-beta pruning
  3. Run the complete program and conduct matches between the implemented AI methods (random, greedy, minimax, alpha_beta). There are 16 different match types (\(4 \times 4\)), including self-play matches (e.g., random (black) vs. random (white)). Consider running multiple trials for each match type.

  4. Report the match results in your submission file, hw2submission.pdf. For each trial of each match, the report should include at least the final count of black and white pieces and a screenshot of the board at the end of the game.

  5. Append your ai.py code at the end of hw2submission.pdf.

  6. Submit hw2submission.pdf on Canvas.