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