November 15, 2019 TCO 2019 Marathon Match Final

Introduction

8-queens puzzle

The idea for this problem came from the famous 8-queens puzzle: how can you place eight queens on a standard 8×8 chess board such that no queen attacks another one. Here is one example solution from ninety-two possible ones:

This is a very famous computer puzzle that is often used to benchmark algorithms. It can be solved with a variety of techniques, such as: depth first search, constraint programming or any number of heuristic algorithms like genetic algorithms or simulated annealing. Even famous people like Carl Gauss and Edsger Dijkstra worked on this puzzle! 

Original formulation

The original formulation of the MM final problem was the following. Place chess pieces on a grid such that no piece attacks any other piece. Pieces can be king, knight, bishop, rook and queen. Pieces cannot traverse through walls. You get points for each piece placed and your task is to maximize the total points gained.

After some thinking we realised that this problem probably doesn’t have enough depth and could possibly be solved optimally with integer linear programming. I will leave this as an exercise to the reader.

Final formulation

Then I saw a Numberphile video about the Peaceable Queens problem – place as many black and white queens such that no queen attacks any enemy queen. Here is an optimal solution for the 11×11 grid, which uses 17 queens of each colour:

This is one of the favourite problems of Neil Sloane (creator of Online Encyclopedia of Integer Sequences), so much so that it received a very nice sequence number A250000. Currently optimal solutions are only known up to 15×15 so this is still an open research problem. You can see the Numberphile video here:

After seeing the video, I realized that adding more players would give our problem more depth and make it more interesting.

So in the final formulation of the problem we allow two to eight players for grids up to 50×50. Now pieces cannot attack enemy pieces, but they can still attack friendly pieces. Also we place random walls which cannot be attacked through. Here is a brief version of the problem statement: https://apps.topcoder.com/forums/?module=Thread&threadID=946822&start=0

There was some debate about the scoring function, but we decided to go for the score of the lowest-scoring player. This way one needs to place as many pieces as possible, but also keep a good balance between all the player scores, which makes it harder. I believe that due to the minimum function you can no longer solve it optimally with integer linear programming, but I am happy to be corrected. Update: according to Petr this problem could still be solved optimally by running a series of integer linear programs and then taking the minimum. I still suspect that this approach would run too slow, especially for larger grids.

Possible Solutions

Now we will discuss some possible solutions to this problem. Note that these are just some ideas I had and may not result in the best possible solution.

Hill-climbing / SA

A naïve solution to this problem is to use something like hill-climbing or simulated annealing (SA) to place the pieces. In these approaches we begin with a random placement of pieces. We then perform random moves and accept them if they improve the score. Once in a while we may accept lower scoring moves in order to escape a local minimum. The moves can be: add a piece to a cell, remove a piece, exchange two pieces, or change a piece’s colour. Here is a good solution that can be achieved with these methods on seed=1 (smallest grid):

Even though you can do some clever optimizations to recompute the score quickly after each move, I believe that these methods alone are too slow to achieve high scores on larger grids.

Flood-filling

Since queens give us the most points we need to use them as much as possible. We also notice that a queen can be surrounded by other pieces (like kings) to neutralize its attacks. So one possible approach that we call “flood-filling” is to fill the area with queens and then surround the region with short-range pieces like kings or knights. Here is a solution using this method for seed=2 (largest grid) produced by our tester Jaco Cronje:

This solution achieves a score of 42161. I believe it can be improved further since the maximum is 5000 points higher. For example the smaller regions can be merged into the larger ones.

Flood-filling + Hill-climbing

Now that we have neutralized the queens, the major area of focus should be the pieces on the border of each region – this is where all the attacks will happen. We may still want to use hill-climbing/SA to improve this area. So the final solution could be: flood-fill to get a good starting point and then hill-climbing around the borders to optimize the score. For some cases (small grids or large grids with many walls) it may be sufficient to use hill-climbing alone.

Other ideas

The original scoring function uses a min, which can produce quite sudden changes in the score. Solutions using this scoring function are more likely to get stuck in local minima. So one idea is to use a “smoothed” version of this function by weighting the contribution of each player. I know that some contestants tried this and it didn’t help them, while for others it made a big difference. Perhaps it is very dependant on the implementation.

One interesting idea is to reduce the search space using symmetry. The idea is to just fill the area for one player and then symmetrically copy it for all the other players. This also ensures that all players have the same score, so min score is max score. Symmetrical placement can be easily obtained for two players (top and bottom) and four players (each quadrant). It may still be tricky to find good symmetry for other player numbers, especially given that there could be great variety due to walls.

An idea used by tourist is to only make moves that modify the colour of the cells. Once all the cell colours are fixed one can actually find the optimal placement of the piece types in constant time for each cell. This is a very powerful method for significantly reducing the search space.

The Contest

The contest was very interesting to watch. After an hour or so we started seeing submissions using the floodfill idea. Some people divided the regions chaotically, while others used regular division, such as rectangles. Contestants found it useful to cycle over different region sizes and positions, and then select the best region split to work on further. The leaders changed regularly and it was difficult to tell who is actually winning. Some people took their time to make the first submission as they were experimenting with different approaches. I also noticed that people use very different editors and coding setup. I really liked wleite’s setup. He had a script that automatically populated a database with the best scoring cases. This allowed him to accurately measure the quality of each solution locally.

Towards the end of the contest the leaderboard started playing up and taking a long time to score each submission. Many submissions were stuck in the queue and it was impossible to know how each one was performing. This was very unfortunate and I do hope that these system issues will be resolved soon.

As I write this only the provisional scores are available. Currently tourist is in the lead, closely followed by nika and sullyper. However, this can all change in the final tests. Well done to all the finalists and I wish you good luck! See you next year.