Amazons was first introduced to me by Dale Garraway, a visiting professor at Colby while I was an undergrad. It is a nice combinatorial game because it can be played on a common checkerboard using chess pieces (though if you use the queen piece as an amazon, you will need multiple sets of pieces) and something to mark destroyed squares. Each turn, a player chooses one of their amazons, then moves that amazon just as a queen piece in chess, but may not move onto or through a square either occupied by another amazon or which had been "destroyed". After moving, that queen shoots an "arrow" at another square which is a "queen move" away from their current location.
The next player then takes their turn, continuing until the current player does not have a move.
Amazons was invented in 1988 by Walter Zamkauskas. The rules are simple to learn and enjoys computer-based opponent championships. In 2005, Bob Hearn showed Amazons to be PSPACE-complete, thus it is unlikely that an efficient algorithm can evaluate all Amazons boards of general size.
The play tip that Dale and I learned was that sugar packets do a great job of marking destroyed squares.
Enjoy the winter break! I am planning on returning to a normal posting schedule on Monday, Jan. 11, 2010.
A Domino-Covering Problem
2 months ago