Artificial intelligence to play the Royal Game of Ur
This project implements artificial intelligence that uses a negamax algorithm to play the Royal Game of Ur. Because of the random element of the game, the algorithm has to calculate a weighted average score for each move and roll instead of travering the game tree directly. In addition, move reordering and alpha-beta pruning are used to speed up the algorithm. The project also contains a small CLI app to test the AI player against other types of players.
Ur is a turn-based race game played between two players. Each players starts with seven pieces, the objective being to get all seven pieces to the end of the above board before their opponent.
During each turn, a player rolls four binary dice giving a roll between 0 and 4. They may advance one of their pieces forward or move a piece onto the board by the value of the roll. They may not move a piece if its destination is blocked by another piece belonging to the same player. Also, the player may move a piece off the other end of the board, making it finished (the piece cannot be moved if the roll value is greater than the exact amount needed to finish). If a player has no moves, their turn is skipped. Otherwise, the player must make a move.
The first four and last two tiles shown above are safe zones for either player's pieces. However, the middle eight tiles are part of a competition zone shared by both players. In this zone, a player can capture another player's pieces if they land on the same tile, sending it back off the board.
There are also five rosette tiles (marked as flowers on the above board). If a player lands on one of these tiles, they get to move again, skipping their opponent's turn. The rosette tile in the competition zone has the special property that pieces on it are invulnerable and cannot be captured by the opponent.
In order to better represent this board programmatically, it has been modified into the functionally equivalent board below. The first four tiles and last two tiles represent the safe zone, and the rest is the competition zone.
To get a local copy up and running follow these simple steps.
You must have CMake 3.16 or higher installed to build this project. You must also have Doxygen and required packages to build the documentation as shown below.
- Clone the repo and move into it
git clone https://github.com/BattleMage0231/Urr.git cd Urr - To build the executable to Urr/bin
cmake . && make
- To build the documentation
cmake . docs && doxygen Doxyfile.out
Simulate one game between two AI players:
urr -p AI -p AISimulate ten games between an AI player and a random player, where the AI player is always white:
urr -p AI -p RANDOM -g 10Simulate a game between a human player and an AI player, where the colors are random:
urr -p HUMAN -p AI -rSee the full list of command line arguments:
urr -hDistributed under the MIT License. See LICENSE for more information.
Leyang Zou - leyang.zou@student.tdsb.on.ca
Project Link: https://github.com/BattleMage0231/Urr