Blocking Game AI Agent
Developed an intelligent game-playing agent for a Blokus-inspired blocking game using Minimax with Alpha-Beta Pruning, Monte Carlo Tree Search, and game-theoretic optimization strategies.
Duration
Spring 2025
Role
Developer
Institution
NTNU
Status
Completed
Technologies Used
Overview
This AIS4002 Intelligent Machines Module 1 project involved developing an AI agent to play a competitive turn-based board game similar to Blokus. The agent uses adversarial search algorithms including Minimax with Alpha-Beta Pruning, Monte Carlo Tree Search, and game-theoretic principles to maximize board control while blocking opponents. The implementation features iterative deepening, transposition tables for state caching, and parallel processing for deeper lookahead.
Problem Statement
The Blocking Game is a combinatorial optimization problem where players compete on an N×N grid to place shapes while blocking opponents. The challenge is developing an AI that can evaluate positions, predict opponent moves, and make strategic decisions within strict time constraints (150ms per turn).
Challenges & Solutions
| Challenge | Solution | Outcome |
|---|---|---|
| Computational Time Constraints | Implemented iterative deepening with time-based cutoff and transposition tables for state caching | Reduced decision time from 150ms to 75ms while maintaining quality |
| Large Search Space | Combined Alpha-Beta Pruning with move ordering and Monte Carlo fallback | Effectively handled 174+ valid moves per turn |
| Multi-Agent Competition | Incorporated game-theoretic principles including strategic dominance and opponent modeling | Successfully competed against multiple AI opponents |