The Back to the Code online coding contest marked our return to multiplayer contests. Over a period of 8 days, the mission was to help Marty and Doc retrieve the Almanach before Biff Tannen got his hands on it.
To do so, they had one secret weapon: a trick that could allow them to go back in time and turn things around… for better or worse.
Back to the Code: The Game
The aim of this game was to help Marty McFly acquire the maximum number of cells in a grid. In order to acquire cells, you had two options: either you moved onto a neutral cell or you surrounded a set of neutral ones with cells that belong to you. Finally, in order to spice things up, you could go back in time in the game and play differently!
A first approach to tackle this game is to focus on the first rule: move into a neutral cell in order to own it. A simple solution is to find the closest neutral cell in the grid and move to the coordinate of that cell. This can be done by browsing the grid and looking for the coordinate of the neutral cell that minimized the Manhattan distance. This can be improved with various heuristics, in particular, while approaching the end of the game, by avoiding cells that were closer to your enemies than to you. Another possible improvement is to give priority to a group of neutral cells that were far from you over a single cell close to you.
The first approach was enough to get you in the top 1000 players but if you wanted to master the game, you had to surround neutral cells. A popular solution, that could even get you in the top 100 if you were really good, was to generate a list of possible rectangular areas around your position and select the most promising one. The heuristic to determine how good a potential area is was the magic part! A nice mix of risk and benefits.
Finally, you could also go back in time, but only once for each game. This allowed a tremendous amount of strategies. It could be used to revert and try to block one of your opponents from winning a large area, or to change your strategy to be more cautious or aggressive with respect to your opponents.
Evaluating the Best Areas to Cover
This is the strategy of Recar (Ukraine, 1st).
“These are the basics of my strategy:
- I find the most optimal rectangle to fill by counting the number of neutral cells inside and the number of steps to surround it.
- I try to find if the areas under my control allow me to fill a bigger number of cells. If it is more optimal, I use this move instead of trying to fill rectangles.
For a two-player game, I check which rectangle my opponent wants to surround, and if their target is better than mine, then I move there.
For a 3 or 4-player game, I assume that my opponents progress straightforward for at least 4 turns or until they find an opponent cell. This strategy helps me to make a turn before anyone ruins my plan of closing an area.
Also, if I travel back to the past, I try to take into consideration my opponents’ moves and assumed they will remain the same. Every 20 turns, I analyze my path and if it did not lead towards filling an area, I travel back and try again hoping this time it would go better.
To find the best area, I sort rectangles starting with 3*3 rectangles and choose the one that earns me the most points. To calculate points for an area, I just count the number of cells inside the area. If this number is larger than the number of points needed to win the game, I use the latter instead. No need to be greedy 🙂 If there are enemy cells in the area, I just set it to 0 and exit.
For an area less then 3 cells long on whatever axis, I calculate the points as such: 1 divided by the number of cells in the path to the upper left corner.
Then I search for the cells on the perimeter and choose the cell from which the roundabout path is the shortest to fill the area. To make my bot fill the current rectangle instead of going to a brand new fancy but distant place, I multiplied by 2 the number of moves needed to reach the first cell of that area. To add even more motivation for the bot to take bigger areas, I added a constant value to the number of moves, which depended on the number of players.
This is how I calculate points:
Number of neutral cells to cover divided by the number of turns to win the area.
I multiply it by 2 if the score for neutral cells was enough to win.
For 2-player games, I multiply points by 2 if my rectangle’s border goes along the 17th line on the x-axis, and there are more than 10 free cells on it. I also divide points by 2 if the rectangle is more than 14 cells in any direction.
For 3 or 4-player games, I multiply points by 1.1 if the rectangle touches the edge of playing field. I also divide points by 2 if the rectangle is more than 13 cells for three players or 12 cells for four.
I divide points by 2 for each of my opponents close to my rectangle by less than 2 cells.
I divide points by 10 if information from the future tells me that one of my opponents is aiming towards this area.
In order to stabilize my bot’s behavior, I give a 1.1 bonus to the rectangle from a past move.
If no rectangle will reward me more than 1 point, then I look for the closest single cell, ignoring those adjacent to an opponent. This helps my bot to escape a mess with the opponents while trying to capture a neighboring cell at the same time.
I start to search for non rectangular areas in an “L-shape” from the current position and check all of them up to 20 cells long. As a result, I got the optimum amount of points which I should get to in order to fill the best chosen area.
Next thing I do is guess the area which my opponents will try to fill with my method. If their area is bigger than mine, and it seems they will fill it quicker than I will, then I try to interfere. To make their efforts futile, I search for the closest cell next to the border of the area they try to close.
After that, I had to either close my area or deal with my opponent. If the path to the target point is diagonal, then I should make my way through as many neutral cells as possible. The best way to solve this was dynamic programming, but what I did was just check the availability of cells after each step vertically or horizontally.”
Searching for the Best Path with a BFS
This is the strategy of Olaf69 (France, 3rd).
“I just finished uploading to GitHub the repository I created to play the contest. There, you can find, among other things, a list of commit messages.
My AI is based on a Breadth-First-Search algorithm (BFS). I believed that to be efficient I had to estimate on each turn the performance of a maximum of possible paths, within the 100 ms limit.
The tree of all possible states of the game was particularly big (close to 5^nbPlayers^350 nodes), so it was necessary to come up with a few rules to limit the amount of possible states. At the end of the contest, my tree expansion rules were as follows:
- If there is at least 1 neutral cell around me, I consider each neutral cell, but I leave out non-neutral cells.
- If there is no neutral cell around me, I’ll leave the area by making sure to never consider 2 different paths to the same non-neutral cell.
As a last resort, if I haven’t found a path that will allow me to improve my score, I will move towards the closest neutral cell. This can happen because of the way I estimate the paths of opponent players.
On each expansion, I must also estimate the most probable move of each opponent. Ideally, I would’ve liked to implement an alpha-beta type algorithm – which consists of evaluating every possible move the opponents can make and assigning a score to each state – but that would have been completely unrealistic in light of the inordinate amount of possible states that would generate (and only 100ms to compute them all)… So what I did was to settle with a much simpler – but risky – solution which consists of moving the opponents in a deterministic way following these rules:
- If the cell in front of them is neutral, they will move onto it (this implies you know in which direction they are moving).
- Otherwise, if their last move was to go left, they will first attempt to go on a neutral cell on their right, then on their left. It’s the other way round if their last move was to go right.
- If no neutral cell is around them, they will move towards the closest one.
These rules assume that the opponents will not act aggressively, they will always privilege scoring points over disturbing my progress.
At the very start, I had implemented a way more defensive strategy, assuming my opponents would recursively move onto EVERY SINGLE cell they could access. This allowed me to evaluate the shapes I was sure I could close, but they were all much smaller – and thus less interesting – than the ones I get with with my final code.
Actually, with those rules of expansion, I was still too limited by the available time, I could only estimate paths to quite shallow depths (close to 10-12, approx. 60000 nodes). A meager 12 cells isn’t enough to form large rectangles on a 20×35 grid! In fact, it mostly made me move in spiral shaped paths!
One idea that truly helped me make progress was to further limit the possible paths by performing 3 cell steps (only across neutral cells). At this point, I could evaluate paths across 30 cells, sometimes even more.
If I succeed in exploring the entire tree (frequent at the end of a game), I will then try again with a step of 2 cells, and then with a step of 1 cell.
Another major problem was to evaluate each path. At first, my criteria was simple: the amount of points. But this was not very satisfying. With the amount of points as the sole criteria, surrounding a larger, and larger zone is always the most interesting behavior. As such, you’ll always end up getting thwarted by your opponents. I proceeded to try a few different formulas:
- Amount of extra points / remaining number of steps → closing a small zone becomes too interesting
- Amount of total points / total number of steps → enables light optimization of generated shapes, but they remain too big.
Finally, I opted for this compromise:
- (Amount of extra points + 20) / (remaining number of steps + 20)
Additionally, there were a few optimizations that helped me advance. For example:
- Limit as much as possible the amount of calls to the fill-in function.
- Optimize the score’s calculation.
- Optimize the search for the closest neutral cell.
- Efficient memory management of nodes from the search tree.
And yet I regret not having had time to implement all of my ideas, namely to exploit the back in time command!”
Contest Report
Check out the global leaderboard.
