Top Spin - Search Methods Project

This repository implements a one-player Top Spin puzzle and compares multiple search strategies for solving it.

Requirements

• Python 3.10+
• pip

Install dependencies:

python -m pip install -r requirements.txt

How To Run

Run the graphical interface (human mode + PC solver mode + hints):

python game.py

Run algorithm experiments and export results to text file:

python benchmark.py --sizes 10,20 --trials 10 --algorithms all --out results/benchmark_results.txt

How To Use (GUI)

• Arrow left/right: rotate track
• Space: switch zone inversion
• comb, gaps, miss, inv: select heuristic used by Greedy / A* / W-A*
• BFS, DFS, IDS, UCS, Greedy, A*, W-A*, D&C: PC solver options
• Best: run all solvers and pick the one with fewest moves
• Fastest: run all solvers and pick the one that finishes first
• Hint: asks PC for next move
• New Game, Reset: game control
• Size - / Size + or keys 1..2: change board size (10, 20)
• Mouse wheel: scroll the algorithm panel to access all solver buttons

Implemented Search Algorithms

Uninformed:

• BFS
• DFS (depth-limited)
• IDS (iterative deepening)
• UCS

Heuristic / informed:

• Greedy Best-First Search
• A* (weight = 1.0)
• Weighted A* (default benchmark weight = 2.0)

Other:

• Meet-in-the-middle (divide_and_conquer)
• Random walk baseline

Heuristics

Four heuristics are available and selectable in the UI:

• combined_score (comb) — weighted blend of missorted, inversions and gaps (non-admissible, fast)
• h_gaps (gaps) — breakpoint count lower bound, admissible
• h_missorted (miss) — misplaced tiles lower bound, admissible
• h_inversions (inv) — inversion count lower bound, admissible

Admissible heuristics guarantee an optimal solution but expand significantly more nodes. combined_score is the default.

Practical Size Policy

Because state growth is exponential:

• BFS/DFS/IDS are limited to small instances (recommended n <= 10)
• UCS is practical up to around n <= 10
• Greedy/A*/Weighted A*/D&C can be tested on n = 20 with strict limits

This policy is enforced by default in the benchmark script.

Benchmark Usage

Run all algorithms with safe default limits:

python benchmark.py --sizes 10,20 --trials 10 --algorithms all --out results/benchmark_results.txt

Run only uninformed methods on small size:

python benchmark.py --sizes 10 --trials 10 --algorithms bfs,dfs,ids,ucs --out results/uninformed_n10.txt

Run informed methods on larger sizes:

python benchmark.py --sizes 20 --trials 10 --algorithms greedy,astar,wastar,dc --out results/informed_n20.txt

Run A* with individual heuristics for comparison:

python benchmark.py --sizes 10,20 --trials 5 --algorithms astar,astar_gaps,astar_miss,astar_inv --out results/heuristic_comparison.txt

Disable automatic size skipping (not recommended):

python benchmark.py --sizes 20 --algorithms bfs,dfs --force-all-sizes

Puzzle File Input

You can load puzzle states from a text file (--states-file).

Example file format (states.txt):

# one state per line
3 4 2 1 5
5,4,3,2,1

Then run:

python benchmark.py --sizes 5 --states-file states.txt --algorithms all --out results/from_file.txt

The benchmark output text file includes per-case data and a final summary (solved count, time, moves, memory peak).

GUI Solver Metrics Output

When using the GUI in PC-solver mode, each solve attempt is appended to:

results/ui_solver_runs.txt

Columns:

• algorithm
• size
• solved (0/1)
• moves
• time_s
• peak_kib