# Maze

Bellman · v(s) = maxₐ [R(s, a) + γ v(s′)]

```
S . . # . . .
# # . # . # .
. . . . . # .
. # # # . # .
. # . . . # .
. # . # # # .
. . . # . . +1
```

[Open in the app](https://www.wavelace.com/app#p=96) · [This page](https://www.wavelace.com/presets/maze)

### What it draws

A seven-by-seven maze. The start `S` is in the top-left corner, the goal, a terminal worth `+1`, in the bottom-right, and the walls are the `#` cells. Moves are certain, `Slip` is 0, every step earns the `Step reward` of −0.02, and `Discount γ` is 0.9. Each open cell rises to its value `v(s)`, the discounted reward of the best walk from there.

The shortest route from the start to the goal is 16 steps, so the start ends up worth `0.9¹⁶ − 0.02·(1 − 0.9¹⁶)/0.1 ≈ 0.02`: the discounted goal, 0.185, less the discounted cost of the steps, 0.163. Cells farther out are worth less than nothing, and the dead end in the bottom-left corner reads −0.02. From there the step costs outweigh what the goal is still worth by the time it is reached.

### A flood from the goal

On a maze, value iteration is a flood. At sweep 1 every open cell takes the step cost and sinks just below the floor, and only the two cells beside the goal feel the goal at all. At sweep `k` the goal's discounted value has reached every cell within `k` steps of it, decaying with distance. Once the flood arrives the arrows point downhill along the shortest path: each cell's best move is to the neighbour one step nearer the goal, so the greedy walk is a shortest path. The residual falls to nothing once the farthest cell has been reached, after 18 sweeps here.

Run with `γ = 1` and a step cost, the same recursion is the relaxation of the Bellman–Ford algorithm (Bellman, 1958). A cell is then worth `1 − 0.02·d`, which is a distance map to the goal with the walls in the way.

### Try

- `Rewind`, then `Step` one sweep at a time: the flood advances one cell per press, and the start rises above the floor on the sixteenth.
- Set `Discount γ` to 1: every value becomes `1 − 0.02·d`, the start reads 0.68, and the tiles step down evenly along the route.
- Set `Step reward` to 0: the discount alone shapes the values, the start reads `0.9¹⁶ ≈ 0.185`, and no cell goes negative.
- Open a wall: in the third row, change the `#` in the sixth column to a `.`, and the walk cuts through, four steps shorter.
- `Top` shows the maze as a map, with the walk threading it.

### Read more

- [Maze-solving algorithm](https://en.wikipedia.org/wiki/Maze-solving_algorithm)
- [Shortest path problem](https://en.wikipedia.org/wiki/Shortest_path_problem)
- [Bellman–Ford algorithm](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm)
- [Breadth-first search](https://en.wikipedia.org/wiki/Breadth-first_search)
- [Markov decision process](https://en.wikipedia.org/wiki/Markov_decision_process)