Psyho's blog

By Psyho, 3 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

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

»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Could you please tell, how do you debug new features with minimized points loss? I am always struggling with the problem that if I restart my solution, I'm losing all information about the map, units etc.

Also, it is very interesting, how did you implement manual control?

Thanks for the interesting story!

p.s. Cool mirrored tag :)

»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Could you please tell, how do you debug new features with minimized points loss? I am always struggling with the problem that if I restart my solution, I'm losing all information about the map, units etc.

First of all, it's a good idea to save your game state to file every turn. Then, when you restart the game, you just load that information. In general, I try to make AI as stateless as possible (fewer bugs, easier to maintain and less pain with restarts). In case of Cauldron, the only things that I lost, were the options (fortifications, etc.), game map (in case of frequent restarts) and reloading status for cannons (which wasn't really important anyway). I could have fixed it within 10 minutes, but it wasn't that important as I didn't restart my programs too often.

Apart from that, you usually should have some backed up version that works fine. So, if you introduce new bug just run the old executable while you're searching for the bug. Alternatively, you could create huge system that could act like a virtual server, which would allow you to essentially replay old games. We have considering something like this, but overall the best dealing with potential bugs is... not creating them in a first place :) That's why in 24h contests, I'm usually going at much slower pace when compared with MMs. Apart from that one big and idiotic bug where I wasted huge amount of time (because I assumed there's something messed up in communication routines and searched for the bug everywhere except the place where it actually was), I don't think I spent more than 10-15 minutes debugging.

Also, it is very interesting, how did you implement manual control?

I'm using CImg.h library. I added a bunch of hot-keys on my keyboard + I was using mouse for choosing cells (in case command required a cell). Visualization run in a separate thread (that's why you see gameUpdate mutex on my whole logic), so I could issue several commands each turn and have an immediate response from the interface.

»
3 years ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

Very nice writeup. Actually I was at the PIZZA contest recently (28 March), and it was pretty much analogous to M24 or D24, just on a smaller scale — it took about 8-10 hours, if I remember correctly. There were only two tasks (one similar to Pokemon battles, and the other was like a Bomberman game with gathering resources like in your TCO Finals and of course killing people), so I took the Bomberman, while the remaining two members of the team concentrated on the Pokemons. A week before the competition, I encountered your writeup of CTF on M24, as I was searching for strategies for similar contests. I found it very instructive, and decided to preimplement basic skeleton for visualization beforehands (also in CImg.h — thanks! That's excellent quick prototyping pick!). This was very beneficial, as I was having instant feedback, decreasing time to implement core features. Especially in the very beginning — I was probably the first one to implement a basic gathering bot that does not kill itself within seconds. In the end, my solution for Bomberman was the second best (the winners were steering only manually, and they started doing that in about half of the contest, but they still won — the final rounds were much more valuable in points). Unfortunately we had a pretty bad solution for Pokemons, so we finally took third place overall.

Probably the main error I did was not implementing any manual controls in my solution — it was pretty hard to do anything more complex than simple strategies without sacrificing too much time and debugging. Also, after a few hours I was completely out of ideas, so I was pretty mch staring at the screen, looking at other people's movements, trying to find out their strategies. Nothing was quite good however, so I could equally well just play the game on my own.

I hope we will meet some day at a competition of some kind — I'd love to exchange a few words with you :)

PS: do you know more contests like that? I can't find too many of them :/

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey,

    AFAIK there are very few such contests. And actually I don't know of any other write-ups other than mine (although TBH there's a big chance that I just didn't search enough).

    Unfortunately I don't know of any such contests other than those I wrote about in my blog post (M24, D24 & CH24). It takes great amount of time to design & organize such contest, so I don't think we will see too many of them in the future. Especially since they tend to be less popular since they usually have a steeper learning curve.

    Even though I'm doing competitive programming for way too long, I don't plan to retire from such contests anytime soon :) "Just" attend one of those 24h events :)

    On a loosely related topic. If you actually like doing AI / writing interfaces to such games, you could try experiment with game design / development. I'd say that having good game designing skills helps a lot in those contests (finding correct strategy, designing visualization & interface). The easiest way to try it, is doing one of the game jams / hackathons. There are offline / onsite, single / team events all over the world. There is a popular one going right now — http://ludumdare.com/compo/. It's a great way of trying something new.

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Tell us more about visualizer. That is, how to make a quick but good visualizer?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Sorry for the late reply.

    There's no simple answer to your question. Imagine answering "How to be good in competitive programming?". It's hard to go between saying "Just practice more" and giving 10+ page elaborate answer.

    Still, I'll try to give you a few hints:

    • The first and foremost, you have to be a better coder. This means doing stuff faster. Writing good visualizer fast, means that you have to be able to produce a lot of code in a short amount of time. Code, that is mostly very repetitive in nature.
    • Try to write a visualizer for some old problem without having a time pressure. Learn your library, etc. For example take one of the past Marathons (from TC) and write your own visualizer without looking at the official one. 24h contests are not the best place for learning your tools.
    • The popular advice in competitive programming is "think before coding". In contests where you have to experiment, this is pretty much bullshit (although TBH it still might work for some in certain situations). In most cases, it's better to write a simple & fast solution and get some feedback out of it, than designing a perfect solution right from the start. The less experienced you are the more important is to follow this advice. This applies to visualization stuff, but also to pretty much all tasks where there's no definitive solution.
    • Ability to design good manual interfaces correlates with good game designing skills. So, in order to get better just play more games and try to understand why each element of the interface works. Of course avoid mobile games while doing so :)

    As for more technical side of things, this is how I usually implement my vis part:

    In main() I spawn a separate thread that does runs a visualization, which looks like this:

    vis() {
      initVisStuff()
      while (true) {
        sleep(~50ms)
        Command[] cmdList = getListOfAllCommands()
        foreach (Command cmd : cmdList) processCommand(cmd)
        if (!needUpdate) continue
        gameMutex.lock()
        visualizeStuff()
        needUpdate = false
        gameMutex.unlock()
      }
    }
    

    while my game loop, looks like this:

    while (true) {
      gameMutex.lock()
      performGameLogic()
      needUpdate = true
      gameMutex.unlock()
      waitForNextTurn()
    }
    

    This is not perfect and works only for games that have turns that are 1+ second long. Generally speaking, thread safety is not a big concern. In most cases, the only thing you want avoid is modifying your thread-unsafe data structures in your logic loop, while you're trying to visualize it. Which should never really happen if you're using a similar system to mine, unless you modify some crucial data in your processCommand() function.