A machine that composes chess problems

The world’s most advanced automatic chess problem composer

By Azlan Iqbal, Ph.D.

Abstract: Automatic chess problem composers are relatively rare compared to chess-playing programs. This is arguably because they are expected to demonstrate more creativity than is needed to just play well; and because creativity, as a process, is still poorly understood scientifically. In previous research, a computational chess aesthetics model was developed and incorporated into a computer program called Chesthetica that can be used to automatically evaluate the beauty of thousands of three-move chess problems in a way that correlates well with human assessment. However, this alone was insufficient to imbue a computer with the ability to independently compose chess problems that people might find interesting. So a new artificial intelligence approach called the DSNS (digital synaptic neural substrate) was developed that enables a computer to become ‘inspired’ by the different types of objects fed into it, such as photographs of people, painting masterpieces, classical music, chess tournament games and other chess problems. Using this technology, the same computer program is now often able to compose challenging and interesting three-move chess problems entirely on its own and indefinitely. Furthermore, the DSNS technology is scalable and can, in principle, be applied to any domain that requires creativity, such as protein folding which is important in the search for cures to many diseases.

In previous articles on ChessBase, I have explained my work in computational aesthetics with regard to chess. The most recent academic paper about the chess aesthetics model was published in 2012 [1]. Since then, however, I have somewhat shifted my attention to computational creativity using chess as the research domain, just as my predecessors in artificial intelligence (AI) used chess to study ‘typical’ intelligence back in the 1950s. This means, for example, the development of approaches and techniques in AI (of which both computational aesthetics and computational creativity are sub-fields) that give computers the ability to compose chess problems or constructs that certainly require – if done by humans, at least – what we would call ‘creativity’.

Indeed, in the last couple of years under a new research project [2], I developed – and with the help of my project members, tested – a new AI approach called, the ‘digital synaptic neural substrate’ (DSNS) which uses fragments of information from chess and other domains such as photos, paintings and music to aid in the creative process. A scientific paper with regard to that is still under review. The basic idea is that humans perceive many different types of information in their lives which mingle in poorly-understood ways in the brain and this somehow, sometimes results in creativity. I programmed a new creativity module based on the DSNS approach into Chesthetica (my original chess aesthetics evaluation program) in order to run our experiments.

Azlan Iqbal met and wrote about Garry Kasparov's visit to Malaysia in April this year

Essentially, the DSNS approach uses extracted (arbitrary) attribute values of pairs of objects from the same or different domains, and arranges them as ‘strings’ that can be used to produce other, new strings for use in either of the original domains. So if a three-move mate sequence taken from a tournament game (described with attributes: piece value, number of white pieces, number of black pieces, year played and material difference) is combined with a photo (described with attributes: number of pixels, number of colours, number of objects in the photo, brightness and contrast), the DSNS approach will produce the necessary attributes from either domain required to ‘build’ a new object, i.e. either a new three-move mate sequence or a new photo.

The ‘building component’ is separate. Imagine a box-building device or factory where you only needed to supply the color, material to be used, height, width and depth measurements to build a new box. The DSNS approach supplies all this information having been ‘inspired’ by other boxes, and perhaps tables, chairs, paintings, photos and music. Chesthetica, which also has a building component to create chess problems, uses the information from the DSNS process to do so and can filter the problems created based on specified user requirements. The beauty of the approach is that neither the two domains nor their attributes need have anything in common semantically. This should be no more surprising than when an artist says he painted the magnificent landscape after having had two drinks and thinking about a former girlfriend. Why the DSNS approach works at all is still an open question. We have only been able to demonstrate experimentally that it does work.

The DSNS approach is independent of the aesthetics evaluation technology developed earlier on. The main reason is that it is quite challenging to make the aesthetics evaluation algorithms function as a heuristic in the composing process. It can only be used as an optional filter for the compositions generated. Think of an art critic (analogous to the aesthetics model) and how this person’s skill or ability does not necessarily translate into the ability to actually create amazing art. So my previous research into chess aesthetics – while useful in evaluating beauty in the game, especially with regard to large databases too cumbersome for humans or where ‘objectivity’ is critical – was not very useful in the work pertaining to the DSNS approach itself. However, I did use Chesthetica to evaluate the submissions for the recent ChessBase chess constructs contest. If I did not agree with its assessment, I would have used my own ranking of the submissions but, all things considered, I actually found myself in agreement with it; so I have no qualms about this. Having said that, was that then the first international composing tournament where the human participants were judged by a computer and did not know the difference? In a manner of speaking, yes... but this is a question best left to philosophers of AI, I think.

White to play and mate in three: example of a computer generated chess problem

Returning to the DSNS experiments, we found that ‘information perceived’ from three-move mate sequences (not necessarily forced) taken from real games between weak players (Elo<1,500) used in combination with information perceived from photographs of people (not selfies) produced the highest quality compositions, on average, based on the aesthetics model. Even better than high quality compositions by humans used alone or in combination with classical music, painting masterpieces or computer-generated abstract art. This was based on a standard set size of 300 objects from each domain and ten attributes per object for a total of 6,000 data fragments if two domains were used. The DSNS can, in principle, draw from much larger pools of data and from even more than two domains. However, it is not clear if simply using more data and more domains improves results significantly.

We also found that using real photographs produced better results than ‘garbage’ image data randomly generated. The reason for this is not clear yet as there seems to be no semantic relationship between chess and photos of people but the experimental results are what they are. Similarly, creativity as it arises in human brains is also not entirely clear. There are actually many findings with regard to the DSNS which are difficult to get into sufficient detail here, so interested readers are advised to wait for the approximately 25,000-word published research article. Here are some examples of the photos and tournament game sequences used in the experiments.

Examples of the photographs of people used

Cute, beautiful and lovely kids on Pinterest by Patricia St Louis (2013)

Mark Wahlberg and Kate Mara: Shooter (motion picture), Paramount Pictures

Examples of the tournament game sequences between weak players used

Nyenhuis,Yannek (964) - Hellwig,Immo (1060) [D32]
Niedersachsen-chT U10 Rotenburg (5.1), 05.06.2005

27.Bd6+ Ka8 28.Rxe8+ Rd8 29.Rxd8# 1-0.

Gubela,Hans Erich Constant (1460) - Wulf,Constanze (1047) [B07]
GER-ch U12 Willingen (3), 12.05.2008

44.h4+ Kxh4 45.Qxg6 f3 46.R7e4# 1-0

A notable point is that the DSNS approach is scalable and can be applied to any field that requires creativity. So it can, in principle, be used to generate paintings, music and designs of objects that would be deemed creative by humans. I am, in fact, in the process of applying for research grants looking into its applicability in protein folding which has a complexity that dwarfs that of chess and is critical in developing cures to diseases. Proteins are basically the tiny machines of the body that do most of the heavy lifting with regard to keeping us healthy. The problem lies in which protein ‘designs’ will get the job done right. A protein molecule could easily have 20^200 different ways of being assembled; most of them useless to any given task. So relentless creativity to cut through a lot of that ‘design space’ is certainly required.

Just as we need machines to help us lift and move heavy objects and travel great distances, we may need creative machines to solve problems beyond what we are capable of solving as well. Unfortunately, this is not something governments or medical organizations typically throw much money at, assuming one could even find research partners willing to take a chance and the availability of a ‘protein building/testing’ system to which the DSNS can be ‘plugged in’. I am completely unqualified myself with regard to protein folding, by the way. There are therefore many hurdles in scientific work and probably less than 1% of proposals and discoveries actually make it all the way to the public in any functional form. Especially work that requires serious collaboration and understanding between scientific fields that traditionally could not be further apart.

In any case, using the DSNS technology, Chesthetica (presently in version 9.45) is able to compose three-move mate problems (or mostly constructs, for the purists) with theoretically no limit. Even as I write this, I have two computers working around the clock composing chess problems at a rate of about one composition every two hours, even though this varies greatly. Sometimes, a single composition can take six hours and sometimes two are produced within half an hour. Processing power and memory do not seem to influence the output rate. I also have no more idea what Chesthetica is going to create than you, the reader, do. Creativity, it would seem, does not necessarily require what we call ‘consciousness’; not that I can actually prove that Chesthetica or any other program is not conscious on some level.

Every few days in the morning, I go over what my computers have come up with and select the compositions that interest me, putting them in a PGN database. Duplicate compositions based on the DSNS approach have to date never been found to happen but Chesthetica has built-in mechanisms to detect and then remove them, in any case. In the diagrams below you will find some examples of the generated compositions (solutions at the end of the article); all White to play and checkmate in 3 moves. By the way, in a previous article, the compositions shown in Figure 2 were actually all created using Chesthetica as well. It is a better composer than I am. Here is a video clip of the program at work:

I am in the process of collecting the compositions generated – there are hundreds featuring all sorts of ideas and motifs – and hopefully publishing them in a ‘Book of Constructs, Vol. 1’ soon, if I can find a willing publisher and perhaps a chess expert to work with (e.g. in selecting the best ones). I suppose this may then be the first book featuring compositions generated entirely by computer, a task typically dominated by only human composers. Given enough machines and more time, volumes 2 and 3 should soon be on the way as well. Will we one day perhaps also see composing tournaments between computers just as there are computer chess-playing tournaments today? I would say the future of chess is still an interesting one for those who had their doubts.

References

1. Azlan Iqbal, Harold van der Heijden, Matej Guid and Ali Makhmali (2012). Evaluating the Aesthetics of Endgame Studies: A Computational Model of Human Aesthetic Perception, IEEE Transactions on Computational Intelligence and AI in Games: Special Issue on Computational Aesthetics in Games, Vol. 4, No. 3, pp. 178-191. ISSN 1943-068X. e-ISSN 1943-0698 [PDF]
2. Azlan Iqbal (Project Leader) (2012). A Computational Model of Human Creativity in a High Complexity Domain (01-02-03-SF0240; RM 126,550; May 2012 – January 2014; COMPLETED). Other members: Dr. Matej Guid (FIDE Master, AI Laboratory, University of Ljubljana, Slovenia), Dr. Cameron Browne (Queensland University of Technology, Australia; Computational Creativity Group, Imperial College, UK), Dr. Simon Colton (Department of Computing, Imperial College, UK), Jana Krivec (Woman Grandmaster, Department of Intelligent Systems, Jožef Stefan Institute, Slovenia), Boshra Talebi Haghighi and Shazril bin Azman (Research Assistants). Ministry of Science, Technology and Innovation (MOSTI) : eScienceFund

Chess problems created by Chesthetica

The problems below include the exact dates and times Chesthetica created the compositions. Typically, human composers do not create more than one problem per day (in some cases only one per month). But with machines the time index is relevant: Chesthetica may compose ten or twelve on the same day.

White to play and mate in three 14/9/2014 3:16:47 PM		White to play and mate in three 17/9/2014 3:55:26 PM
White to play and mate in three 17/9/2014 4:47:29 PM		White to play and mate in three 20/8/2014 7:04:40 PM
White to play and mate in three 19/9/2014 8:14:57 AM		White to play and mate in three 24/9/2014 1:51:11 PM
White to play and mate in three 28/9/2014 3:40:07 AM		White to play and mate in three 11/10/2014 11:23:36 AM
White to play and mate in three 3 /9/2014 10:33:18 PM		White to play and mate in three 25/9/2014 6:21:59 AM

Solutions

Select games from the dropdown menu above the board

Previous articles by the author

• 9/2/2009 – Can computers be made to appreciate beauty?
  Or at least to identify and retrieve positions that human beings consider beautiful? While computers may be able to play at top GM level, they are not able to tell a beautiful combination from a bland one. This has left a research gap which Dr Mohammed Azlan Mohamed Iqbal, working at Universiti Tenaga Nasional, Malaysia, has tried to close. Here's his delightfully interesting PhD thesis.

• 12/15/2012 – A computer program to identify beauty in problems and studies
  Computers today can play chess at the grandmaster level, but cannot tell a beautiful combination from a bland one. In this research, which has been on-going for seven years, the authors of this remarkable article show that a computer can indeed be programmed to recognize and evaluate beauty or aesthetics, at least in three-move mate problems and more recently endgame studies. Fascinating.

• 2/2/2014 – A new, challenging chess variant
  Ever since desktop computers can play at its highest levels and beat practically all humans, the interest of the Artificial Intelligence community in this game has been sagging. That concerns Dr Azlan Iqbal, a senior lecturer with a PhD in AI, who has created a variant of the game that is designed to rekindle the interest of computer scientists – and be enjoyable to humans as well: Switch-Side Chain-Chess.

• 5/11/2014 – Kasparov in Malaysia
  He was mobbed, but in a good way: a large number of chess fans and autograph hunters sought close contact to the legendary World Champion, who officiated the opening of the PMB National Age Group Championship 2014, and took time to discuss a variety of topics with an expert on aesthetics-recognition technology in chess, our author Dr Azlan Iqbal – who sent us a big pictorial report.

• 6/29/2014 – Azlan Iqbal: Introducing ‘Chess Constructs’
  People love brilliancies from chess history – and artistic chess problems. But there is a big gap between the two. Positions from games demonstrate the natural beauty of actual play, while chess problems are highly technical, with little practical relevance. The author of this interesting article suggest an intermediate form, one you can try your hand at – and win a prize in the process.

• 7/26/2014 – Best ‘Chess Constructs’ by ChessBase readers
  Chess constructs are basically an intermediate form of composition or chess problem, lying somewhere between brilliancies from chess history – and artistic chess problems, between real game sequences and traditional award-winning compositions. A month ago Dr Azlan Iqbal explained the concept asked our readers to submit compositions of their own. Here are the winners.