Sounds cool, that title make it sound like yet another worms.io clone, but this is programmatic gaming - I feel the title should include that, or "make a snake bot to battle in a classic 'snake' arena".
I have a question - with AI nowadays that can dominate pretty much any board game - is there any hope for anyone 'hand coding' a strategy here against someone who just trains an AI model.
How does the problem space change in a game such as this where it may be 1v8 opponents vs a 1v1 game such as chess I wonder
Last year, I believe only one team even _tried_ an ML snake and they didn't make enough progress to actually compete. "Hand coding," so far, has been the way to go.
Not sure if it's what you meant, but it's less "hand coding" and more about trying to enumerate board-state possibilities (i.e. "I'm hungry" or "there's a snake at x") and addressing them via generalized algorithms.
Very plainly: no, hand coding is not going to be able to compete with a fully developed ML/AI agent. Even simple hand coded agents use AI techniques such as minimax, which is fundamentally an "AI" technique even though most people today don't really think about it that way since there are no deep neural networks involved.
However, this contest looks unpopular enough that you can likely still compete because no one has spent the effort to actually build a proper deep-neural-network agent, etc.
You can work out the problem space yourself by simply calculating all the possible board states. Or you could calculate the move states (3 moves per player, to the power of the average number of turns).
This is a super interesting question to us, and to be honest we're not sure of the answer. Is it possible for a single ML snake to achieve 100% 1v1 win rate? What about 1v7?
What we've learned so far is that playing against multiple snakes, especially AI/ML driven snakes, adds an incredible amount of complexity to the game and the top ranked snakes tend switch around quite a bit as players adjust to attack/defend specific strategies.
If anyone has formal theory around this sort of problem, we'd love to investigate further.
Sure, the answer is trivial: 100% perfect agent isn't possible. Just have an AI play against itself. Since the game is simultaneous moves, there is no "first move advantage" or anything, so it would play out exactly as a mirror (give or take some random noise in the model). The only thing that would break the symmetry is where food spawns, which also would just be a coin flip which snake it would be close to.
In a 8 player game, it's a little different because there are 'side' and 'corner' positions. Obviously this isn't symmetric anymore, so if you played many games, one position would make itself clearly superior. That likely depends again, on the probability of food appearing in a snakes "zone of control" which you could represent with a voronoi diagram.
My gut instinct is that a 'side' position would eventually be revealed to be stronger because the snake has more options and freedom.
Of course, in a tournament setup, it's fully possible for an AI to have 100% win rate just by random chance, because you are only playing a finite number of games.
More than 2 players adds another level of complexity: alliances. Snake is a bit like Risk in that it's possible to attack a specific player while signalling intent.
We should expect any proper AI to read and understand the others and work out who should be avoided or ganged up on. Rock-Paper-Scissors tournaments have bots that use game moves to recognize eachother and then dump all their points onto a single player -- something similar could happen in Snake as well.
Glad to know that the answer isn't a definitive 'yes' right now then! It's certainly an interesting space I bet you enjoy reading through the solutions :)
From what I found in their documentation, the limitation is latency. Your server can use whatever compute cycles it wants to formulate a decision for a single turn, but if it doesn't respond with sub 250ms latency then the snake just carries on in its current direction instead of making a move that turn.
Does anyone have a list of competitive programming challenges like this? Specifically where you're programming a board game against other algorithms. Googling "competitive programming challenges" doesn't yield a lot of good results.
I know https://leekwars.com/ and have seen a couple others coming by, both on HN and played by my friends, but I haven't seen such a list. There also seems to be a few interesting single player ones, like ruby-warrior.
Scalatron[0] is a fun one. There's also screeps[1] available on steam. Screeps is probably my favorite because it supports webassembly. So you can use any language with it, like Rust, C++, etc...
BotLand is a blast (can write your own scripts or use built in options to get started without coding). There are also related developer streams on Twitch most days if you're into pulling back the curtain. https://bot.land/
Historically, they've recommended Heroku... however, their dynos have a cold-start problem, causing your snake to sometimes timeout. I would recommend using an AWS free-tier instance if you have the option.
I remember that, they recommended a workaround last minute for it. Our snake depended on simulations so we just spun up a beefy GCP instance for a short period at the expense of a few cents.
If you're looking for something easy to get started with digitalocean / linode offer reasonable plans ( and you can always host a site or something with the extra power you'll have spare )
Alternatively aws offers 12 months limited 'free' usage on many of its services last time I checked - you should be able to use their most basic ec2 instance within that free tier I believe
All the options other people are suggesting are good, but if you host on Google Cloud Compute's us-west1 region you'll get very low latency as that's the region from which they send the HTTP requests.
I'm a fan of Google app engine for pain free deployment of simple things. If I have a go at this later, it'll be a Phoenix (Elixir) app running on app engine flex.
That game is super addicting. You will need a mouse. You will have fun testing out various bait-and-switch moves you can use to get noobs. Once you get good enough to make it into the top 10, everyone starts trying to kill you and it becomes exponentially more difficult to stay alive. I used to edit the script to increase my event-out rate a little bit to give me an edge, but I'm not sure it worked, seeing as the server could just throttle the events anyway. Once your snake gets long enough, you can enclose other snakes in a loop and torture them as they face their impending demise. Fun times.
We ran a hackday where we attempted to build a multiplayer snake over websockets using Django channels. I don’t think I touched on it in the write up, but websockets/tcp is the wrong choice for this kind of game.
" Step 1
Write a program to play the game Snake
Step 2
Deploy using whatever technology you like
Step 3
Battle other snakes and compete in arenas!
"
Sounds cool, that title make it sound like yet another worms.io clone, but this is programmatic gaming - I feel the title should include that, or "make a snake bot to battle in a classic 'snake' arena".
Yeah I like something like this: "Build a bot to play the classic game 'Snake'"
That sounds just like armagetron.
I just realized that a multiplayer Snake is basically the TRON racing game played on a discrete grid.
Haha, yes! We actually had a "Tron Mode" at the tournament last year that just flooded the board with food to replicate light cycles.
Wasn't there also a bounty snake with tail pinning on?
I remember playing xtron in the office maybe 20 years ago.
https://screenshots.debian.net/package/xtron
Cool, I'd love an xtron (or waylandtron ;)) legacy, 3D with multiple levels... hmmm...
Looks very cool!
I have a question - with AI nowadays that can dominate pretty much any board game - is there any hope for anyone 'hand coding' a strategy here against someone who just trains an AI model.
How does the problem space change in a game such as this where it may be 1v8 opponents vs a 1v1 game such as chess I wonder
Last year, I believe only one team even _tried_ an ML snake and they didn't make enough progress to actually compete. "Hand coding," so far, has been the way to go.
Not sure if it's what you meant, but it's less "hand coding" and more about trying to enumerate board-state possibilities (i.e. "I'm hungry" or "there's a snake at x") and addressing them via generalized algorithms.
That's interesting I updated my comment to be a bit more specific.
I'd love to know how the problem space looks in this game vs chess for example as I mentioned.
My terming is a little vague what I had meant is 'black box' solutions I guess where the logic can not be inferred via looking at the code
Very plainly: no, hand coding is not going to be able to compete with a fully developed ML/AI agent. Even simple hand coded agents use AI techniques such as minimax, which is fundamentally an "AI" technique even though most people today don't really think about it that way since there are no deep neural networks involved.
However, this contest looks unpopular enough that you can likely still compete because no one has spent the effort to actually build a proper deep-neural-network agent, etc.
You can work out the problem space yourself by simply calculating all the possible board states. Or you could calculate the move states (3 moves per player, to the power of the average number of turns).
This is a super interesting question to us, and to be honest we're not sure of the answer. Is it possible for a single ML snake to achieve 100% 1v1 win rate? What about 1v7?
What we've learned so far is that playing against multiple snakes, especially AI/ML driven snakes, adds an incredible amount of complexity to the game and the top ranked snakes tend switch around quite a bit as players adjust to attack/defend specific strategies.
If anyone has formal theory around this sort of problem, we'd love to investigate further.
Sure, the answer is trivial: 100% perfect agent isn't possible. Just have an AI play against itself. Since the game is simultaneous moves, there is no "first move advantage" or anything, so it would play out exactly as a mirror (give or take some random noise in the model). The only thing that would break the symmetry is where food spawns, which also would just be a coin flip which snake it would be close to.
In a 8 player game, it's a little different because there are 'side' and 'corner' positions. Obviously this isn't symmetric anymore, so if you played many games, one position would make itself clearly superior. That likely depends again, on the probability of food appearing in a snakes "zone of control" which you could represent with a voronoi diagram.
My gut instinct is that a 'side' position would eventually be revealed to be stronger because the snake has more options and freedom.
Of course, in a tournament setup, it's fully possible for an AI to have 100% win rate just by random chance, because you are only playing a finite number of games.
More than 2 players adds another level of complexity: alliances. Snake is a bit like Risk in that it's possible to attack a specific player while signalling intent.
We should expect any proper AI to read and understand the others and work out who should be avoided or ganged up on. Rock-Paper-Scissors tournaments have bots that use game moves to recognize eachother and then dump all their points onto a single player -- something similar could happen in Snake as well.
Glad to know that the answer isn't a definitive 'yes' right now then! It's certainly an interesting space I bet you enjoy reading through the solutions :)
Some competitions like this only give you a certain amount of "cycles" per turn, so hand written solutions would have an "advantage" in that sense.
I don't know if that method is applicable to this particular game though, since the processing is done by the user.
From what I found in their documentation, the limitation is latency. Your server can use whatever compute cycles it wants to formulate a decision for a single turn, but if it doesn't respond with sub 250ms latency then the snake just carries on in its current direction instead of making a move that turn.
This could be appropriately called Snakes on a Plane. Sorry, couldn't resist.
Does anyone have a list of competitive programming challenges like this? Specifically where you're programming a board game against other algorithms. Googling "competitive programming challenges" doesn't yield a lot of good results.
I'm aware of http://fruitbots.org/, which I had a lot of fun with.
These are seasonal and for recruiting but you might be interested: https://halite.io/ https://terminal.c1games.com/
I know https://leekwars.com/ and have seen a couple others coming by, both on HN and played by my friends, but I haven't seen such a list. There also seems to be a few interesting single player ones, like ruby-warrior.
I found the following while browsing AlternativeTo, it might be nice to fill in the others as well: https://codecombat.com/, https://robocode.sourceforge.io/,
https://screeps.com/ is pretty neat, lots of different ways you can try to adapt to different situations.
Scalatron[0] is a fun one. There's also screeps[1] available on steam. Screeps is probably my favorite because it supports webassembly. So you can use any language with it, like Rust, C++, etc...
[0]: https://scalatron.github.io/
[1]: https://store.steampowered.com/app/464350/Screeps/
There is the old (very old) classic, Corewar [1]. I enjoyed playing Robowar[2] back in the day.
[1] https://en.wikipedia.org/wiki/Core_War
[2] https://en.wikipedia.org/wiki/RoboWar
This is a bit rough as an early release: Marionette AI available on Steam:
https://store.steampowered.com/app/652520/MarionetteAI/
BotLand is a blast (can write your own scripts or use built in options to get started without coding). There are also related developer streams on Twitch most days if you're into pulling back the curtain. https://bot.land/
https://www.pommerman.com/
Vindinium[1] is another fun one. It looks like the original game service is now offline but the server code is open source.
[1]: https://github.com/ornicar/vindinium
> Battlesnake Tournament March 2, 2019 || Victoria Conference Centre
What continent is this in? From the sound of things it's in a Commonwealth country but that really doesn't narrow it down much ;)
Victoria BC Canada Eh?! :)
Just curious, what would be the best hosting option for beginners to use for their snake API server?
Historically, they've recommended Heroku... however, their dynos have a cold-start problem, causing your snake to sometimes timeout. I would recommend using an AWS free-tier instance if you have the option.
I remember that, they recommended a workaround last minute for it. Our snake depended on simulations so we just spun up a beefy GCP instance for a short period at the expense of a few cents.
hah! last year, for our bounty snake, we used a c4.2xlarge. Still, we could only manage a depth of 6-7 before hitting the response-time limit.
If you're looking for something easy to get started with digitalocean / linode offer reasonable plans ( and you can always host a site or something with the extra power you'll have spare )
Alternatively aws offers 12 months limited 'free' usage on many of its services last time I checked - you should be able to use their most basic ec2 instance within that free tier I believe
Heroku is a really good option for beginners (and it's free!) We've got a few repos on GitHub that can be forked and deployed directly to Heroku:
https://github.com/battlesnakeio/community/blob/master/start...
All the options other people are suggesting are good, but if you host on Google Cloud Compute's us-west1 region you'll get very low latency as that's the region from which they send the HTTP requests.
I'm a fan of Google app engine for pain free deployment of simple things. If I have a go at this later, it'll be a Phoenix (Elixir) app running on app engine flex.
Dunno if anyone still play/remember this version.
http://www.hacker.org/worm/
For those that clicked thinking there be an actual multiplayer snake game over http:
slither.io
Be warned, this can ruin productivity in your day.
That game is super addicting. You will need a mouse. You will have fun testing out various bait-and-switch moves you can use to get noobs. Once you get good enough to make it into the top 10, everyone starts trying to kill you and it becomes exponentially more difficult to stay alive. I used to edit the script to increase my event-out rate a little bit to give me an edge, but I'm not sure it worked, seeing as the server could just throttle the events anyway. Once your snake gets long enough, you can enclose other snakes in a loop and torture them as they face their impending demise. Fun times.
We ran a hackday where we attempted to build a multiplayer snake over websockets using Django channels. I don’t think I touched on it in the write up, but websockets/tcp is the wrong choice for this kind of game.
Write up: https://devblog.kogan.com/blog/kogame-django-channels
Game: https://kogame-snek.herokuapp.com/
Disclaimer: it’s not very good. It was a one day project.
I'm surprised that Websockets is the wrong choice. What would be the right choice? WebRTC?
Yes, UDP is needed, otherwise you get lockups. We incorrectly attributed rendering delays to react rendering rather than TCP.
Few scripts for slither.io that enhance gameplay. http://void.wikidot.com/system:page-tags/tag/slither.io#page...
Looks better every year!!
we need more snakes in programming
Couldn't this be distributed?