We might remove the ‘undefined’ language submission like we did for others.
BlitzProg - 74th
I use a Genetic algorithm for this contest. I have a population of 200, Crossing over bring a generation to 400, and mutation bring it up to 600. I select the 200 best of these 600 and start again.
The genetic system is very simple, each individual is simply the map of the game, from which I select the tile of one or the other parent to make a child when crossing over. A mutation is a copy of the original but with each possible cell having a chance to change to another arrow or just nothing. individuals are simply ranked according to the score the bots would make on them.
When arrows are created, I replace these with a blank if for whatever reason this arrow would be a very bad choice (pointing the void or another arrow on the opposite direction). which helped me making an extra 1000 points.
I also tried to remove arrows which had 6 neighboring voids (because it’s not really useful to place arrows on narrow passages) but that didn’t help much for some reason.
Lots of effort went into that challenge! It was very difficult. Which is amazing for such a simple contest. The simulator was the easiest ever to code but thinking of a good approach was not obvious 
3 Likes
Finished 6th with ~10.300 points.
Basically my solution was 8 consecutive simulated annealings for ~0.11sec each.
As for preprocessing, i generated all possible arrow placements and assigned weights to them. On the bigger maps (and on some of my handmade testcases) i took most of my highest scoring solutions and generated some statistics. The result showed that any cell having 1 or 2 neighbours is more likely to have an arrow than cells having at least 3. Also for cells having 2 adjacent neighbours are more likely to have an arrow than cells with 2 opposite neighbours. Just a few more ideas worth mentioning: no arrows inside corridors, no 2 adjacent arrows pointing at each other, etc. So i set my weights accordingly.
For SA, in each step i added or removed an arrow by 50-50% chance (no rotations or juggling with multiple arrows at once), picking the arrow based on those preset weights when adding, and completely randomly when removing. Then i simulated all robots 1 by 1 and summed up their scores.
For the simulation part, every robot kept track of its visited cells with direction info on its last run, and when executing an arrow addition/deletion step i checked if it affected the robot’s path in any way (eg when adding an UP arrow i checked that the robot didnt arrive at that cell from top, left, or right at any point of its path [whole process costs a few bitmasks]). If the arrow did not cause any direction change in the path, i used the robot’s last score.
On the bigger testcases i could reach 700k-2M+ (not so) full simulations in IDE, reaching around 10.300 score every time (with different random seeds).
Well, basically thats it, i was surprised to see how well it got me.
Congrats to the guys in top5
12 Likes
I finished 16th, never quite managing to break the 10K score on a submit.
I started off with a quick genetic algorithm implementation which got me to around 8500 by Saturday morning. I had a list of cells that could have arrows in and generated a random arrow (or nothing) for each cell, then did mutation / crossover to find the best solution.
I then tried a less random approach, doing a very narrow beam search with a lot of pruning. I changed my scoreing to return the score and a list of squares visited(stored as a bitmask in 3*uint64) meaning each step of the search I would only try to add arrows to squares that were visited by the solution I was trying to improve. I could also use this to detect if a new solution was a subset of its parent (if no new squares were visited and the score was equal or lower) and not explore that branch any further. I also immediately threw away any solutions where the arrow added pointed into the void. I also removed any solutions with useless arrows (while scoring I set a flag for every arrow if it actually changed the direction of a robot and then this flag had to be set for every arrow at the end).
With the beam search I managed to get around 9300 as it wouldn’t find optimal solutions that involved the same squares as a shorter one in a different direction (eg on roundabout the optimal solution would get discarded either because the score starts quite a bit lower or if the beam width was wide enough it would end up as a subset of the best solution before adding the final arrow as the route in the other direction included all squares). Without the subset filtering the tree expanded too quickly to be usable (it would find the optimal on roundabout as it was simple, but score very low on the bigger levels). I was considering making the subsets be the full state masks (760 bit for each direction in each cell) instead of just visited cells but didn’t get a chance to try this.
I then combined the solutions to use the beam search to seed my GA which didn’t really work at all (it barely improved on my beam even with 50% of the time). I then went for more of a SA approach - I’d take my final beam solution and try up to 10 random changes allowing accepting any arrows that left me within 20 points of my best score (to allow changing away from a solution that just went horizontally). It kept doing this until it had tried 50 times without any improvement at which point it reset to my current best solution. Whenever a new global best was set it would simplify it leaving only the arrows that were used (I found it best to let the random add useless arrows as they would sometimes be useful later).
As most of my solution was deterministic my scoring was very stable, only differing by about 10 points if I submitted the same code. Running offline I was getting over 11000 meaning performance was still a major factor for my final score (I was getting about 20% more simulations offline).
10 Likes
Finished 3rd
Using single simulated annealing for the whole time - running multiple was very similar on average so didn’t bother
Only possible mutations are changing the state of single cell - this makes recalculating simulation scores a bit easier than complex mutations
Recalculating robots scores only for those that were passing through modified cell and resume simulation from the point it first touched that cell - this made checking scores somewhat faster but updates still require full simulation and in the end there were around 1M score calculations for test 30
Never allow placing arrows that would lead to falling out of grid next turn from that cell - didn’t have any other restrictions like corridors but I like some ideas mentioned above
Modify scoring function to add penalty for using arrows on cells that don’t have non-empty neighbours in 8 directions - this was the only clever trick wasn’t mentioned here that I had and the reason is that for big empty tests you want to put arrows on borders and nothing in the middle so that each inner cell gets traversed twice. This was worth less than 500 point probably but good for big scoring tests.
What I didn’t have was very fast simulation and using the fact that all robots usually follow same cycle and you only have to maximize one such cycle and connecting robots to that cycle is relatively easy. Probably it is possible to do and eulerscheZahl even mentioned doing something similar.
17 Likes
Finished #1, 11054 points.
Until the very last night, I used a single simulated annealing for the whole time. My only mutations were placing an arrow into an empty cell and removing a previously placed arrow, and my scoring function was just the objective function without any modifications. I tried adding more complex modifications and penalties for placing arrows, but none of this seemingly helped. In fact, a more extensive testing – say, running a solution 100 times and averaging the score – would’ve helped me compare ideas to each other and probably move to the right direction. But I was somehow too lazy for that, so what I did was just running a new solution several times and looking if the score “seemingly” improved, so there was quite a lot of noise in my decisions.
I made two noticeable improvements in the last few hours which improved my score by several hundred points:
-
Do the big SA for half of the time. For the remaining half of the time, run several small SA’s to improve the score. I took a random 5x5 square subgrid in my current best solution and spent some fixed number of iterations trying to improve the placement of arrows inside it. It has to be mentioned that I implemented this after being overtaken by eldidou. It probably helped me remember that he used a similar idea in a recent Topcoder Marathon Match and described it at the forums – which I’m grateful for
-
Restrict the set of cells touched by the big SA to empty cells which have a neighboring (in eight directions) arrow or void cell. These cells will most likely contain arrows anyway, while arrows in cells with eight empty neighbors will likely screw my score up – every such arrow prevents several cells here and there from being visited twice, which is essential in test cases with large empty areas. It helped me draw pictures like this, which is inoptimal but still pretty good.
The final quick dirty hack was doing SA for the first 0.1 seconds ignoring cells which only have neighboring arrows but not neighboring voids. It helped me get the score of 850 for the 30th test case almost instantly (which turns out to be the best known score), while if I also included cells with arrow neighbors, my score often was in the 700’s. I imagined it wouldn’t hurt me too much on the other test cases as well.
Thank you for the contest, I enjoyed it!
38 Likes
Hi! I was only able to take a short look at the description of the game but due to private reasons I was not able to code. Will it be available as an optimation puzzle in the near future? Looking forward to it!
Finished 18th (almost 10k on provisional, 9.5K for final)
Multiple hill climbing runs
-within a run always continue with best state
-ended up with 4 runs, all using somewhat different tricks
-some runs reuse end state of a previous run
Initialization
-change dead arrow chain to void (*should have been limited to short ones)
-calculate cells worth to have arrow: ignore tunnels (gave up max score on some easy tests, *could have been compensated in the end)
-calculate other characterstics (single component, symmetry)
Random change:
-pick some worthy cells (many changes for start, but only 1 around the end of time)
-2way: always arrow, 3way: almost always, 4way: high chance to became empty
-avoid -> <-
Simulate early exit:
-do not continue if a robot score is much less than before
Simulate with one robot (*coded in last hours and messed up, not used)
-mark the path and after reach end or cycle, calculate remaining length backwards for all cells
-later robots can stop when reaching those trail cells
-only if there are more than 2 robots and all robots are together (should be: in the same partition)
3way only run:
-for a few maps (eg. 15th, 30th) nothing else is needed to achieve a good score
Symmetric run:
-check if both map and robots are symmetric (center symmetry only)
-in a symmetric run, always do the same action on both sides
-use half of the robots when checking
Manual improve:
-try to find and add 2 adjacent unused cell to the path
-only for the final solution (to avoid blocking later improvement and costly check)
6 Likes
Hello,
#32 with 9151
This contest was simple to understand/start yet complex to solve (what all contests, uncluding multis, should be about).
I did not believe in classic random-search algorithm as it appeared clear that you’d need some information on the robots placement in order to put clever arrows on the map.
Reading the top-10 PM, I guess I was completely wrong 
Anyway I used an alternative approach; some kind of heavy-heuristic-guided MC :
Each loop of my search would be :
Run the simulation for a single robot, and at each turn, decide with a heuristic what to do :
- Nothing
- Put arrow U D L R if possible
Each of these 5 possibilities were scored with two simple heuristics, based on the cell that potential arrow would put me at :
Heuristic 1:
- I will fall in the void : -10 (not -20, as falling gives 1 extra point, versus entering an infinite loop)
- I will step on already visited cell : -20
- The cell has hardcoded arrow (the ones that are present before the game starts) : 0
- Virgin cell that I never visited in neither directions : 100
- Cell I already visited in the opposite direction (I will most likely die quickly if I take this path) : 20
- Else (cell that I already visited in another direction, not backward) : 50
The instruction with the best score was picked and simulated (in case of equality, pick one random among the equally scored scenarios)
Heuristic 2:
Same as the first one, but instead of picking the highest ranked option in a deterministic way, I pick a random one, each weighted based on its score; highest scores have bigger probability of being picked but lowest score can be picked too.
That second heuristic was aiming at introducing more randomness in my solutions. At each step I had a 60% chance of using heuristic1, and 40% for heuristic2.
Once I finished simulating the first robot, I would do the same for robot 2, etc, making sure that I didn’t place arrows that would change the previous robots solutions (I used bitmasks on the map’s cells to do that quickly).
A former solution would do this for all the robots at the same time, but it works better if you focus on a single robot at a time; the first robot have an empty map for himself, the other ones adapt to the already placed arrows.
The evaluation order of the robots was random.
At the beggining of each turn I have a 70% chance of reusing my best known solution, that I would mutate a little by removing random arrows, or random chunks of arrows (i.e. removing all arrows in a 3 to 8 sized square of the map).
When reusing an old solution, I clean it first; i.e. I remove arrows that no one stepped on.
Kudos on the permissive rerun (harassing Agade in PM works sometimes).
I’m not a fan of auto-submit tho; I don’t see the point of doing it.
Thanks for the contest
8 Likes
I liked the contest, but I am not very good at these short ones. I had friends over on sunday (played some dnd) and I need more time than some, to come up with a good algorithm and also to implement it.
Still, I am not unhappy with the end result (78th with around 8k points). I went with a backtracking algorithm. Most of the time was spent getting it to work . I did the following steps in my code:
-First I used floodfill to separate the platforms into isolated areas where it is impossible to go from one part to the other. The test case multiple 3x3 is one of those, but there is also anoter test case (forget which) where one platform is separated into two by arrows pointing (anti)parallel. It is important to recognize those splits also.
-I give all tiles an array with options for arrows. There are 6 types of tiles:
- Dead end tiles, with 3 void neighbours: Those always get an arrow pointing toward the non-void tile.
- Corner tiles: They always get one of two possible arrows, so they branch into 2 possibilities.
- Tiles with L/R neighbours or U/D neighbours. These don’t get arrows, because there is no point. I think there are exceptions where it would be good to have an arrow next to a starting position, but I ignored those.
- Edge tiles: They have 4 possibilities (1 void tile neighbor), but I always prefer the one pointing inwards first
- Empty tiles: They have 5 possibilities. I found these hardest to deal with. I prefer them as empty first
- Tiles that already have an arrow dont need to be touched.
Basically I start with the 1st bot on a tilegroup. I use backtracking to find the best path for it. I use about 80% of calculation time for this bot. Then I run the same algo for the other bots on that tilegroup. The second bot is only allowed to place arrows that don’t disturb the 1st bots path. Usually there are very few degrees of freedom left after that 1st bot so they dont require much calculation time. The other bots sometimes get a good score too and sometimes the score is very low, depending on the map.
The main flaw in my approach is that I don’t take into account all bots at once. It is very easy to end up with a bad result if one bot screws over all the other bots. I had no time to try other ways, but I can see how some kind of pruned random search would be better.
Thanks for the contest. It was a good one. I have 0 criticism of the game itself. As I said, the duration was a bit short for my taste, but that is just me personally.
5 Likes
This test case has axial symmetry down the middle, therefore I am assuming that the optimal solution must also have that symmetry. As an example I show some arrows respecting that symmetry.
I think I was somehow inspired by this replay but it’s not a great example actually because the initial arrow placement does not agree with the central point symmetry the robots have.
Edit: The symmetry idea is probably bad, see follow-up posts.
1 Like
I ranked 37th (8932 points) with the following approach:
-
Place the largest possible rectangle inside the empty territory unless it would be only 3x3 or smaller, in that case start with a some cycle. The rectangle can be easily filled to allow passing most of the inner fields twice and then going back to the beginning.
-
For each pair of fields in the current cycle (starting with adjacent fields) find a path from the first to the second and if it is longer than the current connection, replace it.
-
Once step two does not yield any improvements anymore, redirect all empty fields that can reach the cycle into it.
-
Repeat steps 1 to 3 for the other connected components.
-
For any robot that cannot reach a cycle, let him walk and place an arrow when he would walk into the void (90 degree turns preferred to u-turns). This allows for okayish results in the more linear test cases
Hi,
Finished #15 with 9639 points.
Thank you Agade, Magus and CodinGame for this contest which was really fun (simple rules yet hard to master).
Started with a genetic algorithm thinking it would be great to combine good solutions.
On Sunday, I found out that my GA was performing better with a selection of 1, removing crossover and increasing mutations… which was just a poorly optimized hill climbing
My robots were simulated in sequence to quickly reuse previously found loops.
Can’t wait for the game to be available again to try simulated annealing and other tricks mentioned in this forum!
1 Like
I would would rather expect point symmetry to the center (which the map has too).
If you place an arrow next to the axis, pointing towards it, there will be an arrow on the other side too, resulting in a short loop.
2 Likes
Magus, Agade, Automation2000, thanks for the game. Simple rules, but a lot of interesting parts: search algo, performance tweaks in simulation, some heuristics.
My algo (126 in final rank):
- Put some initial arrows if cell matches some condition or generate enumeration of possible arrows for this cell (corners, corridors, dead end, borders of platform).
- For some time find 10 best different solution randomly placing arrows on grid and scoring them (calculate total path)
- Rendomly mutate (add or remove arrows) these solutions for some time - only apply mutation if score is increased.
4th
At first I made random solutions for one second, guided by minor heuristics, and selected the best one as result. This got me a score slightly over 8K.
After adding mutations at the end on top of the best solution I got to 9K.
Tweaking some parameters in my code without adding anything substantial got me to 9.8K.
After trying to keep cells that don’t border the void empty, like other suggested, I got my first 5 digit submit of 10.3K.
Then, to my surprise, I got to my final score of 10.6K after doing some pure optimization (no functional changes) . Performance is a big deal in this game.
About the contest:
I liked the duration, but the game itself wasn’t my cup of tea, although I can see the appeal. One thing that I didn’t like that much was the rather limited amount of submits. I felt scared at times of hitting the limit at an inconvenient time. It would also be nice if the combined score could be displayed when running multiple test cases in the IDE.
9 Likes
#7 with 10297 points
I used a Simulated Annealing as many others for this contest: I first place random arrows on the map and then change 1 or 2 cells at each step to eventually lead to a good solution.
To maximize the score on open maps, a high number of cells should be visited twice. To allow that, my arrows can only be placed on the edges of the map:
I struggled with tests where there could be a “big” local optimum: it was hard for my SA to get out of it:
Good solution:
Not so good:
I tried some stuff to prevent that (with heuristics or including restarts) but unfortunately it was always worse.
During the last night, I also tried to optimize automatically the hyperparameters of my SA: I had a simple hill climbing algorithm to try different parameters and find the best ones. But since the runs are a bit random and I had little time left, it only led to a small improvement.
Game feedback
It was a really interesting contest with simple rules and I had a lot of fun trying different algorithms !
The only downside I can find is about testcases: the total score only depended on half of them. I can understand that simple testcases are needed, but it would have been better if we had 5 basics / 25 interesting ones, especially when we only have 1 rerun. I’m a bit disappointed by my final score (my last submissions where usually between 10k4 and 10k6) but of course the final score is a bit random (duplicating testcases could have helped prevent that).
Anyway, the complexity of the contest was perfect for a 2 days contest and I really liked this kind of short format
7 Likes
Finished 2nd, 10988 points.
I used simulated annealing as well, but instead of working directly on arrows, I worked on a set of cycles (starting with an empty set).
For example, let say that I have a set of cycles like this:
For the evaluation I simulate the robots, and when one enters a cycle, it follows it, (while putting arrows if it was not already done by a previous robot).
The way to go through the cycle depends only on the first robot entering it.
So after a simulation I might have something like this:
For the simulated annealing, in order to go from one state to another I add another small cycle to it this set of cycles.
If an edge is present twice, it is removed (so it’s more a ‘xor’ with another cycle, than an addition).
If we add this small cycle to the previous state:
We’ve got this:
Which might give something like that after a simulation:
The small cycles I used were these ones (and the rotations):
Sometimes adding a small cycle like this can split/merge cycles, sometimes it can reverse a part of a cycle, etc.
One other thing is that the cycles are not necessary on free cells only, they can partially be over void cells, or fixed arrows cells, so it can work (kind of) on test cases without big open area too.
The good thing with this approach, is that it creates a “smooth” search space : it can go from one good state to another without going too low with the evaluation function, and for simulated annealing this is often critical, and I think it has some good scores on tests with big open area.
The bad thing is that it requires some hacks to handle the robots before they enter the cycles, or when you want them to do a 180, and because of that it behave badly on some cases (I almost always miss the 354 points solution of the test #13 by more than 150 points, I should have brute-forced this kind of test cases 
).
27 Likes
Damn I wish we have a multiplayer version soon.
I can’t stand waiting to see how my algorithm perform once I finished debugging it. As I started implementing too late and couldn’t finish in time, I lacked one or two hours probably…
That was a good contest.
I’m 359th with a very simple IA placing a random arrow on each dead-end and computing score, keeping the best combination of arrows.
Several improvements to test when it will be a multiplayers game.