How to master Hypersonic: the best strategies

One month ago was the start of Hypersonic contest. The competition has been intense until the very end. Now that The Accountant hackathon is finished and that the Hypersonic game is close to be released on the platform, it's time to come back on this crazy game and discover the strategies of the winners.

As you probably all recognised, Hypersonic was strongly inspired from the game Bomberman. It was a multiplayer game where your AI had to move on a grid and place bombs to destroy crates and possibly eliminate other players. The goal being to survive and destroy the most crates.
Each bomb had a timer of 8 turns before they explode and a specific range. The game was really accessible in the wood leagues, because your own bombs couldn't harm you. In Bronze league however, they would indeed harm you ("friendly fire"), this is where the game started to get very challenging.

Strategy of Ixanezis, winner of the contest

The Depth-First Search algorithm (DFS)

The crucial thing in Hypersonic is to destroy boxes faster than your opponents do.

Let's first imagine we don't have any opponent and we just want to destroy all crates as fast as we can. I didn't try to invent any heuristics or implement a self-educating system. Just a good old Depth-First Search! On every depth level of this recursive search, I tried to perform at most 10 types of actions:
  • place a bomb + stay where I am
  • do not place a bomb + stay where I am
  • place a bomb + move left
  • do not place a bomb + move left
  • place a bomb + move right
  • etc...
If an action happens to be valid, I simulate the environment and apply changes to it. The process recursively continues until some depth level D is reached. At the level D of the search, I estimate a score for the situation I've reached, and remember the global best score along with the sequence of actions leading to this situation.

My initial implementation was fairly straightforward, and has allowed me to achieve fixed D=5 on any test-case within 20ms (with #pragma GCC optimize("O2") surely).

This was basically the extent of what I did the first day of the contest. After that, I spent 4 days debugging, improving and speeding up the code.

DFS improvements

a. Caching

Since different paths in the DFS tree often lead to the same (or very much alike) situations, we can prune away those branches that lead to the situations where we have already been. In the Hypersonic game, this has improved my depth level up to 6-7.

b. Dynamic Depth

It becomes evident that in some situations we have enough time to run 10-12 steps deep when searching, while other situations branch very quickly, leading to a much lower level of recursion. In order to fully use provided resources (100ms) we try to go as deeper as possible until we hit the time limit

Let me just show you the C++-based pseudocode that makes use of Caching + Dynamic Depth:

The Dynamic Depth approach has increased my depth level to 6-15, depending on the initial situation.

c. Bitmasks

I'm convinced that any required operation such as moving a player, exploding bombs, removing crates or bonuses can be done in O(1) or almost O(1) time using bit masks in Hypersonic. However, I did not achieve such state-of-the-art implementation. I just replaced some commonly used operations with bitwise operations for speed and storage efficiency.

Hypersonic grid contains 11*13 cells, where 5*6 cells are always immovable and irreplaceable stones, so we have 11*13 - 5*6 = 113 playable cells. Luckily, 113 is less than 128, so we can store all boxes on a field within a GCC's unsigned __int128 type. If GCC wouldn't support this type, we would have used two unsigned long long's for the same purpose. After that, we can remove a box from a known location using a simple XOR operation. Most importantly, we can easily calculate the number of crates of a field using this code:

__builtin_popcountll would compile into a single popcnt instruction if the CPU architecture supports it, and if GCC feels like doing so (it usually does not, unless provided a -mpopcnt) option. Otherwise, it will compile into most efficient code possible to calculate those bits. From my experience, the resulting code is fast enough to be considered as a constant-time operation.

Same logic applies to storing and also manipulating bombs, players and bonuses.

These improvements allow to drastically speed up score and hash evaluation in some cases.

Estimating the score

No rocket science here. The score of the state consists of the following:
  1. Number of crates that I've destroyed before I reached this state + the number of crates I will destroy in next 8 moves, if I don't move at all
  2. Number of bonuses that I've collected, the score decreases if I already have enough bombs and a respectable fire range
  3. If I'm dead by this time, the score is strongly decreased.
  4. If I can't escape bombs' fire withing next 8 moves, the score is strongly decreased
  5. If an enemy can make such 2 moves, that I'm dead or deadly stuck after them, the score is strongly decreased
  6. If I can make such two moves, that an enemy is definitely dead or deadly stuck, no matter what he does in the future, the score is a little increased. (I removed this in my very final submission)
From my experience, the information provided above is enough to rank in the top 10 of the Hypersonic competition.

The overwhelming DFS replacement

It soon becomes obvious, that DFS search visits lots and lots of useless states. E.g., if you manage to destroy 3 crates within next 12 moves, then another search path, where you do not destroy any (within next 12 moves), is most probably useless and should not be evaluated further. However, in the DFS search, we know nothing about neighbouring states on the same level depth, so we can't estimate whether the situation is worth expanding.
The trivial solution to the problem is to replace the DFS with a Breadth-First Search algorithm (BFS) and expand all situations on the same depth level at once. On the other hand, BFS requires to simultaneously store all different states from the same depth level, which may require too much memory. The solution to the problem is to leave N (100, 300, 500) best states from the single depth level and to prune away less promising ones.

Such approach allows to iterate 30-50+ levels deep within 100ms. And thanks to this I was able to rank 1st in Hypersonic. Here goes the C++-based pseudocode:


In order to better understand whether one solution is better than another, I wrote a sandbox, that constantly clashed different strategies with each other. And only after a few thousands battles, you can conclude that solution A is 5.2% better, than solution B. Otherwise, it's sometimes very hard to say for sure, whether some improvement you've made improves anything.

Strategy of Romka, 2nd of Hypersonic

At first I thought that brute-force will perform poorly in this task. The reason was that you need to have a depth of at least 8 in order to see what happens after you put a bomb and it explodes. So my initial approach was the following.

For each cell on the field

  • Find some optimal path to this cell to pick up a lot of bonuses (this path could visit each cell at least once)
  • Find some optimal bomb placement along this path
  • Calculate score for this path based on found bombs placement and bonuses collected
  • Select plan with the best score

It was enough to be top-1 for several days, but this approach has obvious limitations. Then I decided to do Breadth-First Search on the graph of all states. I picked BFS because I could naturally limit its depth only by the time limit, which is harder to do with DFS. I decided not to pay any attention on my opponents at first.

One node of graph was describing state of the world after some steps. It included:

  • Vector of bombs that was placed either at the beginning or during the BFS
  • Mask of exploded boxes (64-bit int)
  • Mask of exploded bonuses (64-bit int)
  • My position, bombs, range
While maximum number of bombs was 65, I allowed collisions for them to store in 64-bit mask. It's quite obvious that box number will quickly drop below 64 after the first 8-12 turns of the game.

When performing BFS, for each node extracted from the queue, I did the following:

  • Calculate possible moves before the explosion of bombs
  • Perform bombs explosion

For each possible move:

  • Check if I will not trap myself (that is by far the most time-consuming part)
  • Create new state after that move and put it to the queue

When I have reached time limit for the move, I performed a move that leads to a branch with the state with maximum score. Score for each state was calculated as a linear combination of values of exploded boxes and picked bonuses.
When considering boxes, I assign higher values to boxes with bonuses than to empty boxes. Besides that, I reduce box value by (some coefficient) * (steps before this box will be exploded) in order to explode boxes faster.
When considering bonuses, I assign value to it depending on how much of this bonus I've already picked up. I decided that I do not need more than 5 bombs and more than 8 explosion range. Bonuses increasing bomb count were more preferred that ones that increase range.

That was quite good and I decided to improve it. I created "list of forbidden initial moves": at the beginning of each turn I did brute-force search of depth 2 for me and every opponent. If I see that after some move, the opponent has a sequence of two moves so that I get trapped, I added this move to the list of forbidden moves. This gave me much better survivability. I decided not to spend my time writing code for attacking opponents because I found it very hard to achieve: it is very difficult to trap an opponent that performs at least 2-ply DFS in order to escape (as I do).

This was still not as good as I wanted: I had quite optimised code and still could get only to depth 8-9 at the beginning of the game and to depth 4-5 in the middle when the field is almost empty. I decided then to cut off some branches of BFS tree.

My first cut was not to put a bomb if it will not explode any boxes. While it is not optimal in some situations, it is a very rational decision in general. That increased my depth by 1-3 in some cases.

But the main improvement that allowed me to secure my rank in the top-3 was converting BFS to a Beam Search. On each tree level, I decided to leave only some hundreds of nodes that were "most promising". I tried to do this in the Smash The Code contest too, but there were too many combos and it was very hard to decide which nodes were more promising than others.
Here in Hypersonic it was very, very natural. I selected nodes according to the same scoring function described above. It turned out to be a blast :)
With this improvement I managed to easily reach search depth of 30-40 during all the game and it allowed my bot to see way more ahead than other players.

So the secret was just in the Beam Search, not in the scoring function, as some people assumed in the chat :)

Strategy of kimiyuki, 3rd of Hypersonic

I did a simple Beam Search: generate 10 (MOVE/BOMB and 5 directions) next states for each current state and select good ones, depth was 7,8 turns.

I thought that the main difficulty of this game is the distance of time between the action (e.g. putting a bomb) and the effect (e.g. explosion), so I tried to solve this.

I think the important points of my implementation are the following:

  • In the evaluation function, I estimate the boxes which will be broken in the future.
  • For each state in the beam search, I roughly calculate whether it is a survivable state or not.
  • For diversity of states, I restrict the state sets to having only a few states for the same player position.

Other notes

I didn't implement anything to take other players into account. So my AI was often killed by others.
I suspect that the one step of beam search should be one event (e.g. getting item), instead of one turn.

Thank you all of you for sharing with us and congratulations again! You can find strategies and feedbacks from a lot of other players in this forum topic.
The game will be released really soon in the bot programming section of the platform, stay tuned!

Competitive programming: towards a new era of eSports?


eSports. The phenomenon is not new but is on the rise worldwide. As millions of fans enjoy watching their favorite video games played live at the highest level, new forms of electronic competitions are emerging with technology. Can competitive gaming be taken to the next level by cleverly mixing video games with programming? Competitive programming becoming as popular and entertaining as competitive gaming, utopian dream or prophetic statement?

Welcome to the eSports generation

Most probably you're familiar with eSports already. Every year these video game competitions break records of audience, slowly but surely challenging classic sports competitions. Widely broadcast online through platforms such as Twitch, eSports tournaments are watched by thousands in giant stadiums where they are organised, and by millions online. Prize pools also break records, reaching tens of millions of dollars for winners. Some professional players are beginning to make a living out of it.

The future of eSports is exciting

In years to come, eSports could be pulled in unforeseen directions, taking into consideration the evolution of technology. What will it look like when technologies like Virtual Reality and Drone Racing will have become common? Could programming enter the field and contribute in blurring the boundary between entertainment and sports?
Programming can allow players to make the game whatever they want it to be, which could lead to the most exciting and entertaining competitions.

Pro gamer or programmer?

Imagine you could add a brainteaser dimension to competitive gaming. Not only should gamers have a strategy, but they should implement it, this time with code. Technical skills involved would be different: advanced knowledge of programming languages and algorithms would replace incredible levels of dexterity with controllers. You could program an Artificial Intelligence to do the same actions a gamer would do, and beat other AIs in the same arenas of today's eSport. And why not even try to beat other humans playing the game normally. It is somewhat reminiscent of the victory of the program AphaGo against a human this year at Go.

Watch and learn

One of the reasons people love to watch eSports besides pure entertainment is that they can learn from the best players in the world and try to imitate them. They marvel at players showcasing their technical skills and their fabulous strategic decision-making.
Watching elite coders program live while commenting on their strategy is also a great source of inspiration to learn new programming stuff. Coding streaming has become more and more popular on platforms such as or Twitch. And it takes the learning experience to a whole new level when video game graphics help spectators understand the code as they see it come to life.

It's a kind of magic

The next step will be to make the exercise of programming interesting and enjoyable even to non-programmers. Programming and Artificial Intelligence in particular can be extraordinary: what looks like just several hundreds of lines of code can lead to a bot which autonomously behaves in a really smart way. Sometimes it will even perform better than expected.
The world of programming awakens curiosity as it becomes more and more accessible and compelling. Warner Bros. made no mistake about it. They asked us to create a worldwide coding competition for the release of “The Accountant”, a thriller starring Ben Affleck. Cinema, gaming, programming, all united in a new kind of entertainment.

To glory

To reach the level of popularity of eSports, competitive programming will finally have to adapt and become more social. Why are eSports fans so passionate? They have been able to dive into the different game worlds, learn to love their characters and share this passion with other fans. Let’s flesh programming bots out: build them a story and personalities which people can identify with.

In a near future where programming will become a basic skill to learn, Artificial Intelligence has a true potential to make competitive programming popular. Can we expect coding competitions to become a new category of eSports? At CodinGame, we want to be part of this new era of eSports.

Launch of the Accountant hackathon

We’re inviting you on the 1st of October to dive into the unique world of "The Accountant Hackathon", a contest sponsored by Warner Bros., in theaters on October 14th.

Mission time: 1st - 15th October

From: Warner Bros., Burbank, California

Alias: Christian Wolff, accountant

  • Save the world (thx Bruce and Clark)
  • Secure sensitive data


For this mission, you take the role of Christian Wolff, an unconventional accountant who has lived as a double agent for years, gathering highly sensitive data while working for the most dangerous criminal organizations of the world.
As things are starting to unravel, it is expected that Wolff's enemies will attempt to get their hands on these files.

As Wolff cannot risk to blow his cover up, we need you to make sure the data is secure.

Good luck.

Register now to the hackathon

How CodinGame survived a Reddit Hug of Death

Last Monday afternoon, a link to CodinGame was posted on reddit. It gained a lot of success and resulted in what is called a hug of death: our platform went down for 2 hours because of the overwhelming amount of new visitors.

Internet is beautiful

This was so far a normal day. We were working on the last preparations for the next multiplayer coding contest Hypersonic to be held this Saturday. Around 2pm, Nico, our CTO, shouted that we were suddenly receiving a lot of traffic.
A link to our starting page had been posted on the subreddit /r/InternetIsBeautiful under the title “Learn to code writing a game”. The traffic was already 10 times higher than usual and we were rejoicing.
After a few minutes watching the incoming traffic grow more and more, we began to notice some lags…

When will it stop? Can we support the load?

From excitement to panic

After some quick monitoring, we realized the CPU of the database server was already capped. We decided to multiply the capacity of our RDS (Amazon Relational Database Service) by 4 on AWS. It took 30 minutes at the end of which it interrupted the service completely. We had no choice.
After that change, the server was able to take in a lot more load, lags came back again pretty soon, when some other point of the architecture started to fail too. Now the front-end servers were failing.
The CodinGame platform normally uses two application servers hosted on EC2, behind a load balancer. So we tried scaling up by doubling that number (we eventually reached 6 servers in the end), but some of them started to crash. We tried relaunching them, to see them fail again after a short time.
The platform was becoming barely usable. What a waste, all this traffic to a dead/lagging site...

Reddit had put CodinGame to its knees.

Crisis management

While activity on our social media channels started to increase, the CodinGame chat was buzzing with questions. The community regulars were doing their best welcoming newcomers.
The chat server was also under heavy load and wouldn’t accept new users (more on this later). Forum didn’t last long either. We took the opportunity to offer an AMA (ask me anything) in the comments of the reddit thread.
At the same time, a Twitch streamer was desperately waiting to do a Clash of Code session. Things were looking bad and everyone was preoccupied. Reddit finally tagged the post with “Hug of Death” so visitors didn’t end on a dead site.

The end of the tunnel

After two long hours, we managed to get the servers back and running, and we asked the reddit moderators to bring back the thread. Traffic came back as a wave as the thread was reposted on Hacker News and other tech news sites. And lags again. Something was taking down our servers and we couldn’t find what. Finally we put in place a script that would reboot a server each time it failed so we maintain the service over the night.

On Tuesday afternoon, when things had calmed down, we took the time to come back on what had happened. Traffic had been crazy: we got as many new users in one day as during the last two months. There had been technical failures. Understandable failures but to be taken care of.

Post-Mortem - What went wrong

1) The main bottleneck of the CodinGame platform is the RDS database. Every information on CodinGame is centralized there, all tangled. We cannot distribute the database without setting up separate servers splitting users, for instance by region (America, Europe, Asia). This is the major scaling issue.

Solution: the short term action we’ll take is to investigate caching solutions, distributed caches between our application servers.

2) The second issue we’re currently following up is a memory leak on the application servers. This bug occurs when a server is under heavy load and eventually leads to a crash.

Solution: track the bug, kill the bug.

3) The CodinGame forum is hosted on a really small machine, and is poorly integrated on the platform through an iframe so that every user on any page of the site sends an SSO authentication request to the forum. The number of queries that were sent to this instance capped the CPU, and just like that, the forum was no more.

Solution: Better integrate SSO between the website and the forum to avoid unnecessary requests. Migrate the forum on a tougher machine.

4) This very blog crashed, simply because it was… hosted on the same machine as the forum, that maxed out the CPU.

Solution: Separate applications in different containers/machines.

5) The CodinGame chat server did exactly what it was expected to do: fail under heavy load. It uses XMPP over WebSocket, with a custom client built on top of, and a back-end built with Prosody. Prosody is a really cool back-end built with lua, but it has the slightest problem: it is single-threaded and non-distributable. So, as expected, the server process quickly reached 100% of a single CPU core and started to lag badly and act erratically. It didn’t crash, but wouldn’t take in new users.

Solution: Switch our back-end solution to a scalable one, such as eJabberd or MongooseIM.

6) Last point of failure in this real world scalability test: the push server. We use a websocket connection to push data to the client, triggering diverse events (notifications, mostly). This server had a limitation of open file descriptors, arbitrarily set to 10K. We set it to 100K and it started working again, accepting up to 60K simultaneous connections (this is the best estimation we have of the number of open tabs at that moment) before it went night-night.

Solution: This is an Embarrassingly Parallel Problem, and it should have been a scalable pool of servers behind a load balancer from the beginning.
Impact of reddit on the traffic

We took a blow, but we're back on our feet, stronger than ever. We'll be happy to answer any question you might have about this special event. Don't hesitate!
Welcome to all the new users!

Dev Diary: how the Hypersonic contest was built

There are 16 days left before the beginning of the next contest Hypersonic. We will celebrate the second anniversary* of the platform and we’re really excited to share it with you. We hope you're ready!
Here’s Hypersonic diary, from its origins:

Day minus 117, Conception

Romain, Art Director: “It’s a girl, we need to find her a name”

Romain working on the main illustration
This is the time to work on the main illustration. A vote is done in the development team to help Arthur and Aude find the prizes. "What would you like to win?"

Another vote is conducted to find the name of the contest. Not an easy task! 

Contest name: results of the vote
All of this should be done really early. Indeed at the end of a contest, the registration page of the next one should be updated. So everything needs to be ready at the end of Codebusters.

Day minus 85, Hacking

Alexis, Corporate Relations Hacker: “Hey, the contest has to be crazy good, because another company is ready to work with us”

Some developers register for fun and glory. Others want to get noticed by companies. Our goal is thus to showcase lots of interesting job opportunities to them.

Obviously this isn’t a one-day job. As of today there are 19 sponsors for Hypersonic.

Day minus 54, Brainstorm

The whole dev team:
“_ We could do a game like StarCraft?
_ Too complex.
_ Something chess-like ?
_ Too classic.
_ A game with bluff like poker?
_ Too random

At some point, the type of game should be decided. Either we stay very close to an existing game (Puyo-Puyo for Smash the Code) or we build our own game (like for Codebusters). Indeed we try as much as possible to provide you with something reminiscent of the illustration, but it’s not always easy to do. 

The dev team also begins to discuss the possible rules for each league.

Background of the game

Day minus 50, Building

Julien, Game Builder: “The status for Hypersonic, well, it’s ongoing.”

Each game is mainly built by one developer only. Of course, all the team can help for anything: testing, code review…

It usually takes 2 full weeks until a prototype can be tested. At the same time, the design team (Romain and Malia) starts to work on the assets of the game.

Asset of the game

Day minus 36, Testing

Jerome, Product Manager: “Yeees, I beat the boss”

Follows a series of iterations between the game builder and the testers. Usually all developers try the game and give some feedback. Rules are tweaked, the statement is improved, art assets are added to the game...

One important concern, as you might guess, is the difficulty of the game.

Day minus 24, Promotion

Thibaud, community manager: “Already 5 CodingHubs!”

The more, the merrier. A contest is a programming competition, but it’s also a fun event where a lot of developers discuss and share their passion for coding. For example, in a CodingHub.

This is the time we start to communicate more about the contest, like with this blog post (blogception!).

Hour minus 1, Excitation

It will seem like a normal day at work although it'll be Saturday afternoon. Most of the team will gather to ensure a smooth launch of the contest.

We look forward to seeing you on Saturday 24th of September at 12:00pm EST for the opening of Hypersonic!

*CodinGame isn’t 2 years old, the platform was just really different before.

CodingHubs: Meet, Code, Enjoy!

In less than 4 weeks now, several thousands of programmers will doggedly try to code the best bot they can in the Hypersonic contest. Competing in such a challenge is exhilarating, and the only thing you want to do (apart from coding) is discuss with others about the problem at hand. We're giving you the opportunity to do it, we're indeed launching the CodingHubs!


CodinGame does not only happen online! A CodingHub is a place to meet with other CodinGamers, code together around a game and enjoy the fun of coding.
Meet, code, enjoy!

CodingHubs are organized by voluntary CodinGamers usually for an evening at a private place, may it be at their university, at their company or at home. (provided they get the authorisation to do it).

And to add more fun to the event, we'll be sending CodinGame goodies to each Hub!

Great, where do I sign?

You can find all information (date, address, contact email...) about CodinHubs on the map below. [if the map doesn't show for you, trying clearing your cookies] They are indicated by a yellow wifi icon:

If you're interested in joining an existing CodingHub, you have to contact the organizer to register to it. Obviously the number of available seats is limited.

I can't find any Hub near me :(

No worries, there might not yet be a Hub close to you, but there may be other enthusiastic CodinGamers not too far. They are indicated by the green laptop icon on the map:

Fill this form to signal fellow CodinGamers you'd be ready to join a Hub.

I should update the map within 24h. One day it'll be dynamic, I promise. 

Let's be crazy, I'm up to the task

Interested in hosting your own hub? Congrats!

You can fill this slightly longer form and we'll get in touch with you really soon to help you organize it.

Same, I'll update the map as soon as I can, but at night, I sleep. 

Is there something else I should know?

Once you’ve registered, you can talk about it with your friends and colleagues. The more, the merrier!
And don't forget your laptop! ;)

If you've got any question, don't hesitate to comment below. Else I'm always reachable at

Hub for Codebusters in Lyon
Hub for Codebusters in Montpellier
Hub for Codebusters in Paris