1
\$\begingroup\$

So, as has been done many times before, I am designing an AI that can play Snake as effectively as possible. It didn't take me long to find this extremely useful thread here: How to find a safe path for an AI snake? where the top answer first and foremost recommends forming a Hamiltonian circuit for the grid and begin by just having the Snake follow this route.

However, after attempting this, I realised it didn't work with my initial grid size (23x23), at least I don't think it does. My understanding may be incorrect, but from what I gather, with m rows and n columns, if mn is odd, then there is no Hamiltonian circuit possible. If this is the case, then should I abandon this method? Or is there any way of implementing it in some case?

\$\endgroup\$
  • \$\begingroup\$ That sounds like a theoretical computer science question. Game developers are more specialized in making Snake games for human players to play, not in making theoretically perfect AI to play Snake games. ;) \$\endgroup\$ – DMGregory Feb 2 at 15:37
1
\$\begingroup\$

Yes, you're correct, it's not possible. You can prove this using parity.

Color your grid like a chess-board. The start- and end-tiles of your Hamiltonian circuit must be adjacent, meaning they must have opposite colors. However, with an odd grid size, there are more of one color than the other, meaning to hit every square you must start and end on the same color. Thus no circuit is possible.

\$\endgroup\$
  • \$\begingroup\$ Apologies for the delay. Thank you, I tried exactly this, and it does indeed seem so. Regular old pathfinding it is. Thanks! \$\endgroup\$ – Polyrogue Feb 5 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.