Hey,

I_love_Tanya_Romanova asked me few questions about the Marathon24 contest that finished during the last weekend, and since I thought that my answer could be slightly useful for more people I decided to do a blog post here, which I haven't done before, and I still find it strange that there's no forum :)

For those who don't know who I am — I'm Psyho and, apparently, some guy took my handle ;)

My work throughout the contest was something like this:

• we saw that CTF had a "x2" multiplier, so this was a clear choice for the task for me; especially since it was longer, and the goal was that I'll solve a task that will have a complex visualization.
• short solution for quick points: random walk for monsters (easiest to write, and should get much more points than random shooting)
• move monsters towards enemy snipers
• add random walk for sniper for monster respawn (at this point, I believe I won most of the games I believe)
• add visualization (where I discovered that I incorrectly parsed the given data, since some units were walking on walls).
• add BFS for monsters, so that they can avoid obstacles
• added some simple monster shooting for bonus points, but it turned out to be worthless
• then I slowly started losing out to other people, so I took a longer break to think about the final strategy
• I scrapped all of my logic (it was still under 100 lines), and I implemented a bit more complex sniper logic (monster logic was left intact for the whole contest) — basically the idea was to steal the closest flag, and move towards the cell that maximized some simple scoring function (avoiding getting dead was a priority, getting closer to flag was secondary). After stealing all 5 flags return them to base and repeat (this didn't happen too often, I guess a bit less than once on average, but sometimes it happened 3-4 times with a bit of luck).
• add more stuff to visualizer which was complete at that time
• lastly I was in the loop: look at visualizer, find an obvious mistake, correct it
• add a very simple manual interface, where I could click on a tile, and it changed the current target cell. Useful for forcing sniper to return flags earlier, adding a way-point or changing a target flag. Although to be honest, I have used it very sparingly.

In the end, I spent probably around 3h on coding the logic, which is an usually short time for such contest. The reason is that I was still horribly jetlagged after TCO and that I had no motivation when looking at the scoreboard :) I knew that my solution suddenly won't stop losing, since this strategy was rather independent of what other players are doing.

Few very good ideas that I haven't implemented:

• If you're surrounded by your monsters you're invincible without enemy snipers. If you hide in the corner with 5 flags, and surround yourself with monsters (leaving 2 empty cells, so you can move back and forth to spawn new monsters). The only catch is that you have to actually carefully select the flags of active players (which I forgot to do). This was my #1 on TODO list. If you stole the flags from "best" players, and no one else did that, that was by far a winning strategy by a rather wide margin (at least for CTF2).
• Monsters should ideally approach enemies from the back — even avoiding line of sight as tie-breaker for moving, should improve things greatly.
• You could move around with monsters as "blockers". Unfortunately, this is a very hard thing to implement and it's not clear if this would improve overall results, since you would need few monsters to help you, so there are fewer monsters left for attacking snipers.
• I didn't visualize the "sensing" of monsters which could be useful. Unfortunately, the strategy of avoiding big number of monsters, was usually defeated by a sniper that randomly spawned near you.
• I didn't calculate when near monster should spawn. This could've slightly improved my survivability.
• My code (with my libraries and visualization removed, since it's a work of our whole team and sharing it, would be inappropriate).

P.S. I guess you are not very often guest at CodeForces, and not reading all the blogs, so you might have missed this message — http://codeforces.me/blog/entry/14753#comment-197383 :)

I hope I'll do it someday. I had bigger plans for the whole blog (I wanted to create a series of posts for newcomers for competitive programming and also some tips&tricks for practicing), but unfortunately life and laziness got into my way. I can't promise, but it's on my several-pages long TODO list :)

Feel free to ask questions.