What’s New with Arimaa?
In an earlier articlea I introduced readers to Arimaa, a recently invented and hitherto almost unknown chess variant. I argued that Arimaa has a comparable beauty and complexity to chess, but a much higher potential (given the lengthy history and extensive theory of chess) for creativity and originality.
Readers will, by now, be itching for an update. Are humans still better than computers at Arimaa, and is this ever likely to change? Will interest in Arimaa expand beyond an eclectic, devoted, elite of computer scientists and mathematicians? Who won the 2015 Arimaa World Championship, and how will I get to play the new Champ in a simul?
Good questions! Let’s get started with the perennial man-machine battle for Arimaa supremacy.
The Rise of the Machines
Supporters of the humanoid team for the 2015 Arimaa Computer Challenge1 could have been forgiven for a sense of complacency. The Challenge match is between the world’s strongest bot (computer programme) and a team of 3 elite human players. The competition consists of a 3-game match between the bot and each of the humans, and the bot is required to win all three of the individual matches. A significant incentive is a $12,000 prize for the winning programmer to first accomplish the Challenge.
Although, this competition has been running annually since 2004, there have only been two occasions in which even one member of the human team has been defeated over 3 games. That was in 2010 and 2012, but even then silicon suffered a convincing defeat each time by an overall 3-6 margin.
Could 2015 really be any different? Portents prior to the start of this year’s Computer Challenge were ominous.
In the Computer World Championship2 (March 2015) bot_Sharp flattened 9-0 the rival pretenders to the silicon crown. David Wu is the human intelligence behind Sharp and had previously taken the Computer title in 2011 and 2014, but by the more seemly margin of 7-2 both times.
Next up were the Screening Games (March-April 2015). This is an elimination contest between the top two bots from the Computer World Championship. Any human brave (or foolish) enough could take the field, and the bot which does best against the cannon fodder gets a shot against the elite humans. This was simple target practice for Sharp who demolished all-comers by 28-2. Its remaining rival, bot_Z, was less accurate, with a meagre 18-10 score line against the same opposition.
The honorable exception was Karl ‘Fritz’ Juhnke (former world champion) who scored 50% over two games. His marathon 93 move victory over Sharp3 is a masterful exemplar of anti-computer strategy.
Fritz Juhnke (twice world champion): tied 1-1 with Sharp
Its silicon rivals now bested, Sharp then took its seat in the 2015 Computer Challenge. The Imperial Guards were led by Mathew Brown (newly crowned 2015 world champion) and Jean Daligault (2014 world champion). The third team member was Lev Ruchka who, though never placed on the podium in a world championship, is an experienced and respected player within the Arimaa community. This is one of the strongest humanoid teams ever to have faced the bot onslaught.
It could hardly have gone worse for the humans.
Jean Daligault (six times world champion): defeated 1-2 by Sharp
Arimaa-land was dismayed to find the humanoids trailing 0-3 after Round 1, then staggered by the 0-6 deficit after Round 2. Only a late rally of human intelligence in Round 3 provided the sour consolation of a couple of elegant wins for Mathew and Jean. But an overall 2-7 defeat left no room for doubt – or hope. On 18 April 2015, the Computer Challenge, which had stood for 11 years, was now lost.
The Holy Grail of Arimaa-land had been surrendered almost without a fight: what on earth happened here?
At the Computer Challenge Award Ceremony (9 May 2015), Jean dismissed any notion of a statistical fluke, and was fulsome in his praise of his computer opponent, describing it as “very, very strong … making mistakes in only a few positions”. Commenting on whether Sharp had now better assimilated the lessons of his 2011 workb than any of his other (human) opponents, Jean responded that rather Sharp has actually expanded our conception of Arimaa strategy: to the point where now it is us humans who should start to learn from Sharp’s play. Gasp!
The explanation of why Sharp won the 2015 Computer Challenge is depressingly familiar to anyone who witnessed mankind’s toppling from the chess-throne in 1997: face it, guys, it’s better than us!
Genesis of a Terminator
bot_Sharp and David Wu are no strangers to Arimaa Computer tournaments. Sharp first entered the lists in the 2008 Computer Championship, and achieved a respectable second place behind bot_Bomb (programmed by David Fotland) – the dominant engine of the early Arimaa years.
Indeed, as reigning 2014 Computer World Champion, Sharp could have represented silicon honour in the Computer Challenge last year. However, bot_Ziltoid (programmed by Riccardo Barreira) performed fractionally better in the Screening Games. Ziltoid lost the 2014 Challenge by the convincing margin of 2-7, so the implication is that even as late as 2014 Sharp would also have lost, by a similar or even greater score line.
What did David Wu do between the 2014 and 2015 Computer Challenges that was so radically different? The simple and surprising answer seems to be: not very much!
Top Arimaa (and chess) engines use a move search technique known as “iterative-deepening, depth-limited alpha-beta” (or “alpha-beta” for short) – cf {c} p.13. What this means roughly is that an engine looks at all variations to a given depth, discards the obviously rubbish ones, then does a deeper dive on the remainder. This process is iterated a number of times (assuming a forced end to the game is not found) until a time or depth limit is reached, when the residual node positions are compared using an evaluation function.
Now, the efficiency of any alpha-beta search can be dramatically improved, by looking at the more promising candidate moves first – cf {c} p.17. But the problem of how to arrive at a move selection ordering for an Arimaa engine is even more pressing than that for chess (or Go): since there are so many alternatives (approximately 16,064 for the average position – cf {c} p.9). How could a computer ever rank such a vast number of alternative moves, without first doing some in-depth analysis?
In 2011, for his Harvard BA thesis in Computer Science, David defines an expert prediction methodology for Arimaa – cf {c} pp.17-38 – based on one already successfully deployed for Go. David’s methodology specifies several hundred “features” of an Arimaa move, which might be ascertained by direct inspection, rather than in-depth analysis. Example of types of features are material (whether a piece is won/lost), mobility (whether a piece is frozen/freed), and direct threats (whether goal is now threatened on the next move). A large sample of “expert” games (initially those played by humans rated above 1800) was then surveyed to determine to what extent these features are present in actual moves played by the experts.
This data can then be used to attempt to predict what move an expert is likely to make in a position outside the sample, based on the extent to which these features are present in the moves available from that position. David looked at various algorithms for generating predictions, and showed that accurate prediction of expert moves is indeed possible: for the most promising algorithm he examined in 2011, 90% of the time the experts’ actual move fell within the top 5% ranked by feature – cf {c} pp.37-38.
The power of such an approach is immediately obvious. It would combine the human expert’s intuitive, immediate judgements about what candidate moves “make sense” with the computer’s remorseless ability to grind-out zillions of variations.
Golly! It’s that simple! But does this approach actually work?
Yes it does. This move order function described in his thesis was the basis of the Sharp engine which won the 2011 Computer Championship, but, David tells me, has not been vastly altered in the 2015 version. The prediction engine has, however, been increasingly hardened by comparing the output of the selective move generator with actual moves chosen by the strongest human players – which would, of course, improved in quality over the 2010-15 period.
The overall architecture, therefore, appeared to have been established in 2011, and what David has been doing since then is basically refining and perfecting his initial concept. David’s own metric describing the 2010-15 development process is that while numerous discrete improvements were effective, no single enhancement contributed more than 10% to the total improvement.
But, even if the initial conception was fundamentally sound, is it really credible that small improvements could, all of a sudden, result in bot_sharp just blowing away the opposition? That sounds just crazy!
Well, not at any rate, to the early eighteenth-century philosopher, Georg Hegeld
“The common view has it that when we speak of a growth or a destruction, we always imagine a gradual growth or disappearance. Yet we have seen cases … which … involve … not only a transition from one proportion to another, but also a transition … an interruption of a gradual process, differing qualitatively from the …. former state.’’
A series of incremental, quantitative improvements has morphed a dangerous, but (at the highest level) eminently beatable, Sharp of 2011-14 into the terrifying, qualitatively unrecognizable, Terminator of 2015.
David is actually writing a paper for the ICGA (International Computer Games Association) describing how he achieved his success in the Computer Challenge. (This is a condition of his $12,000 prize.)
I should probably shut-up now, and apologize to David for pre-empting his detailed and canonical explanation. Let the final word on this matter be his!
Judgement Day
Does Arimaa even have a future? Will it survive bot_sharp’s sudden and dramatic dethroning of humanity from the Arimaa summit? Received wisdom among Arimaa hard-core devotees is: yes, of course it will – just as chess survived, even flourished, after Kasparov’s defeat by Deep Blue in 1997. It’s a comforting line only for the faithful.
Chess had a rich culture, history and literature prior to its computerization. The number of chess-players has been variously estimated; however a hard figure to focus on is the 520,000 or so named on the 2015 FIDE rating list.4
But to spice up this number, you might want to add in club, correspondence, internet & social players. Next, for good measure, throw in those who can just about set up the initial position without too many mistakes. You might then even stretch to the jaw-dropping headline of 600 million players worldwide arrived at by the 2012 YouGov survey commissioned by AGON, and endorsed authoritatively on the FIDE website.5 But honestly, surely not even FIDE needs to descend to statistical manipulation to demonstrate the global cultural entrenchment of chess?
Arimaa’s roots are somewhat shallower, a twelve year history, two published booksb,e (or three if you count the Wiki-book)6 – with perhaps around 500 active players worldwide.
Why bother to learn a chess-like game with only an eclectic, scattered band of followers: when you can just play chess, with perhaps almost a million times as many opponents?
Arimaa has set its stall out as “the game of real intelligence” supposedly requiring a type of abstract reasoning ability available to humans, but not to computers. Bot_Sharp has now dismantled this advantage: Arimaa is no longer anymore “computer-resistant” than chess.
And, with the benefit of hind-sight, perhaps the “computer-resistance” of Arimaa was always over-egged. Research on chess-playing software commenced in the 1950s and, with considerable commercial backing, eventually resulted in Kasparov’s debacle against Deep Blue some four decades later. Research on Arimaa-playing software commenced around 2003, with zero commercial backing and a considerably smaller group of programmers, resulting only 12 years later in Sharp’s victory.
Clearly, this data is susceptible of multiple interpretations, but could be used to argue that Arimaa was actually less computer resistant than chess! Perhaps, it just took one exceptionally talented software-engineer, working on the problem persistently over seven years, to land a solution.
Moreover, while detracting nothing from David Wu’s triumph, let’s be clear about what has not been achieved.
What characteristics define human thought? Self-awareness, creativity, abstraction, the freedom to formulate rules, but also to modify or even break them? If it set out to create a thinking machine, the Chess-AI project failed laughably.
But has the Arimaa Computer Challenge, by this standard, done any better? No: Sharp has none of these qualities, or if it does, they are irrelevant to its success.
Just like any other Arimaa (or chess) engine: Sharp is nothing more than a highly superior mechanized abacus.
However, computer resistance was only one plank in the Arimaa USP: even if removed, isn’t it still a game with excellent potential and interest? Certainly! But to achieve that potential, Arimaa-land needs to step up at least a couple of gears.
Arimaa must radically expand its franchise. It has nowhere near the critical mass it needs to ensure long-term survival. It needs to go mainstream. Face-tournaments with elite players are always a great way to generate publicity.
Want chess-GMs to participate in Arimaa tournaments? Easy: show ’em the money!
But this means normalizing Arimaa playing conventions, standards and conduct to that of the wider gaming community: something for which Arimaa-land demonstrates little appetite. And it badly needs some sponsorship deals, something which the paltry number of current followers – dedicated though they are – renders somewhat implausible.
Even if Arimaa-land could survive purely confined to the on-line medium, the opportunities for improvement are self-evident. The front-end needs a refresh, and the creaking web-services on which the Arimaa game-room is hosted require a significant overhaul. These will require volunteer technical effort and/or funding.
Perhaps we will soon see bot_sharp or its counterpart available from the App Store and distributable to any smart phone. This means that to retain its credibility as a mind-sport, Arimaa, like chess, must introduce significant anti-cheating technology: a problem made still more pressing for Arimaa, if there is no face-to-face play to validate an individual’s playing strength.
Bizarrely for a community so obviously rich in software expertise, Arimaa-land appears somewhat under-computerized.
The Arimaa community has reliably provided an abundant harvest of new and improved bots each year: around 200 bots are available from the Game Room. But how about leveraging the engines to provide practical, targeted help for us patzers? For example, an ancillary function might point an Arimaa position at a specified engine and generate an immediate set of candidate moves with evaluations. Perhaps the function could even automatically annotate an entire game. And wouldn’t Arimaa players like to annotate and learn from their own and each other’s games, not just with text comments, but with representations of the other likely paths the game might have taken? How about an “ArimaaBase” containing all games of note, and those between the top players annotated in depth, with a flexible GUI-based querying capacity?
Of course, the equivalent tools have been available to chess-players since the mid-1990s, and are now an essential part of any serious player’s armoury. And this stuff is cheap and easy to use: anyone with a decent laptop and $200 to spend can have a +3000 Elo engine at their command and more shrink-wrapped chess knowledge than you can shake a stick at.
Is the chess-player simply expected to forgo these tools when he journeys into Arimaa-land? Really?
A Chapter Closes
Yet Arimaa might surmount all of these challenges. But not, perhaps, without someone with Omar Syed’s vision, integrity and zeal at the helm.
Omar started work on designing an original game in 1997 following Kasparov’s defeat by Deep Blue. That creative process led to invention of Arimaa around 2002. He developed the Arimaa website and Game Room and financed the hardware used to host it. He devised and stumped up the lion’s share of the prize for the Computer Challenge, which commenced in 2004. He boot-strapped Arimaa strategy. He led mankind in the early bot wars, only standing down when sufficiently strong humanoid players had emerged to relieve him.
Everything unique about Arimaa has Omar’s imprint on it: from the sui generis time-control rules, to the unique tournament format for the World Championship. I have no specific evidence for it, but I suspect Omar’s still the guy doing most of the production and user support on the game room servers and website. All this done without pay or profit in the service of a vision. If only electronic distribution of these was possible, he’d probably provide free beer and pizzas to the Game Room players!
In some ways, it would be helpful if Omar could be less modest and specifically credit his contributions to every aspect of the game on the Arimaa website. This will be useful when he decides to step down from his lead role in the game, so we understand what jobs now need to be filled.
Because, sadly, this is now what has actually happened. In a further blow to the beleaguered Arimaa community, Capt’n Omar announced to a stunned audience at the Computer Challenge Award Ceremony that, after the best part of two decades, he is standing down from the wheel.
Arimaa without Omar is almost unimaginable: how shall Arimaa even survive, still less flourish, without Omar?
The White Knight?
David Wu is clearly on board Arimaa for the long-haul. His association with the Arimaa community commenced in 2007, and although this decade he has spent most of his Arimaa-related time on bot development, he is still a strong player who can hold his own in the world’s top 10.
Harvard educated, and now working in New York, David currently balances a mixture of software development and research within the financial industry. With the massive achievement of the Computer Challenge now on his CV, surely David will soon have Wall Street Heads of Algo Trading beating on his door, demanding his services. The new poster boy of Arimaa-land would certainly be well positioned to look for that much needed Corporate Sponsorship.
David Wu: dark destroyer or new champion of Arimaa-land?
Is David the new White Knight? Commanding respect from geek and gamer alike, David is ideally placed to lead the faithful in the next phase of the Arimaa voyage.
In a gracious acceptance speech at the Computer Challenge Award ceremony, David announced that he plans to plough back his $12,000 award back into the game, unveiling plans for a new and improved Arimaa Game Room, with other ideas to follow. There is so much that can be done for Arimaa, but the Game Room is the shop window: this is the right place to begin.
Within only a couple of days of the announcement of the Game Room re-write, David had already assembled a crack team of six volunteers to work on this project.
The collaborative culture of Arimaa-land, together with its depth of technical expertise, generate a sense of optimism that this project will succeed.
The post-Omar epoch is already off to a promising start. One can only wish David and co every success!
Appendix A: 2015 World Championship – the Clincher
The 2015 World Championship was decided in an elimination battle between Karl Juhnke (aka “Fritz”) World Champion in 2005 and 2008 and Mathew Brown (aka “Browni”) runner up in 2014 and currently the world’s highest rated humanoid player.
The final game7 reached the position below after 40 moves.
Mathew Brown – Fritz Juhnke
World Championship 2015
Gold to play 41g
The material balance is slightly in Gold’s favour with Silver having only a Dog and Rabbit to show for his Horse. However, this is the very least of Silver’s problems.
Note first the over-ambitious Silver Elephant on e3, cut off from the rest of the Silver army, almost smothered (cf {e} pp 95-105) by a combination of Gold and Silver pieces, and nearly out of moves.
Secondly, Silver’s best hope of relieving the beleaguered Elephant, the Camel on g4 is frozen by the Gold’s Elephant on g5. If the Silver Elephant did make a bolt for freedom, by suiciding the Silver Rabbit on d3 into the c3 trap, then darting back via d3 and d4 to join the rest of the Silver forces, the g4 Silver Camel would rapidly get dumped in the f3 trap. Thus, the Silver Camel is said to be hostaged (cf {e} pp 111-128) by the Gold Elephant.
But if Silver’s Elephant can hardly move, and Gold’s Elephant is required to keep Silver’s Camel under lock and key, does this equate to an impasse? No. Because, thirdly, Gold’s Camel on b6 is now the strongest free piece (cf {e} p.97). Its main adversary, the Horse on c6, can do nothing except defend passively against the Camel’s threats: active counter-attack would result in quick material loss. The accumulation of the above 3 factors, equates to an exceptionally difficult position for Silver.
Rather than try to force home his advantage, Browni choose a subtler and more poisonous method. 3-time repetition is not a draw in Arimaa (as it is in chess): rather the side that might seek to repeat for the third time is forced to vary the position. Gold has far more freedom in the above diagram than Silver, therefore by nimbly pirouetting his Dog and Cat around the c3 trap, Browni slowly and insidiously wrested a series of almost intangible concessions from Fritz.
This torture continue for a further 40 moves culminating in the position below.
Mathew Brown – Fritz Juhnke
World Championship 2015
Gold to play 80g
At first glance it might seem that not so much has changed about the position: the only material transition is the loss of a solitary Silver Rabbit. However, the experienced Arimaa player immediately notices the key differences. Firstly, the Silver Elephant (now on d3) has no legal moves whatsoever. Secondly, Gold Camel has now frozen the sole Silver Horse on c8 – indeed it is only the Silver Dog on c5 which prevents an immediate capture. Thirdly, all of the Silver Rabbits have been lured forward to the 5th rank or beyond, where they can play only a limited part in defending the Silver home traps (c6 and f6) against captures, also leaving Silver vulnerable to Rabbit advances to the goal-line.
The resulting position is now hopelessly lost for Silver, and there are perhaps any number of winning methods. Merciful at last, Browni dispatched Fritz in the most economical fashion, displacing the Silver Cats on g5 and h5, then marching his unopposed h-Rabbit to the 8th rank.
A cruel end to his hopes of regaining the World Championship, Fritz’s role at the conclusion was reduced almost to that of a teaching-aid.
Browni’s play is a text-book demonstration of a number of key Arimaa strategic themes uncovered over the past decade, many by Fritz himself. But least the younger generation of Arimaa players give themselves airs, they need to remind themselves that only an exceptional pupil could deliver such a stringent lesson in Arimaa fundamentals.
Congratulations to Mathew Brown, the 6th humanoid Arimaa World Champion, crowned 12 April 2015.
Mathew Brown: 2015 Arimaa World Champion
References
Websites
2) Arimaa Website: follow link for “Championship” for human and computer world championship and “Challenge” for computer challenge and screening games
3) 2015 Arimaa Computer Challenge – Screening Games – bot_sharp v F Juhnke
5) Press Release “AGON releases new chess player statistics from YouGov”
7) 2015 Arimaa World Championship R13 – M Brown v F Juhnke
Books and Papers
a) “Arimaa, Computers and The Future of Chess” (2015) – Andy Lewis
b) Arimaa Strategies and Tactics (2012) – Jean Daligault
c) Move Ranking and Evaluation in the Game of Arimaa (2011) – David Wu
d) Science of Logic (1814) – G.W.F. Hegel. Cited in Robert L. Carneiro (2000)
e) Beginning Arimaa: Chess Reborn Beyond Computer Comprehension (2009) – Fritz Juhnke
About the Author
Andy Lewis is a former British U21 Chess Champion, has a PhD in Philosophy, but spent most of his working career in computer departments for investment banks. He is semi-retired and lives with his wife and two dogs in Manningtree, Essex. He has played Arimaa for ten months and has competed in the 2015 World Championship.
© Andy Lewis 2015
A very interesting article on Arimaa, a game that I have never heard of. Its move evaluation system is ingenious. Well done to all involved.