Game of Amazons Player

Developed an intelligent player to compete against other team's programs in this strategy game.

Project Overview

The goal of this project was to develop a game player to effectively search the game tree and make optimal moves against opponant teams. We were provided game servers to connect to which recieve and send move messages as well as a pre-designed GUI. Our task was to implement basic game logic, move generation, and ensure proper communication with the game server, all while adhering to the rules of the game.

We were given freedom to implement any algorithms and optimizations we wanted to improve our players. Our team implemented a Minimax algorithm with alpha-beta pruning and iterative deepening. We added multiple heuristic evaluation functions and tested them to find the most optimal for our player.

Given the high branching factor of the game, minimax alone proved too slow, so iterative deepening was incorporated to allow the AI to progressively deepen its search, ensuring it always had a move to play if time ran out.

Basic Game Rules

Strategy turn-based board game for two players, played on a chess board with queens.

Objective: The goal of the game is to block your opponent's moves and control the board, preventing them from making a legal move. The player who cannot move any of their pieces loses.

In the version our servers were set up for, each player has 4 amazons, which are able to move like a queen in classic chess. After a queen moves, it then "shoots" an arrow to a square in the same turn. The arrow moves the same way an amazon does, however the square it lands on becomes blocked. Amazons and arrows may not "jump" blocked squares or other amazons.

Project Timeline

Progress Description
Server Communication Initially we started with a random move player to ensure we could communicate with the server and test our algorithm against a human player.
Basic Minimax Then we implemented a basic minimax player to make more intelligent moves.
Heuristic Functions We started out with a basic Move Count Heuristic to get started, later experimenting with various functions including, Min-Distance, Voronoi, and more.
Alpha-Beta Pruning After the basic minimax, it became all about optimizing the player to search the game tree more efficiently and prune unnecessary branches. We added Alpha-Beta pruning to our Minimax algorithm.
Iterative Deepening To further optimize the player, we are currently working on adding iterative deepening to fully take advantage of the time allotted to find the most optimal move.
Class Tournament The project culminates in a tournament against other teams within the class. Starting within lab sections and ending with on the Main Stage with the top players.

Final Analysis of our Player

Overall, the game client we developed stood the test and played effectively against opponent teams. It accurately traversed the game tree, evaluating utilities and returning the next best valid moves. Although there were some flaws in our heuristics, sometimes leading to sub-optimal moves, the player would continue to play well and often only lose by 1-3 squares. This project was a very practical way for team members to explore techniques for fine-tuning and optimizing algorithms. Topics discussed in class were directly related, which furthered our learning as we implemented and modified different approaches to work best with our client.

Random Move Player

Basic Minimax Player

Tournament Match

Video to be uploaded