[CS61a] Hog Project 如何提高胜率？

CS61a的Hog Project, 一个骰子游戏，请问大家如何能达到0.7以上的胜率？
规则如下：In Hog, two players alternate turns trying to be the first to end a turn with at least 100 total points. On each turn, the current player chooses some number of dice to roll, up to 10. That player's score for the turn is the sum of the dice outcomes. However, a player who rolls too many dice risks:
Pig Out. If any of the dice outcomes is a 1, the current player's score for the turn is 1.

还有三种特殊的规则：
Free Bacon. A player who chooses to roll zero dice scores k+3 points, where k is the nth digit of pi after the decimal point, and n is the total score of their opponent. As a special case, if the opponent's score is n = 0, then k = 3 (the digit of pi before the decimal point).
Swine Align. After points for the turn are added to the current player's score, if both players have a positive score and the Greatest Common Divisor (GCD) of the current player's score and the opponent's score is at least 10, take another turn.
Pig Pass. After points for the turn are added to the current player's score, if the current player's score is lower than the opponent's score and the difference between them is less than 3, the current player takes another turn.

我的策略：
1. 稳如老狗 先看Free Bacon能不能触发Swine Align 或者 Pig Pass 拿到 Extra Turn，或者Free Bacon能否直接让你获胜，可以就拿Free Bacon。
2. 孤注一掷 然后再看对手的分数，如果对手再拿10分就能赢（对手1到2个回合就能赢），那么就根据自己分数与目标分数的差值，计算出P(点数>差值)概率最大的情况，然后选择相应的骰子数。
3. 小赌怡情 如果你的分数+1能拿到Extra Turn, 或者你落后对手太多（我设定的是32分）那么直接选择10个骰子。
4. 兢兢业业 如果Free Bacon能至少拿到8点，那么选择Free Bacon, 其他情况就默认选择6个骰子。

稍微解释一下，默认选择6个骰子，是因为一次掷6个骰子的期望是最高的，大约为8.69。还有策略3里加1分拿Extra Turn的操作，是因为10个骰子得到1分的概率为83.8%，其他拿给定点数的概率最大也不到20%。还有想一次拿32分以上时，10个骰子概率更大。

我靠这些策略胜率可以稳定在0.61~0.63，也试了很多其他的情况，但是没有什么提升。求大佬们指点一二，感激不尽。

老师上课的时候说了策略选择的问题,建议去看看视频

张进 发表于 2020-12-14 08:40
老师上课的时候说了策略选择的问题,建议去看看视频

请问是哪一节课啊？

楼主可以考虑一下动态规划算法(DP)，计算每一种游戏状态(我方得分=x，对方得分=y)下我方的胜率。
具体思路是，在每个游戏状态可以模拟计算每个掷骰数所能达到的新状态，新状态的胜率和达到这种状态的概率。这样，该状态的胜率就是每个新状态下的胜率*到达该新状态的概率的总和。
因为分数只会单调增加，所以永远不会出现循环求解卡死的情况。
这样，每个游戏状态的最佳掷骰数就是最大化胜率的那个掷骰数，最终游戏策略就选则每个游戏状态的最佳策略即可。

ericlege 发表于 2020-12-13 21:27:32
楼主可以考虑一下动态规划算法(DP)，计算每一种游戏状态(我方得分=x，对方得分=y)下我方的胜率。
具体思路是，在每个游戏状态可以模拟计算每个掷骰数所能达到的新状态，新状态的胜率和达到这种状态的概

非常感谢你的建议！我有想过，没想出来怎么算这种胜率，而且感觉计算量过大。实际上这个游戏每回合是有一定时间限制的。