A new, challenging chess variant

by Azlan Iqbal
2/2/2014 – 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.

Chess has been the subject of intense research in artificial intelligence (AI) since the mid-1950s. However, since then-world champion Garry Kasparov’s defeat by IBM’s Deep Blue in 1997, research interest in the game has slowed. The reason is partly because the goal of developing a computer program that could defeat the world’s strongest human player had technically been achieved. It is now widely accepted that even desktop computers can play chess at its highest levels and beat practically all humans. It is virtually impossible for anyone reading this article to even beat his or her smartphone at the game. Computer game researchers have therefore shifted their attention to more complex games such as Go and Arimaa. These are considered ‘more complex’ because they have a larger game ‘tree’ or search space (i.e. more games and positions are possible).

It occurred to me that another reason chess lost its ‘Holy Grail of AI’ position is that the technologies developed that could play chess well were not quite applicable beyond the game itself. Of course, there have been applications of computer chess research in other areas such as automated reasoning, molecular synthesis and scheduling problems, but nothing on the level that performed equally well in other domains as it does in chess. In other words, you could not more or less directly apply a good chess engine to genetic engineering or even have it play an equally strong game of Go.

Unfortunately, more complex games such as Go and Arimaa do not benefit as much from all the work that has already been done in chess over the last 60 years. This is where chess variants come in. These are basically games that differ from the standard or international version of the game in terms of the rules, pieces or board used. There are approximately over 1,000 variants on record; most of which most of us have never even heard of. Fischerandom or Chess960, for instance, is one of the more popular ones. 3D chess (as seen on Star Trek) is another.

Switch-Side Chain-Chess

It is not just any variant, however, that can steer the tide of AI research back to chess, where it all started and rightfully belongs. It has to be demonstrably more challenging than the standard version and add, intellectually, to the game such that fundamentally new technologies need to be developed to play it well; technologies that have greater potential of being applied or adapted to other domains with more pressing problems. The variant also needs to be able to take advantage or build upon the decades of work that have already gone into standard chess so as to be more appealing than other variants or games that put researchers further behind. This is how the ‘Holy Grail’ status may possibly be restored.

After studying numerous existing variants and finding them wanting in one way or another, it dawned on me that something unthinkable had never been tried before in all of ‘varianthood’. How about the ability to switch armies with the opponent? It seems absurd. Based on that idea, I created the new variant called, Switch-Side Chain-Chess (SSCC) [1] that features just one simple rule in addition to that of the real game. Either player has the option of switching armies with the opponent should a ‘chain’ (i.e. a link of pieces of any colour) form on the board. Neither colour gets more than one consecutive turn, so the flow of the game is unaffected.

A turntable device or rotating base can be used with an existing chessboard, if necessary

A full description of how to play the variant can be found here.

A 'chain' in SSCC constitutes...

a) a continuous link of pieces of any color completely surrounding at least two adjacent empty squares;
b) such that if a line was drawn following the pieces, it would pass through each only once;
c) and the piece that moved last must be part of the chain.

Above are several examples of chain configurations. In (a), if an additional piece is placed on d7 it would not create a chain because I would have to pass through the d6 square twice to complete the circuit. In (b), I see how a chain can be expanded by adding a piece (the knight on b5) to an existing chain. In (c), the two diagonally adjacent empty squares in the center of the chain are also valid. In (d), a piece already in an existing chain (the black king) can either expand it by moving from e5 to e6 or contract it by moving from e6 to e5, forming a new chain.

The largest chain, in terms of 'area', would constitute 28 pieces stretching along the four edges of the board whereas the smallest chains would consist of 6 pieces and resemble (a) or (c). It follows that, with fewer than 6 pieces on the board, SSCC reverts back into the standard version's endgame as no more chains are possible, and thus no more switching.

The switching rule elevates the complexity of chess to a higher level without affecting the theoretical size of the game tree. This concept is actually quite difficult to grasp because programmers tend to think of the switching possibility as an additional ‘move’. However, this is not the only way to implement a SSCC game-playing program. For instance, one could employ an unmodified existing chess engine and externally ‘invert’ the positional score it produces in cases where a chain has (also externally) been detected in that position. So if switching sides is favourable, additional points are awarded to the score produced by the existing chess engine. As a further example, when switching sides, imagine instead simply having to get up and exchange seats with your opponent. The flow of the game progresses exactly as it would in standard chess. White wins or Black wins (or they draw) as normal. The only difference is who happens to be sitting in White’s seat or Black’s seat at the time.

This has nothing to do with the standard chess game engine, so the game tree is theoretically the same. The complexity, however, as in recognizing chain formations on the board (perception) and deciding whether to switch sides (what we might call, ‘intuition’) goes above and beyond the concerns of the regular game and requires more advanced AI. The benefit is that researchers are not saddled with a much larger game tree or search space (as with Go and Arimaa) that poses additional challenges in terms of processing requirements such as speed, memory and time. The interested reader may wish to explore the new variant further by referring to [2] and [3]. A prototype computer program that plays SSCC was developed under our research grant [4] and has been included below for those who wish to try the game for themselves (see box below). At present, however, it is probably more enjoyable to play against a human opponent. 

Conclusion

In general, we have found that additional heuristics and technologies are likely required not only for infallible chain detection but also in deciding whether it is prudent to switch sides at a particular point in the game (the ‘intuition’ part). There are many considerations once you realize that the opponent could suddenly seize control of your army if you overlooked the possibility of a chain being created on the board or are simply unable to stop it. There are also various traps that can be set – in addition to the concerns of standard chess – to trick the opponent into doing all the work only to switch one move before checkmate or significant material gain. We are, at present, still looking into these open challenges as topics of potential interest in AI. We welcome feedback from both players and games researchers.

SSCC

SSCC v1.0 runs on Windows XP and above. When the program starts, enter your name, choose the difficulty level (‘normal’ makes for a reasonably-timed game), your color and then ‘Go to Board’. Then the board appears. Click ‘Start’ on the left and enjoy. The rest should be self-explanatory.

This program is the only one of its kind and has a few known bugs. Notably, chain detection is not perfect (this is still a fertile area of research that graph theory apparently cannot quite handle) and castling sometimes does not work (I will have to speak to my former research assistant who has returned to Iraq about this). Also, the program prompts the user if he wishes to switch sides when a chain is detected (ordinarily, the user would have to find the chain himself or miss the opportunity) and to ‘agree’ or ‘disagree’ when the program wishes to switch sides (given that chain detection is not perfect and the risk of a false positive). In general, this prototype is a rather weak SSCC player and human opponents with a little practice have a good chance of defeating it.

Download installer: ZIP (2.4 MB), MSI (2.7 MB)

References

  1. Iqbal, M. A. M. (2011). Apparatus for Playing a Chess Variant and Its Method. Malaysia Patent Application No. PI 2011006257. Filing Date: 23 December 2011.

  2. Iqbal, A. (2013). A New Chess Variant for Gaming AI, in Entertainment Computing - ICEC 2013, Lecture Notes in Computer Science, Vol. 8215, pp. 9-16. Anacleto, J.C.; Clua, E.W.G.; Correa da Silva, F.S.; Fels, S.; Yang, H.S. (Eds.). 1st Edition., 2013, XIV. Springer. ISBN 978-3-642-41105-2. PDF.

  3. Iqbal, A. (2013). Switch-Side Chain-Chess, Proceedings of the 18th International Conference on Computer Games: AI, Animation, Mobile, Interactive Multimedia, Educational and Serious Games (CGames 2013), Louisville, Kentucky, USA, 30 July - 1 August, pp. 182-187. ISBN: 978-1-4799-0818-9. PDF.

  4. Iqbal, A. (2010-2012). A New Approach toward Solving the Technology Issues of Games of Very High Complexity (FRGS/1/10/TK/UNITEN/02/2); Ministry of Higher Education (MOHE) : Fundamental Research Grant Scheme (FRGS), Malaysia; March 2010-Feb 2012. Other members: Saraswathy Shamini Gunasekaran (College of Information Technology, Universiti Tenaga Nasional), Sinan Qahtan Mohammad Salih (Graduate Research Assistant).

  5.  

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.



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.
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