Revealing the true face of competitive programming

0          
Competitive programming is scary. Too difficult? Inaccessible? Time-consuming? Above all, it remains a mystery for a lot of programmers who don’t really understand what is is. Two weeks before the launch of the Fantastic Bits competition, it’s time to reveal the true face of competitive programming. Dark arts or light magic?

I don’t have the time to write a proper algorithm. 
I don’t know anything about artificial intelligence. 
I’m not good enough compared to other participants.

These are the reasons we usually hear for not participating in one of our coding contests.

They are all irrelevant!
Don’t get me wrong, I understand your feelings.

You cannot spend the entire week coding because of work, family or whatever. True, but most of the other players can’t either. You’re not alone.

Overwhelmed by the complexity of AI? Trust me, if you’re a developer, you can do it. It’s just about writing code that solves a problem. I never implemented specific algorithms during contests and I wasn't so bad.

Competition scares you? You’re afraid of being compared with other developers? Who cares about who wins and who loses anyway? This is just about the fun of coding.

I think you should participate in the next contest Fantastic Bits. Here's why:
  1. If you haven’t noticed yet, the theme is inspired from the universe of Harry Potter. Come on, you’re not a muggle. Prepare your wand and broom and get ready to code some magic.
  2. You can easily get past the wood leagues. They have been designed to be easy and get the player accustomed to the game. Don't worry, it will become more complex, (fantastic) bit by bit. Remember: easy to enter, hard to master!
  3. We’ll stream on our Twitch channel on Monday 29th! We’ll start the contest from scratch and explain what can be done. We did it for The Accountant contest and it was a lot of fun, here's the video.
  4. There will be CodingHubs! It’s a kind of meetup to code, discuss and have fun around the contest. You can find all the needed information on this public Trello board



If you’re still not convinced, y_kawano, a regular competitor, may inspire you:

- Are you a software developer?
Yes, I am a game programmer! Recently, I‘ve been working on smartphone games.


- What is your favorite language?
C#! It is easy to debug, so I can quickly make and improve my AIs. I also use it to code tools to visualise and analyse the behaviour of my bot.


- Your history on CodinGame is impressive. When and how did you start doing competitive challenges?
I started when I was a student about 10 years ago. The reason I started competition is just for its sheer amount of fun. I’ve also participated in AI competitions in Japan like codeVS and SamurAI Coding and sometimes in TopCoder Marathon Match.

- On the other hand, you don’t train on classic puzzles. Is there anything you’d love to see on the platform?
I prefer battling against other programmers, so I’m only playing multiplayer games.
I think it would be fun to code an AI for a game like HearthStone.


- What do you like in competitive programming? Would you recommend it?
I love exciting battles against awesome programmers. The feeling of beating them is just great. Just look at this replay of a Hypersonic battle, isn’t it nice? Try it and you’ll see the fun in coding AIs.

- How do you prepare for competitions?
In order to make a good start, I get a good quality sleep on the day before competitions, and I wake up at 2am (CodinGame contests always start around 2 in the morning in Japan)

- Do you plan on participating in Fantastic Bits?
Of course I will participate! I want to get the 1st place!

Thank you y_kawano!

To conclude, I invite you to read an amazing answer on Quora which illustrates the difference between competitive programming and real life programming. Are you ready to kill the lion in the jungle?

10 characteristics of an excellent software developer

5          
What makes a great software engineer? There are plenty of opinions on this topic. Most common answers tell the following: able to produce maintainable working software, team player, keeping up-to-date with new technologies…

A study from the University of Washington ( “What makes a great Software Engineer?”) has uncovered 53 attributes of a great programmer. This is the result of almost sixty interviews of experienced engineers at Microsoft.
What makes a Microsoft software engineer great isn’t necessarily what makes a great software engineer. However most of these attributes are worth discussing.

The study classifies the 53 attributes in 4 groups and emphasizes on the most interesting ones in each group.
  1.  Personal characteristics
    “improving”, “passionate”, “open-minded” and “data-driven”
  2. Decision making
    “knowledgeable about people and the organization”, “sees the forest and the trees”, “updates their mental models and handles complexity”
  3. Teammates
    “creates shared context”, “creates shared success”, “creates a safe haven” and “honest”
  4. Software product
    “elegant”, “creative” and “anticipate needs”

Don't hesitate to check the whole list to understand better the ideas behind the attributes. Here below are the ones that resonate the most with us at CodinGame. Let's begin with three attributes from the first group.

1 - Passionate

The word “passionate” has been used and reused everywhere so much that it now appears as a hollow adjective. Still it remains an important trait of a software developer. Or any other company employee. Here at CodinGame, we all really love what we do and we believe in our goals. This is important for us that everyone in the team share this belief.

2 - Open-minded

To us, good software developers should be open-minded. Ready to change their opinion upon discussing with teammates or uncovering new information. No one is omniscient and anyone in the team can suggest ideas. Everyone welcomes and discusses them.

3 - Data-driven

Finally we’re willing to consider data before our own perception. It’s really easy to be deceived by your own judgment. Here at CodinGame we try as much as possible to stick to data instead of focusing on our own feelings before deciding what to do. It doesn’t mean we’re heartless. Of course we want to do awesome things for all our users, but in order to do so, we need to prioritize. At the end of the day, software developers are part of a business and they should decide what’s best for their business based on data.

In the second group, two attributes seem essential to us.

4 - Being knowledgeable about customers and business

As a developer, you build a product for a final user. Your job is to try to understand their needs and build features that are useful to them. Building features here at CodinGame is somewhat easier since we are also users of our platform. On the other hand we need to remain vigilant that we’re not building features for ourselves.

5 - Being knowledgeable about engineering processes and good practices

While processes slow things down, they’re are essential to ensure quality. One thing for example that is critical to us is code review. No feature goes to production before it has been code reviewed. For sure, there are areas where we can improve and we’re determined to keep building better softwares.

Great engineers are supposed to have a positive impact on their teammates. That’s what the third group of attributes is about. Any developer who has worked in a team knows how difficult it can be. Coding is very personal. Sharing your work and having it exposed to the feedback of the team can be hard.

6 - Not making it personal

One thing we agreed on at CodinGame is that we should not make it personal. As the study highlights, quoting a Microsoft manager:
You can have a very open and heated discussions. But it is all very professional; none of this is ever taken personally.” 
It doesn’t mean one can say anything just because it’s for the company’s greater good. To us, it’s just a common understanding that if there is something wrong, it has to be said. For the common good. We believe that good software developers should be egoless and put their company’s interests before their own.

7 - Honest

Software developers must learn to admit their mistakes. After all, making a mistake happens to everybody. The right thing to do is to try to learn from them and avoid them in the future. This is not as easy as it seems, but necessary to keep growing.

8 - Personable

Another one that is critical, especially for a small business like us, is what the study defines as "personable". Work is work but it’s so much easier to work when you get along well with teammates. A great software developer is also someone with whom you’ll enjoy sharing a beer outside of work.

9 - Creating shared success

This involves a lot of things. Software development is really a collaborative process. Each win (or failure) is the result of the team’s ability to work together. The more a developer manages to get everyone aligned on the same goals possibly using compromises, the more efficient the team will be.

Finally the last category regroups attributes about the software product that great engineers produce.

10 - Creative

Nothing is impossible and great software developers should be able to think out of the box and be innovative. However they should also know when to apply some answers to technical problems and avoid reinventing the wheel.


The bottom line is that this list of attributes can refer to a lot of jobs. Obviously a software developer should have plenty of technical skills. The key behind being a great software developer, is to be able to also grow and expand your non-technical skills.

What’s your definition of a great software developer? Which attributes resonate the most with you?

You can also read other very interesting point of views in the following resources:
A quora question What distinguishes a great software engineer from a good one?
And an article from Peter Nixey How to be a great software developer?


Reference: What makes a great software engineer?, by Paul Luo Li, Andrew J. Ko, Jiamin Zhu

How to master The Accountant hackathon: the best strategies

6          
We gave you a mission: take the role of Christian Wolff, aka "The Accountant", and secure data that was threatened by his enemies. Simple mission but difficult to master. The movie "The Accountant" from which the hackathon game was inspired has been live in theatres for three weeks now. Time to come back on the best strategies for the contest.

For everyone, this contest was special: 2 weeks of competition instead of just one, an overlap with Hypersonic (unfortunately we couldn't change the dates of either of the contests), an optimization problem after four consecutive contests of multiplayer bot games... and awesome prizes. So awesome that some players tried to access the validators and based their strategy on it. This was strictly forbidden by the rules of the competition, so sadly we had to invalidate their participation.

At first the hackathon looked straightforward. At each turn of the game, Wolff had to move or to shoot an enemy. Most enemies he could one-shot (kill with one bullet only). However, some enemies had specific amounts of life and the damage Wolff could deal depended on the distance he was from them. Enemies were moving slowly towards the data points Wolff needed to secure. He could afford to lose some data points but could also die if he got in range of the enemies. First difficulty was then to run away from enemies he couldn't kill in time.

To make the game really challenging, you would score most points if you managed to save the most data points using the less bullets as possible. To move or to shoot, that was the question.

Strategy of Rafbill, winner of The Accountant hackathon







My source code is available here (remove s of https) but is probably really not easy to read.

The core of my algorithm is to optimize a strategy generating a move sequence, rather that the move sequence itself. The notion of strategy I settled for is an ordering of the enemies, along with which enemies to intercept and how to intercept them, and where to move in the first steps of the execution (The first move is usually more important than later ones).

I generate several base strategies moving to a close position and then repeatedly killing the closest enemy. I have a function which executes and evaluates strategies: the score of a strategy is simply the end score, plus a large negative constant if I lose. I generate additional strategies to deal with test cases similar to the IDE test 26 by moving to a position required to kill an enemy before he takes his first data point.

I define several operations to randomly change strategies : swap two enemies in the order, decide to start or stop intercepting an enemy, and change the initial move position.

By hill climbing, it is then possible to find a local optimum. I originally used Simulated Annealing (SA) to avoid getting stuck in a bad local optimum, but the changes in scores are to big, so it doesn't work very well. Repeatedly restarting (I restart after 100 iterations without improvement) from a random initial strategy gives better results. This algorithm with the right tweaks gave scores in the 42k-44k range.

At that point, I focused on the stability of the results, as I noticed large score differences between executions. As my algorithm usually found the same ordering of the enemies in both the good executions and the bad ones, I decided to use its move sequence in another algorithm that would try to turn a bad execution into a good one.

The main idea is to generate paths that are close to the original path, but are considered better if they manage to kill enemies earlier/in fewer shots than in the original path. I used beam search. The states at iteration i are game states at time i, ordered so as to prefer move sequences that kill enemies faster.

The children of a state are obtained by moving to random positions, moving towards the next enemy or the position from where we shoot it in the original move sequence, or shooting the next enemy. This ensures this can find the original move sequence, and potentially some better ones. It achieved the original goals, as scores were much more stable using this second algorithm. Tweaking a bit the scoring function for the beam search, using all the available time to keep on improving the solution and a lucky submission got my final score.

Strategy of Ghirtor: 2nd of The Accountant hackathon







First of all, I did a basic simulator to simulate the full game without any optimization (like trying to remove cos or sin).

When I finished to correct all different bugs in my simulator, my first strategy for a turn was a random choice. During a turn, I then simulated all the games from the position I had, and calculated the score for each one (the one given in the rules). I then just saved the sequence of actions which lead to the best score and output the first one.

Then I implemented a few optimizations, to be able to play more games. For example, removing slow functions (cos, sin) and trying to use less square roots. For the moves, I chose a random point on the map and I used vectors to do it. For the enemies, I tried to update the target (data point) of each enemy as little as possible. I only updated it if the target of a specific enemy was removed during the previous turn.
In the middle of the contest, I added a new optimization: if there was only one enemy or only one data point on the map, then it was possible to know exactly where the enemy would be (enemies in case of one data point) at each turn of the game, so I calculated their path. In these situations, any action I did had no impact on the future positions of the enemies. It enabled me to simulate many more games (+200%) during the allocated time since I didn't have to update the position of enemies.

After my optimizations, I added some more strategies. First, if I could one-shot an enemy (one bullet to kill) then I did it. If there were several enemies I could one-shot, I preferred to target the enemy who was the farther away from me. Else I could randomly make a move or a shoot action. If it was a move action then I had a chance to make a random move or a chance to make a move toward the closest enemy. If it was a shoot action, I had a chance (a very small one) to shoot a random enemy on the map. Otherwise I shot the closest one.

And my latest strategy was the following: if I didn't find any way to save a datapoint in 50 or 100ms of simulation, then I tried a new strategy (which was better for test case 26 for example). Indeed the strategy I described above focused on the enemies to shoot and not the data points to save.

With all of these optimizations and strategies, I managed to reach more than 44k of score at the end of the contest.

I really enjoyed the contest and I had fun doing it.

Strategy of Vadasz, 3rd of The Accountant hackathon







Thanks for the contest it was a great amount of fun! When I first saw the contest, I noticed it was very close to Code vs Zombies. Even if there were some base components that I could reuse, the optimization part of the game was different. I thought it will be a contest where I would use a Genetic Algorithm (GA), but I was wrong. Let me explain my strategy:

First of all, my strategy was based on game simulations, so I built a game model, where I could simulate games very fast. I think all top players did this.

When I finished my model, then came the questions: how to simulate games, how to generate random steps, which heuristic should I use? At first I tried GA, where gens were 1-1 steps (1 action - 1 turn). I had got too many variations, so I realized I had to make more heuristics to my algorithm.

I noticed that when I started shooting an enemy, I didn't want to start shooting another one in parallel. I changed my gen from one step to the following: (EnemyId, MaxDistance). So when there were 5 enemies on the map, I had 5 (EnemyId, MaxDistance) gens. A gen determined the maximum distance needed before I started shooting the enemy - when I was further than the max distance I moved closer, and when I was in the distance I started shooting.

I tried to crossover and mutate my gens, but it was not efficient enough, so I dropped my GA. I started to calculate the next enemy to target from the current state: the nearer an opponent is, the more chances it has to be picked. With this technique I think I had about 40-41k points.

There were still too many enemies to be picked, so I added a filter: consider only the opponents that were the closest to their datapoint. If there was a datapoint with 5 enemies, then I chose only the closest. My score was then around 41-42k.

My third idea came from the following observation: when I moved towards an enemy, there could be too many enemies, so I had to dodge. Then the idea was to one-shot enemies if I could. 42-43k with this.

My last modification was simple: instead of always killing the enemies on my route, I sometimes tried to target a random one. With this I reached 44.3k points.

Overall it was a great contest, I didn't sleep too much for 3 weeks (with hypersonic) :)
I'm looking forward to the next contest!

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.
Unfortunately this game won't be released in the bot programming section of the platform, sorry.

How to master Hypersonic: the best strategies

5          
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:


Sandbox


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?

2          

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 Livecoding.tv 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

1          
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

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

Description:

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

13          
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 stanza.io, 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!