Project 01: Game of Hex
Individual, Due: 2025 Sep 16, 11:59pm
In this assignment, you will write a program to play a game of Hex, and you will analyze the run times of different union-find implementations.
This assignment is based on a web exercise from the Algorithms 4/e book website.
Getting Started
You will need to follow the Starting an Assignment in the Setting up for COS265 document.
Important
Read through the entirety of these instructions before beginning.
Introduction
This section introduces the general game of Hex, how we will model the game with data structures, and the main problem of determining a winner.
Videos
I have a couple of videos that go into more details.
Note
Although these videos were created a while ago, the project details are still the same. (this gives you a sneak peek at how much the write up has changed over the past few years!)
Game of Hex
The game of Hex is played on a diamond-shape board of hexagons. The board is typically 11-by-11, totaling in 121 hexagons, but the board can have other dimensions. During the game, two players take turns placing their colored pieces (red and blue) onto an empty hexagon tile until a players creates a connected path of their pieces from one of their sides to the opposite.
The figures below show a 3-by-3 board, a 6-by-6 board, and an 11-by-11 board.
 |
 |
 |
Note
The game of Hex can never end in a tie; either player 1 or player 2 will win the game. In 1952, John Nash proved this statement to be true and that there exists a winning strategy for the first player to make a move on a symmetric (\(N\)-by-\(N\)) board.
Modeling Hex
We will model the board using an \(N\)-by-\(N\) grid of hexagon tiles. Each tile is either unset or it is set by player 1 (red) or player 2 (blue). A player may set any unset tile on the board to their color. We say that the game is won if a player forms a connected path of colored tiles between their two respective sides of the board. player 1 tries to connect the top-left and bottom-right sides of the board, while player 2 tries to connect the bottom-left and top-right sides of the board.
Note
Due to the hexagon shape, all tiles except those along the edge of the board touch six other tiles. The edge tiles have two, three, or four neighboring tiles.
The left figure below is an example of a game just starting, the middle is in progress (no winner, yet), and the right figure shows a game won by player 1. Along the edges of the board extra tiles are drawn to represent the sides corresponding to the two players. The top-left and bottom-right sides correspond to player 1, and the bottom-left and top-right correspond to player 2. Notice that the path connecting sides of player 1 are highlighted in light red.
 |
 |
 |
The Problem
A player has won a game when there exists a connected path between the opposite sides corresponding to the player. Your task is to write the code to manage the board state and to detect when a player has won.
The only game rule that your implementation should enforce is that a player may place their piece only in an unset tile. The rest of the game rules are enforced by the the framework. In other words, you should not enforce that player 1 goes first, then player 2, then player 1, etc.
Hex API
The framework includes several classes that provide different functionality.
Some classes rely on other classes.
You will need to provide implementations for only two of the classes: HexBoard and HexBoardStats.
The following subsections describe each class in detail.
The HexBoard Class
To model a hex board game, create a data type HexBoard with the following public API:
HexBoard is the constructor that creates N-by-N grid with all tiles unset.
isSet returns whether tile in row row and column col has been set by either player (false means the tile is unset).
getPlayer returns which player has set the tile, 1 for player 1 or 2 for player 2.
setTile sets tile to specified player.
numberOfUnsetTiles returns number of unset tiles.
hasPlayer1Won and hasPlayer2Won return whether the game has been won by player 1 or by player 2 (respectively).
isOnWinningPath returns whether the given tile is on the winning path.
By convention, the row (row) and column (col) indices are integers between \(0\) and \(N-1\) specified as (row, col), where \((0,0)\) is the left-most tile in the visualizer, \((N-1,0)\) is the top-most tile, \((0,N-1)\) is the bottom-most tile, and \((N-1,N-1)\) is the right-most tile.
In other words, row numbers increase up-right, while column numbers increase down-right.
Union-Find index from HexBoard (row,col): Notice that HexBoard works with rows and columns, but Union-Find works with an index. Often in projects you will need to a way to convert to/from different numbering/labeling schemes, and this project is one of those times! If you need a hint on how to do the conversion, watch this explaination video.
Edge Cases:
Throw a java.lang.IndexOutOfBoundsException if any argument to a function is outside its prescribed range.
The constructor should throw a java.lang.IllegalArgumentException if \(N \leq 0\).
The setTile function should throw a java.lang.IllegalArgumentException if the tile is already set.
See the Java snippet below to see an example of throwing an exception.
if(N <= 0) throw new java.lang.IllegalArgumentException();
Performance Requirements:
You will use two different implementations of union-find data type and analyze the corresponding running times (see below).
Regardless of which union-find implementation you use, the constructor should take time proportional to \(N^2\), and all methods should take constant time plus a constant number of calls to the union-find methods union(), find(), connected(), and count().
Winning Path:
The isOnWinningPath is not an easy method to implement correctly, as backwash can occur.
Backwash is when a tile is connected indirectly to the player's top virtual tile via the bottom virtual tile.
The left figure below shows the backwash in effect, where the right figure does not.
Notice how the red tiles at the top and at the right are not connected to both sides of the board, and yet they are highlighted as being on the winning path in the left figure.
 |
 |
The HexBoardVisualizer Class
The HexBoardVisualizer class will visualize a HexBoard instance.
This class contains a main() that takes a filename as an argument.
The specified file contains a list of integers in the following format
N r0 c0 p0 r1 c1 p1 r2 c2 p2 r3 c3 p3 ...
where N is the size of the board and the following triplets r c p specify the tile (row r, col c) to set by player p.
We have provided many test files under the data_ref/ folder.
Note
The visualizer does not enforce that players must alternate turns. This makes it easier to run certain tests and find bugs.
Tip
Use this main to run tests over and over again.
You can create tests by hand or by using the console output from InteractiveHexBoardVisualizer.
The InteractiveHexBoardVisualizer Class
The InteractiveHexBoardVisualizer class will interactively visualize a HexBoard instance using the HexBoardVisualizer.
This class contains a main() that optionally takes an integer as argument to specify the board size.
If the argument is not specified, the default board size is 11-by-11.
When running, two players take turn using the mouse to set tiles on the board until one of the players wins.
Tip
The row, column, and player number are written to the console after a tile is set.
You can copy this data into a file to create your own tests, and then you can run these tests with HexBoardVisualizer.
The HexBoardStats Class: Monte Carlo Simulation
Many games are considered a broken game or a solved game, where there is a clear advantage in being the first player. For example, in Tic-Tac-Toe, the first player can guarantee a win or a tie every single game as long as they play perfectly (winning vs tie depends only on mistake of second player). Also on the list is Connect Four.
One of your tasks is to determine if there is an advantage to being player 1 in the game of Hex. However, because Hex can be played on boards of any size (\(N \geq 1\)), you will need to check a bunch of board sizes to see if Hex is broken for any board size or only some board sizes, or if Hex is not a broken game. (Hint: consider a 1-by-1 hex board)
Note
To simplify our analysis, we will assume both players play randomly.
To estimate the probability of player 1 winning a game, consider the following computational experiment:
- Repeat the following to simulate multiple games
- Initialize all tiles to be unset
- Repeat the following to simulate a game play until a player has won:
- Choose a tile row and column uniformly at random among all unset tiles.
- Set the tile according to the current player (players take turns, starting with player 1)
- Record if player 1 has won the game.
- The fraction of games won by player 1 over the total number of games "played" provides an estimate of the probability of player 1 winning a game.
For example, if 10 games are played on a 10-by-10 hex board and 5 of the games were won by player 1, the estimated probability of player 1 winning on a 10-by-10 board is \(5 / 10 = 0.5\). Clearly this estimation technique does not use any game playing strategy to simulate experienced players; it can only simulate players that randomly place their pieces. Regardless, there are some interesting statistics to glean from such an exercise.
The figure below shows the probability estimates for player 1 winning the hex game after playing 10 games for different board size. The horizontal axis is the board size (left=2-by-2; right=15-by-15). The red horizontal line indicates a probability of \(0.5\), where there is an equal probability of player 1 and player 2 winning the game. Above the red line indicates a higher probability of player 1 winning (top=100%), and below indicates a lower probability (bottom=0%).
 |
Notice that it is difficult to determine any trend in the figure above. Below are the results after re-running the same experiment three more times (\(T=10\), \(N=2\) to \(N=15\)).
 |
 |
 |
Again, it is difficult to gain any intuitions from the statistics, since such low sample sizes introduces a large variance in the probability estimates. For example, the left-most point (2-by-2 board) is sometimes above the red line, indicating player 1 wins more often, and sometimes below, indicating player 1 loses more often.
One way to reduce variance in our estimates is to increase the number of games played, \(T\). The figures below show the probability estimates of player 1 winning on boards 2-by-2 up to 15-by-15 by playing 10, 100, and 1000 games for each board size. Notice that the variance in the estimates is lower in right figure and a pattern begins to emerge.
 |
 |
 |
To perform a series of computational experiments, create a data type HexBoardStats with the following public API.
The constructor should take three arguments N0, N1, and T, and perform T independent computational experiments (discussed above) for each N-by-N board where N0 <= N <= N1.
The constructor should throw a java.lang.IllegalArgumentException if N0 <= 0, N1 < N0, or T <= 0.
Calculate the probability estimate for player 1 winning for each of the board sizes.
Use the standard random class (StdRandom) from stdlib.jar to generate random numbers.
Do all of the work inside the constructor so the other methods can return answers in constant time.
Note
Overall, the HexBoardStats constructor will play and record the results of \((N1 - N0 + 1) * T\) games.
The getN0, getN1, and getT functions return the N0, N1, and T parameters (respectively) that were passed to the constructor.
The getP1WinProbabilityEstimate function returns the appropriate probability estimate for player 1 winning on an N-by-N board.
This functions should throw a java.lang.IndexOutOfBoundsException if N < N0 or N > N1.
The getP2WinProbabilityEstimate function returns the appropriate probability estimate for player 2 winning on an N-by-N board.
Do not do any work in thee methods; you should simply return the value already computed from the constructor.
Note
The return values from calling getP1WinProbabilityEstimate and getP2WinProbabilityEstimate with some N should always be in \([0,1]\) range, and their sum should be exactly \(1\).
Example values after creating HexBoardStats(2, 15, 10):
T = 10 N = 2, P1 = 0.5 (5), P2 = 0.5 (5) N = 3, P1 = 0.6 (6), P2 = 0.4 (4) N = 4, P1 = 0.6 (6), P2 = 0.4 (4) N = 5, P1 = 0.5 (5), P2 = 0.5 (5) N = 6, P1 = 0.7 (7), P2 = 0.3 (3) N = 7, P1 = 0.5 (5), P2 = 0.5 (5) N = 8, P1 = 0.6 (6), P2 = 0.4 (4) N = 9, P1 = 0.6 (6), P2 = 0.4 (4) N = 10, P1 = 0.3 (3), P2 = 0.7 (7) N = 11, P1 = 0.6 (6), P2 = 0.4 (4) N = 12, P1 = 0.8 (8), P2 = 0.2 (2) N = 13, P1 = 0.5 (5), P2 = 0.5 (5) N = 14, P1 = 0.3 (3), P2 = 0.7 (7) N = 15, P1 = 0.5 (5), P2 = 0.5 (5)
Note
You will need to use T > 100000 to get low variance results, however this will take a very long time with an inefficient implementation of the union-find data type.
See below for more details.
Report your findings in the readme.md as a table or chart.
Requirements and Submission
You will need to implement several functions in HexBoard and HexBoardStats to perform runtime analysis.
Analysis of Running Time
Analyze the running times of QuickFindUF and WeightedQuickUnionUF to verify the performance claims made in the slides.
We will use HexBoardStats to measure the time it takes to play a bunch of games, and then solve for the exponents and factors using the doubling hypothesis (assuming the runtimes follow the power law equation).
Implement the HexBoard data type using the quick-find data type QuickFindUF from algs4.jar.
Measure the running time of HexBoardStats for various values of N and T by using the stopwatch data type (Stopwatch) from stdlib.jar.
Give a formula using tilde notation for the total running time on your computer (in seconds) as a single function of both N and T.
Now, switch the HexBoard implementation to use the weighted quick-union data type WeightedQuickUnionUF from algs4.jar.
Answer the same questions in the previous paragraph.
Report your findings in the readme.md.
Important
Be sure your implementation uses the WeightedQuickUnionUF type before you submit, otherwise your code will run too slowly to pass our tests!
All methods of HexBoardStats except for the constructor should return in constant amount of time!
In other words, calling getP1WinProbabilityEstimate or getP2WinProbabilityEstimate should take exactly the same amount of time no matter what value of N is passed.
Only the constructor is allowed to take time dependent on N0, N1, and T.
Conformance Requirements
On this assignment, the only library functions you may call are those in java.lang, stdlib.jar, and algs4.jar.
Do not import any other library.
You may add private functions or private inner classes in the classes provided, but you may not add public functions, change the signature of the public functions, or add any other public classes.
Files
The diagram below indicate which files you can edit, which files/folder you should not edit, and the rest are files/folder that might be changed by IntelliJ or git but you should not change directl.
P01_Hex/... ├─ P01_Hex.iml ├─ .idea/... ├─ .git/... <- **DO NOT EDIT** ├─ .gitignore <- **DO NOT EDIT** ├─ .gitmodules <- **DO NOT EDIT** ├─ out/... ├─ libs/... ├─ src/... │ ├─ HexBoard.java <- Java file that you might need to modify │ ├─ HexBoardStats.java <- Java file that you might need to modify │ │ The following files should not need edited │ ├─ HexBoardVisualizer.java │ └─ InteractiveHexBoardVisualizer.java ├─ data/... <- Additional test input files you create ├─ data_ref/.. <- **DO NOT EDIT** └─ readme.md <- Fill this out before submission!
You may create your own test games under the data/ folder.
Submission
Once you have completed the assignment requirements, simply stage, commit, and push your changes to the CSE GitLab, and then close the issues.
Do NOT submit anything to the course Brightspace page.
Grading Rubric
| Implementation Correctness | |
| 3pts | Correct HexBoard: isSet, getPlayer, setTile, numberOfUnsetTiles |
| 3pts | Correct HexBoard: hasPlayer1Won, hasPlayer2Won |
| 3pts | Correct HexBoard: isOnWinningPath |
| 3pts | Correct HexBoardStats API |
| Implementation Performance and Conformance | |
| 3pts | Efficient HexBoard code (must also be correct) |
| 3pts | Efficient HexBoardStats code (must also be correct) |
| 3pts | Meets conformance requirements (API + Exceptions) |
| Documentation | |
| 3pts | Completed readme.html |
| 3pts | Reasonable win analysis |
| 3pts | Reasonable runtime analysis |