Atropos is two-player game invented in our own Computer Science Department by Kyle Burke and Prof. Shang-Hua Teng. For this assignment we implemenedt a strategy to play this game intelligently (as opposed to randomly or via brute-force search). Specifically, we:
Designed a static evaluator,
Selected alpha beta pruning with a custom heuristic (explained below)
Implemented this algorithm and apply it to the Atropos game
Rules of the Game
The rules of the game are as follows:
Atropos is a two-player game played on a triangle-shaped board. It is convenient to visualize each position on this board as a circle rather than a square.
There is no “regulation” size for the board. You and your opponent agree on the board size for each game. Atropos gets interesting when the board size is at least 6.
The boundaries of the board are pre-colored before the game starts. The “bottom” side of the triangle is always colored with the red-blue pattern. The left side is always colored with the red-green pattern, and the right side with the green-blue pattern.
Each move (play) consists of filling an uncolored position (circle) on the board with one of the three colors (red, green, or blue).
Restrictions on the placement of the next move are as follows. The very first move may be anywhere on the board. For all subsequent moves, if the previous move (play) was adjacent to some uncolored circles, the current move must select one of these uncolored circles. Otherwise, if there are no adjacent uncolored circles, the current player may play anywhere on the board.
The game is over when a player (call her player A) colors a circle in such a way that it completes a three-colored triangle (i.e., a configuration of red, green, and blue circles all adjacent to each other). When this happens, player A loses the game and player B wins. Note that player A can lose either due to carelessness or because player B forces player A to make the losing move (see rule 5).
A Sample Game
Here is an example of a game played on the board of size 4.
Player A goes first, coloring a circle red
Player B colors an adjacent circle blue
Player A colors another circle blue
Player B sets up a trap by coloring another circle blue
Player A has to color a circle at the top of the board. Unfortunately for her, any color is a losing color. The yellow triangle delineates three adjacent red-gree-blue circles that form a losing configuration. Game over!
Programming a Player
We use a redundant coordinate system to specify a position by its distance from the bottom side (height), the left-hand side (left distance) and the right-hand side (right distance). This picture shows a board where each of the coordinates runs from zero to five.
The location of a point is specified by a triple (x, y, z) where x is the height, y is the left distance and z is the right distance. In the next picture, we have two positions marked.
The yellow point is at (3, 1, 2) and the grey point is at (1, 3, 2). Note that yellow and grey are not valid Atropos colors–we picked them for visualization purposes only.
The “size” of a board refers to the number of circles on a side in the playable region of an initial board. Since the boundary of an Atropos board always begins colored in, this is the length of the red bracket in our example picture above; The size of the above board is four.
Notice that for any point (x, y, z), x + y + z = size + 2. Be sure that this property holds whenever you make a move, otherwise the move will be considered invalid.
Analysis
Our program utilizes the Alpha-Beta Pruning procedure discussed in class. For each turn the player parses in the game state and executes 3 Alpha-Beta procedures, one for each color. It then chooses the best color solution it can and makes that move. The evaluator function searches for win conditions first and if it finds any returns a large value. It then searches for trapping conditions and scores them based on how many open spaces there are in the trapping condition. After running the completed player several times a diagonal play tendency was noted. The player also exhibits a trend towards trapping its opponent, but usually it’s over the course of the game, and not a quick direct trap. When playing against human players our code does a good job of holding its own, and unless a complicated trap is sprung, it can win about half the time. Our tournament results match this with a win-lose of 50-50. When playing against random players it win more quickly, and seldom loses, but if it does its usually in the last move of the game.
Intelligent Player
Atropos
Atropos is two-player game invented in our own Computer Science Department by Kyle Burke and Prof. Shang-Hua Teng. For this assignment we implemenedt a strategy to play this game intelligently (as opposed to randomly or via brute-force search). Specifically, we:
Rules of the Game
The rules of the game are as follows:
A Sample Game
Here is an example of a game played on the board of size 4.
Player A goes first, coloring a circle red
Player B colors an adjacent circle blue
Player A colors another circle blue
Player B sets up a trap by coloring another circle blue
Player A has to color a circle at the top of the board. Unfortunately for her, any color is a losing color. The yellow triangle delineates three adjacent red-gree-blue circles that form a losing configuration. Game over!
Programming a Player
We use a redundant coordinate system to specify a position by its distance from the bottom side (height), the left-hand side (left distance) and the right-hand side (right distance). This picture shows a board where each of the coordinates runs from zero to five.
The location of a point is specified by a triple (x, y, z) where x is the height, y is the left distance and z is the right distance. In the next picture, we have two positions marked.
The yellow point is at (3, 1, 2) and the grey point is at (1, 3, 2). Note that yellow and grey are not valid Atropos colors–we picked them for visualization purposes only.
The “size” of a board refers to the number of circles on a side in the playable region of an initial board. Since the boundary of an Atropos board always begins colored in, this is the length of the red bracket in our example picture above; The size of the above board is four.
Notice that for any point (x, y, z), x + y + z = size + 2. Be sure that this property holds whenever you make a move, otherwise the move will be considered invalid.
Analysis
Our program utilizes the Alpha-Beta Pruning procedure discussed in class. For each turn the player parses in the game state and executes 3 Alpha-Beta procedures, one for each color. It then chooses the best color solution it can and makes that move. The evaluator function searches for win conditions first and if it finds any returns a large value. It then searches for trapping conditions and scores them based on how many open spaces there are in the trapping condition. After running the completed player several times a diagonal play tendency was noted. The player also exhibits a trend towards trapping its opponent, but usually it’s over the course of the game, and not a quick direct trap. When playing against human players our code does a good job of holding its own, and unless a complicated trap is sprung, it can win about half the time. Our tournament results match this with a win-lose of 50-50. When playing against random players it win more quickly, and seldom loses, but if it does its usually in the last move of the game.
Old Page
To compile g++ -o kPlayer kPlayer.cpp
Players
They are all the same, so to compile fillow instructions above where k = name of cpp file-
luiscarr
-
newrad
-
volta11
Source Files