ILP Part 62 – Maximally attacking chessboard

This is the sixtieth second part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to solve a chess problem variation. We want to generate a chess board (with regular pieces for each player) with maximal attacking score. An attack is the same as in chess — a position in which one piece can capture another one in subsequent move.

We are interested in any position, it doesn’t need to be a legal one (so both kings can be under check, pawns can be in any rank or file etc) nor achievable (so we don’t care if there is a sequence of legal moves leading to a given position). We need to use all 32 pieces, no promotions are allowed.

The code is rather trivial, however, it is pretty hard to maximize the function:

In lines 13-32 we define binary flags describing what piece a field is. Next, in lines 34-48 we define some helper variables (to avoid recalculation) and then in lines 50-57 we make sure each field is of an exactly one type (or is empty). Finally, in lines 59-71 we make sure we have correct number of pieces on the board.

Then we define our goal. We start with some helper functions in lines 73-90 and then start adding rules for each piece. Pawns in lines 91-102 are rather trivial, we just check if a pawn attacks one of two neighbours (notice that we number rows from top to bottom so white pawns would move form higher ranks to lower ones). Similarly for knights in lines 104-127 (knight is essentially a pawn attacking some different fields).

Bishops, rooks, queens and kings are based on the same approach. We move farther and farther away from the starting position (whether in rank/file for rooks or diagonally for bishops), calculate a variable if given direction is still allowed (as we cannot “jump over” pieces) and update the state. For queens and kings it’s essentially the same.

Finally, we save the model, solve it and print the solution. Below is an example of some (non-optimal) result:

This is after running for 10 minutes on my machine using CPLEX. However, I ran it through Neos for 8 hours and found solution of value 98 which is presented below:

I actually don’t know if this is the optimal one but according to Gurobi it cannot be higher than 116. Maybe one day I’ll run it for more time to explore all nodes.

We can use this snippet to set a lower bound for the solution:

This allows for getting any solution as soon as possible or improving above something we know is possible.