Four knights vs queen challenge

by Frederic Friedel
9/8/2017 – It is a seven-piece ending over which Troitzky once toiled. In the meantime endgame databases have mastered it and can solve billions of non-trivial positions, each in an instant. But can a computer program be taught to generate interesting studies or problems with the given material? KI researcher Dr Azlan Iqbal has instructed his software to try, and it has produced a mate-in-five. We ask our readers: can you do better?

Endgame four knights vs queen

In an article Troitzky: In Memoriam by Prof. Nagesh Havanur, published in March last year, AI scientist Prof. Azlan Iqbal came across the following quote:

“When I imagine Troitzky in his Siberian forest, surrounded by howling wolves, analyzing night after night whether king plus four knights can always beat king plus queen, that is great. That’s what chess is all about, only you have to be a chess player to appreciate it. How can you explain to a non-chess player that within chess there is a little world of endgame studies… within which there is a microcosm made of utterly mad men analyzing four knights against queen.” – Tim Krabbé, Chess Curiosities

Inspired by this passage Dr. Iqbal, who has a Ph.D. in Artificial Intelligence and is a senior lecturer at Universiti Tenaga Nasional, Malaysia, decided to turn his attention to the endgame four knights against a lone queen, which was part of the 7-man Lomonosov tablebases calculated in 2012 at the Computer Science department of Moscow State University. It contains the exact evaluations (draw or moves to mate) for all positions with seven (or less) pieces on the board. The total number of positions is more than 500 trillions – 500,000,000,000,000! The true number is in fact several times larger, but many of the positions can be obtained from others by mirroring and rotating of the board, so there is no need to store them on disks.

Storing 500 trillion positions, together with evaluations and best move for each, would require 1000 hard drives with petabytes of data on them. Fortunately there is a possibility to compress the data, and 100 Terabyte of data turned out to be enough to store the information. Of course that does not fit on regular desktop or notebook drives, so the Russians created a special site and made the information available for online access. And this is what Azlan Iqbal used to study the NNNN-Q endgame.

First came a survey of chess problem and puzzle books published in the last 50 years or so. This did not reveal any existing compositions using the four knights vs. queen – hardly surprising since chess problems tend to avoid promoted pieces in the starting position. Azlan only managed to find a YouTube video showing a particularly long mate with the NNNN-Q material. No composer or source is mentioned, and not all the moves or even the length of the total solution are shown, but the initial position is real and valid. You can try playing it out against Fritz on this page.

_REPLACE_BY_ADV_1

A strong chess engine will show the position as essentially drawn, and it is extremely difficult to beat it. The 7-man Lomonosov tablebases, on the other hand, tell us that it is a forced mate in 89 moves. Interestingly, the position was published on YouTube in 2008, four years before the development of the first 7-piece endgame tablebase. The solution in the video may not be the most optimal one, but whoever composed the study was correct in thinking that it was indeed a forced mate – even though they could not have been certain of it.

To illustrate how important or delicate the initial position is using these pieces, take a look at the following position:

Here, the knight is simply moved from the e1 to c8, but the Lomonosov tablebases evaluate the position as a draw, given optimal play by both sides! We do not give you the moves and, heaven forbid, all the possible variations of these positions, but you are welcome to play them out against our online Fritz program and see if it defends (or attacks) competently. Kudos if you can win the first position, compliments to the computer if it can successfully defend the second.

There are probably tens of billions of positions where none of the knights are under threat of immediate capture (or trapped or hanging). Most of these positions are likely to be wins or draws for White, some like the above in up to 89 moves. But it is clear that very few of these positions would be considered appealing to human chess enthusiasts.

So how to extract the interesting ones? This is where Chesthetica comes in. This program, well known to our readers, was developed by Dr Iqbal and uses Digital Synaptic Neural Substrate (DSNS) technology to try to identify positions that are not just sound but also aesthetically pleasing. The articles listed in the links at the bottom of this article trace the development of Chesthetica in great detail.

A recent addition to Chesthetica is that it can now compose studies using particular piece sets. In the above screen shot (click to enlarge) you can see that four knights and one queen is selected, and certain other parameters set which are meant to extract study-like positions. All the four problem types are selected, and a number of conventions applied: no cooked problems, no check and no capture in the key move), no ‘cooked’ problem, i.e. an additional key move not intended by the composer. Applying these conventions helps ensure that the composition is not simply one where the key move was say, forking the king and queen and then winning the queen. That would not be particularly interesting or having aesthetic merit.

Given the rarity and complexity of forcing a win with the pieces, it was quite surprising to Dr. Iqbal when Chesthetica managed to compose the following position in just ten days of computing, using a small personal computer.

You can try solving against Fritz and find the forced mate in five moves. Chesthetica evaluates this composition as scoring 3.086 aesthetically, which is rather good and definitely within the class of what most human players with domain competence would consider a chess problem.

We were not deeply impressed by the problem and wrote to Azlan: "The problem composed by Chesthetica does not appear to be valuable: Black loses the queen on move two, which is only slightly better than losing it to a fork on move one?!"

To this Dr Iqbal wrote back: "Indeed the problem may not be the most beautiful forced mate in five there could possibly be, using these pieces, but that was never the intention. The fact that a computer could compose such a thing at all is what is a milestone for computational creativity in this area. Do you know of any other program that can do that? How about any 10-12 year human child who has been playing for a few years? Why not set up the pieces for these children and see what they come up with? As for the one composed by Chesthetica, there is no check, capture or fork in the key move and so that's not bad for a small computer that did not refer to an omniscient 7-piece endgame tablebase in the composing process."

So here's the challenge: can any of our readers come up with a nice, aesthetically pleasing mate problem, let us say mate in five, using four knights against a lone queen? Problemists, can you do something exceptional – like no early capture of the queen? We will anxiously await your submission (subject: "Four knights" please).

For the best effort there will be a prize of a Deep Rybka program signed by some of the best players in the world.

 
Links


Editor-in-Chief of the ChessBase News Page. Studied Philosophy and Linguistics at the University of Hamburg and Oxford, graduating with a thesis on speech act theory and moral language. He started a university career but switched to science journalism, producing documentaries for German TV. In 1986 he co-founded ChessBase.
Feedback and mail to our news service Please use this account if you want to contribute to or comment on our news page service



Discuss

Rules for reader comments

 
 

Not registered yet? Register

TMMM TMMM 9/9/2017 04:55
Depending on how the table bases are indexed, isn't finding such positions a matter of "lookups" rather than "computations"? I would say you just query that database for positions with mate in 5 say, eliminate those where there is a capture on the first move, and look at the results. Are you saying that Chesthetica does not use these table bases and somehow computed those positions from scratch? (In that case I would say that's both impressive and stupid.)
1