White moves first, and the players alternate moves thereafter. Each move consists of two parts. First, one moves one of one's own amazons one or more empty squares in a straight line (orthogonally or diagonally), exactly as a queen moves in chess; it may not cross or enter a square occupied by an amazon of either color or an arrow. Second, after moving, the amazon shoots an arrow from its landing square to another square, using another queenlike move. This arrow may travel in any orthogonal or diagonal direction (even backwards along the same path the amazon just traveled, into or across the starting square if desired). An arrow, like an amazon, cannot cross or enter a square where another arrow has landed or an amazon of either color stands. The square where the arrow lands is marked to show that it can no longer be used. The last player to be able to make a move wins. Draws are impossible.
The algorithm that I chose this particular assignment was a Monte Carlo tree search (MCTS). MCTS works by learning which moves are most promising by using a large number of simulated games. From these simulated games, the MCTS stores a probabilistic confidence interval for each state (board configuration) which it encounters. MCTS works in four phases: selection, expansion, simulation and back-propagation. In the selection phase, the MCTS starts at the starting board configuration, and continues to recurse upon the most promising moves until it encounters a node with unexplored children. In the expansion phase, one of the unvisited children from the selected node is randomly returned. In the simulation phase, a game simulation is randomly carried out from the expanded node. The game simulation carrier out until one of the players is no longer able to move. Lastly, in the back-propagation phase, the results of the simulation are propagated back to along the game path, rewarding the winning player's moves and penalizing the loosing player. promising states more often. If you want a more in depth explanation of how MCTS works, see this article.
MCTS is beneficial because it does not require any specific heuristics that may be difficult to realize and expensive to compute. In addition, at test time, MCTS performs in optimal O(N) time. Because each board lookup is constant time, and no further exploration past the first level of moves is necessary, MCTS can perform well at test time for games with large branching factors where algorithms like alpha-beta pruning would struggle.
The Game of the Amazons presents a rather difficult problem: the search space is smaller than chess, but is nonetheless too extensive to learn within the span of a single day. Serious players should therefore train their MCTS extensively, but for the purposes of this assignment I have only managed to train the model for 10 hours. The result is decidedly lackluster, but demonstrates the general idea behind the algorithm. Using a board of size 4 with only 2 amazons per side was decidedly more interesting: after 2 hours of training, the model could beat me every time.
If one did want to train the MCTS to a sufficient standard, it might be helpful to ensure that some percentage of the overall state space has been encountered by the model. See this article for a detailed explanation on exhaustive search and the total size of the state space for various sized boards.
If you wish to try your hand against my algorithm, simply copy and paste my code between the given lines into your implementation and change the configuration file accordingly. If you wish to use a pre-trained model, made sure the pickle file is named 'ejw45_amazon.pickle' as is inside the same directory that the program is being run from. If you wish to train the model, set the optional parameter in the ejw45_MonteCarlo constructor to the amount of simulations that you would like to run. The model will automatically pickle and save itself every 10 iterations to 'ejw45_amazon.pickle'.