A* Craft - Feedback & Strategies

[Neumann]

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

[MSmits]

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:

1. Dead end tiles, with 3 void neighbours: Those always get an arrow pointing toward the non-void tile.
2. Corner tiles: They always get one of two possible arrows, so they branch into 2 possibilities.
3. 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.
4. Edge tiles: They have 4 possibilities (1 void tile neighbor), but I always prefer the one pointing inwards first
5. Empty tiles: They have 5 possibilities. I found these hardest to deal with. I prefer them as empty first
6. 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.

[Agade]

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.

[Zilvarro]

I ranked 37th (8932 points) with the following approach:

1. 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.

2. 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.

3. Once step two does not yield any improvements anymore, redirect all empty fields that can reach the cycle into it.

4. Repeat steps 1 to 3 for the other connected components.

5. 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

[_Royale]

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!

[eulerscheZahl]

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.

[dbf]

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):

1. 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).
2. For some time find 10 best different solution randomly placing arrows on grid and scoring them (calculate total path)
3. Rendomly mutate (add or remove arrows) these solutions for some time - only apply mutation if score is increased.

[Daporan]

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.

[Saelyos]

#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

[eldidou]

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 ).

[FredericBautista]

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…

[Merome]

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.

[Agade]

The map has two axial symmetries and a point symmetry. Which allows you to search on only one quarter of the map.

The two axial symmetries are equivalent to a point symmetry, except on the vertical symmetry line where you cannot place left/right arrows without breaking either the horizontal axial symmetry (e.g: pair of black arrows) or the central symmetry (e.g: pair of yellow arrows).

Edit: @eulerscheZahl gave a counter-example in PM. If your solution respects an axial symmetry there is seemingly no way of going from one side of the map to the other without dying very quickly, which is probably not the optimal solution ( →…|…←). As for point symmetry it also seems like a very bad idea as you will just make 1 circle and die.

[cegprakash]

Finished #76 (7883 points)

Very nice contest for this duration.

Initially I did random search robot by robot (computing full path for one robot then then create a path for remaining robots) This took me to 3600 points.The score I calculated during random search was differing from actual score. Once I fixed those bugs, I reached 4200 points. Then I converted my random search in such a way that I choose a random move for all robots together in each step. This took me to 4800ish. When I was out of ideas MadKnight suggested me to try mutation. So I tried my first mutation and crossover in this contest. Once I implemented my first add arrows mutation my score jumped to 6000+. Then I added delete arrows and change arrow direction. (As someone suggested I also tried moving arrow to one position. But this didn’t help me) By this time my score was 7000+

Crossover was a failure strategy for this contest.
Attempt 1) Find a random solution with only 1 robot (for all robots). Mutate each of these solution to improve the global score. Run a crossover in all these solutions. Mutate this solution for several iterations.

Attempt 2) Take the two best random solutions. Mutate them separately. Apply crossover on these two mutated solutions. Then mutate this solution for several iterations.

Attempt 3) Same as attempt 2 but I pick n best random solutions instead of 2.

All three attempts did not outperform SA. By this time the contest was almost over and I was very tired. So I just did some performance optimisations and it took me to 8092 points

I have learnt a lot from this contest.
My favorite post mortems : eldidou and euler

[JFB]

Agade - I do not know do symetry of sytuation means that best solution is symetrical too. It is well know in physics that even in case of symetrical environment and physical laws -it is possible that the best solution is not symetrical. It have even special name ‘spontanous symetry breaking’. In current phisical models ‘spontanous symetry breaking’ is the reason that particles have the mass (and because you are made from particles - it is the reason that you have the mass ) Think about ball on other ball. This sytuaction is symetrical regarding rotation around vertical axis but solution with minimal gravitational energy is not symetrical (balls lie on the floor next to each other).

In this case best solution can be symetrical but symetry of the sytuation is not the proof of it.

[Jahz]

Finished 48 in Java with 8.6K.
Excellent game, thanks a lot to Magus and Agade, I had a lot of fun to play and wish I would have had more time.
No bug, simple statement, deep game, fun to watch the little robots walking for my kid…

I used SA with poor tuning (initial temperature and annealing schedule are almost random numbers).
I added some restarts when I’m stuck for 10K iterations, this helped for “path tests” such as 13 and 28.
@Agade I’m amazed by your restarts after 256 iterations, for me lowering it to even 1K was completely breaking my score.
For the large maps like 22 26 29, I was clearly lacking performance ( 40K on test 30) as my best solution was always found in the last 1% of my simulations.
I’m wondering how much the other Java guys achieved, but I guess it’s not only the language’s fault… even if with such a simple simulation, I don’t see a lot of options to be better.

For the validators during such a contest, I think that it was an excellent idea to have the same in IDE & submit during the coding, and then slightly different ones for the final ranking.
Maybe for the final ranking it would have been good to have more tests or to run the set multiples times (and then take average or best, depending on what you want to promote).

Finally, even if thanks to the validators it was not a spam-submit contest, it was sometimes a pain to be stuck by the submit limit, without knowing easily those limits (no idea where they’re documented) and when you’ll be able to submit again.
I see a possibility that someone is unable to submit his last version before the deadline because of the limit, that would be sad for him

[dbf]

And how did you guys store history of visited cells? In my submit I use integer hash set of something like 1000x+10y+direction and tracking/updating history was in top of my profiler output. I also tried to use bit array with cleanup using arraycopy from empty array (some java-specific stuff), but it just made it slower. Anyone was able to find something interesting for it?

[nicola]

Each robot has a set of triplets (x,y,direction).

[Magus]

My Robot class has a bool states[190 * 4]; member. When a robot visit a cell i just do states[robot.direction * 190 + cell.id] = true;

[_CG_SaiksyApo]

I also tried to used a byte[190] array. When a robot visit a cell, I just do
path[pos] = path[pos] | (1 << direction);

But I didn’t need to clear/copy it like you mentioned