We begin with a physical grid representation of the environment. The maze contains traversable corridor cells, black wall obstacles, a starting location S, and a goal location G.
At the grid-cell level, a robot navigating the maze must track both its precise grid position and its current orientation (facing North, East, South, or West):
A navigation decision is only needed at turning points, corners, dead-ends, the start (S), or the goal (G). Intermediate grid cells along straight corridors are abstracted away.
Instead of low-level steering, we allow abstract actions to move directly from one turning point to the next. Orientation is implicitly handled by the actions and removed from the state.
We connect turning points by tracing the corridors. Each abstract action represents a direct path between nodes, with the cell distance as the transition cost.
Compare the initial representation and state space with the abstracted representation.
| Initial Representation | Abstract Representation |
|---|---|
| Every traversable location matters | Decision points matter |
| State = location + orientation | State = decision point |
| Forward / Turn Left / Turn Right | Move N / E / S / W |
| 280 states (4T or 4K states) |
25 states (T or J states) |
| Many small transitions | One transition between decision points |
| Algorithm | Time | Space | Expanded | Memory | Cost | Opt? | Action |
|---|
The standard 8-puzzle contains 8 numbered tiles and 1 empty position (blank space '_') on a 3 × 3 grid. The target is to rearrange the tiles from their initial arrangement to the goal arrangement.
A state is stored as a 9-element tuple read row by row, with 0 for the blank. How many different tuples are there? Build one yourself: Clear the board, then place pieces into the squares in order.
The transition model defines which actions are possible in a state, and the resulting state after applying an action: RESULT(s, a) = s'. In this puzzle, we define actions from the perspective of moving the blank space.
The full tree to depth 2 is drawn; run an algorithm to see the order it visits the nodes.
Read the tiles row by row (skip the blank) and count inversions: pairs where a larger tile comes before a smaller one. A goal is reachable from s0 only if both counts are even or both are odd.
| Step | Selected | Expanded? | Frontier | Reached |
|---|
Direct side-by-side comparison of discovered solution paths, total path costs, node expansion counts, and optimality guarantees for all search algorithms from A to G.
| Algorithm | Discovered Solution Path | Path Cost | Expanded | Optimality Guarantee | Action |
|---|
Enter any propositional sentence using standard syntax: & (AND), | (OR), ~ (NOT), >> (IMPLIES), <=> (BICONDITIONAL).
Click any node on the DAG to toggle evidence: True → False → Unobserved. Posteriors update instantly via exact enumeration.
Simulate stochastic sampling for query P(Burglary | JohnCalls=True, MaryCalls=True) (Ground Truth = 28.42%).
Simulate self-play rollouts and inspect the balance between Exploitation (win rate) and Exploration (UCB1 formula bonus).
Demonstrates how optimal move ordering reduces the effective branching factor from \(b\) to \(\sqrt{b}\), allowing search to go twice as deep.
| Algorithm / Ordering Strategy | Theoretical Complexity | Evaluated States (\(b=4, d=6\)) | Pruning Efficiency |
|---|---|---|---|
| Pure Minimax (No Pruning) | \(O(b^d)\) | 4,096 | 0% (Baseline) |
| Alpha-Beta: Best-Case Move Ordering | \(O(b^{d/2}) = O((\sqrt{b})^d)\) | 64 | 64.0× Faster |
| Alpha-Beta: Random Move Ordering | \(O(b^{3d/4})\) | 512 | 87.5% Pruned |
| Alpha-Beta: Worst-Case Move Ordering | \(O(b^d)\) | 4,096 | 0% Pruned (No cutoffs) |