An AI engine for the strategy board game Quoridor, featuring multiple competing agents from simple heuristics to a optimized Minimax algorithm.
Project report (French): docs/rapport.md
This project explores various AI techniques to create intelligent agents capable of playing Quoridor.
-
Optimized Minimax Agent: Implements the Minimax algorithm with Alpha-Beta Pruning to efficiently search the game tree. The decision-making process is driven by a custom evaluation function that prioritizes reducing the player's path to victory while increasing the opponent's.
-
Advanced Minimax Agent: A more sophisticated version that intelligently limits its search space. Instead of considering all possible wall placements, it focuses on placing walls in a strategic radius around the opponent. It also features a dynamic search depth, allowing it to "think" deeper as the game progresses and decisions become more critical.
-
Heuristic Agent (Adapt strategy): A fast and surprisingly effective agent based on a simple rule: if you have the advantage (i.e. your path to the goal is shorter than your opponent's), press forward. If you're behind, place a wall to block the opponent's most direct path.
-
A* Pathfinding: At the core of every agent's evaluation function is the A* algorithm. It uses a smart heuristic to efficiently find the true shortest path to the goal line without exhaustively calculating the path to every target square. Results are cached per game state to reduce redundant computations during the Minimax tree search.
-
Benchmarking System: To objectively measure performance, a duel and tournament system was built. This framework allows for systematic testing of each strategy against all others. The Minimax-based agents consistently demonstrated superior performance, winning over 90% of matches in tournament settings.
To run a demo match between two AI agents with the Pygame graphical interface:
# 1. Clone the repository
git clone https://github.com/vfiszbin/quoridor.git
cd projet-quoridor
# 2. Set up a virtual environment
python3 -m venv .venv
source .venv/bin/activate
# 3. Install dependencies
pip install pygame numpy pandas
# 4. Run the game
python3 src/main.py