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.com/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.
Thanks for interesting post:) It is nice to see that intuitive and simple approach is good enough to win a contest, in case it is implemented carefully.
For me it was first such onsite contest, so i had very little experience about solving such tasks and proper strategy at all:) And this contest seems to be a great experience:)
Maybe some other guys will also describe their approaches, strategies and so on? It will be very interesting for me to read about it.
I was working on ICE problem, it is funny to work on problem with penguins while representing team LNU Penguins:)
we saw that CTF had a "x2" multiplier — yeah, and for some reason we saw it only somewhere in the middle of contest:) And it was the point when i got the feeling "seems that we screwed up".
Thanks for interesting post:) It is nice to see that intuitive and simple approach is good enough to win a contest, in case it is implemented carefully.
That's the usual case :)
we saw that CTF had a "x2" multiplier — yeah, and for some reason we saw it only somewhere in the middle of contest:) And it was the point when i got the feeling "seems that we screwed up".
There was a public announcement at the start, that some problems might have a different weight.
We have a bit another logic: sent almost all our monsters defend our flag, and often bring collected flags to base.
By the way, we took 2nd place in CTF :) As Renat sad we tried to return flags more often (move flags — higher probability to chose the base as destination). We used ascii to visualise maps. Some our tricks: - Look at the moving direction when are not in danger - Shoot when we won't die in the next turn - Try to avoid stepping in some monster traps like a pass between enemy monsters - Take "Shotgun", "Pacifist" and "Deal" bonuses, avoid "Mine" and the one that disables flag-points - We tried to count scores for other players to look for their strategies and then we start sending some monsters to assassinate nearby top players I think our biggest mistake was the we pick useless flags, that won't give us points and that we didn't use monster's sensor info to recover invisible part of the map near us it order to kill better and survive longer
sent almost all our monsters defend our flag, and often bring collected flags to base
Defending the flag is questionable, since it reduces your score gained from killing snipers. I'm not saying that it was bad, but it's one of those things, where you can't really say that it definitely improved the score.
By the way, we took 2nd place in CTF :)
I remember that there was one case where I had nearly 8K in CTF2, but you still won :) It seemed that our solutions are very close (especially for CTF1).
We used ascii to visualise maps.
It works for some contests, but here having a full-blown graphic visualization was very useful. I have drawn the targets for monsters and snipers, and I could also draw the direction for the snipers. Plus, the ability to create a mouse interface.
Look at the moving direction when are not in danger
That was probably one of the more important ones. I saw that many people used only basic directions (up/down/left/right), but using correct angle was far superior.
Shoot when we won't die in the next turn — Try to avoid stepping in some monster traps like a pass between enemy monsters
I believe all of those stuff could be summed up as: prefer moves were you won't die on the next turn. In most cases it was better to pass through some enemy and run, instead of waiting for several turns in order to shoot him. Another common mistake was to not stand still when surrounded from the corners.
If you had situation like this:
You will die with 50% probability if you move. But when you stand still, you will always pass the enemy.
Take "Shotgun", "Pacifist" and "Deal" bonuses, avoid "Mine" and the one that disables flag-points
I didn't use bonuses at all, although the Pacifist was really powerful. The main problem I had, is that I wasn't 100% certain, what are they doing (except for the "Deal" and "Mine"). There were very few cases where I explicitly ordered the sniper to go for the bonus.
We tried to count scores for other players to look for their strategies and then we start sending some monsters to assassinate nearby top players
That explains a lot ;) I only used the distance for choosing the targets for the monsters.
I think our biggest mistake was the we pick useless flags
Same for me.
use monster's sensor info to recover invisible part of the map near us it order to kill better and survive longer
I'm not sure if it would be possible to use this information for those things you mentioned. In theory, yes. But extremely hard to make it work, and very little to gain. But using it for estimating the density of enemy monsters would work great.
Can anybody describe how were they adding visualisation for their solutions? I was writing using C++ and I had two main ideas.
The first one was to create DLL from my solution with some helper functions (such as makeTurn() and getState()) so I can call them from my C# code (Or Java or something else).
The second one was the one, I used. I just saved my game state to a txt file at every turn. Then my visualisator tried to read that file at every second and update its view accordingly to what it had seen in that file.
we used the second approach
http://pastebin.com/qNPEHmDP That's how our gui looks like :)
Screenshot here I made almost the same and thew wrote it on the canvas. Black — wall, brown — base, yellow — sniper, green — monster, blue — flag.
If any cell has an outline (2 pix wide, magenta color) — that's my cell.
It seems you have not made the file public. I can't access it :p
Fixed.
The visualization is done inside the solution. We use CImg.h library (which may be seen in the code, as it's included at the top).
Hmm. Nice. I'd like to play with that. ) Thanks.
You're really awesome. I've been to your "lectures" (I won't call them lectures, since they are way funnier and interesting than typical boring lectures) and I still can't comprehend how you manage to beat in almost every marathon you participate in.
For me marathons are extremely different, and require absolutely different approaches sometimes, so I can't wrap my head around how you manage to get the right observations each time! Even though I enjoy them, I'm rarely in the top spots. Congratulations to you and your team for Marathon24, you're awesome :P
Thanks for the kind words! :)
so I can't wrap my head around how you manage to get the right observations each time!
Not each time :) Still, the reality is that it comes with experience. And, I just happen to be participating in those contests almost longer than anyone else :) The problem is that due to the much lower number of the competitions, it's harder to find motivation, since this means that most of your time spent is going to be outside of the contest (experimenting, looking at the solutions, etc.).