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
-
Currently, MSc student Gabe Van Eyck is working on an investigation of
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.
-
MSc student Jiaxing Song is working on an improved solver for small boards
and endgames.
He is building more databases for territories and active areas, and incorporating
them into a solver.
Research and Results
- 2010/2011:
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.
Arrow2
plays
on
LittleGolem,
a turn-based server.
Its score as of November 29, 2011 is 40 wins 7 losses.
It has beaten several highly ranking human players, but also suffered a number of losses
exposing weaknesses in its opening play.
At the 2011 Olympiad, the new Arrow2, enhanced with move groups,
won a Bronze medal.
It won a game from Silver medalist 8QP. It still has some weaknesses in its opening play,
deriving from its ancient evaluation function. The program can fight well if
it survives the opening phase.
- In 2003/2004, Amazons has been used extensively for our experiments with
Temperature Discovery Search.
- On January 4, 2001, using a solver based on Arrow and
some pruning ideas motivated by combinatorial game theory,
I proved that Amazons on a 5x5 board is a first-player win. There
seem to be many winning moves.
The easiest to prove was 1. B1-D3xB3 (or the symmetric 1.D1-B3xD3).
1. B1-B3xD3 was just slightly harder.
-
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.
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.
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.
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.
H. Iida and M. Müller.
Report on the
Second Open Computer-Amazons Championship.
ICGA Journal Vol.23 No.1, March 2000.
The Amazons program Arrow
The released version of Arrow runs on Macintosh PowerPC only. See the Readme file for details.
Links
-
Amazons 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 and 2009
champion, interesting UCT program with short playouts and strong classical evaluation
function.
-
ICGA Amazons page, updated circa 2003.
-
LittleGolem
Amazons forum
Created: Aug 4, 2000 Last modified: Feb 1, 2012
Martin Müller