Hypersonic game: programming a bot for fun (Part One)

Last month I discovered a web, CodinGame, where people can learn to program or try new languages in a fun way. There are small tutorials, to familiarize with loops, conditions, arrays and things like that. Quick competitions between users (5 minute battles) and multiplayer games. And also a contest every month, it is a multiplayer game but with prizes 😀

When I found it there was a contest going on, called Hypersonic. And it looked really good, so I decided to try it out and see if I could reach a high score in the rankings and for fun.

I picked Javascript because I feel comfortable enough with it and I don’t want to code in Java all day haha. This is what happened.

The contest

Hypersonic is pretty much a bomberman, and the objective is to destroy more boxes than your opponents. Simple uh? Nothing I can’t do. So yeah, the start is easy enough cause you don’t have to care about being killed by bombs, nor selecting moves very carefully. You just move and place bombs and if your bot performs better than the «boss», you are promoted to the next league.

Wood leagues are very easy. Bronze is fine. Silver is harder. Game rules change a bit on each league: bombs can harm you, there are also items on the map you can collect, up to 3 opponents… So the game is more complex as you progress, bots get smarter with every league and you are forced to improve. Reaching Gold league isn’t easy. And only a few managed to reach the last one: Legends league. My Javascript bot was not one of them 🙁

I managed to finish in the top 273 out of 2715. And top 11 for Javascript. Not bad. But why there are only 10 Javascript bots in the top 250, strange uh? There is a reason for that: bots have 100ms to provide an answer each turn. Yeah, C++ guys kicked javascripters out of the top haha.

But the contest was really fun. I spent like 5 days on it, 2 of them full time (and when I say full time I mean 24h – 8h to sleep and a couple hours to «survive» as a human), and it is always a good idea to do new things and learn something different having fun on the way. The people at CodinGame did a great job with this game, rules were clear, leagues were challenging, well done!!

The bot

My bot started as every single program on earth: a dirty & quick™ solution. The problem is that it didn’t improve over time haha. With rules changing on each league and a very limited amount of time till the end of the contest I had very good excuses not to stop and refactor before adding new features. So yeah, the code is not beautiful.

But apart from that, if you have a look at the code, you will see something interesting, and it is that the bot just «simulated» one turn ahead. Only one. Why? Cause I didn’t need more than that in the beginning, and once I had spent 3 days on it, changing it completely was not possible. With just 100ms per turn there was no guarantee I could simulate multiple turns so a simple strategy was needed.

Stay safe

Instead of simulating every possible move, up to 6 or even 8 turns ahead, the bot follows a «simple» rule: place a bomb and go to the closest safe spot. If there is no safe spot, then do not place a bomb. Even more, think of what would happen if all players placed a bomb this turn, if you can’t find a safe spot then don’t place a bomb.

What is a safe spot? A place out of range of bombs, that my bot can reach without exploding. That is, every spot in the way to that «safe spot» must not explode when my bot is on it. That’s what I call a safe path to a «safe spot».

The good news is that this is enough to keep the bot safe most of the time. And there is no need to simulate hundreds of scenarios, just to compute the number of safe turns for each spot.
The bad news is that you don’t need a safe spot to stay safe. Confused? Let me explain: bombs explode after 8 turns, so you can stay next to a bomb for 7 turns and then move away. You don’t need a safe place immediately after placing a bomb, you just need a temporary safe place, thats enough.

So yeah, my bot survived most of the time, but Gold league bots were smarter and destroyed more boxes in the same time. They chained bombs to explode boxes faster, they moved into «traps» cause they knew a box will blow up in a few turns and they will be able to scape that way… beautiful moves, really.

My approach was not that sophisticated. No decision trees, no minimax, no BFS nor DFS. Just a simple strategy.

So here is the Gitlab repo with bronze, silver and gold versions so you can have a look at it: https://gitlab.com/salvatorelab/hypersonic

The lessons

Test

I had no tests. When something is easy, like the Wood leagues, sometimes you feel that tests are going to slow you down, you are going to waste time on them. You just parse the input, write a few lines and the bot works. Good, next league. Repeat.

But at some point, you start to spend more time reading your own code than writing new lines. At some point you break something that was working before. And at this point, writing tests for what your bot already does (and it does a lot of things) is a pain in the ass.

So the lesson is: always write tests. Parsing the input should be a test (well, multiple tests probably), placing a bomb in the easiest scenario should be a test. Finding a safe spot should be a test. And so on.

And in this case, with a game you can’t debug, having tests is a huge advantage. Reproducing a specific move of your bot when you don’t have tests is very hard. And if your opponents have some kind of randomness, you won’t be able to reproduce anything at all. But with tests, you just have to copy the input for that turn and see whats going on, debugging your code locally.

Refactor

Try to refactor once your new feature works. If you don’t have tests, then refactoring is risky cause you can break things and that’s a good reason not to change anything.

That happened to me so many times… Even with very simple changes like renaming methods and variables. When this happens multiple times, you start refactoring less and less, cause you know there is a chance you will loose time fixing errors.

Something interesting happens with refactors: it is easy to measure time spent on refactoring. But, once you refactor something, how much time will you gain thanks to renaming a variable or a method? That’s really hard to notice and measure. You only care about it when you are working with ugly code, and questions like «WTF was this method doing?» start to come to your mind frequently.

So, I think its a good rule to refactor once a new feature works. Or in other words, once a test is green.

Martin Fowler says that optimizing for performance is not refactoring, but I am going to include optimizations here in this section anyways. With a 100ms time limit per turn, performance is important. If you know something can perform faster, I think you should change it.

Learn

This game was a good opportunity to learn about decision trees and game strategy. I am currently working on a new version of the bot, this time in Java, with a more «academic» approach (the Javascript bot was kinda homemade). The code is in the same repo and I will talk about it in another article probably, once it performs better than the Javascript version hahaha.

CodinGame is a great way to learn about new things. I’ve never used decision trees, just learned about them when I was studying but thats all. This game is a good excuse to do something different, learn about ways to traverse the tree and stuff like that. If you are interested, I found this video from MIT very helpful: Search: Games, Minimax, and Alpha-Beta

So if you have time, have a look at CodinGame, maybe you can learn something new, or try a new language while having fun. There is also a good community around it, and a chat, so you are not going to be alone.

And that’s it for now, stay tunned for part two cause the Java version is going to be interesting: taming the garbage collector.

Here is part two: Hypersonic game: when Objects hurt performance (Part Two)

If you think my content is worth it you can Buy me a Ko-fi