1

I'm playing a game that has an optimization problem built into it that I am struggling to determine the correct solution for.

In this game, you have a probability to win determined by the function $f(x)$ posted below (e.g., when $x = 300$ you have a 20% chance of success, at $x = 500$ you have a 50% chance).

$$f(x) = \begin{cases} 0 & \text{if } x < 300 \\ (x - 300) \cdot 0.0015 + 0.2 &\text{if } 300 \le x < 500 \\ (x - 500) \cdot 0.001 + 0.5 &\text{if } 500 \le x < 1000 \\ \end{cases}$$

$x$ generally increases linearly with time $t$, i.e. $\Delta x = \Delta t$. You can attempt your first chance to win this game anytime $x >= 300$. However, if you fail, you cannot try again until $x = g(x') + x'$ where $x'$ is the value of $x$ that you last attempted to win with. Additionally there is penalty imposed in that $x$ increases at half the rate as it did before, i.e., $\Delta x = \frac 12 \Delta t$, until you have reached the new $x$ that you can (optionally) try again with, i.e., $x = g(x') + x'$.

$$g(x) = \frac{1000 - x}{10 \cdot 0.86}$$

Ultimately, the goal is to win the game with the minimal amount of time $t$. Given these constraints, how should I best approach solving at what $x$ should I first start attempting to win the game?

I am struggling with how to best approach this problem and the only solution I can think of is to code and run a large number of simulations where I first attempt at $x = 300, x = 301, ...$ and use the large volume of data to find the smallest value of $t$.

Variance: I note that an individual's tolerance for variance does come into play. For now I'm assuming that the player does not mind a high variance but I suppose I should also consider the case where a player wishes to have low vairance.

TheoCS
  • 11
  • a) Is $x$ retricted to integers? (I'm asking because you were considering to find the solution by trying out integers.) b) Do I understand correctly that the slow-down by a factor of $2$ is in effect only until you reach the value of $x$ at which you're allowed to try again, and if you wait after that this penalty is no longer imposed? c) Most importantly, you don't define an objective function. In a probabilistic setting, "to win the game with the minimal amount of time" makes no sense. From what you write about the variance, I'm guessing you want to minimize the expected time to win? – joriki Feb 25 '23 at 10:30
  • Thanks for the comment. a) Yes $x$ is restricted to integers (you can assume $g(x)$ is rounded to the nearest integer). b) Yes you understood that correctly. The slow-down by a factor of 2 is only in effect until you reach the value of x at which you're allowed to try again. c) Yes, you're correct. I'm trying to minimize the expected time to win. – TheoCS Feb 25 '23 at 21:49

1 Answers1

1

With $x$ restricted to integers, this can be solved by starting at $x=1000$ and working your way back. For each $x$, compute the expected time $t_x$ that it will take to win after you reach $x$ with no penalty in effect. This is the lesser of the expected times for your two options: wait, in which case $t_x=t_{x+1}+1$, or attempt, in which case $t_x=(1-f(x))(t_{x+g(x)}+2g(x))$.

Here’s Java code that performs this calculation. The result is that you should first attempt to win at $x=368$. If you fail, you should then always attempt as soon as you’re allowed to, which is at $x=441$, $506$, $563$, $614$, $659$, $699$, $734$, $765$, $792$, $816$, $837$, $856$, $873$, $888$, $901$, $913$, $923$, $932$, $940$, $947$, $953$, $958$, $963$, $967$, $971$, $974$, $977$, $980$, $982$, $984$, $986$, $988$ and from then on every turn.

The expected time to win if you follow this strategy is about $559.82$.

joriki
  • 238,052