第28名方案（银牌）- 多阶段决策树 + 66% 防御性随机策略

我参加这次“石头剪刀布”比赛的目标很简单，就是探索和比较各种不同的技术。

我在整个比赛过程中公开了所有的工作成果，总共发布了23个Notebook，并提交了277次代理程序。

我得分最高的代理程序（28/1667 = 前2%）是我的“多阶段决策树（v36）”，该版本在两个月前就已发布。

• https://www.kaggle.com/jamesmcguigan/rock-paper-scissors-multi-stage-decision-tree?scriptVersionId=50045978

我相信这是比赛中得分最高的公开Notebook（不包括在最终提交截止日期后发布的解决方案）。

该Notebook总共提交了75次，获胜的超参数如下：

• 得分 = 971.0 | window=9, stages=2, random_freq=0.66, warmup_period=10

亚军超参数：

• 得分 = 914.1 | window=10, stages=3, random_freq=0, warmup_period=0

核心思想非常简单：将游戏历史（你的动作 + 对手的动作）视为时间序列数据，并训练一个决策树，根据前9步的移动窗口来预测对手的下一个动作。

这个想法的第一个版本仅得了609分，而且很容易被预测，但当结合了两个关键概念后，效果就好多了。

第一个概念来自电影《公主新娘》中的“艾欧凯恩粉末”场景，即试图猜测、再猜测和三重猜测对手预测我们会做什么。

• https://www.youtube.com/watch?v=9s0UURBihH8&ab_channel=nerfboogers

这个概念通过多阶段决策树来实现。第一阶段使用普通的决策树进行预测。这个预测结果被保存到游戏历史中，然后作为额外的输入馈送到第二个决策树。该过程可以选择性地通过第三阶段决策树重复进行。问题变成了：相对于我们预测他们会采取的行动，对手实际上是如何行动的。

第二个概念是统计防御性。获胜的超参数有66%的时间在随机出招。这样做的结果是，让代理程序在对手看来，在统计上与随机机器人无法区分，从而几乎无法被预测。

随机出招是纳什均衡的统计平局，因此一个1000步的游戏实际上被压缩成了333步的实际预测性博弈。我们只需要±20分就能获胜。每进行1轮预测性博弈，我们就能获得3个回合的观察机会，观察对手如何应对我们的随机出招。另一方面，对手每收到1个真实的博弈信号，就会面对2个统计噪声。这带来了9倍的信息流信噪比优势。

这种策略是一种“慢热型”策略。它的大多数比赛都以平局告终，但它的获胜次数几乎是失败次数的两倍（76胜 / 131平 / 44负 / 总计252场）。它以纳什均衡统计平局为基准，然后试图获得微小的统计优势，从长远来看，这会导致缓慢的上升趋势。具有讽刺意味的是，这个代理程序在面对评分较高的对手时，似乎比面对评分较低的对手表现更好。

通过这次努力，我获得了银牌奖励，这是我的第一枚单人奖牌，并终于达到了“3x Kaggle Competitions Expert”的等级。我也证明了仅使用公开的Notebook而不需要保密，也是有可能赢得Kaggle奖牌的。

延伸阅读

这项工作是探索“石头剪刀布”系列的一部分：