Search Arena

Here you can find Python-based versions of various unidirectional and bidirectional search algorithms that can be run against standard evaluation domains, namely Sliding Tile, Pancake, Towers of Hanoi, and Pathfinding (Dragon Age Origins grids and various mazes sourced from https://www.movingai.com/benchmarks/grids.html).

Setup and Installation

Tested under Python 3.12 on Ubuntu and CentOS.

1. Install Python into a virtual environment.
2. Install numpy, and sortedcontainers.
3. Clone this repository. The project structure is very simple: all code and run scripts are in /code, all problems are specified in text files in subdirectories off /problems, all outputs will appear in /outputs which will be created dynamically.

Run a set of algorithms on a set of problems

1. From a terminal in the /code subdirectory run: bash run_test_easy.sh
2. Results and logs will be in /outputs.
3. Reviewing bash run_test_easy.sh will give you the idea as to how to run different algorithms on different problems. Basically everything starts in search_runner.py.

Adding Rust Modules (Optional)

1. pip install maturin
2. Run maturin develop --release on the command line to compile the Rust library .../code/src/lib.rs as an importable Python package rust_utils.
3. Add a --rust_heur flag to your run script to run the Rust version of the manhattan heuristic for Sliding Tile. Speeds up 4x4 Sliding Tile problems by 15% or so.
4. Add a --rust flag to your run script to use a Rust version of the node dictionary that stores g, h and the parent for each state. Actually runs a bit slower due to the calling overhead but saves a modest amount on memory usage.