May 15, 2017 Marathon Round 2: Pick Your Battles

Marathon Round 2 has started this past week. It happens to be the fifth contest I’ve written in the past 6 weeks, and I finally have some time to spend on writing random stuff for the blog. Yay for me!
As a blogger I have to say that Round 1 problem GraphDrawing was not particularly interesting to write about. It didn’t look like it had an exciting background story (and it didn’t have one). Nor did it have a captivating visualization.
In my defense as a writer, I have to point out that GraphDrawing was a beautiful geometry problem with full information, which had a short and clear statement and could be approached using several standard techniques. You don’t really need a background story or breathtaking graphics to enjoy this kind of problems.
Now, the Round 2 problem AbstractWars is another story altogether. For the online rounds of Topcoder Open we aim to select three problems which differ from each other as much as possible. (And yes, I’m still traumatized by the traveling salesman fiasco of TCO16, when both second and third rounds featured variations of this classic task). That ruled out full information problems, and problems which could be solved using standard methods. This sounded as an interactive game-based task, and so I set to playing games… er, doing research.
After some consideration we picked a variation of a classic game, inspired by this game. The basic idea is simple: you compete against one or several AIs for control over the given military bases. Each base has troops assigned to it, and the only action you can do is send troops from a base you control to another base – either as reinforcement or as a raid. If your troops overpower the enemy’s units at the base, you win control over the base!
As usual, the devil is in the details. The seemingly simple idea requires a huge statement – and that’s after I decided to drop the extra complications of having troops navigate a maze of passages between the bases and fight each other in process! However, pretty much everything in the simulation behaves rather intuitively, and playing with the visualizer and sample solutions provided should make things quite clear.

I encourage you to try participating in the match – the match runs through May 24, 2017 so there is more than half of the time left, not to mention the two Data Science challenges associated with it (the first one is up).
Meanwhile, I need to start plotting for Round 3…