Research Related to the Game of Amazons

The game of Amazons is a game which allows an interesting mix of chess- and Go-like analysis. It exhibits interesting mathematical structure, and the endgame often breaks down into independent subgames, making it well-suited for experiments in combinatorial game theory. In contrast to Go, there are no repetitions possible, so the classical loopfree theory applies.

Current Projects

• The Arrow 2 program. Now in Version 2.1 with move groups.
• 2013: Continuing Jiaxing's work on solving 5x6, an attempt to solve 6x5 (6 wide, 5 high) solved many of the 2-ply openings but was not finished. 6x5 is hard! 6x6 still seems out of reach of current methods.

Research and Results

• 2012: MSc student Jiaxing Song proved that 5x6 Amazons is a first player win . See his MSc thesis and our TCIAIG paper listed under publications below.

• 2010-2012: MSc student Jiaxing Song worked on an improved solver for small boards and endgames. He built more databases for territories and active areas, and incorporated them into a dfpn-based solver. He defined and built a new type of database for "blocker territories". He implemented several methods for bounding the value of local subgames based on concepts from combinatorial game theory. One method exploits information contained in an active area database containing thermographs.

• 2010-2012: Gabe Van Eyck wrote a MSc thesis investigating move groups in MCTS. This work is partially motivated by Amazons, where a move can be naturally split into three parts - selecting the amazon, its destination square, and the arrow shot. See our paper on move groups listed below. Gabe's work led to a ten-fold speedup of the MCTS engine, with no loss in performance.

• 2010-now: After as long break, we have restarted work on Amazons in 2010. As part of my graduate course on games, CMPUT 655, Rick Valenzano and Daniel Huntley implemented new players based on MCTS and Arrow's evaluation function. In testing on an 8x8 board, Daniel's program achieved 80 percent wins against the classical, alphabeta based Arrow. So Arrow2 was born.

  Later in 2010, Gabe van Eyck contributed to the development of Arrow2. The brand new program took part in the Olympiad in Kanazawa end of that month. It was not quite ready for the big time, but over the course of the tournament a number of crippling bugs were found and fixed, so the program became much stronger.

  See the Arrow 2 page.

• In 2003/2004, Amazons has been used extensively for our experiments with Temperature Discovery Search.

• On January 4, 2001 I proved that Amazons on a 5x5 board is a first-player win. See the paper "Solving 5x5 Amazons" listed under publications below.

• In the early 2000's, we developed two strong (at the time) Amazons-playing programs, Antiope by T. Tegos and Arrow by myself.

• Around 1999, I defined the concept of line segment graphs (LSG), a natural mathematical structure on which to analyze Amazons. One chapter of T. Tegos' thesis contains a large-scale empirical investigation of those graphs.

  Richard Krueger's masters thesis, supervised by Ryan Hayward, proved that isomorphism of LSG (he called them Line Segment Diagrams) can be decided in polynomial time.

Publications

These are our publications. See the Amazons-related publications page for links to many other papers.

J. Song and M. Müller. An Enhanced Solver for The Game of Amazons. IEEE Transactions on Computational Intelligence and AI in Games (TCIAIG) 7(1), 16-27, 2015. On IEEE Explore or pre-print

J. Song. An enhanced solver for the game of Amazons. MSc thesis, University of Alberta, 2012.

G. Van Eyck and M. Müller. Revisiting Move Groups in Monte Carlo Tree Search. Accepted Oct 8, 2011 for Advances in Computer Games 13.

M. Müller, M. Enzenberger, and J. Schaeffer. Temperature discovery search. In Nineteenth National Conference on Artificial Intelligence (AAAI 2004), pages 658-663, San Jose, CA, 2004.

• pdf, 149k.

M. Müller and T. Tegos. Experiments in Computer Amazons. In R. Nowakowski, editor, More Games of No Chance, pages 243-260. Cambridge University Press, 2002.

• compressed pdf, 22-Jan-2001, 309k.

T. Tegos. Shooting the last arrow. Master's thesis, University of Alberta, 2002.

M. Müller. Solving 5x5 Amazons. In The 6th Game Programming Workshop (GPW 2001), number 14 in IPSJ Symposium Series Vol.2001, pages 64-71, Hakone (Japan), 2001.

• compressed pdf, 304k.

H. Iida and M. Müller. Report on the Second Open Computer-Amazons Championship. ICGA Journal Vol.23 No.1, March 2000.

The Old Arrow Program

The released version of Arrow, Arrow0.09b, runs on Macintosh PowerPC only. See the Readme file for details.

• Arrow0.09b, dated Nov 8, 2000, PowerPC Mac only, stuffit archive.
• Readme file

Links

• Amazons on LittleGolem:
  • Arrow2 on LittleGolem: Arrow2_bot and Arrow2_1_bot.
  • A discussion thread about Arrow2
  • Top players on LittleGolem
• (broken link) Jens Lieberum's Amazong. Papers, presentations, online and offline versions of Amazong (offline version works in Firefox, but not in Safari)
• Computer Olympiad Amazons Competitions.
• Invader, 2008 - 2011 four times Computer Olympiad champion. UCT program with short playouts combined with a strong classical evaluation function.
  • Invader on Little Golem Record as of April 2013: 16 wins, no losses!
• ICGA Amazons page, updated circa 2003.
• LittleGolem Amazons forum