New game challenges AI programmers

By Jamie Engle
Staff Writer

Have you ever seen the commercial where the inventors and programmers are the rock stars? When preparing to interview Murphy resident Omar Syed, inventor of the abstract strategy game Arimaa, and Karl Juhnke, two-time Arimaa world champion, I realized they are like rock stars of the gaming world.

With write-ups in major gaming magazines and on mega-popular gaming Web sites, and mentions on BBC, “Scientific American Mind” and in university and engineering journals, Arimaa is taking the gaming world – and the computer engineering world – by storm.

Noted gaming programmer David Fotland and $1 million Netflix challenge winners Martin Piotte and Martin Chabbert are just a few of those taking Syed up on his $10,000 challenge to write a “bot” (computer program) that can beat a human at Arimaa.

So far, humans – namely, Syed – have won every time.

That’s no mean feat, considering that computers have been beating human chess players for years, with no sign of humans beating computers anytime soon. In Arimaa, it’s exactly the opposite: it doesn’t look like computers will beat humans anytime soon.

“Because of the number of moves per turn, it takes a computer an incredibly long time to process all the possible moves and to look ahead,” said Juhnke. “Even considering how fast computers will get in the next 10 years, they will only be able to look a half move deeper than they can now. And that’s not good enough to win.”

Syed said Arimaa is now the only game in the world that can be played using a chess set where the top human players are still defeating the best computer programs.

“There are a few other games where the top human players are also better than the best computer programs, but all of these games use a much bigger board and many more pieces; also these games take much longer to finish. Arimaa is now considered the second deepest strategy game ever invented, according to en.wikipedia.org/wiki/Game_complexity,” he said.

The Arimaa game site (www.arimaa.com) launched in November 2002 along with a challenge to the Artificial Intelligence community to develop a program that would play Arimaa better than the top humans. The first challenge match was played in 2004 and has been played each year since then. Syed said it will continue until the year 2020 or until the challenge prize is won before that.

Syed hopes Arimaa will be the catalyst for innovations in Artificial Intelligence programming, as programmers try to come up with bots to beat humans at Arimaa. Juhnke says while that’s a noble goal, his love of Arimaa is more basic.

“For Omar, it’s a great computer engineering experiment. For me, his experiment ‘accidentally’ produced what to me is the most fun I’ve had playing a game! It’s really fun, really deep and really strategic. There are no draws, no opening moves to memorize, no advantage to being the black or the white. You can play it 100 times and still not be done with learning about the game. There’s a richness to the game that makes me believe that if there are enough players who get interested, it could eventually take over chess.”

Each year there’s an online Arimaa World Championship, which Juhnke, a Garland resident, has won twice. He recently released a book on Arimaa called “Beginning Arimaa: Chess Reborn Beyond Computer Comprehension” (Flying Camel Publications, 2009).



How Arimaa started
Arimaa started in May 1997, when the Deep Blue chess computer defeated Gary Kasparov.

“Even though I was just a spectator to that match along with millions of others, that match became like a life changing experience for me,” Syed said. “I had an attachment to both sides of that match. Having played countless hours against the Fidelity chess computer I could sympathize with Kasparov when he was in tough positions. Having tried to write my own chess programs I knew how thrilling it was to see your own creation perform well. But in the end I guess I was more on Kasparov’s side, because after that match I just didn’t feel the same about my favorite game.”

Syed said the match seemed like a glorified example of a computer out-calculating a human and short of demonstrating a machine achieving human-level intelligence. Having recently finished his master’s degree in Artificial Intelligence, he knew how difficult pattern recognition problems were for computer, yet so easy for humans.

“I felt that humans have an incredible ability to draw on their experience, knowledge and intuition to make judgmental decisions, which just could not be replicated by a brute force approach. So I began thinking how the rules of chess could be changed to show this by making the game much more difficult for computers,” Syed said.

The whole process took over four years. After an initial attempt at trying to change the chess rules to make the game harder for computers, Syed concluded such a game was not going to be possible without the game also becoming more difficult for humans and gave up on it.

“Then in January 1999, while trying to teach my son Aamir, who was 4 years old at the time, to play chess, I realized that using simple movements for the pieces might be the key to making the game difficult for computers but still easy for humans,” Syed said.

It was then he decided to call the game Arimaa; it is actually Aamir spelled backwards but with a leading ‘A.’ After a year of trying many variations, he had a game that would be difficult for computers, but it didn't seem very interesting to play. Syed wasn't quite satisfied with it and gave up on it again. Then in September 2001, while deleting old files on the computer, he came across the rules he had previously written and began working on it again. After some more changes and play testing, Arimaa was finally finished around November 2001.

Syed designed the Arimaa Web site to be a gaming community, with discussion forums and game-playing forums. So far, there are more than 10,000 registered players from just about every country in the world. The Arimaa Wikipedia article (http://en.wikipedia.org/wiki/Arimaa) originally written in English has been translated to 16 different languages.

“Some of the players have played over a thousand games,” Syed noted. “About a hundred games are played each day on the Arimaa Web site. However, these numbers are all very small compared to chess which has millions of players worldwide and 10s of thousands of games played each day. However, the players who have discovered Arimaa are becoming big fans of the game and giving it very positive reviews and comments.”

According to comments posted on BoardGameGeek.com, many of them like it even more than chess (http://boardgamegeek.com/thread/372482).

Originally, Arimaa was played on a chess board. This fall, board game publisher Z-Man published the board game, with a specially designed board and animal pieces.

Syed is still surprised by how much Arimaa has grown.

“I was interviewing a candidate for a job once and he said ‘Are you the same Omar Syed who invented Arimaa?’. When I asked him how he had heard about Arimaa he said his professor mentioned it in a lecture. Several graduate students have done their master’s and Ph.D. thesis in computer science on ways to develop better Arimaa playing programs, and some people have heard about it from university professors mentioning Arimaa in their AI classes as an example of a game that is difficult for computers,” he said.

According to Syed, it is easy to get started playing Arimaa.

“If you like to play online, the Arimaa.com site has a section that teaches the rules by way of a short video clip. Once you’ve learned the rules, there is a game room section where you can play other people from all over the world. The game room also has a ladder of increasing harder programs to play against,” he said. “If you like to play off-line, an Arimaa set can be purchased over the Internet or from a local game ship like ‘Game Chest’ and it includes a rule book. The “Beginning Arimaa” book by Karl is also a good guide for improving at the game and learning about its background and history.”

Next steps
At the sold-out BoardGameGeek Convention in Dallas this month, Juhnke will have 10 Arimaa boards set up and will play all 10 games simultaneously. Syed will give a presentation about Arimaa, and the game will be on display at the Z-Man booth. The convention is being held Nov. 19 through 22 at the Westin Dallas Fort Worth Airport. For more information, visit http://www.boardgamegeek.com/bggcon.