The project was developed as part of the Introduction to Artificial Intelligence (CSC384) at the University of Toronto, Department of Computer Science.
Role
Developer
Tools
Python
Focus Areas
Artificial Intelligence, Recursive Algorithm Design, Adversarial Search, Heuristic Engineering, Performance Optimization
Timeline
April 2025
Overview
Developed a competitive AI agent for Othello (Reversi), a two-player adversarial board game involving strategic disk placement and piece flipping under strict move legality rules.
The objective of the game is to finish with the majority of disks on the board. Unlike the standard rules, this version ends when one player has no legal moves remaining.
This project focused on adversarial search, pruning optimization, and heuristic design under strict time constraints (10 seconds per move).
What I Built
Minimax Search
- Implemented recursive Minimax with utility evaluation
- Modeled game states as immutable board tuples
- Computed terminal state utility as disk differential
- Evaluated full game trees on small boards (4×4)
Alpha-Beta Pruning
- Implemented Alpha-Beta pruning to eliminate unnecessary branches
- Reduced effective branching factor and improved runtime performance
- Enabled scaling to larger board sizes (6×6, 8×8)
Depth-Limited Search
- Integrated configurable depth limits for practical performance
- Evaluated non-terminal states using heuristic estimation
- Balanced lookahead depth with computation constraints
State Caching
- Implemented transposition table using hash-based board caching
- Avoided recomputation of previously evaluated states
- Improved deep search efficiency
Node Ordering Optimization
- Designed heuristic-based successor ordering
- Explored higher-utility branches first to maximize pruning efficiency
- Increased alpha-beta pruning effectiveness
Custom Game Heuristic
Designed an improved evaluation function incorporating:
- Disk differential
- Mobility (available legal moves)
- Positional stability (corner and edge control)
- Game-phase awareness (opening vs. endgame weighting)
The heuristic was tested competitively against baseline minimax agents across multiple depth limits and board sizes.
Skills Demonstrated
Adversarial Search & Game AI
- Minimax algorithm
- Alpha-Beta pruning
- Depth-limited search
- Heuristic evaluation design
Optimization & Performance Engineering
- Branch pruning strategies
- Node ordering for search efficiency
- Memoization / state caching
- Time-constrained decision systems
Algorithmic Thinking
- Recursive tree search
- Utility function design
- Tradeoff analysis (search depth vs. runtime)
- Complexity management in exponential game trees
Systems Implementation
- Immutable state representation
- Inter-process communication via pipes
- Time-bound execution handling
- Python performance-aware implementation