A multi player coding competition was held over last week. The topic was a game, which was played on a 35×20 grid. Players were controlling a single unit, which could travel to any of the four directions. Once it was alone on a neutral cell, it got converted to his color. After surrounding a larger neutral area, all of the cells got colored to the matching color of the player. The goal of the game was to have more cells then the opponent has in the end.
See this Replay to get a sense of how the game was played: https://www.codingame.com/replay/55699634
I started off by writing the game locally, it turned out to be a great help in prototyping and debugging later on. I wanted to create a strong AI that can play this game without any heuristics, but I soon found out that running simulations are quite costly. It took between 4-6 ms to produce a game state after every step, and given the 100ms limitation of every round, the amount of simulations could have done was simply not enough to produce a sensible result.
For a start I worked out a simple algorithm: the game was running through all the cells, and checked what is the maximum sized Island, which can be created from that point. An Island is an Area consisting of empty cells, which can be surrounded by a single rectangle. The program was counting how many neutral cells was in this Area and how many steps required to capture the whole adding the distance from the player, and started to conquer the one with the biggest payoff. I’ve managed to get to the position of 24/1413 by the end of the second day with this approach.
For the next five days I haven’t submitted anything, but my program was keeping up, it stayed between positions 40 and 90 all the time. I’ve found some logical and computational bugs in the algorithm, but surprisingly, when I’ve fixed them, the new bot performed consistently worse. It looks like the bugs were the essence of this first program. 🙂
After fixing up the main issues I’ve started working on making the bot smarter. I’ve added a new way of creating interesting Areas: the Rooms. Rooms are areas which can be formed in any shapes. The basic idea behind this was to examine every cell and see how many walls of the same color they can look at. After a bit of research it turned out there are a few rules which can be followed to be able to determine the optimal borders of each Room, and they were added to the potentially interesting Area’s list.
After finding all the Areas, I was running a second pass on them, and created smaller Areas of each of them which could be safely conquered depending on the distance of the enemies. Using this logic the program was able to identify a potentially threatening enemy’s approach and close the area early without risking losing the whole.
At this point I had a lot of information about every Area:
– how much point does the player gain after conquering this area
– what is the nearest point to the player
– how many steps needed to get to the entry point
– how many steps needed to capture the area
– how close is the closest enemy to any point of the area
– what’s the moving direction of this enemy: is he heading towards/away from the area, or moving parallel to it
The next step was to find the correct balance between these numbers. I’ve been playing with them a lot, but was unable to come up with an universal solution.
As I was already calculating the above for all the players, I was trying to add all the enemy’s Areas to the current player’s ones, and use a generic sorting on the whole array. It managed to successfully pick up the areas the opponent was trying to capture, and managed to block them if they were more rewarding then capturing one of our owns. However, since I couldn’t find the right balance between them, I ended up submitting without this logic.
There was one addition to the above game: over the whole play each player was able to reverse time once, essentially reverting the last up to 25 rounds of the board. I didn’t wanted to exploit it deeply without having a correct capturing algorithm in place, so was aiming for something simple, yet effective to go with. It checked whenever a bigger capture happened and if the bot didn’t have any good Areas nearly complete in the next couple of steps, it checked if it could’ve prevented it by moving in the centre of the captured area. If there were enough time to go there, it reverted the time and blocked the opponent from capturing it.
One of the replays have caught my attentiton. I was playing against another bot who ranked fairly well in the end. It clearly looks that both players got stuck in the middle of the game, and was unable to move forward. It shows that we’ve implemented exactly the same logic to decide where to move next. Unfortunately, he has succeeded to find the correct balance in the end, and I haven’t. 🙂
The competition was running for 8 days, and the final outcome was:
Global Position: 106/2,018
Country Position (HU): 2/48
Overall I’ve learned a lot from this competition, and although I’m a bit disappointed my bot didn’t make it into the top 100, being in the first 5% is still not bad.
See you in the end of November, on the 24 hours optimization challenge! 🙂