Computer-resistant chess variants

2/21/2014 – As you know from recent articles, there has been a spate of board games specifically designed to be difficult for computers, making it impossible for them to beat the strongest human players. One such game, Arimaa, has resisted computer assaults for more than a decade. Here is some general advice for anti-computer game inventors, provided by a two-time Arimaa World Champion.

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

Creating computer-resistant chess variants

By Fritz Juhnke

As an expert in the game of Arimaa, I was intrigued by three recent articles about computer-resistant chess variants: “Switch Side Chain Chess” by Azlan Iqbal, “Tandem Pawn Chess” by Ken Regan, and “Option Chess” by Paul Bonham. My own observation has been that a chess variant is generally touted as computer-resistant only until it garners enough attention that someone takes the trouble to write a dominant program for it. Indeed, the track record of anti-computer claims has been so wretched that many chess players read articles such as the above with deep skepticism, if they read them at all.

It seems a bit harsh toward inventors of new chess variants to punish them for the exaggerated and mistaken claims of their predecessors. On the other hand, it seems foolish not to adjust our expectations based on experience. Therefore, in an attempt to be open-minded without being gullible, I have compiled a list of a few arguments that impress me and a few that do not. I hope it will be useful both for anti-computer game inventors and for impartial observers who want to form a judicious opinion of supposedly anti-computer games.

Arimaa is a modern abstract strategy game that is playable with chess equipment. It was published in 2002 by Omar Syed, an Indian American computer engineer trained in artificial intelligence. Syed was inspired by Garry Kasparov's defeat at the hands of the chess computer Deep Blue to design a new game which could be played with a standard chess set, would be difficult for computers to play well, but would have rules simple enough for his then four-year-old son Aamir to understand.

Together with the game Syed offers a $10,000 prize, available until 2020, for software that runs on commodity hardware and can beat the best human players of Arimaa. As of 2014, the Arimaa challenge prize has not been won.

Learn to play Arimaa in this YouTube video.

Let me first note that I am not talking about proof of computer resistance, which a new game by definition cannot have. Arimaa is an example of a game that has weathered enough scrutiny that one doesn’t have to make plausibility arguments any more. The many serious attempts at world-beating Arimaa software include efforts from people who made World Computer Champion programs at other games: chess, Go, Octi, and roshambo, by Don Dailey, David Fotland, Jeff Bacher, and Toby Hudson respectively. None of their engines could top the best human Arimaa players. For this article, however, I want to consider a game that is in the position that Arimaa was in a decade ago, namely trying to convince developers, without evidence, that it represents a worthwhile challenge.

Here, now, are seven things I look for designers of computer-resistant games to do or avoid doing.

  1. Don't worry about the opening book. The advantage computers have over humans in chess has little to do with their huge opening repertoire. Chess960 was supposed to be difficult for computers because it took away the opening book, but in fact that change made hardly any difference in the relative balance of power. Focus on the meat of the game instead.

  2. Know that increased complexity is a double-edged sword. A modern example is Seirawan Chess. Because the two added pieces increased the complexity relative to chess, GM Seirawan initially expected computers to have a harder time with it, but experience has shown that computers retain the upper hand over humans. The problem is that increased complexity makes a game harder for humans as well. What we really care about is the relative balance of power. We don’t merely want a game that is hard for computers, we want a game that is hard for computers and easy for us.

The Seirawan Chess set, with an additional Hawk and Elephant

Yasser Seirawan explaining his chess variant in this ChessBase report and this Youtube video

  1. Exclude mind-bending moves. Moves that are hard for the human mind to wrap around will naturally favor computers. Alas, Dr. Iqbal’s game fails this test. A computer can switch sides by flipping a single bit, but for humans it is challenging not to know what pieces belong to whom and therefore be uncertain who has which advantages. In the face of chaos, where a position swings from won to lost based on a tiny change such as an otherwise irrelevant piece being in or out of line by one square, accurate calculation beats fuzzy understanding. Yes, it is great intellectual training for humans to play games with mind-bending rules, and great fun as well, but in terms of computer resistance, including anything that is hard for humans to do is begging to be thrashed by silicon.

  2. Rely on human spatial perception. It is often said that humans recognize patterns better than computers, but this is not true for every kind of logical pattern, only for spatially localized patterns. Where we shine relative to computers is in understanding clumps of pieces that will more or less stay clumped for a while. Recall that when the human/computer balance in chess was still in doubt, humans wanted queens off and pawns locked precisely because locked pawns stay localized and queens don’t. Queens can quickly and drastically change the situation on the other side of the board. (Adding two queen-like pieces to Seirawan chess was supposed to help humans?)

    Adding more pawns in Tandem Pawn Chess should intuitively create more rigid structures, slow down chess, and make our spatial perception more relevant. This should help humans. But then why add the “rocket move” for a tandem pawn? Is it included only because it is fun, and not because it tips the balance of the variant against computers?

  3. Increase the branching factor without introducing sudden spatial changes. The game of Octi was specifically designed by Donald Green to thwart computers by having a large number of possible moves on each turn. Unfortunately, the tension in Octi is usually resolved in an explosive sequence of moves that radically alters the position and leaves one player devastated. Humans are worse than computers at sudden board revision. Despite the large branching factor of Octi, humans can only beat top computers by accumulating small advantages in the quiet buildup phase of the game, and even so it is unclear whether this would be enough if there were still serious efforts on the development side.

    Omar Syed's first rule set when attempting to design Arimaa was essentially four-move chess, which massively increased the branching factor, but also brought about drastic board changes on every move. He quickly abandoned this line of investigation, concluding that four-move chess would increase computer dominance of humans, not decrease it.

    Therefore, I fear that Paul Bonham's Option Chess is also a step in the wrong direction. Yes, the decision of when to use one's options would be strategic and thus favor humans, but execution of the options would make even more drastic positional changes with each move than chess already has, thus favoring computers. I suspect humans would have difficulty seeing (and we do think visually) the even more explosive tactics that computers would be capable of uncorking.

Designer Donald Green Designer on why computers like Deep Blue couldn't play Octi

  1. Preserve small markers of progress in any position. The likely result of trying to make a game with few sudden spatial changes is to create massive gridlock. My main concern about Tandem Pawn chess is that the eight tandems will become sixteen pawns, and because of the ability to split to the same color square while capturing, each side will predominate on one color while ceding the other. Why won’t every game grind to a halt? But I admit I have never played chess with sixteen pawns on a side, so I am curious whether my intuition holds water.

  2. Create a game with strategic depth. This was the holy grail of strategy game design before there were computers, yet it is easy to lose sight of it in an effort to create computer resistance. My pocket calculator has enough horsepower to beat me at chess, but nevertheless there is one abstract strategy game I can play as well as any supercomputer: tic-tac-toe! The most important challenge is to avoid turning chess into tic-tac-toe while trying to save it.

    I confess that my seventh point is cheating, because the strategic depth of a new game or even a new variant can’t be proven a priori any more than its computer resistance. Still, I retain this point because it has its own set of plausibility arguments based on early play testing. Here are a few:

  • Can you play blindfold? Can you remember where all the pieces are because you remember what they are all doing?

  • Can you win a simultaneous exhibition against beginners? Does your understanding allow you to use only seconds per move and still beat folks who have ample calculation time but shallower understanding?

  • Do equally matched opponents often win in different ways? Different styles of play are a hint that there are multiple important strategic themes.

  • Is your idea of what to play for still evolving? If your intermediate goalposts are not changing any more, perhaps you can only improve in execution and not in strategic understanding.

It may seem that I have strayed from the topic of computer resistance, but I submit Arimaa as evidence that the seventh point is not only relevant but essential. Only a few months after the publication of Arimaa in late 2002, David Fotland created an engine that played as well as any human. So much for computer resistance, eh? But the tide turned again, in a way that critically depended on Arimaa having strategic depth. When all sides were blindly flailing about, it was not too surprising that silicon would make fewer mistakes by virtue of infallibly considering every possibility. Humans only had a chance to regain dominance because there were strategies “in there” to be discovered and exploited. Without that strategic depth lurking, humans would have had nothing to fight with; it would have been curtains for the supposed computer resistance of Arimaa.

In summary, while I am less skeptical of Tandem Pawn Chess than the other two proposals, I would rather leave you with general guidelines than up-or-down evaluations of specific variants. I have tried to reflect a little bit of what past attempts to create computer-resistant abstract strategy games have revealed. I hope we collectively can avoid naively taking the claims of game inventors at face value, yet also avoid unfairly dismissing all chess variants as too unlikely to be computer resistant to be worth examining.

About the author

Fritz Juhnke is the 2005 and 2008 Arimaa World Champion. In 2009 he published the book Beginning Arimaa: Chess Reborn Beyond Computer Comprehension. He is currently a Ph.D. student in applied mathematics at Southern Methodist University.

See also

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.

2/13/2014 – Ken Regan's Tandem Pawn Chess
"Some years ago Frederic Friedel of ChessBase asked for a game that was reasonably like chess but would give humanity a chance against today's computers," writes IM Ken Regan, Associate Professor at the University of Buffalo, NY. He has produced a new chess variant in which two pawns are strapped together initially. The aim is to make a game that is harder for computers to play.

2/17/2014 – Option Chess by Paul Bonham
As you know we have been on a search for a chess variant that keeps the game as recognizable as possible yet dramatically weakens the play of even the most optimized computer engine. The goal is to weaken the play of such engines so that they cannot defeat most humans, and won't be able to do so for decades or centuries to come. The latest variant is by a Canadian software engineer.


Discussion and Feedback Join the public discussion or submit your feedback to the editors


Discuss

Rules for reader comments

 
 

Not registered yet? Register

Mark Schreiber Mark Schreiber 9/3/2017 04:49
There is another game we can throw on the heap of exaggerated and mistaken claims that a game is computer resistant. That game is Arimaa. One year after this article was written Sharp by David Wu won the Arimaa Challenge. Why was it necessary in 2002 to create a computer resistant game when we already had the ultimate computer resistant game? That game is the Asian game Go.
Mageant Mageant 3/7/2014 11:17
Thank you for that informative article.

I would to suggest that my game Nymbat is (IMHO) highly computer resistant as it follows some these rules put forth in that article.

It has namely a high branching factor, relies on spatial/pattern perception, preserves a marker of progress, and has high strategic depth.

I estimate there to be about 1 billion possibilites for an opening move of Nymbat.

I estimate the total number of (reasonable) Nymbat games at about 10^120, which is significantly higher than the estimate of 10^50 for Chess. Just to give you a rough idea of the branching factor in Nymbat.
azlan azlan 2/22/2014 01:49
I would like to point out that in AI research, it's not necessarily about what's easy for humans and what's difficult for computers. (In fact, chess was considered rather difficult for humans to be really good at, which is why it was studied so intently.) Rather, in AI research, the ultimate goal is about making what's difficult for humans much easier using computers. In other words, such and such a task is intellectually difficult for humans, but look, we now have a computer program that can help them with it. Can the methods the program employs also be used in other areas intellectually demanding for humans? We certainly hope so!
M van Veen M van Veen 2/21/2014 11:30
We often hear the phrase "human versus computer."
In fact it is human versus a man made machine with the virtual human behind it.
The reason Arimaa can’t be played well by a computer is because there are no masters who can translate crucial goals, tactics and strategy into computer code.

If understanding is limited, even if this person is able to program software, the code will only produce the perceptual horizon of the human - at best!

More likely is that limited understanding will result in a code that produces very bad moves, because the different subroutines are not working well together.
Just like early chess programs; the programs were not able to produce coherent play.

It is not that computers are not fit for Amiraa, because it is an overt game with strict mathematical principles.
Very fit for a calculating machine, the same as chess in fact.
But chess has a centuries old history, Amiraa hasn't; you need a programmer who understands the game well.

Given the complexity of the game, it will be 2050 before a good programmer can be found.
At least, if people will make serious studies about Amiraa.
Good game theory doesn't happen in 10 or 20 years. This takes many decades.
If this doesn't happen no good program will ever exist.

You can invent and implement certain game elements that "thwart computers."
But these only form an obstruction if the programmer doesn't know how to implement it.
You don't thwart computers, you thwart the ability to program it well.

Any subroutine of an overt game with strict mathematical rules can generate the numbers needed for the program to work.
As long as these rules make this possible, humans will be at a disadvantage, it only depends on the quality of the program code. Humans will lose from the calculator.
Fritz Juhnke Fritz Juhnke 2/21/2014 07:22
There are indeed good reasons to play Chess960 (and Seirawan chess, etc.) other than computer-resistance. We should certainly not judge a game solely or even primarily by whether humans can play it better than computers. My point was merely that Fischer claimed his variant would help humans relative to computers, and that his claim (like claims about Seirawan chess, etc.) did not hold up in practice. In Fischer's words (lifted from Wikipedia) : "One reason that computers are strong in chess is that they have access to enormous theory [...] I think if you can turn off the computer's book, which I've done when I've played the computer, they are still rather weak, at least at the opening part of the game [...]"
hpaul hpaul 2/21/2014 01:51
The author remarks that "Chess960 was supposed to be difficult for computers." That was not the point behind Chess960. Fischer (and others) recommended this because there are so many opening variants that specific in-depth opening analysis is a waste of a player's time - even with the help of a computer, so that the game would revert to tactics and strategy. This is what "new-and-improved" chess variants ought to concentrate on: removing the influence of computers on memorization, which has become such a great factor in recent chess.

Playing against computers is no longer interesting, it's like running a foot race against a motorcycle. What's the point of that? What matters is that the human-to-human game remains rich, new, revealing, and fun. Remember that it's a "game," and we "play" at it. Computers don't "play," they don't enjoy the game, and their involvement ought to be limited to post-game analysis. Chess960 is still a good choice to accomplish that.
1