Hello to all!
After testing CodeRoyale and getting Gold, I started my first Codingame Challenge with my meager AI knowledge.
So I’m very happy to have arrived at the gates of Legend with for a few hours even the hope to pass. Unfortunately the boss was too strong for me and all my attempts to improve the last 3 days were a complete failure.
As the only search algorithm I know is Djikstra, all my AI is heuristic and mainly uses Djikstra to calculate the distance from a cell to any other cell.
My AI is relatively simple and breaks down into 5 steps:
- Construction of recyclers
- Moving the remaining robots
- Building the robots
I loop on all enemy robots and see if he has a neighbor that belongs to me. In this case, I defend the square by doing :
- if he has 2 or more robots, I build a recycler
- otherwise I spawn robots if I have some material left
- otherwise I leave the robots on the square
- I move robots from the neighboring square if necessary
This heuristic had a lot of problems. How to choose the square to defend if the attacker touches several of my squares. How to choose the best squares to defend if I can’t defend them all. I did not find good solutions to these questions.
Construction of the recyclers
If I didn’t build a recycler in the previous round and there are more than 130 squares left on the field, I build one that maximizes scraps/grassCreated.
I haven’t managed to implement anything better than this basic but overall effective version.
EDIT following @Lysk question:
I have in my IA many experimental hardcoded threshold to solve issues with my heuristic. It seems globaly a bad idea but I didn’t manage to do better.
The exact condition to build a recycler is the following AND condition:
- turn > 2 => to avoid blocking my robots in the first turns
- !hasBuildLastRound => to avoid to build too many recyclers
- (notGrassBlocks.length >= 130 || opponentRecyclers.length > myRecyclers.length) => to avoid killing myself on small maps. The 130 threshold was originaly 80 but it seems that 130 was giving better results. Therefore on small maps I only build if the opponent has more recyclers than me. I count every blocks on the map but blocks with 0 scraps.
- (myRobots.length < 10 || myRobots.length <= opponentRobots.length + 5) => to build robots but not too many
- myMatter < 40 => if I have 40 matter in one turn, I have already too many recyclers.
If all this conditions are true, I build the best recycler on a case which will bring me more than 20 scraps and sorted by scraps/grassCreated.
I calculate in the first round the squares that separate the map in two. At each turn if these squares are not occupied, I make a double loop on the squares of the separation and my robots to find the square and the robot that minimizes the distance. Very expensive algorithm in n*m^(min(n,m)) (n = robots, m = separation squares) which gave me many timeouts. I continue the algorithm until I have no more robots or until all the cells of the separation have found a robot that will go towards it.
EDIT: after reading some postmortem, I think I was only trying to write an Hungarian Algorithm but mine is poor writen in O(n!) against O(n^3)
Moving the remaining robots
If a robot has not moved for expansion, I move it with an evaluation function that checks the squares within 5 range and adds for each square 1/distance if it is neutral 2/distance if it is enemy.
Construction of the robots
I spawn a robot closest to an enemy square and at equal distance on the square which has the least robots.
I tried a lot of upgrades for each step but I felt like I had reached a local minimum and any change made my rank go down.
Very happy to have participated in this Challenge, the people on the Discord were all cool and will more fun if there was more people on Discord to discuss about the Challenge