[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