30 面骰 vs 20 面骰：Bob 可不看 Alice

Alice 获胜当且仅当 $A>B$。

由于 $B\le 20$，要最小化 $P(A>B)$ 等价于让 Bob 最大化自己最终点数 $B$ 的期望（因为 $P(A>B)=\mathbb{E}[(30-B)/30]=1-\mathbb{E}[B]/30$）。

若 Bob 采用阈值策略：当第一次掷到 $b\le t$ 就重掷，否则保留，则

$$\mathbb{E}[B]=\frac{-t^2+20t+420}{40},$$

该二次函数在 $t=10$ 处取最大值。

因此 Bob 最优为：第一次掷到 1..10 就重掷，掷到 11..20 就保留。此时 $\mathbb{E}[B]=13$，所以

$$P(A>B)=1-\frac{13}{30}=\frac{17}{30}.$$

---

Original Explanation

Let $W$ be the event Alice wins. First, we want to find $\mathbb{P}[W]$. Let $A$ and $B$ be the value of Alice's roll and Bob's first roll, respectively. The key here is to condition on whether or not $A \leq 20$. Namely, this means $$\mathbb{P}[W] = \mathbb{P}[W \mid A \leq 20] \mathbb{P}[A \leq 20] + \mathbb{P}[W \mid A > 20] \mathbb{P}[A > 20].$$ We can quickly see that $\mathbb{P}[A \leq 20] = \frac{2}{3}$, as this accounts for $20$ of $30$ equally-likely values. If $A > 20$, then clearly Alice wins regardless of what Bob obtains, so $\mathbb{P}[W \mid A > 20] = 1$.

If $A \leq 20$, then we are really rolling $2$ independent $20-$sided fair dice. Namely, to compute $\mathbb{P}[W \mid A \leq 20]$, we see that the probability of a tie is $\frac{1}{20}$, as there are $20$ values they can agree upon out of $20^2 = 400$ outcomes. Therefore, the probability the two rolls are different is $\frac{19}{20}$. Because of the fact that the two dice are symmetric, $\mathbb{P}[A > B] = \frac{1}{2} \cdot \frac{19}{20} = \frac{19}{40}$.

Combining these all together, we see that $$\mathbb{P}[W] = \frac{1}{3} \cdot 1 + \frac{2}{3} \cdot \frac{19}{40} = \frac{39}{60}.$$ Now, Bob is going to roll again whenever $\mathbb{P}[W \mid B = b] > \mathbb{P}[W] = \frac{39}{60}$. This is because he wants to minimize Alice's chance of winning. It is easy to see that $$\mathbb{P}[W \mid B = b] = 1 - \frac{b}{30}.$$ Alice just needs to roll a value of at least $b + 1$.

We just need to find the maximum value of $b$, say $b^*$, such that $\mathbb{P}[W \mid B = b] = 1 - \frac{b}{30} > \frac{39}{60}$. Solving this inequality, we get that $b \leq 10.5$, so $b^* = 10$ is the maximum value that Bob rolls again. Let $W_1$ be the event that Alice wins in this new game where Bob can roll again. We have that $$\mathbb{P}[W_1] = \mathbb{P}[W] + \frac{10}{20}\left(\mathbb{P}[W] - \mathbb{P}[W \mid B \leq 10]\right).$$ We get this because of the fact that Bob rolls again with probability $\frac{1}{2}$ which is when he rolls at most $10$. Then, the probability Alice wins is going to change by $$\mathbb{P}[W] - \mathbb{P}[W \mid B \leq 10].$$

To calculate $\mathbb{P}[W \mid B \leq 10]$, this is simply just averaging all the cases where $B = b$ for $1 \leq b \leq 10$, as when $B \leq 10$, the value is uniformly distributed on the first $10$ positive integers. Therefore, $$\mathbb{P}[W \mid B \leq 10] = \frac{1}{10}\sum_{b=1}^{10} \left(1 - \frac{b}{30}\right) = \frac{49}{60}.$$ Therefore, we get that $$\mathbb{P}[W] = \frac{39}{60} + \frac{1}{2}\left(\frac{39}{60} - \frac{49}{60}\right) = \frac{17}{30}.$$