Labyrinth Search Agents

The problem

Project 1 of 3 for the Artificial Intelligence course at the Universitat de les Illes Balears — the one on search.

The board is a grid with walls, a destination and one or two travellers. On its turn an agent picks one of twelve actions: move one cell (cost 1), jump over the adjacent one (cost 2) or raise a wall beside it (cost 3), each in four directions.

The rule that makes it interesting is that moving or jumping leaves a wall behind in the cell you came from. The board closes in as the game advances, so a route that existed two turns ago may not exist now.

That single rule set covers two very different problems. With one traveller it is a shortest-path search through a maze the searcher itself is closing. With two it is adversarial: every step you take is a wall you hand your opponent, and arriving first is the only thing that counts.

How it works

• One state, three searches — Estat holds the walls, the destination, the agent positions and whose turn it is. It generates its own successors, knows when it is terminal and who won, and exposes both the accumulated cost g and a Manhattan heuristic, so the same object serves all three algorithms.
• Hashable and comparable — states hash on their walls, destination, agents and turn, which is what makes the closed set and the minimax transposition table O(1). __lt__ compares on f(), so a state goes straight into a PriorityQueue with no tie-breaking wrapper.
• Depth-first — a LIFO frontier and a closed set, planning the whole route once and then replaying it action by action.
• A* — the same skeleton over a queue ordered by f() = g + h. Because the three actions cost 1, 2 and 3, this is where the cost model earns its place.
• Minimax with alpha-beta — plus a dictionary of already-scored states, so a position reached by two different move orders is evaluated once. A position with no legal move scores as a loss for the player to move, which is what makes being walled in count as losing. Unlike the other two it re-plans every turn, because the opponent invalidates the plan.
• Action order is per algorithm, and it matters — minimax tries MOURE first so the usually-better move is explored before the pruning window narrows; the depth-first order reverses the list so MOURE is pushed last and therefore popped first off the stack. For A* the order is irrelevant, since the queue re-sorts everything anyway.

The game itself and its pygame rendering come with the course; the state model and the three agents are the practice.

Running it

Requires Python 3.10 or newer, pygame and the course’s iaLib, all pinned in the repository’s requirements.txt. Run it as a module from the repository root so that P1 resolves as a package:

pip install -r requirements.txt
python -m P1

Which agent runs is decided by the import at the top of __main__.py and by the ADVERSARIOS flag in estat.py, which have to agree: two agents on a 5×5 board with the flag on for minimax, one agent on a 10×10 board with it off for the other two.