Overview

A trio of Python agents that play the same labyrinth game three ways (depth-first, A* with a Manhattan heuristic and minimax with alpha-beta pruning) over one shared state model.

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, jump over the next one, or raise a wall beside it, each in four directions and each at a different cost. The rule that makes it a real problem is that moving or jumping leaves a wall behind in the cell you came from, so the board closes in as the game goes on and a route that existed two turns ago may not exist now.

That one rule set covers two very different problems. With a single traveller it is a search: depth-first finds a way through without knowing anything, A* finds a cheap one by estimating what is left. With two, it stops being a search at all and becomes a game: the other traveller is closing the board too, which is what minimax is for.

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

pythonsearchgame-ai