Chess Concurrent Compress
We take a chess puzzle challenge from 1985, published in Kijk magazine and — since we solved it to optimality before — devise a 2020, harder ‘concurrent’ version of it and solve it again to optimality, again with Integer Programming. Finding the optimal solution to the 1985 version of the puzzle was still doable for some humans (like chess masters). This 2020 version of the puzzle is a lot harder, so maybe grand masters only can manage. Mere mortals will find a feasible but maybe still far from optimal solution. This shows the power and so usefulness of Integer Programming for complex problems, be it in a playful way.
1 What you Will Learn¹
Constructing a solution to a problem from (parts of) solutions of subproblems, which is also the essence of dynamic programming, but then in a recursive way.
In integer programming, user cuts are constraints that are not strictly needed to get a valid solution, but they can help the solver to find solutions or/and the optimal solution more quickly.
Seeing a combined solution, humans can switch on a part of their visual cortex to filter out sub-solutions, but it doesn’t happen automatically.
2 Ye Olde 1985 Chess Compress Challenge
In our previous story, Chess Compress, we took up a challenge published by the kijk.nl magazine back in 1985 where we tried to put as many pieces on a chess board as possible, without any threatening any other. More accurately, we are rewarded a score of 1/n for each piece in a solution, where maximally n pieces of that type can be put on a board without any threatening another. So each queen and rook score 1/8 points, each king scores 1/16 and each bishop scores 1/14, each knight scores 1/32. One then has to come up with a bunch of chess pieces on a chess board that maximises this score. If we restrict ourselves to just one type, the optimal solution is just one. So the challenge is to smartly combine different piece types that are in some way complementary.
Spoiler alert! Optimal solution coming up!
Do not read on if you want to first have a try at it with your personal brain.
You managed to find a solution? Let’s see how it compares to the optimal solution …
For the 1985 version on the puzzle, we had some manual tries but also calculated, via an integer programming solver, an optimal solution. This turned out for the Gurobi solver to output
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
which scores 1.334821 or more precisely 299 / 224, and was found in less than 28 seconds. The solver proved this to be an optimal solution. Rotations of the pieces over multiples of 90 degrees as well as mirroring a this solution over horizontal or vertical axis leads to other optimal solutions. Combinations of rotations and mirroring can lead to other similar solutions. Maybe there are even optimal solutions of an entirely different kind. What is sure is that none will have a higher than 299/224 score.
2 The New and Enhanced 2020 Challenge
Now that this is known, can we make the puzzle harder for humans? Would it then also be harder for the solver?…
What would be harder for humans is to restate the problem so that there are more pieces in the optimal solution. For humans, it is then harder to check the increased interplay between the higher number of pieces.
To allow more pieces in the optimal solution, how about this. Let us remove some constraints between some pairs of chess pieces.
More particularly, let’s remove altogether the constraint(s) playing between pieces of different type. So, in a solution, for example, still a horse is not allowed to threaten a horse, but now a horse can threaten any other type of piece. Intuitively that will lead to more pieces on the board indeed, which in turn may lead to more constraints to be checked altogether in an optimal solution.
As a human, at least one with a preference for an initially structured approach, one would first think of constructing a valid solution for the total problem out of valid sub-solutions to sub-problems. Here, sub-solutions could be the ones to the problems where we restrict ourselves to one chess piece type.
For example, we could know a solution with knights only and could add a (parts of) the solution with bishops only, as for example in this one.
which displays
It’s a bit exhausting, error prone and also boring for a human to calculate the score, but I imagine that for a computer, it must be fun. :) So let’s write a function to do that based on the fen string and the piece weights as the two function inputs.
This outputs
1.357142857142857This solution scores 32/32 for the knights and 5/14 for the bishops, which makes (14 + 5)/14 = 19/14 =1.3571428571428571428… for the total score.
Of course, it’s higher than 1, but not by much. Could one do a lot better? Likely so… One way to find out is via Integer Programming.
3 Towards the Concurrent Solution
We refer to this articles notebook version on GitHub if you want to run things yourself. You will need access to the Gurobi solver, since its python API is what we use there for modelling the problem.
Or if you just want to only read the code and not execute but still understand, you can also refer to our previous medium article Chess Compress.
This Chess Compress Concurrently article relies for 95% on the code developed in ChessCompress and the remainder 5% of code needed is all presented here.
3.1 Teams, assume position, all Pieces get Equal Weights
Hmm, shall we try to piece things together?
Surely we have the constraint saying that any square can contain at most one chess piece. This is formulated as the add_at_most_a_piece_per_square_constraints ChessCompress class method in the code below. This constraint was also required in the Chess Compress version of course.
However, now we also add the function max_pieces_on_board_forbidding_threat_within_own_type_only, which is exactly the main difference with the Chess Compress function called kijk_chess_challenge, which generated the same ‘non-threat’ constraints but between all chess piece pairs, regardless if they belong to the same piece type or not.
We first add these 2 function as is, without regard for solving speed., which leads us so the ‘plain vanilla’ model.
3.1.1 Equal Weights, Plain Vanilla Model
Executing the above prints
Needed 90.975840 seconds to find optimal solution.
I could maximally fit 5 queens, 15 kings, 10 bishops,
26 knights and 7 rooks together on the chess board.
The board setup scores 63.000000.
NKBKNKNR/RNBNQNBB/NQNKNKNK/KBRN1QBN/NBNRNKNK/KBKNRBQN/NRNQNBNK/KNKNKNRNand returns
Now that’s surprising: 63 pieces could be fit but just nothing in that last square! Would you have predicted that? Not me…
Our scoring function, parameterised with the weighting map of a unit score 1 per chess piece confirms the score:
63.0Gurobi took 95 seconds to solve this. Can we improve on that?
3.1.2 Equal Weights, Improving Time to Solution by Adding User Cuts
The above problem takes about 88 to 95 seconds — it varies a bit from run to run — to solve on my laptop. Maybe this time to optimal solution can be improved with adding user cuts? These are constraints that are not strictly necessary (or also called (mathematically) redundant because they can be mathematically derived from the ones already present in the model) but they may help the solver reaching the optimal solution more quickly than with a model not possessing them. Let’s try.
gives
Needed 6.729438 seconds to find optimal solution.
I could maximally fit 5 queens, 15 kings, 8 bishops,
28 knights and 7 rooks together on the chess board.
The board setup scores 63.000000.
KNKNKNRN/NRNBNQNK/KNKNKNBQ/NQN1NRNK/KNKNRNQN/BBQRNKNK/KNRBBNBN/NNNKNKBR
Yes! We only need about 7 seconds when including the user cuts. So this shows how big an effect this can have. In fact user cuts in business questions can come from business logic. It is something the solver cannot automatically identify, but the human modeller can add by having some higher level insight.
The solution has of course the same ‘quality’, objective function value -63 as the previous one without user cuts, but it need not be the same, and indeed here it isn’t. Such is the nature of user cuts.
Let’s double check our score just to be sure.
63.0Ok, that’s correct, since the score should equal the number of pieces on the board here.
3.2 Adding the Correct Weights per Chess Piece
For now, we have weighted pieces with the same weight 1. Maybe if weigh them differently, we get a different structure. Let’s try first without user cuts.
3.2.1 Weighted, Plain Vanilla
gives
Needed 79.650085 seconds to find optimal solution.
I could maximally fit 8 queens, 16 kings, 13 bishops,
16 knights and 8 rooks together on the chess board.
The board setup scores 4.428571.
KBBQKBRB/N1KRNQNK/KN1NRKBQ/BQNKNRNK/BKRN1NQB/QRNKNKNK/BNQNBNBR/RKBKQKBK
Ha, by introduction of these different weights we get that the optimal solution does not contain 63 pieces anymore but only 61. The solver cannot improve the solution by putting any piece on the leftover 3 squares. Double checking with weights all equal to 1 gives
61.0indeed, that’s the amount of chess pieces in this solution.
Double checking the score, but now with the different weights, gives
4.428571428571429indeed.
3.2.2 Weighted, Improving Time to Optimal Solution by Adding User Cuts
Let’s try again with user cuts, to see if this speeds up Gurobi, also in the case of different chess piece weights.
outputs
Needed 16.673932 seconds to find optimal solution.
I could maximally fit 8 queens, 16 kings, 13 bishops,
16 knights and 8 rooks together on the chess board.
The board setup scores 4.428571.
KNKBBQBR/B1NQKRNK/BK1NRNQB/QRNKNKNK/KNRN1NBQ/BQKRNKNK/RNBNQNBB/BKQKBKRK
So this is again a solution with ‘the same’ 61 pieces but not the same positioning as found without user cuts.
61.0and with the correct different weights
4.42857142857142So this is an optimal solution to the 2020 “Chess Concurrent Compress” challenge. The top score, given by this solution found by Gurobi is 4.428571.
Gurobi says: “No other solutions better than -4.428571” and that means it has proven this solution is optimal.
To be totally exact about the final number, we can express it in rational number notation. The 8 queens give score 8/8=1, 16 kings give 16/16=1, 13 bishops give 13/14, 16 knights give 16/32=1/2 and 8 rooks give 8/8=1
together that makes 1 + 1 + (1–1/14) + 1/2 + 1 = 5.5–1/14 = 9/2 -1/14 = (9*7–1)/14 = 62/14.
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=62%2F14. This gives
62/14=4.428571428571428571428571428571428571428571428571428571428...from which the period 142857 can clearly be identified.
So this takes about 17 seconds on my laptop with the same user cuts, compared to about 53 seconds without user cuts.
A significant improvement again.
⃞
3.2.3 Analysing the Structure of the Optimal Solution
There are some remarkable properties to be found in the optimal solution.
First, there are many chess piece types that score a full one (queens, kings and rooks). So these make up a combined score of 3.
Then the combined score of the knights is 16/32, so we can only put half of the number of knight (32) compared to the case where no other pieces would be allowed.
For the bishops we just have 13 i.o. 14 of them in a bishop only optimal configuration.
So are the sub-structures formed per type of piece quite similar to the structures of the optimal solution to the problems of the solution with one allowed piece type only?
We guess they must be. But a human cannot easily separate the combined solution into the per piece type sub-solutions as it’s hard to think away the ones we are not trying to focus on, like also in this case:
or in this case, unless you train your mind a bit on that.
However, a computer is good at it, well, … when taught as by the code below.
Calling this function for queens, we get
Filtering to see only the queens, one gets
sub_fen: 5Q2/3Q4/6Q1/Q7/7Q/1Q6/4Q3/2Q5
sub_score: 1.000000
Note that this is an optimal solution for the maximum (=eight) queens (and no other pieces) problem, and even one possessing some symmetries.
Focussing on the kings in the solution only, we get
sub_fen: K1K5/4K2K/1K6/3K1K1K/K7/2K2K1K/8/1K1K1K1K
sub_score: 1.000000
This is an optimal kings only solution as well, but not the one Gurobi finds with 4 kings in 4 corners of the board. So it is adapted because of the presence of other pieces, but its score does not get lowered by it.
For the rooks, we get
sub_fen: 7R/5R2/4R3/1R6/2R5/3R4/R7/6R1
sub_score: 1.000000
The diagonal is used for only one rook, where it was used for all rooks in Gurobi found optimal solution for the rooks-only problem. But this solution also scores 1 of course.
For the bishops, we get
sub_fen: 3BB1B1/B7/B6B/8/6B1/B7/2B3BB/B3B3
sub_score: 0.928571
So for the bishops we have one less piece then in an optimal solution to the bishops only problem, where we have 14.
For the knights
sub_fen: 1N6/2N3N1/3N1N2/2N1N1N1/1N1N1N2/4N1N1/1N1N1N2/8
sub_score: 0.500000
So we have only half the number of knights compared to the optimal solution to the knight only problem. They are still all on one square color though,
so that much is left of ‘the pattern’.
All in all, I think it’s remarkable that the score of the combined problem is so high.
4 Conclusions
4.1 Time to Optimal Solution
The right user cuts seem to speed up solving these problems to optimality. The extent to which can apparently depend on weights in the objective function.
Indeed when weights of pieces were all 1, adding user cuts lowered solution time from 88 to 7 seconds, but when weights were 1/n with n the maximum possible pieces of its chess piece type possible to put on a chess board without threats, the
time to optimal solution by just adding user cuts went down from 55 to 19 seconds. Nevertheless, in both cases solver time went down, so it is always useful to consider user cuts.
4.2 Decoupling Solutions into Chess Piece Families
By splitting the solution into sub-solutions per each chess family, we see that
a lot of the structures of the optimal solutions per chess piece family
are still present in the solution to the combined problem.
5 Possible Speed Improvements
To minimise total solver time, it may be useful to first solve the problem with weights set to 1 and add user cuts,
which only took 7 seconds, and then insert that solution to the problem with the 1/n weights.
Gurobi and other solvers can be warm started with a valid solution. Doing so may reduced total solver time to solve the combined problems.
6 References
[1] https://github.com/PeterSels/OnComputation/tree/master/ChessCompress
[2] https://gist.github.com/PeterSels/923d2f39fe742fce3cc13065e97c9f57
Footnotes
- What you will learn or reappreciate of you know already.
2. To convert all generated svgs to pngs, to then insert the pngs in this article, we used the following code.
['ThirtyTwoKnightsBoard.svg', 'MaxPiecesBoard.svg', 'OpeningChessBoard.svg', 'FirstMoveBoard.svg', 'MaxPiecesUserCutsBoard.svg', 'SixteenKingsBoard.svg', 'CCC_optimal_board_filtered_b.svg', 'SixteenBishopsBoard.svg', 'CCC_optimal_board_filtered_r.svg', 'EightQueensBoard.svg', 'CCC_optimal_board_filtered_q.svg', 'CCC_optimal_board_filtered_k.svg', 'MaxWeightedPiecesBoard.svg', 'ChessCompressConcurrentPeter1Board.svg', 'CCC_optimal_board_filtered_n.svg', 'MaxWeightedPiecesUserCutsBoard.svg', 'EightRooksBoard.svg']
rsvg-convert -h 320 ThirtyTwoKnightsBoard.svg > ThirtyTwoKnightsBoard.png
rsvg-convert -h 320 MaxPiecesBoard.svg > MaxPiecesBoard.png
rsvg-convert -h 320 OpeningChessBoard.svg > OpeningChessBoard.png
rsvg-convert -h 320 FirstMoveBoard.svg > FirstMoveBoard.png
rsvg-convert -h 320 MaxPiecesUserCutsBoard.svg > MaxPiecesUserCutsBoard.png
rsvg-convert -h 320 SixteenKingsBoard.svg > SixteenKingsBoard.png
rsvg-convert -h 320 CCC_optimal_board_filtered_b.svg > CCC_optimal_board_filtered_b.png
rsvg-convert -h 320 SixteenBishopsBoard.svg > SixteenBishopsBoard.png
rsvg-convert -h 320 CCC_optimal_board_filtered_r.svg > CCC_optimal_board_filtered_r.png
rsvg-convert -h 320 EightQueensBoard.svg > EightQueensBoard.png
rsvg-convert -h 320 CCC_optimal_board_filtered_q.svg > CCC_optimal_board_filtered_q.png
rsvg-convert -h 320 CCC_optimal_board_filtered_k.svg > CCC_optimal_board_filtered_k.png
rsvg-convert -h 320 MaxWeightedPiecesBoard.svg > MaxWeightedPiecesBoard.png
rsvg-convert -h 320 ChessCompressConcurrentPeter1Board.svg > ChessCompressConcurrentPeter1Board.png
rsvg-convert -h 320 CCC_optimal_board_filtered_n.svg > CCC_optimal_board_filtered_n.png
rsvg-convert -h 320 MaxWeightedPiecesUserCutsBoard.svg > MaxWeightedPiecesUserCutsBoard.png
rsvg-convert -h 320 EightRooksBoard.svg > EightRooksBoard.pngPeter Sels, April 22nd 2020.
The code from this article is available as a notebook on Github at https://github.com/PeterSels/OnComputation/tree/master/ChessCompressConcurrently so you could run it yourself and as a gist at https://gist.github.com/PeterSels/965c5ce567daf870d4817e2d8afc1e5b in case you just want to browse code and results without running it.
Copyright © 2020 Logically Yours BV.
