Maze Solver Meta-System

Instead of hardcoding a single graph search algorithm, this project builds a system that predicts which solver (BFS, DFS, or A*) will perform best for a given maze based on structural features.

The goal: treat solver selection as a supervised learning problem.

---

Why I Built This

Different search algorithms behave very differently depending on maze structure.

Sometimes DFS expands fewer nodes.
Sometimes A* dominates in open environments.
BFS guarantees shortest paths but can be inefficient.

Rather than guessing which one to use, I wanted to:

1. Generate diverse mazes
2. Measure solver performance
3. Label the optimal solver
4. Train a model to predict it
5. Evaluate using regret, not just accuracy

---

How It Works

Maze Generation

Two maze families:

• Family A (structured generation)
• Family B (open-ratio controlled randomness)

Sweeps over:

• Sizes: 21, 31, 51
• Open ratios: 0.15–0.60
• Multiple seeds

---

Feature Engineering

Each maze is described using:

• cells_total
• open_ratio
• dead_end_ratio
• shortest_path_length
• reachable_ratio

These features capture topology and connectivity.

---

Oracle Labeling

For each maze, all three solvers are executed.

The “best” solver is selected using:

(path_length, nodes_expanded, runtime_ms)

This becomes the ground-truth label.

---

Model

• Random Forest (200 trees)
• Stratified train/test split
• Majority baseline comparison
• Regret-based evaluation

Regret is defined as:

nodes_expanded(predicted_solver) − nodes_expanded(oracle_solver)

This measures how much extra work the model caused.

---

Results

Dataset size: 144 mazes

Class distribution:

• A*: 96
• DFS: 48

Majority baseline: 65.5%
Model accuracy: 100%

Average regret: 0
Median regret: 0

The model perfectly predicted the best solver on the held-out test set.

---

Visual Results

Confusion Matrix

Regret Distribution

---

Heuristic vs Learned Selector

I also implemented a rule-based heuristic selector.

Heuristic:

• 96.7% accuracy
• Avg regret: 1.3 expanded nodes

The learned model eliminated regret entirely on the test set.

---

What This Project Demonstrates

• Feature-driven decision systems
• Structured experiment design
• Regret-based evaluation
• Clean dataset construction
• Reproducible benchmarking

---

Limitations

• Moderate dataset size
• No BFS-dominant class observed
• Static mazes only

---

Tech Stack

Core

• Python
• NumPy
• SciPy

Machine Learning

• Scikit-learn (Random Forest, evaluation metrics)

Visualization

• Matplotlib

---

Future Work

• Larger parameter sweeps
• Weighted mazes
• More algorithms
• Direct regression on nodes expanded
• Policy-learning approaches

---

Run Instructions

pip install -r requirements.txt

python -m scripts.test_build_dataset
python -m scripts.train_random_forest
python -m scripts.