The same path, less searching

A* finds the routes breadth first search finds, having looked at a fraction of the board

Breadth first search expands in rings, so by the time it reaches a fruit four tiles away it has also visited everything four tiles in the opposite direction. A* keeps the same guarantee and skips most of that.

This post is not really about playing snake - the two players score the same - it is about the search.

The idea

Breadth first search takes tiles off the queue in the order it found them. A* takes them off in order of the cost already paid plus the distance still to go, so the search leans towards the target instead of spreading evenly.

The estimate has to never overstate the remaining distance, or the first route found stops being the shortest one. Manhattan distance on a grid where every move costs one is exactly that: it is the distance on an empty board, and a board with a snake on it can only be worse.

breadth first                        A*
. 4 3 4 . . . .                      . . . . . . . .
. 3 2 3 4 . . .                      . . . . . . . .
. 2 1 2 3 4 . o                      . . . 1 2 3 4 o
. 1 @ 1 2 3 . .                      . . @ 1 2 3 4 .
. 2 1 2 3 4 . .                      . . . 1 2 3 . .
. 3 2 3 4 . . .                      . . . . . . . .

everything within four            only what is on the way

The heap

Taking the cheapest guess next means a priority queue, and the one in container/heap takes an any, which would put every tile on the heap through an interface. So it is written out.

// estimate is a tile waiting to be expanded, and what the whole route through
// it is guessed to cost.
type estimate struct {
	at   pos
	cost int32
}

// estimates is a binary min-heap of tiles to expand, cheapest guess first.
type estimates []estimate

func (e *estimates) push(v estimate) {
	*e = append(*e, v)
	h := *e
	for i := len(h) - 1; i > 0; {
		parent := (i - 1) / 2
		if h[parent].cost <= h[i].cost {
			break
		}
		h[parent], h[i] = h[i], h[parent]
		i = parent
	}
}

func (e *estimates) pop() estimate {
	h := *e
	top := h[0]
	last := len(h) - 1
	h[0] = h[last]
	h = h[:last]
	*e = h

	for i := 0; ; {
		left, right := i*2+1, i*2+2
		smallest := i
		if left < len(h) && h[left].cost < h[smallest].cost {
			smallest = left
		}
		if right < len(h) && h[right].cost < h[smallest].cost {
			smallest = right
		}
		if smallest == i {
			break
		}
		h[i], h[smallest] = h[smallest], h[i]
		i = smallest
	}
	return top
}

Not clearing the board

The breadth first search starts by copying the board’s mask over its working memory, which doubles as its visited set. That copy is free next to a search that visits nearly every tile.

A* does not visit nearly every tile - that is the entire point of it - so the copy would cost more than the search does. Instead it keeps a stamp per tile and bumps a counter for each search.

// visits records which tiles a search has reached, without clearing anything
// between searches: each search takes the next stamp, and a tile counts as
// reached only if it carries that one.
type visits struct {
	stamps []uint32
	stamp  uint32
}

func (v *visits) begin() {
	v.stamp++
	if v.stamp == 0 {
		// Wrapped round, after four billion searches. Clear the stamps, or
		// leftovers from before the wrap would pass for this search's own.
		for i := range v.stamps {
			v.stamps[i] = 0
		}
		v.stamp = 1
	}
}

func (v *visits) seen(at pos) bool { return v.stamps[at] == v.stamp }
func (v *visits) see(at pos)       { v.stamps[at] = v.stamp }

Four billion searches sounds like a number that will never come up. A training run plays millions of games, so it comes up, and a wrapped counter would quietly report tiles as visited that no search had touched.

The search

func (g *AStar) Generate(st *state.State, from *tile.Vector, to *tile.Vector) (Path, bool) {
	mask, stride := st.Open(), st.Stride()
	g.reached.begin()
	owners, costs := g.owners, g.costs

	delta := stepDeltas(stride)
	fromI, toI := index(from, stride), index(to, stride)
	owners[fromI] = noOwner
	costs[fromI] = 0
	g.reached.see(fromI)
	behind := backwards(st)

	queue := g.open[:0]
	queue.push(estimate{at: fromI, cost: int32(tile.ManhattanDistance(*from, *to))})

	for len(queue) > 0 {
		i := queue.pop().at
		if i == toI {
			g.open = queue
			return backtrace(i, owners, stride), true
		}
		v := vector(i, stride)

		for at, dir := range direction.All {
			if i == fromI && at == behind {
				// The snake can't turn back on itself on the first step.
				continue
			}
			adj := i + delta[at]
			if !passable(mask, adj) {
				continue
			}

			cost := costs[i] + 1
			if g.reached.seen(adj) && cost >= costs[adj] {
				continue
			}
			g.reached.see(adj)
			costs[adj] = cost
			owners[adj] = i
			queue.push(estimate{
				at:   adj,
				cost: cost + int32(tile.ManhattanDistance(tile.Step(v, dir), *to)),
			})
		}
	}

	g.open = queue
	return nil, false
}

How it does

The search, on a mid-game board, from go test -bench ./path/:

BenchmarkBreadthFirstSearch/reachable-16      1204 ns/op
BenchmarkAStar/reachable-16                    460 ns/op

Two and a half times quicker, for the same routes.

The game:

solver        games   wins  stalled  avg score   best  worst  avg moves   per game
shortest       2000      0        0       28.2     51      8      228.1      423us
astar          2000      0        0       28.5     52      6      229.5      485us

Identical, to inside the noise - and the per-game column has A* slower, which is the measurement rather than the code. A game is a couple of hundred moves and a lot of things that are not the search; a batch of two thousand games run back to back on this machine moves by several per cent run to run. The place the difference is real is the benchmark that repeats one search until it can be timed.

There is a second case where they are identical for a better reason:

BenchmarkBreadthFirstSearch/sealedOff-16        45.9 ns/op
BenchmarkAStar/sealedOff-16                     40.2 ns/op

When the snake has sealed itself into a pocket, neither search has anywhere to go, and both give up in forty-odd nanoseconds having filled a handful of tiles. Late in a game that is most of the searches, which is another reason the difference does not show up in a whole game.

Pros

• The same guarantee for a fraction of the tiles, and it scales with the board: the bigger the board, the more of it breadth first search is visiting for nothing.
• No allocation per search, and no clearing between searches.

Cons

• It answers exactly the same question as breadth first search, so it plays exactly as badly. Twenty-eight of ninety-nine.
• A heap, a cost array and a stamp array against one array and a queue. It is a real amount of extra machinery to buy something the game cannot feel.

The two search players are where “just find the fruit” runs out. Everything after this is about the shape the snake is left in.

Next: a route that is deliberately as long as possible.