Skip to content

Problem 12 (0pts)

实现 final_strategy，它结合了这些想法以及您拥有的任何其他想法，以在与基线战略对抗时获得高胜率。 一些建议：

  • picky_strategy 或 swine_strategy 是您可以开始使用的默认战略。
  • 如果您知道目标得分（默认为 100），那么得分超过目标就没有意义了。检查您是否可以通过掷 0、1 或 2 个骰子获胜。如果您领先，您可能会决定承担更少的风险。
  • 仔细选择 num_rolls 和 threshold 参数。
  • 采取最有可能赢得游戏的行动。

您可以通过运行 ok 来检查您的最终战略是否有效。

python ok -q 12

您还可以通过图形用户界面与您的最终战略对战：

python hog_gui.py

Solutions

首先需要通过动态规划求出公平骰子情况下的最优策略。

当扔 \(k\) 个骰子时，对于每一种可能的得分 \(n\)，我们可以求得发生这种情况的概率。我们希望在对手也采取最优策略时，自己的期望胜率最大，即对方的期望胜率最小（这里没有考虑 swine_swap）。后继状态的胜率可以通过递归和记忆化求解，在求解完后继状态之后就可以枚举自己扔 \(k\) 个骰子，取最优答案。

def custom_strategy(score, opponent_score):
    import numpy as np
    my_goal = 100
    global win_rate, strategy, transf
    if win_rate not in globals():
        win_rate = [[-1] * my_goal for _ in range(my_goal)]
        strategy = [[-1] * my_goal for _ in range(my_goal)]
        transf = [0, np.array([1 / 6] * 5)]
        for i in range(10):
            transf.append(np.convolve(transf[-1], transf[1]))

    def get_moved_win_rate(x, y):
        if x < my_goal:
            return 1 - get_win_rate(*((x, y) if swine_swap(x) else (y, x)))
        return 1

    def get_win_rate(x, y):
        if win_rate[x][y] >= 0:
            return win_rate[x][y]
        else:
            best_choice = 0
            best_win_rate = get_moved_win_rate(x + picky_piggy(y), y)
            for i in range(1, 11):
                cur_win_rate = 0
                pig_rate = 1 - (5 / 6) ** i
                for j in range(len(transf[i])):
                    dx = j + 2 * i
                    cur_win_rate += transf[i][j] * get_moved_win_rate(x + dx, y)
                cur_win_rate += pig_rate * get_moved_win_rate(x + 1, y)
                if cur_win_rate > best_win_rate:
                    best_choice, best_win_rate = i, cur_win_rate
            strategy[x][y] = best_choice
            win_rate[x][y] = best_win_rate
            return best_win_rate

    get_win_rate(score, opponent_score)
    return strategy[score][opponent_score]

Hogcon

~~其实这段应该让雪碧来写，我写还是有点班门弄斧了（~~

然而这样还是不够。注意到 OJ 使用的是不公平的骰子，可以在上面的最优解（打表）基础上进行微调，提交上去查看胜率的变化。不断重复这个过程，留下胜率高的版本。

那么邪恶助教是怎么做到用超短代码拿下榜零的呢？OJ 上代码长度不计算空白字符，

exec(bytes(map(len, '''
# tons of whitespaces and newlines
'''.splitlines())).decode())