The game Master of Orion, first released in 1995 by Microprose, entails settling the galaxy planet by planet.  To settle a planet, the player must construct a colony ship on one of her/his planets, send that ship to a new, unoccupied habitable planet, land the ship, and then send colonists from some of their planets to the new planet.  Early in the game,

• it costs about 550 MC to build the colony ship,
• it takes around 5 turns for the colony ship to reach a new planet,
• it takes and additional 5 turns for additional colonists to arrive on the planet on separate (free) transport ships,
• it takes around 20 turns for the planet to build new factories before it can build new colony ships, and
• the new planet might generate 110 MC per turn of income to build more ships,

so 30 turns after investing 550 MC, the player’s income increases by about 110 MC per turn.

If we try to create a differential equation to model the early stage of the game, we get something like

$$y'(t) = \frac{110}{550} y(t-30) = \frac{1}{5}y(t-30) $$

where $y(t)$ is the income available for building ships on turn $t$. This differential equation has a solution of the form $$y(t) = c \exp(\alpha t).$$ We can compute the derivative and substitute into the differential equation to find $\alpha$.

$$y'(t) = c\alpha \exp(\alpha t).$$

So,
$$\begin{aligned} c\alpha \exp(\alpha t) &= y'(t) =\frac{1}{5} y(t-30)\\c\alpha \exp(\alpha t) &=\frac{1}{5}c \exp(\alpha(t-30)) \\\alpha &=\frac{1}{5} \exp(-30 \alpha) \\\alpha \exp(30 \alpha) &=\frac{1}{5}\\30 \alpha \exp(30 \alpha) &= 6 \end{aligned}$$
According to the definition of the Lambert W function $W_0(x)$ for $x>0$,
$$ W_0(z) = x$$
if and only if
$$ x\exp(x) = z.$$
Setting $x=30\alpha$ above gives
$$\begin{aligned}W_0(6) &= 30\alpha\\ W_0(6)/30 &=\alpha\\ \alpha &= W_0(6)/30\approx 0.0477468.\end{aligned}$$
So the the economy at the start of the Master of Orion gain should grow by about 5% per year.

More generally, if

– the time between the investment in the colony ship and the maturing of the colonized planet is $T$,
– the cost of the ship is $C$,
– and the mature planets produces $i$ income per turn,
then the income on turn $t$ can be approximated by $$y(t) = y(0) \exp(\alpha t)$$ where
$$\alpha = \frac{W_0\left(\frac{i T}{C}\right)}{T}.$$

(Thanks to stackedit.io for helping me format the TeX.)

There are many games that have an investment phase followed by an exploitation phase including the card game Dominion, Terraforming Mars, Slay the Spire (during a combat), Saint Petersburg, Roll for the Galaxy, Master of Orion, Hansa Teutonica, Century Spice Road, Cash Flow and many more games.

One of the basic ideas is that you should not invest in something if there is not enough time for the investment to pay for itself.

A VERY SIMPLE HYPOTHETICAL GAME

Suppose that there are $T$ turns left in a game excluding the current turn, your current income level is I dollars per turn, and you have two choices:

1. (invest) Invest this turn to increase your income from $I$ dollars per turn to $I +i$ dollars per turn. You would then receive $I+i$ dollars per turn for the remaining $T$ turns for a total of $(I+i)\cdot T$ dollars.
2. (don’t invest) Receive $I$ dollars this turn and the remaining $T$ turns for a total of $(T+1)\cdot I$ dollars.

EXAMPLE

For example, assume that

• it is currently turn 5,

• at the start of turn 5 you have an income of $I$ = \$2 per turn,

• the game ends on turn 9, and

• you have the choice between two options:

1. Invest this turn to increase your income from \$2 per turn to \$3 dollars per turn. You would then receive \$3 dollars per turn for turns 6,7,8, and 9 for a total of \$3 * 4 = \$12 dollars.

2. Do not invest and you receive \$2 on this turn, turn 5, and the remaining turns 6,7,8, and 9, for a total of \$$2\cdot5$ = \$10 dollars.

For this example, $T=4$ because there are 4 remaining turns after the current turn. You have the option of increasing your income from \$2 to \$3, so the investment increases your income by $i$ = \$1 per turn.

The Correct Strategy

If you choose option 1, then your total earnings will be

invest_option_returns = $T\cdot (I+i)$ dollars.

If you choose option 2, then your total earnings will be

no_investment_option_returns = $(T+1)\cdot I$ dollars.

So, you should invest if

$$\begin{aligned}T\cdot (I+i) &> (T+1)\cdot I \\T\cdot I+T\cdot i &> T\cdot I + I \\T\cdot i &> I \\T&>\frac{I}{i}. \\\end{aligned}$$

So, according to the math above, you should not invest in something unless there are more than $$\frac{I}{i}= \frac1{r}$$ turns left in the game after the current turn where $$r=\frac{i}{I}$$ is sometimes called the return on investment (ROI).

When you invest $I$ dollars to get an increase of $i$ dollars per turn, it takes $I/i$ turns for the investment to “pay for itself”.

The Gain

If there are more than $\frac1{r}=\frac{I}{i}$ turns in the game, then you will gain

gain = invest_option_returns – no_investment_option_returns

$$\begin{aligned}&=T\cdot (I+i) – (T+1)\cdot I\\&=T I+T i – T i – I\\&= T i – I \\&= T r I – I \\&= (Tr -1) I \\&= I r  \left(T -\frac1{r}\right) \end{aligned}$$

dollars by choosing to invest.  The investment pays for itself after $1/r$ turns and every turn after that gives you $I r=i$ dollars.

APPLYING THE CORRECT STRATEGY TO THE EXAMPLE

For the example, $T=4, I=2,$ and $i=1$, so $r = i/I =0.5$. The correct strategy is to invest if

$$T > I/i,$$

but T=4 which is greater then I/i = 2, so the best option is the investment option.

I am hoping to write about applying this idea to several games over the next few weeks.

About a year ago, I posted a short article about optimal putting in disc golf.  I gave an approximate rule of thumb to use at the end of the article, but it turns out that there is a better thumb rule, so I’m revising the post accordingly below.

I often have to make a decision when putting at the edge of the green during disc golf.  Should I try to put the disc in the basket (choice 1) or should I just try to put the disc near the basket (choice 2)? If I try to put it in the basket and I miss, sometimes the disc will fly or roll so far way that I miss the next shot.

In order to answer this question, I created a simplified model.  Assume:

• If I do try to put it in the basket (choice 1), I will succeed with probability $p_1$.
• If I do try to put it in the basket (choice 1), fail to get it in the basket, and then fail again on my second try, then I will always succeed on the third try.
• If I don’t try to put the disc in the basket (choice 2), I will land near the basket and get it in the basket on the next throw.

Using these assumptions, I can compute the average number of throws for each choice.

For choice 2, I will always use two throws to get the disc in the basket.

For choice 1, there are three possible outcomes:

• outcome 1.1: With probability $p_1$, I get it the basket on the first throw!
• outcome 1.2: With probability $p_2$, I miss the basket, but get the disc in the basket on the second throw.
• outcome 1.3: With probability $p_3$, I miss twice, and get it on the third throw.

I am assuming that if I miss twice, I will always get it on the third try, so

$$p_1 + p_2 + p_3=1.$$

Let $a$ be the average number of throws for choice 1. Then $$a = p_1\cdot 1 +p_2\cdot 2 +p_3\cdot 3.$$

I should choose choice 1 (go for it) if I average fewer throws than choice 2, i.e. if $a<2$.  This occurs when

$$\begin{aligned}2 >& p_1\cdot 1 +p_2\cdot 2 +p_3\cdot 3 \\2 (p_1+p_2+p_3) >&  p_1\cdot 1 +p_2\cdot 2 +p_3\cdot 3\\p_1\cdot 2+p_2\cdot 2+p_3\cdot 2 >&  p_1\cdot 1 +p_2\cdot 2 +p_3\cdot 3\\ p_1 >& p_3.\end{aligned}$$

So, I should choose choice 1 if $p_1> p_3$.  In words,

“Go for it if the probability of getting it on the first try is greater than the probability of missing twice”.

I often have to make a decision when putting at the edge of the green during disc golf.  Should I try to put the disc in the basket (choice 1) or should I just try to put the disc near the basket (choice 2)? If I try to put it in the basket and I miss, sometimes the disc will fly or roll so far way that I miss the next shot.

In order to answer this question, I created a simplified model.  Assume:

• If I don’t try to put the disc in the basket (choice 2), I will land near the basket and get it in the basket on the next throw.
• If I do try to put it in the basket (choice 1), I will succeed with probability $p$, where $p$ depends only on distance to the basket.
• If I do try to put it in the basket and fail to get it in the basket (choice 1), the probability that I will succeed on the second try is $q$ where $q$ is constant which does not depend on distance.
• If I do try to put it in the basket (choice 1), fail to get it in the basket, and then fail again on my second try, then I will always succeed on the third try.

Using these assumptions, I can compute the average number of throws for each choice.

For choice 2, I will always use two throws to get the disc in the basket.

For choice 1, there are three possible outcomes:

• outcome 1.1: I get it the basket on the first throw!
• outcome 1.2: I miss the basket, but get the disc in the basket on the second throw.
• outcome 1.3: I miss twice, and get it on the third throw.

The probabilities for each of those outcomes are:  $p$, $(1-p) q$, and $(1-p)(1-q)$ respectively.

Let $a$ be the average number of throws for choice 1. Then $$\begin{aligned}a &= p\cdot 1 +(1-p)q\cdot 2 + (1-p)(1-q)\cdot 3 \\&= p + 2 q – 2 p q + 3 – 3 p – 3 q + 3 p q\\&=3 -2 p – q + p q.\end{aligned}$$

I should choose choice 1 if $ 2>a$.  This occurs when

$$\begin{aligned} 2 &> 3 -2 p – q + p q\\-1 &> -2 p – q + p q \\-1 &> (q-2) p – q  \\q -1 &> (q-2) p\\ \frac{q -1}{q-2} &< p   \\\frac{1-q}{2-q} &< p. \\ \end{aligned}$$

Now you can plug in various values for $q$ to find the lowest value for $p$ needed to go for it.

Probability of Success          Required
 After Missing             Probability of Success
                             on the first try
     100%                           0%
      99%                           1%
      95%                           5%
      90%                           9%
      85%                          13%
      80%                          17%
      75%                          20%
      50%                          33%
      0%                           50%

So, if you are 100% certain that you will put it in the basket on the second try, then you should use choice 1 (going for it) if $p>0$ (i.e. always).

If you are 90% certain that you will put it in the basket on the second try, then you should use choice 1 (going for it) if $p>0.09=9\%$.

$$ $$

a rule of thumb

A nice approximate rule of thumb is to go for it if the sum of $p$ and $q$ is more than 100%.

When I am 6 yards from the basket, I will get it in about 75% of the time (p=0.75), and if I miss, I will usually get it in 90% of the time.  The sum of 70% and 90% is 160%, so obviously, I should go for it.

When I am 9 yards from the basket, I will get it in about 20% of the time (p=0.20), and if I miss, I will usually get it in 85% of the time.  The sum of 20% and 85% is 105%, so it seems like I should go for it.

If the basket is on a hill or if it is windy, then the disc will sometimes roll a fair distance if I miss.  In that case, $q$ might be only 75%. The rule of thumb is that $p+q$ should be at least 100% to go for it, so according to the rule of thumb, I would need $p$ to be at least 25% to go for it.  On a windy day, that’s like 6 yards for me.

So, I have played about 300 hours of Slay the Spire since I got it on July 26.  It’s a turn-based deck building game.  Many of these deck building games have interesting mathematics, so I have been devoting a fair amount of time to analyzing the game and writing about the game.

The most interesting theorem about the game is

D = h (( d – c b + w)/a + b/alpha)

where D is the total damage that you take, h is the total amount of damage that you give to the enemy, d is the average attack per turn from the enemy, c is the average number of cards you play per turn, b is the average block per blocking card played, w is the average amount of waisted block per turn, and alpha is the average attack for the attack cards you played.  (PDF slides here.)

The nice thing about the formula is that h, d, c, b, and alpha are often precisely known or easy to calculate.  Also, a large portion of the reasonable strategies have w=0.  If you know h,d,c,b, and w and they are constant, then the correct strategy is simple:  if (d-c b + w) is positive, then don’t block.  If it’s negative, then block a lot.

There are other analysis techniques that were mentioned in the Sept 27, 2020 reddit post “Simplified Spire Puzzles“.  My favorite is looking at the ratio of damage received to damage given.

Also, I wrote a computer program that computes the best possible strategy for just about any Slay Spire combat situation.  The drawback is that if you have over 20 cards and 10 different types of cards, the program needs about 10 terabytes of ram and 3 years of cpu time to computer the answer.  It is much quicker if you have only 10 cards the are all strike or block cards in which case it takes less than one cpu second and only a few kilobytes of ram.

I have been wondering how to present this information to the world.  Today, I showed the formula and my program to my friends Cat and Chuck who are both a) fans of Slay the Spire, and b) programmers.  Additionally, I created about 10 power point slides and a 16 page document mostly describing simplified Slay the Spire problems and their solutions.

Additionally, I would like to document all the card combinations that result in either an infinite sequence of actions (resulting from hyperbolic growth) or another kind of growth.  Growth in this game seems to be limited to quadratic (1 4 9 16 25…), cubic (1 8 27 64 125…), or exponential (1 2 4 8 16 32…).  I have never seen any other kind of growth in any game except dominion which  can have polynomial growth where the exponent is a fraction.

I don’t mind writing, but I do mind rewriting and combining my short essays into a larger, more useful work especially if no one is going to read it.

Cheers, Hein