A machine that composes chess problems

by Azlan Iqbal
11/7/2014 – Chess problems are an art – positions and solutions, pleasing to the mind and satisfying high aesthetic standards. Only humans can compose real chess problems; computers will never understand true beauty. Really? Dr Azlan Iqbal, an expert on automatic aesthetic evaluation, imbued his software with enough creativity to generate problems indefinitely. The results are quite startling.

ChessBase 14 Download ChessBase 14 Download

Everyone uses ChessBase, from the World Champion to the amateur next door. Start your personal success story with ChessBase 14 and enjoy your chess even more!


Along with the ChessBase 14 program you can access the Live Database of 8 million games, and receive three months of free ChesssBase Account Premium membership and all of our online apps! Have a look today!

More...

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

Dr. Mohammed Azlan Bin Mohamed Iqbal received the BSc and MSc degrees in computer science from Universiti Putra Malaysia (2000 and 2001, respectively) and the Ph.D. degree in computer science (artificial intelligence) from the University of Malaya in 2009. He has been with the College of Information Technology, Universiti Tenaga Nasional since 2002, where he is senior lecturer (class A). Azlan is a member of the ICGA, IEEE, AAAI, AAAS and chief editor of the electronic Journal of Computer Science and Information Technology (eJCSIT). His research interests include computational aesthetics and computational creativity in games. Azlan Iqbal Web site.

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.

Topics Azlan Iqbal

Dr. Azlan Iqbal has a Ph.D. in artificial intelligence from the University of Malaya and is a senior lecturer at Universiti Tenaga Nasional, Malaysia, where he has worked since 2002. His research interests include computational aesthetics and computational creativity in games. He is a regular contributor at ChessBase News.
Discussion and Feedback Join the public discussion or submit your feedback to the editors


Discuss

Rules for reader comments

 
 

Not registered yet? Register

ildjarn ildjarn 11/7/2014 05:21
Vaclav Kotesovec (fairies) and Torsten Linß (selfmates) have been creating chess compositions with their computer for ages by the way, all of them of a much higher quality than the chess puzzles (they're not really compositions....) on this page.

Theoretically an interesting concept, but practically human composers are still lightyears ahead.
ildjarn ildjarn 11/7/2014 05:06
Small correction to smurfo's message: David Gurgenidze is still alive, Iuri Akobia died 2 days ago.
Chessdurik Chessdurik 11/7/2014 12:35
As a composer I can say that all these problems created by computer are too primitive. I can compose 100 of such every day. And if I am payed I could increase my output to 1000 problems a day.
RJS RJS 11/7/2014 09:34
These are all rather banal, and none can remotely compare with anything created by, for example, Troitzky (Troitsky) or Reti. The king, rook and pawn versus king has surely been seen before. Compare it with this study from Richard Reti: White King e7, Rook d4; Black King e5, Pawn d5. White to play and win.
smurfo smurfo 11/6/2014 11:32
Problem composition has generally been the one area of chess that computers have not been able to touch - where beauty, elegance and other 'human' traits reign supreme. I admit Azlan's work from an academic perspective, but I can't help but feel a little sad about this new technological development. It's somehow ironic that this article was published just one day after the death of one of the greatest ever chess composers, David Gurgenidze (20/5/1937-5/11/2014).
dhochee dhochee 11/6/2014 11:26
Interesting work. It's hard to imagine there's a correlation between the subject of a photograph as an input for a composition and the aesthetic beauty of the problem that results, but if the research does indeed show that to be true, it's fascinating.

The relative beauty of a problem depends on the purpose of the problem. For tactics training, a lopsided position where one side can win easily (e.g., the KRPvK in the picture) is not too useful, but such a problem can be interesting with respect to the difficulty of finding the solution. Generally, problem difficulty corresponds to the number of variations, and aesthetic beauty is influenced by the unexpectedness of the solution. Some of the problems above were not particularly interesting to me, such as the the 8th one, where the discovered double-check with the bishop and resulting forced line is probably the first move any strong player would look at.

The concept is great, but the filtering to judge beauty definitely needs to be tweaked in line with the intention of the problem.
Timothy Chow Timothy Chow 11/6/2014 10:17
All the compositions are atrocious by human standards for the simple reason that the key move in every case greatly restricts Black's mobility. It should be relatively easy to improve the quality of the compositions by simply requiring the key move not to be a check or a flight-taking move or a capture or a pin.
Ralph sherman Ralph sherman 11/6/2014 08:23
I have suggested that Transition State Theory (Eyring – Activation Entropy) is a kinetic factor in Mate in Two Problems, Ralph Sherman, Myrtle Point, Oregon – LinkedIn.
idratherplay960 idratherplay960 11/6/2014 05:29
Sorry but this just doesn't seem real, especially the notion of 'perception'. Though it is not April Fool's so I will indeed wait for the paper (and product) and in the meantime remain very unsettled.
tigerprowl tigerprowl 11/6/2014 05:03
"White to play and mate in three: example of a computer generated chess problem"

White has pawn and rook, black has nothing. You need a computer to generate a win? I don't see the importance of this or the article. They just souped up a weird position. White is facing black when you would expect the colors to be reversed.
ChiliBean ChiliBean 11/6/2014 04:34
Fascinating! And thank you for 1440p video quality setting. Not that we really need that quality of detail such as watching art, a scenery, etc.
MortalWombat MortalWombat 11/6/2014 04:31
Some of this compositions are not bad, but the author said nothing about what level (expert, master, or GM, etc.) in composition it would correspond to. Good luck on the paper, let us know please, when it's out! The research sounds really, really intriguing. You are obviously onto something there.
1