The Accountant - Feedback & Strategy

Contests
#42

It could be this which would actually be real plain illegal cheating, however you could extract informations on validators by elimination, once you can with a deterministic algorithm that ensure you can win or fail every validator by just playing them in a certain way or not playing them you could find out informations good enough with like 10-20 submit and yes / no condition to categorize each validator.

Once you got there, you would then be able to know the score you do on a specific validator by purposedly failing all the other and therefore optimize for a few specific difficult validators, ensuring that your overall score remain the same when failing pruposedly those few validator and running the other (supposedly all maxed out) that would have been a clever way to use your limited submits to devise an improved optimization method adapted to the validators.

I did not think of doing such a thing as I started from the idea that you were not supposed to “know” the validators, however such a method would not have really been cheating actually and could have lead to code able to detect the current validator and select settings for that specific validator…

If that is what happened then it’s hard to tell that this was actual cheating or just legit optimization.

#43

Hi,

I finished 2nd and i will tell you bellow what was my strategy for this contest

  1. first of all I did a basic simulator to simulate full games without any optimization like trying to remove cos or sin.

  2. When i finished to correct all differents bugs of simulation, I first tried to do a simple random choice for the action I was supposed to do during a turn of a game and at the end of a game i calculated a score, the one who was given in the game rules, and i only saved the best one.

  3. Then I did few optimizations, to play more games, like removing slow functions (cos, sin) and trying to use less sqrt. For my moves i chose a random point on the map and i used vectors to do a move. For the enemys, I tried to update as less as possible the target of each enemy, I only updated it if the target of a specific enemy was removed at the past turn. At the middle of the contest, I added a new optimization : If I have only one enemy or only one datapoint on the map, then i can know exactly where will be the enemy at each turn of a game, so I calculated his path. This last one gave me 200% simulations in case of one enemy or one data.

  4. After my optimizations I added some strategies, for example, if i can shoot an enemy in one turn of a game then i shoot him (if i can shoot more then one with only one turn i prefered to shoot the enemy as far away from me) else i can randomly do a move or a shoot, if it is a move then I have a chance to do a random move or a chance to do a move toward the closest enemy, but if it is a shoot, I have a chance (just a little one) to shoot a random enemy on the map and a bigger one to shoot the closest enemy. And my last strategy was : if i don’t find any way to save a datapoint in 50 or 100ms of simulation, then i try a new strategy wich was better for test case 26 for example. Because with my strategy i just described before my IA only tried to shoot enemys and not to save datas.

With all of these optimizations and strategies i got all time more then 44k of score at the end of the contest.

I really enjoyed the contest and I had fun doing it.

6 Likes
#44

Great that you managed to find a simple algorithm that actually scored well, it’s pretty difficult to tell what choices will do good, there was so much ways to try to solve this problem. I think that most people like me chose to heavily rely on stochastic algorithms to find the best solutions.

Predetermined simple strategies as you describe them actually seem to have worked better than i would have expected to even try to implement them… Well that was a good move on your end. Good job.

1 Like
#45

Skyyker – 9ème

Preliminaries – Re-produce the behaviour.
First step, it was mandatory for me to reproduce the environment. It took me 2-3 nights sessions to perform it, and I really insist on the importance of this step!
Being able to debug on codingame is not always easy (I have seen that some people like oook are coding their own visualization, awesome!). To debug it, I computed
all the turns in advance during the first loop, and then compare each turn with my simulation and print the differences. Thanks to this rigorous steps, I have
worked without glitch during the entire contest. This allows to focus only on strategy.

Strategy
I don’t really know if what I have done has a name, but I would describe it as a mix between a Monte Carlo and a “basic” strategy:

The basic strategy
The first version was very “basic”: if you are going to die find a safe place, else shoot the nearest enemy. Then I have added some upgrades:

  • if an enemy is shoot, don’t focus another one until he die
  • set a random minimum distance before shooting unless you can kill him in one shot – to do so focus the next data point
  • if I am in dangerous zone (3500 = safe zone(2000) +
    max move(1000+500)), try to find the best spot --> hard to find and nearly useless… ! -_-’

The random strategy
In order to limit the random actions I have added rules:

Shoot rules

  • select a random target: I have limited the random selection by removing enemies that have the same amount of life and focus the same data point: only the closest to the data
    point was kept.
  • if an enemy is shoot, don’t focus another one until he die (same as basic strategy)

Move rules - 2 possibilities:

  1. move in direction of a random data point (percentage:1/3)
  2. move in a random point restricted by an area around my target enemy

Let shake it all!!!
On every simulation, I was computing random parameters that were remaining unchanged during the entire simulation:

  • number of random moves (between 1 and 8)
  • number of first basic moves (between -10 and 10 reduced to 0 if negative)
  • percentage for attack / move (between 10% and 100% of attack)
  • minimal distance before shooting (between 2020
    and 5000)
  • Boolean to focus data point (5%)

So, my algo could be a mix like:
2 BASIC ACTIONS, 7 RANDOM MOVES, BASIC ACTIONS until the end
0 BASIC ACTIONS, 3 RANDOM MOVES, BASIC ACTIONS until the end

And, obviously, I kept the simulation with the best score (if same score, I kept the one with less moves)

Important informations

  • always work with distance squared in order to avoid the cost of a root
  • have a table [distance <=> shoot power] for performance (only 14 possible shoot power)
  • compute the maximum score at every turn of your simulation. If it is less than your best simulation, stop the simulation and start another one. Truly important rule! Avoid useless simulations.
  • limit the number of computation by the time (for me 995ms for the first turn, 95ms for others)

Conclusion

Good: Really interesting contest and I truly love when it last for 2 weeks! With such duration it is possible to have a good solution even without being able to code everyday =).
Rules were very well described (only the hesitation between rerun or not were not great – (it would not really impact me because my submit were pretty stable; but the information must be known before the end)

Bad: Not having easily the sum of the test cases scores. The life points of the enemies on the screen… Not described rules on submit.

A great achievements for me during the contest: 1st position with my language (Java) =D

And a special thanks to all the codingamers with whom I have exchanged on the chat :wink:

P.S: Should I add a potato?

6 Likes
#46

Thank you for taking your time to explain. I’m trying to understand it (I’m new to GA).
Thank you again 'cause one is not enough :smile:

#47

I finished in 164th place overall and 3rd in my preferred programming language (Dart). It was my first time finishing in the top 3 of my language, so I finally got that achievement.

My eventual strategy was a Genetic Algorithm with crossover and mutation. A lot of the inspiration came from Magus’s post about his GA solution for Coders Strike Back found here: http://files.magusgeek.com/csb/csb_en.html. Most of the general principles still apply.

Each solution was some number of moves of either “Move 0.0-1.0” or “Shoot 0.0-1.0”. So basically just a list of floating point doubles. The 0-1 Move double represented a 0-360 degree move at max distance. So if the Move double was 0.5, calculate a point 1000 units away at 180 degrees. The Shoot move 0-1 representing what number in the list of enemies to shoot at by multiplying the move value by the length of the list and calling floor(). So a “Shoot 0.5” with 12 enemies on the board would shoot the 6th enemy.
I would generate a pool of solutions, score them, then mutate and crossover solutions from the pool, trying to getter scores. Finally I would submit the first move of the best solution.
I also would hold a pointer to the previous turn’s solution and use that to generate a few initial solutions on the next turn.
My best scoring algorithm was a combination of data points left, enemies killed, total enemy health, and distance between my guy and the average position of all enemies left.

I consistently ran into timeout issues with the large entity validators, which I could not track down during the contest. But I now think that it may be because or garbage collection happening after the timeout check. I need to improve my memory management quite a bit.

I am currently in the process of converting this code over to Code vs. Zombies game, as there is a lot of overlap.

2 Likes
#48

Upvote for the C++ code :slight_smile:

#49

I finished with a rank of 210
You can read my postmortem here
http://ankursheel.com/blog/2016/10/accountant-postmortem/

3 Likes