Chess Compress, Revisiting the Kijk 1986 Chess Challenge

Peter Sels

Published in

The Startup

21 min readApr 13, 2020

1 Introduction

1.1 The Challenge

As a 14 year old boy, so in the year 1985, my parents donated me a subscription to “Kijk”, which on its cover, in Dutch, called itself “Populair Wetenschappelijk Maandblad”. This translates as “popular science magazine” rather than “popular scientific magazine”, as it wasn’t so much trying to boast about its high subscription levels but was aiming to awaken interest with readers in general scientific and engineering topics. As far as I am concerned, it managed to do so.

One month, I must have been 15, Kijk published a challenge that intrigued me. It was about trying to place as many chess pieces on a board without any being able to catch any other. You were allowed an unlimited amount (or 64 if you want) of pieces of each type. However, pawns do not participate.

Clearly, if the weight by which you count would be 1 for each type, you’d just put 32 knights on all squares of a chosen color (either black or white) and be done and the score would be 32.

However, instead, each piece is counted with a certain weight depending on its type only. This type weight is equal to one over the number of pieces of that type only you could put on the board without any of the pieces being able to catch any other piece. So a queen would get 1/8 points, as one can put maximum 8 queens on a board without any queen threatening any other queen. The “Eight Queens” problem is in fact quite well known. See https://en.wikipedia.org/wiki/Eight_queens_puzzle.

A king gets 1/16 points, a rook 1/8 points, a bishop 1/14 points and a knight 1/32 points. The idea of the weights scaling is that, the more ‘powerful’ a piece is, the fewer one can typically collect on a board and so the harder it is to get many of them, so the higher the reward must be to fit more of them on the final problem. Fitting 8 queens results in a score of 8 1/8 = 1 but fitting 8 kings only results in a score of 8 1/16 = 1/2.

I puzzled a bit and my dad also helped and then we wrote a letter back to Kijk, which I still remember contained the hand-waving sentence that “Surely, the best solution could not possibly be much better than ours.” A feeling of uncertainty about that claim stuck … until now, when we actually have some tools and some time to find a better solution and also possibly prove its optimality.

I still have all my Kijk magazines at home, bundled in 3 dark blue hard covers, one per year, which you got when you extended your membership with a year. I should look for the issue that published the results of that contest. I only remember there were quite some people that beat us at it which higher scores. So much for the hand-waving argument. But before looking things up, let’s try with a IP (Integer Programming) solver. So it took 34 years for me to have time to reconsider this gem of a challenge. :)

1.2 Spoiler Alert

You may want to have some fun trying to find a good solution before you read on. If you don’t have physical chess pieces this virtual version may help. https://lichess.org/editor/8/8/8/8/8/8/8/8_w_-_-_0_1

1.3 Generating a Clean Visualisation

To motivate ourselves even a bit more, let’s first look for a nice, generatable representation of a chess board with its pieces positioned on it. What about this one? https://pypi.org/project/python-chess/

To install it, just run the next pip3 command from the shell. If you’re in a notebook, prefix it with the first line to indicate to the notebook that the commands following are to be interpreted as shell commands.

%%sh
pip3 install python-chess

Then, in a Python3 notebook, go

import chess
chess.Board()

Ha! Nice! One cannot possibly beat this representation. This took me 1 minute. Long live open source! A good epidemic. :)

To write a python-chess produced chess board to a file you can do

import chess.svg
boardsvg = chess.svg.board(chess.Board())
f = open("OpeningChessBoard.svg", "w") # It only writes to svg.
f.write(boardsvg)
f.close()

By the way, to convert an svg file to a png on a *nix machine, you can do:

rsvg-convert -h 640 OpeningChessBoard.svg  > OpeningChessBoard.png
# on a Mac, first install this tool with: brew install rsvg-convert

python-chess also uses a simple string format to represent a board situation as follows.

chess.Board("rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR")

This generates

This one line string format is called the Forsyth Edwards Notation (FEN), see https://en.wikipedia.org/wiki/Forsyth–Edwards_Notation.
It is easily understood when realising that the 8 subsequent rows are separated by a / and that the numerals stand for the number of empty squares in that row and that lower case letters represent black pieces and upper case letters represent white pieces.

1.4 Sidebar: Incrementally Adding Methods to a Python Class

For this challenge we want to setup an IP model to calculate the weights per piece. Each of these problems has its own variables and constraints that will be reused exactly in the same form for the final problem. Only the final problem will have extra constraints, formulating that there cannot be two pieces of different types on the same board square.

So we will need code to construct an empty model and then various functions that add variables and constraints to this model. This means we build up ‘state’, bit by bit. A logical programming construct to handle that is a Class. Let’s call it ChessCompress.

In regular python, one writes a Class as one piece of code, where variables and methods are contained inside the single Class definition. However, as Notebooks go, we will want to add code (chess) piece by (chess) piece. There is a way to handle that by the use of recursive class definitions.
Consider the example below, which we got from user dsblank’s answer on https://github.com/jupyter/notebook/issues/1243.

So in one Python notebook cell, we write

class MyClass():
    def method1(self):
        print('method1')

and in a later cell, we can extend functionality of this class as

class MyClass(MyClass):
    def method2(self):
        print('method2')

We can then call methods defined previously in an even later cell as

instance = MyClass()
instance.method1()
instance.method2()

which produces

method1
method2

So the first cell is the most regular Pythonic way to define a class and add method1. But the second cell does not simply say class MyClass() again but extends the first class by specifying class MyClass(MyClass). The third cell shows that there is no syntactic difference in calling method1 or method2. This is what we like. We can now proceed in a modular way, cell by cell, enriching the python class definition.

2 Determining the Weights per Chess Piece

We start with calculating the weights of the piece types and begin with the queens problem.

2.1 The Queens Problem

If a queen takes a certain position the diagonals and row and column cannot contain another queen. To encode that, we will define binary variables q[r,c] that are 1 when we decide to put a queen in row r column c and 0 otherwise.

To solve all the below problems, we call the Mixed Integer Programming solver Gurobi (https://www.gurobi.com/) via its Python API. You will need this solver to run this notebook. We have tested this notebook with Python 3.7.6 and Gurobi 9.

So that took only 10 milliseconds. Not a lot. :) We allowed the solver to output its log here, to show you that a solver is called. In the next notebook cells we will avoid that by calling set_solver_output(False) instead.

Let’s now display the 8 queens on the board. We need to generate that string encoding.

This generates

3Q4/5Q2/7Q/2Q5/Q7/6Q1/4Q3/1Q6

We can indeed visually check that each row and column has at most one queen. Also on each diagonal we have at most one queen. This is one solution and there are of course others, even only due to symmetries alone. For example by flipping the queen positions along the horizontal axis or vertical axis in the middle of the board. Also, a multiple of 90 degrees rotations of the queens positions delivers new solutions.

In fact the wikipedia page https://en.wikipedia.org/wiki/Eight_queens_puzzle mentions a more symmetrical version reproduced here below.

Note that the solver Gurobi does not have a preference for this symmetric solution. The objective function of both solutions is the same: 1.

In any case, because we can maximally fit 8 queens, the score of the type queen will be 1/8 in the final problem.

2.2 The Bishops Problem

Hmm, we have done this one before. We should reuse the diagonal constraints we defined for the queens. ‘Not entirely accidentally’, we have written up the queens problem so that we can just call the function add_long_range_piece_variables_and_constraints (piece_letter) with piece letter=’b’ and we’re done with the bishops. Let’s try.

maximum bishops on a board

produces

I could maximally fit 14 bishops on the chess board.
BB2B1B1/8/B6B/B7/7B/B6B/8/BB1B2B1

So 14 bishops can be fitted and the bishops weight in the final problem becomes 1/14.

2.3 The Rooks Problem

Done before for queens. Let’s reuse that. Hmm, I wonder if Gurobi is going to put all the rooks on the diagonal… Let’s see.

gives

I could maximally fit 8 rooks on the chess board.
R7/1R6/2R5/3R4/4R3/5R2/6R1/7R

So 8 rooks can be fitted and the rook’s weight in the final problem becomes 1/8. Yes, the diagonal it is! There are obviously many other possible solutions, all with the same number of rooks: 8. Let’s write up the problem for the kings now.

2.4 The Kings Problem

Kings are like queens in the sense that they can attack or threaten other pieces in the same directions: up, down, left, right and the 4 diagonal directions, but their reach is only one square instead of the whole row, column or diagonal. So the problem is similar, but the constraints only span two subsequent squares in these same directions.

I could maximally fit 16 kings on the chess board.
K1K2K1K/8/K1K2K1K/8/8/K1K2K1K/8/K1K2K1K

Another 10 ms wasted. :) So 16 kings can be fitted and the king’s weight in the final problem becomes 1/16.

Let’s go for the knights problem, which is quite different.

2.5 The Knights Problem

when run gives

I could maximally fit 32 knights on the chess board.
The board setup scores 32.000000.
N1N1N1N1/1N1N1N1N/N1N1N1N1/1N1N1N1N/N1N1N1N1/1N1N1N1N/N1N1N1N1/1N1N1N1N

So 32 knights is the maximum fittable on a board, so they get the weight of 1/32 in the final problem. They are on (all) the squares of one color only, white here, but another solution would be for them on all the black squares.

Let’s summarise by writing a function that calculates the weights for a given board dimension.

k 16
q 8
b 14
r 8
n 32
{'k': 0.0625, 'q': 0.125, 'b': 0.07142857142857142, 'r': 0.125, 'n': 0.03125}

3 The Real Problem

We now add the still missing constraints for the solution to be a valid one.

3.1 One Chess Piece per Square Only

Hmm, shall we try to already piece things together? Surely we still have to add a constraint saying that any square can contain at most one chess piece. This is done by adding the method add_at_most_a_piece_per_square_constraints below.

3.2 Now, also Be Kind to Others

We now impose that chess pieces do not threaten each other on the board.

This outputs

Needed 27.623997 seconds to find this solution.
With this objective, this solution contains: 0 q, 9 k, 6 b, 1 r, 7 n
The board setup scores 1.334821.
This optimal solution's MIP gap equals: 0.00
1R6/N1NBNBNB/8/K1K1K1K1/8/K1K1K1K1/8/K1NBNBNB

and

So this is an optimal solution to the Kijk Chess challenge of 1985 and it only took about 30 seconds to solve! The top score, given by this solution found by Gurobi is 1.334821428571. Gurobi says: “No other solutions better than -1.33482” and that means it has indeed proven this solution to be optimal.

To be totally exact about the final number, we can express it in rational number notation. The 9 kings give score 9/16, 6 bishops give 6/14, 7 knights give 7/32 and the 1 rook gives 1/8, together that makes 9/16 + 6/14 + 7 / 32 + 1/8 = (18 + 7 + 4) / 32 + 6 / 14 = (29 * 7)/(32 * 7) + (6 * 16)/(14 * 16) = 203 / 224 + 96 / 224 = 299 / 224.

By the way, note the periodicity in the decimal number? Any rational number in ℚ is either a terminating or repeating decimal. One can check this with WolframAlpha, via https://www.wolframalpha.com/input/?i=299+%2F+224. This gives

299/224=1.334821428571428571428571428571428571428571428571428571428...

from which the period 142857 can clearly be identified.

▢

Of course, there are some rotate-and-mirror variations of the above solution, which score exactly the same optimal value. One example is this one.

Needed 28.443811 seconds to find this solution.
With this objective, this solution contains: 0 q, 9 k, 6 b, 1 r, 7 n
The board setup scores 1.334821.
This optimal solution's MIP gap equals: 0.00
BNBNBN1K/8/1K1K1K1K/8/1K1K1K1K/8/BNBNBN1N/6R1

A rotation over 180 degrees of the above mentioned solution is also optimal

In fact, this solution was reached automatically by Gurobi, a week later. While Gurobi is deterministic — so should always results in the same output, given exactly the same input — the order of coefficients in the input was changed in that week, which explains an other, but just as good, solution being reached.

4 Problem Variations

We can now easily code variations of the problem.

4.1 A Second Division

So queens do not occur and kings and horses occur abundantly. So what happens if we exclude kings and horses from the game?

outputs

Needed 2.133906 seconds to find this solution.
With this objective, this solution contains: 4 q, 8 b, 0 n
The board setup scores 1.071429.
This optimal solution's MIP gap equals: 0.00
3Q4/BB6/4Q3/7Q/BB6/6Q1/8/BBB2B2

second division board, not allowing kings nor rooks

This took less than 3 seconds. So also with only 2 chess piece types we can get a score above 1. Rooks do not occur here because all empty squares are already under threat. The score of 1.071429 surely is higher than 1 but quite far from the optimal 1.334821428571.

4.2 A Mixed Division

Can we define a problem to which the optimal solution contains all the piece types, by discouraging the use of kings and knights a bit? For that we can give these first division players a small handicap. Let’s try.

leads to

Needed 24.540599 seconds to find this solution.
With this objective, this solution contains: 0 q, 1 k, 7 b, 4 r, 6 n
The board setup scores 1.216667.
This optimal solution's MIP gap equals: 0.00
3R4/N1N1N2B/1R6/6R1/5R2/N3N2B/B3B2N/B1K1B2B

Handicapping kings and knights — by assigning smaller weights to them — still results in knights occurring in the optimal solution (be it with 6 i.o. 7), but also in kings being replaced with a ‘horse and bishop mix’.

The solver took about 25 seconds and makes an interesting combination of 4 piece types but no queens. Queens don’t seem to combine so well with other pieces apart from bishops. The score here 1.216667 should not be compared to the 1.334821428571 since the weights in the objective are different.

4.3 Scaling Down

Scaling down a problem is often a good way to debug a model more easily.

4.3.1 A 4x4 Chess Board

gives

{'k': 0.25, 'q': 0.25, 'b': 0.16666666666666666, 'r': 0.25, 'n': 0.125}
Needed 0.178019 seconds to find this solution.
With this objective, this solution contains: 2 k, 0 q, 0 b, 2 r, 2 n
The board setup scores 1.250000.
This optimal solution's MIP gap equals: 0.00
K . . N 
. . R . 
. R . . 
N . . K

4.3.2 A 3x3 Chess Board

{'k': 0.25, 'q': 0.5, 'b': 0.25, 'r': 0.3333333333333333, 'n': 0.2}
Needed 0.020182 seconds to find this solution.
With this objective, this solution contains: 0 k, 1 q, 0 b, 2 r, 0 n
The board setup scores 1.166667.
This optimal solution's MIP gap equals: 0.00
. . Q 
R . . 
. R .

4.3.3 A 2x2 Chess Board

{'k': 1.0, 'q': 1.0, 'b': 0.5, 'r': 0.5, 'n': 0.25}
Needed 0.000834 seconds to find this solution.
With this objective, this solution contains: 1 k, 0 q, 0 b, 0 r, 0 n
The board setup scores 1.000000.
This optimal solution's MIP gap equals: 0.00
. . 
K .

4.3.4 A 1x1 Chess Board

{'k': 1.0, 'q': 1.0, 'b': 1.0, 'r': 1.0, 'n': 1.0}
Needed 0.000164 seconds to find this solution.
With this objective, this solution contains: 0 k, 1 q, 0 b, 0 r, 0 n
The board setup scores 1.000000.
This optimal solution's MIP gap equals: 0.00
Q

It does not matter much what symbol is chosen here since all pieces have score 1 on a 1x1 board.

4.4 Scaling Up

Scaling up a problem is a good way to check performance for real world applications. Here it’s just play of course or solver testing at best. :)

4.4.1 A 9x9 Chess Board

gives

{'k': 0.04, 'q': 0.1111111111111111, 'b': 0.0625, 'r': 0.1111111111111111, 'n': 0.024390243902439025}
Needed 78.455520 seconds to find this solution.
With this objective, this solution contains: 15 k, 0 q, 8 b, 0 r, 10 n
The board setup scores 1.343902.
This optimal solution's MIP gap equals: 0.00
N B N B N B N B N 
. . . . . . . . . 
K . K . K . K . K 
. . . . . . . . . 
K . K . K . K . K 
. . . . . . . . . 
K . K . K . K . K 
. . . . . . . . . 
N B N B N B N B N

Calculated in 78 seconds, … ooh that’s a nice and regular ‘optimal’ structure! :)

4.4.2 A 10x10 Chess Board

{'k': 0.04, 'q': 0.1, 'b': 0.05555555555555555, 'r': 0.1, 'n': 0.02}
Needed 43.156987 seconds to find this solution.
With this objective, this solution contains: 9 k, 0 q, 8 b, 3 r, 14 n
The board setup scores 1.384444.
This suboptimal solution's MIP gap equals: 0.28
. . . . . . R . . . 
B N B N . N . N . K 
. . . . R . . . . . 
. K . . . N . K . N 
. . . . . . . . . B 
B N B N . K . K . N 
. . . . . . . . . B 
. K . K . K . . . N 
. . . . . . . . R . 
B N B N . K . N . N

A similar structure, calculated in about 43 seconds.

4.4.3 Aa 11x11 Chess Board

{'k': 0.027777777777777776, 'q': 0.09090909090909091, 'b': 0.05, 'r': 0.09090909090909091, 'n': 0.01639344262295082}
Needed 8.304014 seconds to find this solution.
With this objective, this solution contains: 22 k, 0 q, 8 b, 1 r, 12 n
The board setup scores 1.298742.
This suboptimal solution's MIP gap equals: 0.33
K . N B N B N B N . N 
. . . . . . . . . R . 
K . K . K . K . . . N 
. . . . . . . . . . . 
K . K . K . K . K . K 
. . . . . . . . . . . 
K . K . K . K . K . K 
. . . . . . . . . . . 
K . K . K . K . K . N 
. . . . . . . . . . B 
N B N B N B N B . . N

So that took only about 8 seconds to reach the optimal solution, quite a bit less than for the 10x10 board.

4.4.4 A 12x12 Chess Board

The above solution is only the one found after 10 minutes. The optimal solution calculated earlier took 34125.92 to calculate and is:

No other solutions better than -1.42298
Optimal solution found (tolerance 1.00e-04)
Best objective -1.422979797980e+00, best bound -1.422979797980e+00, gap 0.0000%
Needed 34126.014710 seconds to find optimal solution.
With this objective, the best solution contains:
  , 15 k, 0 q, 9 b, 4 r, 19 n
The board setup scores 1.422980.K . N . N . K . N B N B 
. . . R . . . . . . . . 
N . N . N . K . K . K . 
. R . . . . . . . . . . 
N . . . K . K . N . . B 
B . . . . . . . B . . N 
N . K . K . K . N . . B 
B . . . . . . . . . . . 
N . K . N . N . K . K . 
. . . . . R . . . . . . 
K . K . N . N . N B N B 
. . . . . . . R . . . .

4.4.5 A 13x13 Chess Board

{'k': 0.02040816326530612, 'q': 0.07692307692307693, 'b': 0.041666666666666664, 'r': 0.07692307692307693, 'n': 0.011764705882352941}

After the allowed 3 minutes, we get the solution:

Needed 180.091648 seconds to find this solution.
With this objective, this solution contains: 35 k, 0 q, 12 b, 0 r, 14 n
The board setup scores 1.378992.
This suboptimal solution's MIP gap equals: 0.27
N B N B N B N B N B N B N 
. . . . . . . . . . . . . 
K . K . K . K . K . K . K 
. . . . . . . . . . . . . 
K . K . K . K . K . K . K 
. . . . . . . . . . . . . 
K . K . K . K . K . K . K 
. . . . . . . . . . . . . 
K . K . K . K . K . K . K 
. . . . . . . . . . . . . 
K . K . K . K . K . K . K 
. . . . . . . . . . . . . 
N B N B N B N B N B N B N

Solving the above problem did instead take 10668 seconds when run up to the optimal solution, which is:

Optimal solution found (tolerance 1.00e-04)
Best objective -1.467456213255e+00, best bound -1.467456213255e+00, gap 0.0000%
Needed 10668.292165 seconds to find optimal solution.
With this objective, the best solution contains:
  , 22 k, 0 q, 10 b, 4 r, 25 n
The board setup scores 1.467456.
K . K . K . N . N B N B N 
. . . . . . . R . . . . . 
K . K . N . N . . . K . K 
. . . . . R . . . . . . . 
N . K . N . N . N B N B N 
B . . . . . . . . . . . . 
N . K . K . K . K . K . K 
B . . . . . . . . . . . . 
N . . . K . K . N B N B N 
. R . . . . . . . . . . . 
N . N . N . K . K . K . K 
. . . R . . . . . . . . . 
K . N . N . K . N B N B N

4.4.6 A 14x14 Chess Board

From here onwards, things take more time. After 90000 seconds the solver was only just below 5% removed from the lower bound to the optimal solution.

gives

{'k': 0.02040816326530612, 'q': 0.07142857142857142, 'b': 0.038461538461538464, 'r': 0.07142857142857142, 'n': 0.01020408163265306}
Needed 180.091715 seconds to find this solution.
With this objective, this solution contains: 25 k, 0 q, 9 b, 5 r, 21 n
The board setup scores 1.427786.
This suboptimal solution's MIP gap equals: 0.28
B . . . . . B . B N B N B . 
N . K . K . . . . . . . . . 
. . . . . . . R . . . . . . 
K . K . N . N . N . K . K . 
. . . . . R . . . . . . . . 
K . K . N . N . K . K . K . 
. . . . . . . . . . . . . . 
K . N . N . K . N B N B N . 
. . . R . . . . . . . . . . 
N . N . N . K . K . K . K . 
. R . . . . . . . . . . . . 
N . N . K . K . K . K . . . 
. . . . . . . . . . . . . R 
K . K . K . K . N B N B N .

The above is calculated in a 3 minutes time restriction.
One run took 90000 seconds to calculate a solution still 5% removed from the lower bound to the optimal solution.

4.4.7 A 15x15 Chess Board

after 3 minutes, gives

{'k': 0.015625, 'q': 0.06666666666666667, 'b': 0.03571428571428571, 'r': 0.06666666666666667, 'n': 0.008849557522123894}
Needed 180.107001 seconds to find this solution.
With this objective, this solution contains: 35 k, 0 q, 14 b, 3 r, 27 n
The board setup scores 1.485813.
This suboptimal solution's MIP gap equals: 0.20
N B N B N . N . K . N B N B N 
. . . . . R . . . . . . . . . 
K . K . . . N . K . K . K . K 
. . . . . . . . . . . . . . . 
N . K . K . K . K . K . K . N 
B . . . . . . . . . . . . . B 
N . K . K . K . K . K . K . N 
B . . . . . . . . . . . . . B 
N . K . K . K . K . K . K . N 
B . . . . . . . . . . . . . B 
N . K . K . N . N . K . K . N 
. . . . . . . R . . . . . . . 
K . K . K . N . N . . . K . K 
. . . . . . . . . R . . . . . 
N B N B N . K . N . N B N B N

4.4.8 A 16x16 Chess Board

gives 3 minutes later

{'k': 0.015625, 'q': 0.0625, 'b': 0.03333333333333333, 'r': 0.0625, 'n': 0.0078125}
Needed 180.032649 seconds to find this solution.
With this objective, this solution contains: 34 k, 0 q, 12 b, 6 r, 28 n
The board setup scores 1.525000.
This suboptimal solution's MIP gap equals: 0.22
. B . . . B . . . B . . . B . . 
. N . K . N . K . N . K . N . K 
. B . . . B . . . B . . . B . . 
. N . . . N . K . N . K . N . K 
. . . . R . . . . . . . . . . . 
. N . N . N . K . K . K . K . K 
. . R . . . . . . . . . . . . . 
. N . N . K . K . K . K . K . K 
R . . . . . . . . . . . . . . . 
. N . K . K . K . . . N . K . K 
. . . . . . . . . . R . . . . . 
. K . K . N B N B N . N . N . K 
. . . . . . . . . . . . R . . . 
. K . K . K . K . K . N . N . N 
. . . . . . . . . . . . . . R . 
. K . K . N B N B N . K . N . N

The CO₂/fun ratio is getting too high here so we’ll stop the fun here.

5 Other Ways to (Almost) Get There and Beyond

Apart from Integer Programming, one can also use constraint programming (e.g. with IBM © CPOptimizer) to get to the same solution in one minute calculation time as a colleague of mine demonstrated.

As for artificial intelligence techniques, a nice challenge would be to solve this with reinforcement learning.

Apart from that, one can keep using ones own natural intelligence. Another colleague of mine found the optimal solution right away, but yeah, he is a chess master. But also my 17 year old nephew Edward came up with the next two sub-optimal but attention deserving solutions.