Assertion breaks

[Svalorzen]

There is an assertion that breaks when running some cell algorithms:

snake: /home/svalorzen/Projects/snake/src/game_util.hpp:20: GameBase after_moves(const GameBase&, const std::vector<Coord>&, Lookahead): Assertion `is_neighbor(path.back(), game.snake_pos())' failed.

I can look into the seed if you need, but it was happening fairly consistently.

[hh2010]

random state 12 seems to be an unlucky one in which it traps itself
still looking into where the unreachable cell 3B algo might have gone wrong here

[hh2010]

after a lot of time looking into it. it seems to be a fundamental weakness of calculating the entire snake path to apple, running flood fill, and re-calcing. sometimes the nearest unreachable (after the snake moves) cannot be visited from current position unreachable.dist_to_nearest == INT_MAX then when an apple randomly spawns in an unreachable area, it's game over (assert trip).

@twanvl recognizes this issue per the debug lines below

        if (0) {
          std::cout << game;
          std::cout << "Unreachable grid points (will) exist, but no alternative moves or cached path" << std::endl;
        }

and he tried to resolve it directly through the cell-fixed algorithm which does not recalculate path based on the tail moving. but it still has to recalculate upon visiting unreachables since the snake goes off the path for those. then the recalculation of the shortest path may create unreachables which cannot be visited.

as a result of this, cell and cell-fixed are broken in master. which makes me wonder: how were the snake all stats populated in the readme? its possible i am missing something, or perhaps there was some code to catch exception and try a new random seed for failing runs.

[twanvl]

If I remember correctly, the idea is that the snake always follows a valid Hamiltonian cycle, or at least that one exists. For the cell algorithm that means that when considering a new path, the unused cells have to be reachable, as determined by the flood fill. And if that fails then the snake sticks to the old path. The exception is that the path can be non-Hamiltonian as long as it becomes Hamiltonian again by the time the snake reaches the apple. With those rules the snake should never back itself into a corner.

But apparently I broke the code at some point. I don't remember it failing this often of course. I will have to check what I changed, but it has been a while.

[hh2010]

i just checked random commits until 6d41717 when the command line interface was added. and the cell algo was failing all the way through.

For the cell algorithm that means that when considering a new path, the unused cells have to be reachable, as determined by the flood fill

im a bit unclear on this comment.
the flood fill marks the cells as reachable after taking the shortest path to the apple, based on criteria which includes what you said.
but for the cells that flood fills determines are not reachable, there is no guarantee that they can actually be visited from the current position. see turns 6540 and 6541 below for cell --seed 10 which is reproducible from master.

[hh2010]

ok, i think i figured it out
https://github.com/twanvl/snake/blob/master/src/cell_tree_agent.hpp#L95C3-L95C51
This line was added in the same commit as the command line interface.
And this many_move_tail method has a weakness that lead to my observations above.
By doing the floodfill on the snake position after moving tail to the shortest path
The snake is not touching all the possible unreachables that would break subsequent calls to the a-star shortest path
Keeping the snake tail fixed is an important safety measure in this regard

I will verify that the results in the README are reproducible by changing the default back to ```Lookahead::many_keep_tail`` and then PR that change if so.

PR: #4

[twanvl]

Thanks for the investigation.

You are completely right that the many_move_tail lookahead can lead to a problem where cells become unreachable. The idea behind this method was that it is okay for cells to temporarily become unreachable, as long as they are reachable by the time the snake is at the goal. The problem happens if the path is re-considered at a point in between.

I have some ideas for fixing this issue:

• It is safe to use many_move_tail lookahead if no cells become unreachable.
• If cells do become unreachable in a way that can't be fixed, then stick to the old path. This requires that there is a complete path to the goal.
• If cells become unreachable because the path has become shorter, we should be able to make the part longer until those cells become reachable again.

The first of these is clearly correct and not too hard to implement, the other ideas are more difficult.

[hh2010]

1. tried it this morning (ba657ef). it improves the mean cell game turns from 51244 to 50724 hah. not super exciting. i think theres some ways to juice it a bit maybe by putting a filter on required count of unreachables before switching to many_move_tail.
2. this one i think already has one implementation in master
   the following is triggered when unreachable.dist_to_nearest == INF_MAX or "if cells do become unreachable in a way that cant be fixed" per your comment.

          // failed to find detour
          // This can happen because it previously looked like everything would be reachable upon reaching the apple,
          // but moving the snake's tail opened up a shorter path
          // Solution: just continue along previous path
          if (!cached_path.empty()) {
            next_step = cached_path.back();
            cached_path.pop_back();
            return next_step - pos;
          }

i tried a more strict implementation by calculating unreachable.unreachables_can_be_visited. so it would default to the cached path when all unreachables cannot be fixed rather than just the nearest one. there is more work i can do on this.
3. good way of describing this. i know what you mean but didnt think of it this way. will think more on it.

i will update my PR to incorporate 1 for now. then i will report back on 2 and 3.

[twanvl]

1. Setting recalculate_path=false is not the best way to do this, because then you never re-check the path until the goal is reached. If unreachable_move_tail.any && unreachables.dist_to_farthest < INT_MAX then it should be ok to follow the path.
2. Yes, there is already an implementation of sticking to the cached path. But when taking a detour to avoid unreachable cells, the cached_path is cleared, because the path is not a path to the goal.

[hh2010]

once you use move_tail calculation for unreachables, the reason for recalculate_path=False is that re-checking the path is dangerous since the tail moving can result in shorter paths that create unreachables that cannot be fixed.

If unreachable_move_tail.any && unreachables.dist_to_farthest < INT_MAX then it should be ok to follow the path.

can you explain this further? i spent a lot of time tonight trying to understand and try out variations of this in the code, but was unsuccessful.

happy to discuss in a chat if easier. thank you.

[hh2010]

ok after coming back to it i understand what you are saying now. implemented in PR above and will fix the problem.