When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Psyho's blog

By Psyho, history, 7 years ago, In English

As you may or may not be aware, TCO starts in a few days.

Last year, there was a twitch livestream available throughout the most of the event. They interviewed some of the finalists, did the live commentary for some of the categories (at least for Algorithms and Marathons), conducted Q&A sessions with admins, etc. Overall, I think they did a surprisingly good job of covering the event.

This year, there are going to do the livestream again, so I thought I'll share it in case no one else does.

Link (with schedule): https://www.twitch.tv/topcoder_official

Full text and comments »

  • Vote: I like it
  • +55
  • Vote: I do not like it

By Psyho, history, 8 years ago, In English

Some of you may read my previous post. It's official now, so I can safely say that this will happen.

In short:

  • As in title, I will be doing a 24h stream during the Marathon24. Sleeping not allowed.
  • 28/11 Saturday 9:15 AM GMT+1 to 29/11 Sunday 10:15 AM GMT+1 — I'm starting 1 hour before the contest, that's why it's 25 hours.
  • I will be screencasting throughout the whole time + I will explain what and why I'm doing. The emphasis is on educational aspect. This means, that probably I won't perform too good, but at least you'll know everything that goes through my head.
  • My code should be available online (almost sure) + I'll maintain current TODO/schedule lists (100% sure). I'm also usually quickly writing a rich visualizer. You should be able to easily hop in at any moment and understand what's currently happening in 5-10 minutes at most.
  • If you don't know/don't care about Marathon24, don't worry. This should be interesting even for people who only do "classic" contests. At the same time, it's unique occasion to experience what it feels like to participate in 24h contest. Or experience, me experiencing the 24h event. Or... um... whatever :)
  • You will be able to ask questions during the stream. Either via twitch chat or twitter (links below).

Links:

  • Twitch Stream — streaming will happen here
  • FB event — save the event date, invite people, etc.
  • Twitter — you can tweet me if you have any questions during the stream (otherwise use twitch chat)
  • Boring Interview — honestly, it's not that interesting

Other:

  • I might do a testing stream on Thursday. That depends on my available time. If I'm going to do that, I'll just solve some random old MM from Topcoder (or you can suggest me one), that I never touched before. I guess this way, people would finally have their SA tutorial :)
  • If you would like to spread the news it would be awesome! I'm doing insane preparations for this, so I really hope that as many people will show up as possible. Right now, I stopped working on designing room escapes just to prepare for this live stream :) Anything would help. Upvoting, sharing on social media, telling your mom :)
  • I thought about doing 10 push-ups every time my code doesn't compile, but I might collapse after 4-6 hours :)

If you have any questions or suggestions, let me know.

Full text and comments »

  • Vote: I like it
  • +56
  • Vote: I do not like it

By Psyho, history, 9 years ago, In English

Updated on 07/12 for the last time

  • Postmortem -- explains a lot of stuff and it might help you decide if there's any point in watching this
  • Twitch stream -- original livestream
  • YT mirror -- because for some reason a lot of people wanted it

If you have any feedback (bad or good, doesn't matter as long as it's constructive), I'll be more than happy to hear it. Especially since I might do more of these (just not that long).

Updated on 27/11, because it got into "recent actions"

The stream will happen 28/11 Saturday 9:15 AM GMT+1 to 29/11 Sunday 10:15 AM GMT+1

The address for the stream is http://www.twitch.tv/fakepsyho — yes, I mailed with the support and coding on twitch is now perfectly fine. Also, the stream contains all of the essential information, so I'm not duplicating it here.

Also, I'm using this mic, so don't worry about sound quality ;)

Edits:

0) For people who are confused about who took my handle. This guy.

1) I thought I should make it a little bit more clear: I really want to hear what you would like to see. There are no stupid ideas. Want me to eat 0.5kg burger? Want me to play IWBTG? Want me to do push-ups (pls no)? It's entirely up to you what I will talk about. I'm giving free upvotes for every suggestion ;) My goal is to make it interesting for everyone (i.e. across all of the skill levels), so don't be afraid to suggest something that you may feel is very basic.

Short version:

  • I will participate unofficially in M24, I don't want to break my streak of winning three 24h contests in a row ;)

  • I will do the livestream with full commentary (and most probably with full code although it may not happen due to security risks)

  • Since this is for you (across all the skill levels), I need to know what you'd like to see!

Longer version:

Since twitch was born, I thought about doing an educational livestream with solving some problems. The two biggest obstacles are: I wanted to do the livestream during the onsite contest (otherwise there's no thrill, and the conditions are artificial, so even educational values suffers). Unfortunately, this means that the contest would require the participants to have no internet connection. The other thing is that, doing the contest without commentary (and without interacting with chat) is quite boring. If I had participated, this would really hurt my performance. So, this really only works when I'm not 100% focused on winning. Unofficial participation in Marathon24 is a rare occasion to fulfill both of those requirements.

Current status:

  • If you have any ideas for the setup let me know. I will stream the editor + any possible visualization (pretty much everything that happens on my main screen). I may stream the livecam if people want it for some reason. I'm guessing I will also use some virtual whiteboard for drawing/explaining things. I may set up secondary stream exclusively for visualization (so that people will know how the game looks even if I'm not looking at the visualization). I may set up dropbox so that all of my local files will be synchronized. The last thing may not happen due to security risk (some participating team could download it and it would be hard to detect).

  • The stream will be full 24 hours. Probably even longer since I'll start a little earlier. I may also do some pre-finals testing stream, just to be sure to not mess up things during the finals.

  • I'm considering using Twitch. I have some experience with using OBS since I started doing some lame speedrunning recently.

  • Small disclaimer. I should also add that this is not 100% confirmed yet, but folks behind Marathon24 loved the idea (or they are convincing liars).

The things I can do:

  • I want to start at the same time as other competitors will do. The first 15-30 minutes will be reserved time for me (and hopefully viewers too) to read the problem statement.

  • For at least first few hours I will focus on the problem in the same way I would in the contest. I will definitely go way slower since I will be explaining all of the stuff I'm doing. I guess I will shift my priorities dynamically, depending on how I perform.

  • I could try to do live interviews with some participants. That may be hard to do technically, but it's definitely a possibility. The problem is, people don't really like being hassled during the 24h contests.

  • I'm not tied to talking only about M24. For example I could take a 2h break to talk about TC's marathons or stuff like that. It's entirely up to what you want to see.

  • You will be able to ask me questions via chat (less reliable) or twitter (more reliable). I'll try to answer them, unless I will be already braindead ;)

So, to sum things up. Livestream. I need your ideas. Also, if you don't want to miss the news follow me on twitter. And don't worry. I don't spam there too much, since I haven't figured what's the point of it ;)

Full text and comments »

  • Vote: I like it
  • +332
  • Vote: I do not like it

By Psyho, history, 9 years ago, In English

Last week there was a BubbleCup contest, where I was invited as a guest and gave a presentation. AFAIK the presentation was recorded, but I have no idea if it's going to be released (or when). The presentation itself, is probably the worst presentation I ever gave. I talked mostly about how confusing it's going to be, but I was the one confused there :)

Anyway, here's the link to the slides. I still think it might be useful for some people, since it touches something that is very rarely talked about. The presentation itself was made to counterbalance all of the simple answers to the old question of "How to get better in competitive programming?".

My main points (that I don't think were made clear enough):

  • It's better to train to be an all-rounder than to have a narrow specialization. Especially in the long-term. People very often change the area of interest. By focusing on being all-rounder, you don't have to start from beginning each time.

  • It's better to focus on skills that are harder to come by (writing bug-free code, problem solving), than focusing on some specific parts of knowledge (learning algorithms).

  • Since CP provides great feedback, it's an efficient way of developing general personal skills that have wide application (concentration, self-coaching, short & long-term memory, etc). Thus, it's usually better to not have a coach. You may feel lost without a coach, but that's how you'll learn to do your own research effectively.

Feel free to ask any questions or state how much you disagree with what I said :)

Full text and comments »

  • Vote: I like it
  • +236
  • Vote: I do not like it

By Psyho, history, 9 years ago, In English

Link to the write-up: http://psyho.gg/2015-challenge24-finals/

Sorry for making another blog on the same subject, but I already was a halfway through when ArtDitel posted his own. And, considering the amount of work I had put into it, I think it deserves its own post.

I went the hard way, and the write-up focuses on solving the actual problems, instead of bashing the organizers :)

Full text and comments »

  • Vote: I like it
  • +134
  • Vote: I do not like it

By Psyho, 9 years ago, In English

[Note: Somehow it turned out to be very lengthy]

Not sure if you guys are interested in seeing this, but I figured out I need a brake from coding. And well, I wrote about the M24, so I guess I should write about D24 as well :)

The Deadline24 finals were hosted last week. Our team won (by a small margin, but still) and I managed to get the highest score on my problem (The Power of Cauldron, or something like that). Unfortunately, the problems are not available on the website, so I cannot link to them.

Overall our initial strategy was to split the problems by the amounts of pages — I take the longest one, then Marek Cygan, and the shortest one goes to Mojito1. The length of the statement usually correlates with the amount of code you have to write in order to get a decent solution. Plus, we quickly saw that Cauldron will requires a lot of visualization work, which kind of is my specialization in those 24h contests, apart from specializing in dozens of other areas ;)

Enough of the lengthy intro, let's get into the details of the problem. Usually my goal in those contests is to quickly write a working solution, so that (a) I can verify I correctly understand the problem (b) I can quickly get some points while very few people are playing.

  • First read of the problems. I don't care about the visibility, land types and attacking since it's harder to implement. The goal is to understand the scoring and the general goal of the game. In general, it looked very similar to the CTF problem from M24, but much more complex (in a good way).
  • Implement some basic communication with the server and add random walking with units. By that time, I understood that the goal was to acquire and hold strategic points (SPs), so by random walking I might accidentally step on one and get some points. I looked at the scoreboard in order to verify that it actually works (my scores were increasing).
  • Add obligatory game state parsing. Quite boring, but it has to be done. Since our TCP/IP wrapper creates logs are whole communication, I'm looking at those logs in order to have some idea about the map generation and various parameters that are used.
  • After seeing the logs I'm getting some better understanding of the problem and I'm able to prioritize all of the things that needs to be done. Honestly, I think this is where many teams are failing — a lots of people just implement anything that comes to their minds, instead of spending more time thinking and getting better feel about the game.
  • Start doing stuff (in this order): Greedily move each unit towards closest SP (without BFS since all of the maps I saw were pretty open); Swap greedy movements for evaluation function so that my army spreads over all SPs (bad strategy in general, but great when very few people are playing); Figure out that cannons are easiest to implement (visibility issue looked like an absolute horror to implement) and should also be the most versatile unit; Add building cannons as long as the number of units is below the maximum amount of commands; Attack random enemy if it's within range (for tanks and armored set the range to 1, so they never hit my units); If unit is on SP, hold position;
  • At this point I believe I was having around 50-60 points lead and quite often I was able to conquer whole map (had all SPs). This was a good moment to start writing visualizer (I haven't touched it earlier).
  • I spent a lot of time, trying to squeeze the map (which was up to 200x200) onto my 1440x900 screen. The biggest problem was visualizing different types of units, while still seeing the owner (my or enemy), land type, and potential strategy point that was on this tile.
  • After having visualizer, I finally got some proper output of what is actually happening in my games. The funny thing was that the first thing that I saw, was the SP put in the middle of the water and I actually triple checked that I'm correctly interpreting the types of tiles. But it turned out, that problem setters just put some easter eggs in the problem (later I heard that the probability of having this was around 1/60).
  • Begin to optimize small things. Figure out that since I'm winning by a huge margin I should minimize the variance in each of the games. Stopping HQ in the original tile was much safer tactic. Since maps became much more active (more players playing), I changed my evaluation function so that I'm focusing on less number of SPs to conquer. In general, as soon as I got 1 SP, I was safe, and usually I was able to most of the map (except those small "mini-tournaments" kinds of maps.
  • Ignore SPs that are not reachable (happens only in those mini-tournaments). Then, Spent nearly 2 hours on a one-character bug that was introduced by doing this :) I believe this was around 6-8 hours into the contest. I wasn't particularly rushing, and by that time I already spent a lots of time looking at the logs and the visualizer.
  • My goal was to fully understand the mechanics of the game. I tried to eliminate all error messages that I'm getting and read the problem again, to see if I missed anything. One thing that I discovered is that attacks are immediate, so in general the faster you get to the point where you can send attack commands, the more chances you get to destroy your opponent. This is really important since in open terrain, you'll see your opponent at the same time as he sees you. On the other hand, cannons have much longer range than visibility range, so all of the units are going to be destroyed anyway (by units behind the one that spotted enemy). I haven't figured any reasonable way of dealing with this other than moving attacking commands right after the commands that retrieve the current state of the game.
  • Lots of small tweaks. Add manual command to change the maximum number of produced units (later I used it in order to stop producing units at the end of round); stop moving units when near opponents; don't issue redundant commands (shoot while reloading, move while moving); don't attack opponent HQ; try to capture HQ and 1 tile away; retrieve map only when it's not available; few more that I don't remember;
  • At this point my basic strategy was pretty much complete. I was still missing few important details — I was still attacking random targets, my tanks & armored were restricted to melee combat, I didn't do any BFS when choosing path (I ignored terrain when computing distance). But I was thinking that adding them won't change too much, so I tried to better understand if there are any advanced strategies and if there are any, if anything is possible to implement. I also saw that fog of war plays a huge role. And most importantly, cannon placed on hill that has full visibility is pretty much invincible.
  • From this point, I pretty much stopped developing AI. The only things I added was more manual control over my units. The reasoning was as follows: Pretty much all of the strategies that I came up with were nearly impossible to automatize and at the same time pretty simple for human to perform. Also, this was the point were a lot of teams had some working solution. Usually the optimal strategy in such games, changes depending on what your opponents are doing. Having manual control allows me to dynamically change the strategy without additional coding/recompiling my program. This has a trade-off though: while I'm controlling, I'm unable to add new features and thus slowing down my development. Also, not being able to rest throughout the last 2-4 hours of the contest is a major pain :)
  • The first and most important thing was being able to "fortify" your cannons — i.e. place them at some strategic points. I usually used this on hills so that they could defend my SPs.
  • Other things that I added: Setting the target destination for HQ, setting tile to "ignore" so that it's not used for moving (I used it sometimes to unstuck my units, or to make them ignore SPs that were heavily defended); changing production between tanks, tanks+cannons, cannons (tanks were great for meat shields even though they still only had 1 range); moving scouts (armored) in the same fashion as cannons; adding lots of debug output (displayed directly on my visualization, so that I don't have to look at the console anymore); added "bombarding" (shooting with cannons at some specific tiles that are outside of range);
  • When organizers introduced the limit of 5 cannons I finally added visibility to the units, so that tanks could finally shoot. Even though I feel pretty confident with 2D geometry (gamedev, blah), Marek helped me with that, since he felt that he hit glass ceiling with his solution.
  • And that's pretty much all of the things that I wrote :)

Some interesting strategies that I used (all of them were done manually):

  • Unless you were able to conquer new SP, it was pointless to have an open fight with opponent (since this usually resulted in even losses). If someone sent big stream of forces towards me, I tried to fortify my position (on hills) and treat as an additional source of income :)
  • I sometimes moved my HQ forward in order quickly introduce new reinforcements.
  • I tried to stop unit production (setting the max number of units to zero) near the end of round.
  • In those maps where you immediately have to fight for 1 SP, I often waited with my cannons and tried to destroy as many enemies as I could, without having too many losses (so that my opponents are running out of resources). After having 1 SP I usually resorted to my default strategy. I usually tried to put my 5 cannons in places where they are able to kill most units (somewhere on hills where lots of enemy units are frequently traveling). I rarely used them for attacking. Most often other people used all of their forces to attack and then they had a naked HQ, so the strategy was to "wait them out" and then attack only with tanks.
  • In the beginning I try to spread my scouts on the map, sometimes acquiring SP on a different side of map, where there were no active players.
  • In those moments when all hope was lost (like single HQ with 1 or 2 cannons), I used an interesting strategy. I manually moved my HQ forward to use it as a scout. Since it's invincible, no one could destroy it, while I was shooting at the enemies and I was gradually getting enough resource to build big enough army to fight for an SP. I guess I did like 6-8 times in total. The biggest problem was that it was very time consuming and I couldn't do anything else (so I was 100% focused on one server). I had to run away with HQ as soon as someone tried to capture it, and hope that the unit is going to get destroyed earlier.
  • There was a very strange map somewhere near the end of the contest. There was a single SP in the middle, but you had only HQ at the start. This happened on the 3rd server. When I looked at that map I thought that I actually already lost all of the units and I lost (there's not much you can do with single HQ, except for capturing other HQs). Out of despair, I ordered to move my HQ to that SP and I was actually shocked because no one was defending it, which essentially meant that I conquered whole map. This map alone gave me around 10-15 points on 3rd server :)

Oh, and here's my source code (again visualization is stripped): http://pastebin.com/MhPx4hsw

Full text and comments »

  • Vote: I like it
  • +163
  • Vote: I do not like it

By Psyho, 9 years ago, In English

After several months of inactivity I finally added something new to my blog: http://psyho.gg/overview-of-programming-contests/

Long time ago, I had a goal to write a small series of articles around competitive programming, so that most of the commonly asked questions (what's the point it, what people do there, how to practice, can I earn money on those, what sites should I use, etc.) could be simply answered by linking to the appropriate article. Unfortunately, after switching to being a full-time game designer I run out of time to do so. So I won't promise that I'll ever finish the series, but at least I'll try :)

If you think that I have missed something very important, let me know (either here, or on my blog). Just keep in mind, that the article is already long and I don't want to write about some niche contests.

Also a small remainder. You have less than one month to gather a team for Deadline24 & Challenge24 contests. Competing in Challenge24 qualifier is worth it, even if you don't want to attend the onsite finals.

Full text and comments »

  • Vote: I like it
  • +177
  • Vote: I do not like it

By Psyho, 9 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +85
  • Vote: I do not like it