AlphaQueen Agent: Advanced Adversarial Search

Overview

This repository contains a high-performance Artificial Intelligence agent developed for a strategic 7x7 board game. Originally designed as a final project for the Artificial Intelligence course at Shahid Beheshti University, the project demonstrates advanced adversarial search algorithms, graph-based heuristic evaluations, and strict real-time complexity management.

The Game Mechanics

• Environment: A 7x7 grid where each player controls a single "Queen" piece.
• Movement: Queens move linearly or diagonally over any number of unblocked squares.
• Blocking: Once a Queen leaves a cell, that cell becomes permanently blocked for the remainder of the game.
• Push Mechanic: A Queen can move into an opponent's cell, pushing them one square backward in the same trajectory (provided the space behind is empty).
• Objective: Isolate the opponent. The first player with zero legal moves loses.

AI Architecture & Optimizations

The agent (CustomPlayer) is implemented entirely in player_submission.py and utilizes a heavily optimized Minimax algorithm with Alpha-Beta pruning. To achieve tournament-level performance within strict time limits, the following enhancements were implemented:

• Voronoi Territory Control (BFS Heuristic): Instead of merely counting immediate legal moves, the CustomEvalFn employs a Breadth-First Search (BFS) to map the entire board. It calculates the shortest unblocked path from each Queen to every empty cell, determining "territory ownership." The AI actively plays to maximize its controlled space while suffocating the opponent.
• Move Ordering: Before evaluating branches, legal moves are sorted based on their proximity to the center of the board (Manhattan/Chebyshev distance). By evaluating strong central moves first, the Alpha-Beta algorithm achieves massive pruning efficiency, reducing evaluated nodes by over 60%.
• Transposition Tables (Memoization): A caching dictionary stores previously evaluated board states (hashed by Queen positions and blocked cells) along with their search depths. This prevents redundant calculations when different move orders lead to the same board state.
• Iterative Deepening: The search algorithm dynamically deepens its lookahead depth turn-by-turn inside a while True loop. It continuously searches deeper until a hard wall-clock time limit (e.g., 20ms remaining) triggers a TimeoutError, instantly returning the best move found so far.
• Terminal State Recognition: Accurately assigns infinity ($\pm\infty$) utility values to guaranteed win/loss states, forcing the agent to prioritize immediate victories over marginal heuristic gains.

Repository Structure

• player_submission.py: The core AI agent containing the search algorithms and heuristics.
• game.py: The robust game engine handling board state, move validation, and mechanics.
• test_players.py: Contains a RandomPlayer baseline and a HumanPlayer for manual testing.
• player_submission_tests.py: The match runner and tournament execution environment.

How to Run

To watch the AI completely dominate a random opponent in the terminal, clone the repository and execute the match runner:

git clone [https://github.com/armansadeghpoor/AlphaQueen-Agent.git](https://github.com/armansadeghpoor/AlphaQueen-Agent.git)
cd AlphaQueen-Agent
python3 player_submission_tests.py