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 well-suited for experiments in combinatorial game theory. In contrast
to Go, there are no repetitions possible, so the classical loopfree theory applies.
Research and Results
- In the early 2000's, we developed two strong (at the time) Amazons-playing programs,
Antiope by T. Tegos and Arrow by myself.
- I defined the concept of line segment graphs, a natural mathematical structure
on which to analyze Amazons. One chapter of
T. Tegos' thesis contains a large-scale empirical investigation of those graphs.
- On January 4, 2001, 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.
- Amazons has been used extensively for our experiments with
Temperature Discovery Search.
Projects
I think that solving 6x6 Amazons would be a nice topic for a MSc thesis.
One approach would be to use df-pn as a solver,
and use domain-specific ideas and possible combinatorial
game analysis for early evaluation/pruning.
Publications
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
Created: Aug 4, 2000 Last modified: Jun 19, 2009
Martin Müller