Taking the longest way round
Stretching a route to keep the body trailing behind, and why it scores worse than walking straight at the fruit
The two search players die because a short route leaves the snake coiled up next to itself. The obvious opposite idea is to take the longest route you can, so that by the time you arrive the tail has had time to get out of the way.
It scores worse than walking straight at the fruit. It is also the single most useful piece of machinery in this series, because it is how you grow a route into a tour of the whole board.
Stretching a route
There is no search for “longest path” - that problem is NP-hard, and this is a snake game. Instead: find the shortest route with a breadth first search, then repeatedly push bits of it sideways.
func (g *BreadthFirstSearchLongest) Generate(state *state.State, from *tile.Vector, to *tile.Vector) (Path, bool) {
path, found := g.bfs.Generate(state, from, to)
if !found {
return path, found
}
return g.expandPath(state, path, to), true
}
Take any two tiles that are next to each other on the route. If the two tiles alongside them are both free, the route can go round the outside instead, and it is two tiles longer for it.
a run going up or down a run going left or right
p x p p p
p x p x x
p p
x is the pair of tiles on the route
p is a pair it could be pushed onto
// parallelVectors is the pair of tiles alongside a and b on either side of the
// run between them. The second result is false for two tiles that are not in
// line, which two steps of a route never are.
func (g *BreadthFirstSearchLongest) parallelVectors(a tile.Vector, b tile.Vector) ([2][2]tile.Vector, bool) {
if a.X == b.X {
return [2][2]tile.Vector{
{{X: a.X - 1, Y: a.Y}, {X: b.X - 1, Y: b.Y}},
{{X: a.X + 1, Y: a.Y}, {X: b.X + 1, Y: b.Y}},
}, true
}
if a.Y == b.Y {
return [2][2]tile.Vector{
{{X: a.X, Y: a.Y - 1}, {X: b.X, Y: b.Y - 1}},
{{X: a.X, Y: a.Y + 1}, {X: b.X, Y: b.Y + 1}},
}, true
}
return [2][2]tile.Vector{}, false
}
Doing that from the far end back towards the head, over and over, turns a four move route into a route that fills most of the free space.
the shortest route after stretching
. . . . . . . . . . . . . . . .
. @ > > > > o . . @ v . . > o .
. . . . . . . . . . > > > ^ . .
. . . . . . . . . . . . . . . .
The one step it will not touch
i := len(longestPath) - 1
for i >= 2 {
The loop stops at two rather than one, and that is not an off-by-one. The step out of the head is the move the snake is about to make, and the search chose it knowing which way the snake is facing - it is the one step that may not double back on the neck. Stretching it puts a tile between the head and it, and the new first step is chosen by geometry alone.
On about one board in fifteen that asked the snake to reverse. The board refuses such a move and carries straight on instead, so the snake ends up somewhere the route does not go while the solver walks the rest of it regardless - into a wall, usually before it has eaten anything.
The fruit is not an obstacle
// canOccupyVector reports whether the expansion may route through a tile.
//
// The fruit counts as free. It is a tile the snake can walk onto - it eats it
// on the way past - and the end of the route is kept clear by the check on to
// below, which is what the caller actually needs protected.
func (g *BreadthFirstSearchLongest) canOccupyVector(v tile.Vector, state *state.State, to *tile.Vector, occupied []bool) bool {
if !state.ValidPosition(v.X, v.Y) {
return false
}
if t := state.Tile(v.X, v.Y); t != tile.TypeNone && t != tile.TypeFruit {
return false
}
tileNumX, _ := state.Dimensions()
if occupied[v.Y*tileNumX+v.X] {
return false
}
return v != *to
}
Treating the fruit as occupied cost the tour player in a later post most of what it was worth. A tour has to cover every tile, so a single tile the expansion refuses to tread on is enough to make one impossible - and the fruit only lies on the short route the expansion starts from by luck.
With the fruit treated as an obstacle, that player found a tour on three fresh 10x10 boards in two hundred. Letting it eat: three boards in four.
How it does
solver games wins stalled avg score best worst avg moves per game
greedy 2000 0 0 22.4 47 6 182.3 42us
shortest 2000 0 0 28.2 51 8 228.1 423us
longest 2000 0 0 19.1 44 4 1495.6 449us
Nineteen. It is beaten by the player that walks in a straight line at the fruit and has no search at all, and its games are eight times longer.
The idea is not wrong - a long route really does give the tail time to move - but the execution has two problems that the numbers make obvious.
The route is planned once per fruit and then walked to the end. Fifteen hundred moves for nineteen fruit is about eighty moves a fruit, and every one of those is eighty moves during which the plan is not being reconsidered. Worse, the plan is deliberately laying the snake through every free tile it can reach, so the board it arrives at is one where there is nothing left to stretch into and no room to plan the next route.
It is the pathological version of the right instinct. Keeping room is good; spending all of it every time is not.
Pros
- It does what it says: the body trails behind the head instead of coiling next to it.
- The expansion is exactly the primitive needed to build a Hamiltonian cycle, which is three posts away and wins every game it plays.
- Working on a flat
[]boolof occupancy and a fixed array of candidate tiles, it allocates nothing per attempt. That matters when the tour player makes thousands of attempts in a single game.
Cons
- Nineteen of ninety-nine, behind a twelve-line player.
- Committing to the whole route means it cannot react to the board it has made.
- Filling the free space with the route is the same mistake as filling it with the snake.
Next: stop optimising the route and start checking whether it is survivable.