This project was made and submitted to the College Board as my "create task" for the AP Computer Science Principles course.
Go to https://catan.ivanovich.us/ to get balanced or unbalanced boards!The demo is hosted on a static site that chooses from a pre-generated, large list of 2,000 potential boards of each kind. This is an unfortunate waste of the capabilities of the backend, but this was very easy to set up free high-quality hosting. Code for that is on the static-site-deployment branch - I quickly threw it together using Frozen-Flask, if interested.
This algorithm is broken down in detail below.
- Built from the ground-up following the principles of object-oriented design
- Thorough board balance evaluation algorithm built upon 5 factors:
- Resource distribution
- Resource clustering
- Probability clustering
- Probability distribution per resource
- Probability distribution on board
- Test-driven development: thorough test system to evaluate each factor on several known layouts
- Flask-based web server with minimalistic interface
- Clear, vector-graphic interface of generated board layout
The board balance evaluation algorithm is built upon 5 distinct factors that are combined into a final score between 0 and 1, where 0 represents the most balanced board and 1 represents the least balanced board.
Typical ranges of this final score are detailed above.
When measuring distribution across the board, the symmetry of the shape of a Catan board was utilized. Three lines through the center of the board that do not cross any valid settlement locations can be drawn as follows:
We will refer to these lines as the "dividing lines." These were used in the resource distribution scoring algorithm. For each dividing line, the algorithm examines all possible settlement positions and counts the frequency of the 1-3 terrain types accessible at that position. For each resource type, the frequencies on each side of the line are summed, then the sums on one side of the dividing line are subtracted from the sum on the other side of the line. The differences are squared, then these squares are summed.
For example, here is what the process would look like for the horizontal dividing line for forest terrain hexes:
Here are what the resource distribution scores would look like for various boards, illustrating how the algorithm properly scores resource distribution for balance:
The lower the score, the more balanced the algorithm has deemed the board to be.
This algorithm is similar to the resource distribution algorithm, using the same three dividing lines. For each dividing line, this algorithm also considers every possible settlement location, summing the relative likelihoods of the 0-3 number tiles accessible from that location. Again, the scores are summed for each side of the dividing line, then the difference between the halves is squared and these squares are summed.Here are what the probability distribution scores would look like for various boards, illustrating how the algorithm properly scores probability distribution for balance:
The lower the score, the more balanced the algorithm has deemed the board to be.
Resource clustering is a far simpler algorithm, adding points for every edge that two resources of identical types share. Here are what the resource clustering scores would look like for various boards, illustrating how the algorithm properly scores resource clustering for balance:
Again, the lower the score, the more balanced the algorithm has deemed the board to be.
Probability clustering is analyzed by a similar algorithm, adding points for every edge shared by two terrain hexes with the same number tile. Here are what the probability clustering scores would look like for various boards, illustrating how the algorithm properly scores probability clustering for balance:
You get the drill, lower is better.
The fifth and final factor used to score a board's balance analyzes the probability distribution per resource. This algorithm was built to ensure **resources have a total probability of paying out proportional to their presence on the board.** In short, it takes the difference between the expected and actual payout probabilities for each resource type, squares the differences, then sums the squares.Here are what the probability distribution per resource scores would look like for various boards, illustrating how the algorithm properly scores probability distribution for balance:
As always, lower is better.
These 5 aforementioned factors are scaled down between 0 and 1 using their highest expected individual scores, then these scaled-down results are averaged with uniform weighting to provide the final 0-to-1 score.When a user asks the server to generate a balanced (or unbalanced) board, the server generates several thousand random boards, scores them, and shows the user the most (or least) balanced board that it generated. Thus, although not every board generated will be the theoretically most-balanced board possible, they will all be fairly close to this bound while continuing to vary with every generation, letting future games still be interesting.
Methodology inspired by and images from Board Game Analysis
The home page of the interface
The page displays a loading animation as it generates a balanced board
The user is redirected to a page displaying the generated board and its associated balance score. This board scored 0.0442, meaning it is very well-balanced. A cursory glance makes it clear why this is the case - there are several equally-good starting positions available.
The result if the user asked for an unbalanced board. This board scored 0.6126, meaning it is very unbalanced. It's clear why this is - terrain types are clustered together, as are the best number tiles.
The pages with the generated boards are populated via GET parameters, which would allow a player to bookmark/save a board they like or share the generated board with other players simply via URL.