Edit April 9, 2019: Bob has proven again that the lazy way works. Read his new article: Lazy Coders Strike Back
CodinGame held the “Fantastic Beasts” coding competition in November 2016. The game is now available to play.
Legend of the Lazy
Anyone who has discussed with me for some time on the chat must have learned the sad truth about me: I’m lazy. I’m also not very ambitious. So, during coding contests, I usually want two things:
- Get a decent rank
Not necessarily great but at least reaching the Legend league or the top 100 players. Anything above that would be a welcome surprise, but I probably won’t go out of my way for that. - Spend as little time as possible
In addition to being a professional developer, I happen to have a family life that I’d like to keep. So the amount of time I can divert to CodinGame is relatively limited.
The latter is the reason why I’m not trying genetic algorithms, Monte Carlo, or anything like that, even if I do have sufficient background and experience to do so. I actually did write a small genetic algorithm back in my second year of engineering school 20 years ago…
So, what’s left for me? Heuristics, simple ideas, more or less crude approximations. They will not yield perfect results, they may even fail quite horribly at times, but the point is that they will work well enough for what I want to achieve.
Another advantage of heuristics is that since I’m not going to simulate the entire game engine I’m not concerned about performance issues, so I can use all of my language’s high-level helpers (containers, sorting and search algorithms, etc…) which might otherwise be too inefficient for a fast simulation. This helps in expressing simple ideas quickly and clearly in my code.
Here are my basic keys to laziness:
- Work with very simple ideas. Avoid rare situations and focus on the most frequent ones.
- Implement only one idea at a time. Finish it before moving on to another one and always leave the current task in a finished, working state.
- Code little, but code a little bit every day of the contest in order to stay on top of things; it is a bit easier to maintain a good rank you get early on than to regain it once there are many players.
- Do as little as necessary. Start refactoring or extending the design only when it’s necessary for the current idea.
- Don’t bother with run time or memory usage. I can afford bloated data structures and inefficient design as long as it does the job quickly.
- Hang around the chat, discuss ideas with others. You may get very good advice at very little cost.
Admittedly, keys #4 and #5 have a risk of leaving you with rather ugly code. Experience will make you better at applying those while at the same time keeping your code in a reasonably maintainable state.
As an illustration, here’s an overview of how my Fantastic Bits contest went.
Saturday
First things first, I write a small data structure to keep all of the input and whatever other information I will need. According to key #5, I just put everything together in a single structure and I use only the necessary bits depending on the context, ignoring the rest – one size fits all. Likewise, I make a single, global list of objects that I can address from anywhere in the code.
Now, key #1 suggests two very simple actions: if a player has a snaffle, he should try to score and if he doesn’t, he should try to get one as quickly as possible. And that’s it. I’m not considering opponents at all, or that my players might target the same snaffle. There will be enough time to add complexity later on if the initial idea doesn’t perform well enough. So here is the pseudocode for those basic ideas.
for each player done = false if player has a snaffle throw to center of goal at max power done = true if not done find snaffle closest to player move to the snaffle’s position at max thrust
Experienced players will immediately see how inaccurate this is. However it is accurate enough to immediately beat the boss of Wood 2 league. Also note that “find snaffle closest to player” is little more than what you can find in the very first solo puzzles of CodinGame such as The Descent, definitely not high wizardry.
Wood 1 league introduces bludgers. According to key #3, I decide to just ignore them until they turn out to be a nuisance. All I add is a check in my snaffle lookup for the MOVE part to ensure that I only check snaffle entities. That is sufficient to go to Bronze. At this point, I have coded for no more than 20 minutes.
Sunday
Moving on to using spells. Lazy key #2 says to start with just one spell. Lazy key #1 makes me discard Obliviate (since I’m disregarding bludgers and other collisions), Petrificus (doesn’t fit with my current logic of score-or-chase) and Flipendo (feels like it might need some math to get right). So I go for Accio and use it to steal snaffles from the opponent.
I assume the opponent is also going to chase the snaffle nearest to him. I even decide to match opposite players so I have only one opponent to look up, instead of checking both. Of course, there is some minimal work: “snaffle closest to player” becomes a factorized function. I also add a little book-keeping stuff, such as mana and spell counters, as well as a “targeted” flag in the entity structure to ensure that each wizard handles a different snaffle.
for each player done = false if player has a snaffle throw to center of goal at max power done = true if not done and mana >= 20 and player did not accio in the past 6 turns accio snaffle closest to “matching” opponent (0<->2, 1<->3) mana -= 20 done = true if not done find snaffle closest to player move to the snaffle’s position at max thrust
This new submission goes right into top 100 of Bronze. Less than one hour of code so far.
Monday
My bot has lost a good hundred places overnight. In the morning I just tinker a bit with my current code, replacing the opponent “match” with an actual loop over the opponents and keeping the target snaffle that is closest to my player (10 minutes).
In the afternoon, I start with some quick refactoring, replacing my “find closest snaffle to player” code with an actual sorting of the entire snaffle list by distance to the player (hey, remember Horse Racing Duals?). With that, I can now implement a basic use of Flipendo: starting from the closest snaffle, I check whether shooting it might end up in the goal, and if it’s not possible, then I check the next one, and so on.
Key #1: This is done with a very basic alignment check. Is the snaffle between me and the goal? Does the line between me and the snaffle go between the goal posts? The line computation is junior high school math, or can be googled easily. Still nothing complex.
for each player done = false [ throw code ] if not done and mana >= 20 and player did not flipendo in the past 3 turns for each snaffle (ordered by increasing distance from player) if snaffle is not between player and goal continue compute line between player and snaffle if line intersects the goal line between the posts flipendo snaffle mana = mana – 20 done = true break [ new accio code ] [ move code ]
As for the other initial heuristics, that Flipendo code is very crude and doesn’t check for possible obstacles, or account for the radius or velocity of entities, etc. Still, it turns out to be good enough for most alignment cases, and that submission reaches around #70 before the opening of Silver.
Example of Flipendo
Key #6: That evening on the chat, Gadzy.fr mentions that carried snaffles inherit the wizard’s velocity. This velocity is added to the throw vector to calculate the next position of the snaffle, so it should be subtracted from the target when throwing to be sure the target is the center of the goal. While I don’t actually need it, this extra accuracy comes at virtually no cost so there’s no harm in trying.
throw to center of goal at max power
becomes
throw to center of goal minus snaffle velocity, at max power
In fact, that simple change boosts me right to the top 20 of Silver, for a total of less than 90 minutes of code.
Tuesday
My bot still stands at a solid #24 in the morning, much higher than I anticipated. This is definitely Gold material at the very least so my only change that day is along the same lines as the evening before: a 5-second change to account for the snaffle velocity when moving, so that the wizard will target where the snaffle will be rather than where it is:
move to the snaffle’s position at max thrust
in turn becomes:
move to the snaffle’s position plus velocity, at max thrust
This is also where instability in the ranking process starts to appear, as there is now a large buffer of similar AIs in the middle of the board. Two successive submissions of the same code may end anywhere between top 50 and below 200, so several submissions are now necessary to assess the validity of any change, or regain a rank similar to the previous one.
Wednesday
That day is usually work and family for me, so nothing much happens until the opening of Gold, by which time I’m still snugly in the top 50.
Thursday
I’m still around #70 in Gold in the morning. From experience it might not be enough for promotion to Legend. I’d like to secure at least a top 50 rank before the opening of the league.
I extend my Flipendo code to add bouncing off the top and bottom walls. This is a bit more complex, but not much. Check that the player-snaffle line intersects the top or bottom walls before reaching the left or right walls. Invert the line’s vertical component. Check whether that new line, starting from that intersection point, goes through the goal. As with my other heuristics, this doesn’t account for entity radius, but still provides nice results, although I sometimes get spectacular rebounds off the goal posts.
I also add Petrificus on snaffles that look like they’re about to score against me. Still simple and approximate: move snaffle by its current velocity and friction for 3 turns, and check the final position.
for each player done = false [ throw code ] [ flipendo code, now with rebounds ] [ accio code ] if not done and mana >= 10 for each snaffle (ordered by increasing distance from my own goal) is snaffle is about to score petrificus snaffle mana = mana – 10 break [ move code ]
Example of Petrificus
Things are definitely harder now though, and more players keep coming to Gold. Several successive submissions (and maybe a couple of lucky win streaks) are necessary before I eventually make it back into the top 100. Still, no more than two hours of code.
Friday
This is the day where I need to secure a place in top 50, but I’m now around #130. I have no time for a full overhaul or thinking up brand-new, game-changing ideas, so I try to get rid of some of the worst approximations at a reasonable cost.
One of my main concerns, confirmed by watching some replays, is that playing each wizard in turn, as I had been doing until now, means the first one always gets priority for spells or moves, even if the other one has a better opportunity.
Time for some simple refactoring: instead of outputting the commands straight away for each player in turn, I now store the command string in my entity structure and output all commands in one batch at the end of turn. This lets me invert the general structure of my algorithm, pushing the external player loop inside each action block. Instead of
for each player done = false [ throw code ] [ flipendo code ] [ accio code ] [ petrificus code ] [ move code ]
I now have
[ throw code for both players ] [ flipendo code for both players ] [ accio code for both players ] [ petrificus code for both players ] [ move code for both players ] output commands
For each of the Flipendo, Accio and Move blocks, I now check the possibilities of both players, assign a command to the best one and reiterate until both players have something to do, or no interesting action is possible.
For Flipendo for instance, I refactor the existing straight-line-or-rebound check in a separate function for getting the “best flip candidate”, and the corresponding block code now looks like this:
while mana >= 20 and at least one player has no command assigned collect best flipendo candidate for each player with no command yet and no flipendo in the past 3 turns if there are no candidates break assign flipendo command to the player closest to its target mana = mana – 20
With that, spells appear to be a bit more efficient, my players end up in each other’s path much less often and I manage to get back slightly below #100 – still not good enough. Watching some more replays where I’m losing against lower-ranking players (those are quite harmful at the start of the ranking process), I get a couple more ideas that can be fixed easily and quickly.
The first one is that my move code always assumes the snaffle will keep on moving in its current direction, but this is definitely wrong when the snaffle is being carried by an opponent. By assuming the opponent will throw the snaffle straight at my goal in such a case, and compensating my target accordingly, I should get better at intercepting opponent throws.
The second one is that most AIs are targeting the middle of the goal, so players tend to bump around the central part of the field and throw snaffles at each other. Therefore, I try to throw at slightly different locations, depending on where my player is placed vertically.
Being a bit pressed by time, I do not bother assessing those last changes separately and just submit one version with those two changes bundled together. My second submission finishes its ranking at #25, less than 4 hours away from the opening of Legend league. This was probably due to a rather lucky win streak, though, and it slowly trickles down during the afternoon. When the Legend league opens, I’m still in top 50, just above the entry point of Bossdemort.
After that I had no time for the contest over the weekend while other players kept improving their code, and I finally ranked #137, out of 156 players in Legend league, and 2,399 players overall.
As imperfect and inaccurate as it was, this rather simple and quickly written code (4 hours spread over one week, that’s only 30 minutes per day) was still able to get a reasonably good ranking, and at least get to Legend… So don’t be afraid, you can do the same next time!
As a final note, consider that this could even be the opportunity to learn one of the less common languages. You might even have a very real chance at finishing first for this language!