Inventing a board game
An algorithmic approach
Introduction
Some years ago, I tried to invent a board game. I wanted to create one with a lot of activity with cards but still turn-based. I wrote down some rules after tinkering with some ideas. I wrote the list of cards and their effects. I convinced some friends to try it out and it quickly became obvious that some cards were overpowered while others were useless. Also, there was a diffused sense of “missing purpose” among the players. I tried to fix it but then moved on to other projects and forgot about it.
Fast forward to December 2024, I have a full-time job, a master’s degree in progress, a blog and I moved to another city. I needed to study for the upcoming exam session but the will to study was nowhere to be found. So, I started to look for new ideas for my blog and ended up digging in my “Projects” folder in my old laptop. That’s where I found a strange “board_game.docx” file and here we are, four months later.
Escaping the black hole
The players are a group of spaceship pilots who were fighting in space but then ended up with their ships broken orbiting around a black hole. Moreover, the group of asteroids they were fighting in is getting dangerously closer, attracted by the black hole. Between the black hole and the incoming asteroids, they will need to find a way to save themselves. If they cannot manage to escape the orbit, they will all eventually fall in.
The number of players can range from 4 to 6. Each player can win by repairing their ship. To do so, they require:
- 1 computer
- 1 engine
- enough energy to power the computer and the engine
Each one of these three requirements has a variation in order to allow more winning combinations. In particular, there are:
- two types of computers: one which requires one additional energy source and the other which does not.
- two types of engines: one which requires energy and another which does not but is needed in higher quantity.
- two types of energy sources: one which provides half the energy of the other but is common.
The game’s loop is straightforward:
- at the first turn, each player draws 5 cards from the deck.
- at the beginning of each turn, the player draws one card from the deck and can play any number of cards.
- each card, once it’s been played, goes into the discard pile and can never come back into the game, meaning that, once the deck is finished, no player can draw any card and they have to play with whatever is left in their hands.
- only those who manage to escape win. All the others, even those who remain in game after the deck is finished, lose.
Here are the card types with their effects:
- Supplies: all players draw a card in order starting from whoever played this card.
- Missiles: shoot at two other players of your choice. If they don’t protect themselves, they discard a card.
- Meteor Shower: you must play this card as soon as you draw it from the deck. Everybody needs to discard an Engine of any kind otherwise they lose.
- Barter: pick a player with at least one card in hand. You two exchange a card from your hands.
- Fuel Cell: it is needed to make engines work.
- Computer: discard this card with an Engine and 2 Fuel Cells to Escape the Black Hole.
- Quantum Computer: you can use this instead of a Computer but you need 1 extra Fuel Cell.
- Swap: pick a player and exchange your hand with theirs.
- Electromagnetic Pulse: place this card in front of you and remove it at the beginning of your next turn (before drawing from the deck). When this card is on the table, Solar Panels and Electric Engines do not work and cannot be used.
- Threat: pick a player with at least one card in hand. Say the name of a card: if they have it, they must give it to you.
- Combustion Engine: discard this card, a Computer and 2 Fuel Cells to Escape the Black Hole.
- Electric Engine: discard 3 Electric Engines and a Computer to Escape the Black Hole.
- Solar Panels: you can discard 2 Solar Panels instead of a Fuel Cell when you need to.
- Laser Gun: shoot at a player of your choice, if they don’t protect themselves, they discard a card of their choice.
- Free Repair: discard this card and a Scrap to draw a card.
- Scrap: this card has no effect.
- Exchange of Information: every player takes a card from their hand and places it face-down on the table. Shuffle all these cards and give them back to the players one by one starting from whoever played this card. The players who have zero cards do not participate in this.
- Energy Shield: use this card when somebody is shooting at you to protect yourself.
- Espionage: take a card from the hand of a player of your choice.
The basic approach
Having defined the rules of the game, now comes the moment for the real question: how can I optimize this game? How can I find out the most balanced set of cards? How can I discover loopholes in the rules without playing the game hundreds of times IRL? How can I find out if some cards are useless or overpowered?
So, I implemented a basic engine to simulate random matches, with players playing random moves. With this in hand, we can transform this task into a minimization problem. We define some constraints that we want to satisfy (or at least we want to compromise as little as possible with) and an objective function to minimize.
The objective function can be the sum (or the mean) of the following:
- probability of first turn victories: one player has everything needed to win on the first turn
- probability of defeat by meteor shower: all alive players losing at the same time due to the meteor shower
- probability of victory by meteor shower: all alive players except one lose at the same time due to the meteor shower
- probability of the game being too long: at least two alive players and at least one card in the deck after a certain number of turns
- probability of having no moves in a given turn: players hate being forced to do nothing
The actual algorithm
Given all of the constraints above, we finally define what the algorithm (or the problem) looks like.
The inputs (the $x$ in $f(x)$) of our objective function will be the number of each card type to put in the deck (how many Solar Panels, how many Laser Guns and so on): starting from a minimum of 1 for all cards even though it could be interesting to find out if a card is useless, meaning that the game has a higher fun coefficient (as I like to call it) without it in the deck.
So, the input of our function gives us all we need to build the deck. The evaluation of the function in a given point will be to simulate a lot (let’s say 1 million, for now) random matches (let’s say 1 million fixed seeds, so that the function is deterministic). During these matches some statistics are gathered and, based on those, the actual final score will be computed.
Oddly enough, the search space we just defined is big but finite. We have 19 card types (if I counted correctly), assume 5 possibilities to check for each. This comes up to $5^{19} = 19.073.486.328.125 \approx 1.907\cdot 10^{13}$. If each evaluation of the function (simulating 1 million matches) takes an hypothetical (and highly optimistic) 1 second to compute, this would take around half a million years. All of this yapping is to say that we need a little search algorithm to navigate efficiently this space.
Something simple like Pattern Search should suffice, starting from the configuration I thought was good. At each iteration, say the current point is $x_0$, we need to evaluate all the points $x_1$ in the discrete hyperplane such that $\parallel x_1 - x_0 \parallel = 1$. This translates into checking the same configuration as the current one but adding or subtracting one card for each type. This means that, at every iteration, we need to evaluate $2 \cdot d$ configurations and $d$ being 19 in our case, the total is 38. This algorithm is not the best one for minimization and it is, honestly, rarely used due to its computational cost scaling linearly in the number of dimensions of the search space making it a poor choice for problems with high dimensionality. Unfortunately, I haven’t found much else in the space of discrete derivative-free minimization (maybe a genetic algorithm?).
Results
This was the starting configuration:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
+-------------------------+----+
| Espionage | 6 |
| Energy Shield | 6 |
| Exchange of Information | 2 |
| Scrap | 5 |
| Free Repair | 4 |
| Laser Gun | 6 |
| Supplies | 3 |
| Missiles | 2 |
| Meteor Shower | 1 |
| Barter | 4 |
| Fuel Cell | 10 |
| Computer | 2 |
| Quantum Computer | 2 |
| Swap | 2 |
| Electromagnetic Pulse | 1 |
| Threat | 2 |
| Combustion Engine | 4 |
| Electric Engine | 9 |
| Solar Panels | 10 |
+-------------------------+----+
| Total | 81 |
+-------------------------+----+
After 22 steps, as shown here …
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Step 0/100: +1 Computer (score: 1.38072)
Step 1/100: +1 Computer (score: 1.3236)
Step 2/100: +1 Combustion Engine (score: 1.2699)
Step 3/100: +1 Computer (score: 1.22101)
Step 4/100: +1 Combustion Engine (score: 1.16884)
Step 5/100: +1 Computer (score: 1.12414)
Step 6/100: -1 Missiles (score: 1.07422)
Step 7/100: +1 Combustion Engine (score: 1.02914)
Step 8/100: +1 Supplies (score: 0.997686)
Step 9/100: +1 Supplies (score: 0.958065)
Step 10/100: +1 Supplies (score: 0.921841)
Step 11/100: +1 Combustion Engine (score: 0.885602)
Step 12/100: +1 Supplies (score: 0.860632)
Step 13/100: +1 Computer (score: 0.820865)
Step 14/100: +1 Supplies (score: 0.783823)
Step 15/100: +1 Supplies (score: 0.75131)
Step 16/100: +1 Supplies (score: 0.728306)
Step 17/100: -1 Laser Gun (score: 0.703216)
Step 18/100: +1 Computer (score: 0.683618)
Step 19/100: -1 Threat (score: 0.667535)
Step 20/100: +1 Combustion Engine (score: 0.655467)
Step 21/100: -1 Solar Panels (score: 0.637856)
… the algorithm landed on this configuration:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
+-------------------------+----+
| Espionage | 6 |
| Energy Shield | 6 |
| Exchange of Information | 2 |
| Scrap | 5 |
| Free Repair | 4 |
| Laser Gun | 5 |
| Supplies | 10 |
| Missiles | 1 |
| Meteor Shower | 1 |
| Barter | 4 |
| Fuel Cell | 10 |
| Computer | 8 |
| Quantum Computer | 2 |
| Swap | 2 |
| Electromagnetic Pulse | 1 |
| Threat | 1 |
| Combustion Engine | 9 |
| Electric Engine | 9 |
| Solar Panels | 9 |
+-------------------------+----+
| Total | 95 |
+-------------------------+----+
Analysis
The limits were initially a minimum of 1 and a maximum of 10 for each card. After many attempts, however, I noticed that the algorithm kept maxing out the number of Solar Panels and Fuel Cells. So, I increased the maximum for those two cards to 20 but those didn’t change. What changed was the number of Supplies cards, which then became maxed out. So I tried increasing that maximum number of Supplies cards and it became maxed out again.
Why is that?
The supplies card is a “free” card, meaning that a player can always play it without conditions. This means that a higher number of these cards allows players to always have at least one playable card, lowering the average number of turns without moves.
Another thing we can notice from the sequence of improvement steps above is that there were far too few resources at the beginning and far too many “combat” cards. Since this is not what I want this game to be about, it means that I modelled the objective function incorrectly, probably missing some important metric.
Conclusions
In this post I experimented with combining board games and algorithms and the whole experience has been really fun and educating. You may have noticed that I have oversimplified some things or directly omitted others. This whole project was a new challenge for me and I wanted to get some results relatively quickly. There are a lot of things that I would like to do differently and I will probably need to expand this project. Maybe it will become a library/framework on its own.
The next post (I can guarantee you this will not be the last one) will dive more in depth on the problem or maybe try new types of board games. At the moment, I have at least 4 other board games with the rules already on paper, so the ideas are not missing.
Thank you very much for having taken time to read this and see you in the next post.
P.S. If you’re interested in the actual code, here it is.