MIP Knights

Introduction

I play a bit of chess and enjoy solving chess problems, so when someone showed me this problem writen by the chess grandmaster Ben Finegold ¹ I first had a go at solving it (manually) and then wondered if I could phrase it as a mixed integer programming (MIP) problem. Turns out you can!

The rules of problem are as follows:

• Throughout the problem a white queen stays unmoved on the D5 square
• A black knight, which can move, starts off on the H8 square,
• The knight is not allowed to capture the queen,
• The knight moves around the board using standard chess knight move rules ² but isn’t allowed to land on a square attacked by the queen at any point,
• To complete the game the knight has to land on every (un-attacked) square on the board, in sequence, moving from right to left along the eighth rank (H8, F8, E8, C8, B8) and then from right to left on the seventh rank (H7, G7, E7, C7, A7), and so on.

MIPs seem like a good fit for this since the problem is discrete and there is a clear objective function which can be expressed in integer terms - minimise the moves taken to complete the board.

TL;DR - just give me the code! See ³.

Building the general solver

The solver I built is actually a bit more general than the one needed to solve the problem in ¹. It solves the problem:

“Taking $K$ knight initial positions and $Q$ queen initial positions, touch every one of a pre-determined set of squares at least once”

which easily collapses to the problem in ¹ by taking $K=Q=1$ and solving a series of problem like “starting at H8, complete the board where the only objective square is H6”, and then “starting at H6, complete the…”

So how does the general solver work? We have three main variables in the model, all of which are binary:

• $X$: a 4D array of binary variables with dimension $(N,N,T,K)$. $i$ and $j$ index over the chess board $i,j=1,\dots ,N$. Where $T$ indexes over time steps $t=1,\dots ,T$ and $K$ indexes over the knights on the board $k=1,\dots ,K$. $X[i,j,t,k]=1$ implies that knight $k$, is at square $(i,j)$ on the chess board at time $t$ (although a chess board is $(8,8)$ in the code it is flexible, parametrised by $N$, so you can play with bigger or smaller boards if you wish),
• $Y$: a 2D array with dimension $(N,N)$. $Y[i,j]=1$ implies at least one of the knights has visited square $(i,j)$,
• $Z$: a 1D array with dimension $(T,)$. $Z[t]=1$ implies that at least one knight move was made at time $t$.

The code has two additional variables, $M$ and $S$, which track the number of knight moves made and the number of timesteps used to complete the problem (resp.) but they are really just syntactic sugar so I’ll just work with $X$, $Y$ and $Z$ here.

Most of the constraints in the model are on $X$. I won’t show all of them in code because they read quite similarly – I’ll just list the ‘boring’ ones and then go through the fun ones in more detail in a moment. The ‘boring’ ones then:

• At $t=0$ we must set which $(i,j)$ each knight is at (it’s determined by the user),
• At no point in time can any knight have $X[i,j,t,k]=1$ if $(i,j)$ is attacked by the queen,
• No two knights can share a square $(i,j)$ at the same point in time, $t$,
• $Y[i,j]=1$ can only be true if one of the knights as visited $(i,j)$ at some point in time.

And now the fun ones

• Each knight can be in at most one place on the board at each point in time. The interesting bit here is that the inequality is not strict, which allows the model to remove knights from the board when they are no longer needed (e.g. when all the squares have been visited by a knight). This trick lets us track the number of knight moves taken and minimise it. Gurobi’s addConsts accepts a python generator which lets us express a large number of constraints in one go:

model.addConstrs(
    (
        lp.quicksum(X[i, j, t, k] for i in range(N) for j in range(N)) <= 1
        for t in range(T)
        for k in range(K)
    ),
    name="knights_one_square_at_a_time_each",
)

• Knight moves: This is effectively ‘conservation of knights’. We’re saying that at time, t, knight, $k$ can only be at (i, j) if that same knight was one legal knights move away at time $t-1$. In code:

model.addConstrs(
    (
        X[i, j, t, k] <= lp.quicksum(X[move_x, move_y, t - 1, k] for move_x, move_y in legal_moves(i, j, knight_moves, N))
        for i in range(N)
        for j in range(N)
        for t in range(1, T)
        for k in range(K)
    ),
    name="legal_moves",
)

Finally, in order to track the timesteps we use the fact that if any knights are on the board at time, $t$, then we need to include it as a timestep. Again this only works because the model is allowed to remove knights from the board. In code:

model.addConstrs(
    (
        lp.quicksum(X[i, j, t, k] for i in range(N) for j in range(N)) <= Z[t]
        for t in range(T)
        for k in range(K)
    ),
    name="timestep_tracking",

The sum of $Z$ is then the number of timesteps. This is the objective function for the optimiser to minimise.

Solving the general case model

We’re ready to solve it! The objective function is also configurable with three options:

• No objective function: Just try and find a feasible solution. It’s not very exciting but it solves really quickly,
• Minimise the number of knight moves: This and the next option are the same when there is only one knight, but gets interesting when we play with multiple knights…
• Minimise the number of time steps: Actually in this mode it’s a heirarchical optimisation. We first minimise the number of timesteps and then within that minimise the number of knight moves. Doing this makes the model realise that it can remove some knights from the problem early if it doesn’t need them.

Solving with the MINIMISE_TIME_STEPS objective:

import chess
from mip_knights.knight_problem import KnightProblem, ObjectiveChoice

knight_problem = KnightProblem(
    [chess.H8],
    [chess.D5],
    objective_choice=ObjectiveChoice.MINIMISE_TIME_STEPS,
)

knight_problem.solve()

print(knight_problem.get_number_of_moves())
>>> 46

Solving the Finegold problem

As explained above we can now express the original Finegold problem as a series of these problem stitched together. In terms of code there is a separate class, KnightTransportProblem, which derives from the KnightProblem but specialises to solving the A-to-B knight problem for a single knight. The FinegoldProblem class then holds and solves a chain ofKnightTransportProblem.

import chess
from mip_knights.finegold_problem import FinegoldProblem

finegold = FinegoldProblem()
finegold.solve()

print(finegold.get_number_of_moves())
>>> 158

Making it fancier…

Apparently very good chess players can solve the Finegold problem pretty easily (it took me a fair while!). But the MIP solver can do fancier things like:

• Solving boards quicker using multiple knights and teamwork,
• Solve harder boards with multiple queens
• Solving different initial conditions,
• Finding the initial positions for $K$ knights which solves a given queen position fastest

For instance:

which is cool because the interaction between the knights is, I think, quite a bit harder to reason about when planning an optimal route for solving the problem.

References