Never dying
A snake that can reach its own tail always has a way out, and that one rule is worth sixty points
Everything so far dies. The search players die at about 28 of 99, and they die because a shortest route and a survivable route are different things.
This one does not die. Not once in two thousand games, and it scores 90.8.
The rule
If the head can reach the tail, the snake is not trapped.
The reasoning is short. The tail moves out of the way every tick, so a route to the tail is a route that is opening up ahead of you rather than closing. And from any board where the head can reach the tail there is always a move that still can - the first step of that very route - so a snake that never gives that up always has somewhere to go.
trapped not trapped
# # # # # . . # # # # # . .
# . . . # . . # . . . . . .
# . @ . # . . # . @ . . . .
# # # # # . . # # # # t . .
. . . . . . . . . . . . . .
the head is sealed into a the head can walk out and
pocket with no tail in it round to its own tail
So the player plans a whole route to the fruit, plays it out on a copy of the board, and only takes it if the tail is still in sight at the end. When no route passes that test it does not take one - it stalls, and waits for the board to open up.
Playing the route out
state.Clone hands back a board that can be played forward without touching the real game.
func (s *SafeSolver) chaseFruit(st *state.State) (direction.Direction, bool) {
moves, found := s.routeToFruit(st)
if !found || len(moves) == 0 {
return direction.None, false
}
sim := s.simulate(st)
for i, move := range moves {
alive, err := sim.Move(move)
if err != nil {
return direction.None, false
}
if !alive {
// Nothing on this path can kill us except filling the final free
// tile, and that is a win worth walking into.
return moves[0], sim.Won()
}
if i > 0 && i < len(moves)-1 {
continue
}
if !s.scratch.Reaches(sim, *sim.SnakeHead(), *sim.SnakeTail()) {
return direction.None, false
}
}
return moves[0], true
}
The tail is checked at the end of the route, which is the obvious place, and after the first step, which is not.
The end of the route is where the lookahead earns its keep. But the first step is the only one being committed to - the solver searches again from scratch on the next tick rather than walking the route out. A first step that loses sight of the tail leaves the next tick with nothing safe to choose between, and the step after that fewer still. Checking only the far end of the route let it walk into pockets it could not get back out of, and about one game in sixty ended in a death rather than a stall.
That is where the “never dies” comes from. It is not the lookahead. It is that every single step taken keeps the tail in sight, and the lookahead is buying score on top of that.
One survey, three answers
Stalling needs to know how much room each move leads into. Chasing needs to know whether there is a route to the fruit at all, and what it is. Those look like three flood fills a tick, and they were.
They are one now. A single breadth-first pass out from the fruit labels the region the fruit is in and measures the distance to everywhere in it; any other region is only labelled if one of the three moves leads into it.
// One survey of the board, from the fruit, does for both of what follows.
s.room.Survey(st, *st.Fruit())
if s.canReachFruit(st, legal[:n]) {
if dir, ok := s.chaseFruit(st); ok {
return dir
}
}
return s.stall(st, legal, n)
A survey from the fruit is a map of how far every tile is from it, so the route is downhill all the way: step to a neighbour one nearer, and keep doing that until the distance is nothing. That is the same route a search would return, for the length of the route rather than the size of the board.
distances from the fruit the route is downhill
. 5 4 3 4 5 . . @
. 4 3 2 3 4 . . \
. 3 2 1 2 3 . . 3 - 2 - 1 - o
. 4 3 2 o 2 . .
. 5 4 3 2 3 . .
Four ticks in five there is no route to the fruit at all, and the survey answers that for nothing: if none of the three moves lands on a tile the survey reached, the fruit is walled off and there is nothing to search for.
Stalling
func (s *SafeSolver) stall(st *state.State, legal [3]direction.Direction, n int) direction.Direction {
head, fruit := *st.SnakeHead(), *st.Fruit()
winning := st.Score()+1 == st.MaxScore()
var options [3]stallOption
spin := int(s.roll() % uint32(n))
for i := 0; i < n; i++ {
dir := legal[(i+spin)%n]
next := tile.Step(head, dir)
if winning && next == fruit {
return dir
}
options[i] = stallOption{dir: dir, room: s.room.Room(next)}
}
sortByRoom(options[:n])
for _, option := range options[:n] {
sim := s.simulate(st)
if alive, err := sim.Move(option.dir); err != nil || !alive {
continue
}
if s.scratch.Reaches(sim, *sim.SnakeHead(), *sim.SnakeTail()) {
return option.dir
}
}
return options[0].dir
}
Take the move that leaves the most room, prefer any move that keeps the tail in reach, and wait.
Two details in there are worth more than the rest of the player put together, and both of them are about what happens when two moves are equally good.
spin. The comparison starts at a different move each tick. Without it the solver reads nothing but the board, so once it is circling it comes back round to a position it has been in - the same tiles of snake, facing the same way, with the fruit in the same place - and from there it does the same thing again forever. Raising the move limit a hundredfold, from ten thousand to a million, changed nothing and spent the whole budget on every game.
Rotating where the comparison starts breaks that, and gives up nothing: the ordering still decides between moves that differ, and every move is still tested for the tail before it is taken. Over a thousand games it took the average from 86.4 to 89.1 on a 10x10 and 224.5 to 230.3 on a 16x16, and the worst game of a batch from 33 to 66.
It does not steer at the fruit while it waits. It used to: distance to the fruit broke the tie between two moves that left the same room. Dropping that is worth another 1.86 points at 10x10, and nothing is given up for it.
That reads backwards until you remember when this code runs. It runs when there is no route to the fruit the snake can take and get back out of, so the fruit is not somewhere to go - it is somewhere the snake is shut out of. Edging that way packs it into the corner the fruit is in and spends the room it is waiting on. Taking the room and waiting is the whole job.
How it does
solver games wins stalled avg score best worst avg moves per game
astar 2000 0 0 28.5 52 6 229.5 485us
safe 2000 22 1978 90.8 99 83 9916.6 3.10ms
Twenty-eight to ninety. Nothing else in this series moves the number that far.
The two thousand stalled games are not deaths - the snake is still alive when the move limit calls time. Late in a game it can no longer prove that any route to the fruit is survivable, so it circles instead, and never gets the last handful of fruit.
The worst game of two thousand is 83. It is not just good on average, it is good every time.
Pros
- It does not die. One rule, checked on every step, and the entire category of “lost the game” is gone.
- Ninety of ninety-nine from a player small enough to read in one sitting.
- Two of its best ideas cost nothing at all. Rotating a tie-break and not using a piece of information are both free.
Cons
- It is the most expensive hand-written player here by a factor of twelve, at 3.1ms a game. It plans a route, plays the route out on a copy of the board, and fills the space around up to three more moves - every tick.
- It stalls almost every game. It is honest about not being able to see a safe way in, but the score it leaves on the table is the last eight or nine fruit.
- The move limit is not what is capping it. Thirty times the budget is worth nothing. What is left after the loops are broken is a snake that genuinely cannot see a way through its own body.
That last point is why the next three players exist. If you want to win every game, you cannot work it out move by move - you have to commit to a plan for the whole board before the game starts.