Searching for a tour
Growing a route into a Hamiltonian cycle, and the two small decisions that took it from 65 to winning every game
The zig-zag tour is laid out by hand, which works because a rectangle is easy to walk. The other way to get a tour is to search for one on the board in front of you.
This player is the most fragile thing in the series and the most instructive, because almost all of its score comes from two decisions that have nothing to do with the search.
Growing a route into a tour
The pieces are already built. The longest-path expansion takes a route and pushes runs of it sideways, two tiles at a time, into any free space alongside. Do that until it stops growing, and if the result happens to cover every tile, it is a Hamiltonian path.
Make it start and end next to each other and it is a cycle.
36 tiles to cover
breadth first route: 6 tiles ███░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
after stretching: 36 tiles ████████████████████████████████████ a tour
func (g *HamiltonianCycle) Generate(state *state.State, from *tile.Vector, to *tile.Vector) (Path, bool) {
potentialEndVectors := g.getPotentialTailVectors(state)
if len(potentialEndVectors) == 0 {
return Path{}, false
}
// We will attempt multiple expansion directions within the longest algo
prefs := []PrefParallelDirection{
PrefPositive,
PrefNegative,
PrefRandom,
}
for _, pref := range prefs {
g.longest.SetPrefParallel(pref)
cycle, found := g.findCycleToAnyEnd(state, from, potentialEndVectors)
if found {
return cycle, found
}
}
return Path{}, false
}
The expansion has a choice each time of which side to push a run onto, and which one it takes decides what it ends up covering. So the search runs three times: always favouring one side, always the other, and at random.
func (g *HamiltonianCycle) findCycleToAnyEnd(state *state.State, from *tile.Vector, potentialEndVectors []*tile.Vector) (Path, bool) {
for _, endV := range potentialEndVectors {
path, found := g.longest.Generate(state, from, endV)
if !found {
continue
}
// The cycle needs to cover ALL tiles
if len(path) != state.TotalTiles() {
continue
}
// The cycle needs to end on the starting point
path = append(path, path[0])
return path, true
}
return Path{}, false
}
The route has to end somewhere the snake can get back to its own start from. With a body, that is the tail. With a snake one tile long there is no tail, so any neighbour of the head that is not straight ahead will do as a stand-in.
func (g *HamiltonianCycle) getPotentialTailVectors(state *state.State) []*tile.Vector {
potentialVectors := make([]*tile.Vector, 0)
head := state.SnakeHead()
tail := state.SnakeTail()
// If snake has some length, then return only the tail vector
if *head != *tail {
potentialVectors = append(potentialVectors, tail)
return potentialVectors
}
// We need give a fake tail that can move into the snakes head vector.
snakeDir := state.SnakeDir()
for _, dir := range direction.All {
if dir == snakeDir {
continue
}
adj := tile.Step(*head, dir)
if !state.ValidPosition(adj.X, adj.Y) {
continue
}
potentialVectors = append(potentialVectors, &adj)
}
return potentialVectors
}
The tour is generated once - RegenNever - and then walked forever.
The window is two tiles wide
Here is the fragile part. A tour has to cover every tile, and the search can only route through empty tiles plus the head and the tail. So the moment there is a third piece of snake on the board there is no tour left to find, and there never will be again in that game, because the snake only grows.
noTour := func(st *state.State) bool {
x, y := st.Dimensions()
// A tour of every tile needs an even side.
if x%2 == 1 && y%2 == 1 {
return true
}
// It also needs both sides to be at least two.
if x < 2 || y < 2 {
return true
}
// And a tour has to cover every tile, while the search can only route
// through the empty ones - plus the head and the tail. So the moment
// there is a third piece of snake on the board, no tour exists.
return st.SnakeLength() > 2
}
return tour.WithFallback(NewSafeSolver(), noTour)
So the player has one shot, at the start of the game, and if it misses it plays out the rest of the game as somebody else.
The two decisions that mattered
Hand over as soon as it is hopeless. Before that check existed, a failed search left the player moving at random - and searching the entire board again on every single tick for a tour that provably could not be there. A game where the snake grew past two before a tour turned up was played out at random to the end, and about one in eight of those finished on single figures.
Handing over to safe took it from 65 to 95, and stopped it losing games outright. It also took three quarters of its running time and twenty times its memory with it.
Keep off the fruit while you are still looking. When the search fails on a board it could have succeeded on, the right thing is to move somewhere and try again - a search presented with the same board gives the same answer.
But moving at random will sooner or later move onto the fruit, and eating is exactly what ends the window.
// anyLegalDirectionAvoiding is anyLegalDirection, keeping off one tile if it
// can. It is for the solver that is retrying a search the board has to stay a
// certain shape for: wandering at random while it retries can walk into the
// fruit, and a snake that has grown is a board the tour search can no longer
// succeed on, so the wandering would end the very thing it is waiting for.
func anyLegalDirectionAvoiding(st *state.State, avoid tile.Vector) direction.Direction {
options, n := legalDirections(st)
if n == 0 {
return direction.None
}
head := *st.SnakeHead()
kept := options
k := 0
for _, dir := range options[:n] {
if tile.Step(head, dir) == avoid {
continue
}
kept[k] = dir
k++
}
if k == 0 {
// Every way out is onto it, which happens on a board one tile wide.
return options[rand.Intn(n)]
}
return kept[rand.Intn(k)]
}
It costs nothing - it is one of three moves rather than any of them, and it is given up rather than died for - and it is the difference between winning most games and winning all of them.
There is a third decision of the same kind hiding in the expansion, covered in the longest-path post: the fruit counts as a free tile when stretching a route, because the snake eats it on the way past. Treating it as an obstacle meant a single unlucky fruit made a tour impossible, and the search found one on three fresh 10x10 boards in two hundred instead of three in four.
How it does
solver games wins stalled avg score best worst avg moves per game
hamiltonian 2000 2000 0 99.0 99 99 2520.1 242us
zigzag 2000 2000 0 99.0 99 99 2530.7 192us
Two thousand games, two thousand wins - and it never once had to hand over, because keeping off the fruit means it can keep trying until a tour turns up.
The move count is the same as the zig-zag, which makes sense: it is walking a tour of the whole board too, and one tour is as long as another. It has none of the shortcut player’s cleverness, so it pays the full lap for every fruit.
Pros
- It wins every game, and unlike the zig-zag it works out its own tour rather than being told one.
- The three failure modes are all checked rather than hoped for, and each has a sensible thing to do about it.
- It is cheap - 242us a game - because the expensive part happens once, in the first few ticks.
Cons
- It has a window two tiles long. Everything about this player is arrangements to protect that window.
- The tour it finds is arbitrary, so there is no shortcut logic possible on top of it the way there is for a laid-out tour. It is the zig-zag’s cost with none of the shortcut player’s savings.
- It still cannot help a 9x9 board, for exactly the reason the zig-zag cannot.
That is the end of the players I wrote by hand. Between them they say something fairly bleak: the ones that think about the board top out at 90 and stall, and the ones that win do it by not thinking about the board at all.
Next: stop writing the player, and evolve one instead.