Coders Strike Back Post-mortem

The latest couple of months I've spent around 40 hours at weekends and in evenings trying to write a bot that is able to finish the track of Coders Strike Back faster than opponents. During this time I'd made quite a lot of mistakes before I got into the Legendary league. This is a post-mortem for that project.

I have an important disclaimer. Almost all bots that I wrote was in Python. However, I passed high leagues with the C++ bot. I don't think that there is something wrong with Python. I think there were several errors in my code that I decided not to fix. I'm a lazy-ass.

CodinGames

At first, I have to say a couple of words about the website there competitions is hosted. CodinGames is a collection of programming challenges that are presented as games. Some of them are puzzles. Sometimes you have to beat an AI. In others, you compete with bots written by other users. There are many challenges and puzzles with different difficulty and that covers different fields. They all have one thing in common. You have to guide your hero or heroes by writing a bot.

In any case, all games on this website are masked programming challenges. I think a big fraction of them you can find on websites like HackerRank in more direct form. This is the main advantage of CodinGames. It is much more interesting to spend time trying to understand why your bot is so slow than why your solution fails test 16 and gets a timeout in test 20.

I think CodinGames and HackerRank can be used for different things. HackerRank is a great interview preparation tool. It is extremely useful when you want to learn how to solve a standard algorithmic challenge that is formulated as they are usually formulated for the technical interviews. Despite not having any time limits on HackerRank, I often have a filling that someone urges me saying "You have an hour to solve it".

CodinGames is more like a laboratory. Challenges here are more about finding new ways to solve them. I have not so big experience working with this site, but my internal timer hasn't started ever. As a result, I spent much more time finding a solution that I planned. Challenges in form of games give me a feeling of freedom. On this site much easier to say yourself that you are stuck and it's time to google. On one hand, I want to solve everything myself without any help. On the other hand, this freedom cases that I try more approaches to solve a problem then I've ever done solving any HackerRank challenge.

Coders Strike Back

Coders Strike Back is a good illustration for that difference between HackerRank and CodinGames. In spite of challenges on HackerRank, there is no the right way to write a code for that challenge. During a search of an inspiration, I found that good result could be achieved using a variety of methods form some heuristics algorithms to machine learning.

In this game, your goal is to flight thought checkpoints several laps. I must to it faster than your opponent. The competition is divided into leagues. You'll pass from one league to other if your AI gets more points in races with other players' bots than league boss' AI.

There higher league the more rules are in it: boost, shield, second pot... Bosses became better and faster. To be honest it is easy to write a bot based on heuristics for leagues below golden league. On this stages, there is no sense to write anything more complex than if-based AI. The most valuable tip here is to forget about opponents and to concentrate on improving accuracy and speed. It is not so hard to do.

Golden league

The golden league is the first league with serious resistance. For a long time, I couldn't get more than a half of the points that league boss got. With my naive approach, I had a place near 2000 or so only because there were a lot of broken bots that was able to make 3 or 4 turns before timeouts.

I hadn't wanted to use complex algorithms and had planned to pass to the legendary league with a bot based on heuristics only. My mood was getting worse as my code becoming more and more complex. Then after a couple hours of intensive googling, I found an extremely interesting and simple heuristics. The goal coordinate equals to the coordinate of the next checkpoint minus tripled velocity projection.

So as I got a very compact bot that however performed very well finishing at places around 300.

laps = int(input())
cp_count = int(input())
checkpoints = []
for i in range(cp_count):
    checkpoint_x, checkpoint_y = [int(j) for j in input().split()]
    checkpoints.append((checkpoint_x, checkpoint_y))

while(1):
    fp_x, fp_y, fp_vx, fp_vy, fp_angle, fp_next_cp_id = [int(j) for j in input().split()]
    sp_x, sp_y, sp_vx, sp_vy, sp_angle, sp_next_cp_id = [int(j) for j in input().split()]

    print(
        "{} {} {}".format(
            checkpoints[fp_next_cp_id][0] - 3*fp_vx,
            checkpoints[fp_next_cp_id][1] - 3*fp_vy,
            "BOOST"
        )
    )

    print(
        "{} {} {}".format(
            checkpoints[sp_next_cp_id][0] - 3*sp_vx,
            checkpoints[sp_next_cp_id][1] - 3*sp_vy,
            "BOOST"
        )
    )

    input().split()
    input().split()

And again, adding new logic made it worse. I needed a new better more advanced approach. Then I found several articles with one interesting idea. If you can build a number of possible future trajectories for your pot, evaluating them somehow you will find the optimal solution.

• GENETIC ALGORITHMS IN CODERS STRIKE BACK GAME
• CODERS STRIKE BACK – PB4608’S AI (RANK: 3RD)
• Coders Strikes Back

In addition to that plans generation, it is rather easy to do, you need to build a model that can predict pot positions after each turn. The latest link in the list describes this model and gives detailed instruction on how to implement it on your own.

Unfortunately, straightforward Python realization of it is quite slow. My best result is 60 plans without risk of a timeout. I guess it is possible to improve it using NumPy. But I decided to take an easy way. By that time I had been quite tired of this project and I thought only how to finish it. So I returned to Google and tried to find an appropriate template.

Such template was found in 20 minutes. It was a piece of code written by Roman Ring. And after changing evaluating function a little bit I was promoted to Legendary League.

Legendary League / Conclusion

Changing only speed limit I got 40th place in the league. Because promotion to the Legendary League was the project goal, I stopped. However, having a good moving prediction model template you can get better results changing some parts, evaluation function and plan generation algorithm for example.