简单介绍

第一次结对编程,邹欣老师选择了一个博弈游戏作为题目。博弈论是一门非常有趣的学科。之前竞赛时接触的博弈论大部分都是存在均衡点/必胜策略的。像这次这种多人参与,没有完美策略,你方唱罢我登台的游戏,我还是第一次参与。由于没有使用深度模型且在训练时成绩并不出众,最后成绩拿到第一确实没有想到。接下来为大家介绍一下我们的游戏策略。


什么是黄金点游戏

N 名玩家,每人写出两个 0 到 100 之间的有理数 (不包括 0 或 100,精确到 0.001),提交给服务器,服务器在回合结束时算出所有数字的平均值,然后乘以 0.618(黄金分割数),得到本轮 G 值。所有提交的数字中最靠近 G 的数字对应玩家得到 N 分,离 G 最远的数字对应的玩家得到 -2 分,其他玩家得 0 分。

在本次比赛中,每组同学都会提交一个 Bot,加上老师的一共十一个 Bot,共比赛 11000 轮,积分最高者获胜。前 1000 轮结束后,可根据比赛结果修改自己的 Bot,在后 10000 轮中拿到更好的成绩。我称前 1000 轮为上半场,后 10000 轮为后半场。


黄金点游戏难在哪

假设我们完成了一轮比赛。那么新的一轮中,由于有了已知黄金点的“经验”,那么看起来选择上一轮的黄金点是个不错的策略。于是,大部分人认为大部分人(没写错)会选择上一轮的黄金点。这样,如果大部分人都这么选,那么看起来选择上一轮黄金点的 0.618 倍看起来是个不错的选择。但由于大部分人都想到了这一点,所以很有可能大部分人都选了上一轮黄金点的 0.618 倍,于是黄金点应该会再变低... 按照这个逻辑,每轮的黄金点应该都是 0.001 才对。但现实告诉我们根本不是这样。猜中别人的策略是非常困难的事情。

按照刚才所说,虽然我们很难猜中别人的策略是什么,但有一点我们知道:基本所有策略都是根据前 X 轮的结果得出的。前几轮的游戏环境会对本轮的结果产生至关重要的影响。在某些时候突然给出一个奇怪的数字(如 0.001 或 99.999)来扰动游戏环境可能会成功干扰到其他玩家的策略。在这个游戏的原始版本中,每个人每轮只能提交一个有理数。这样如果有人扰动局势,则当前回合他几乎肯定会受到扣分的惩罚。而在新的游戏规则中,可以选择其中一个数字扰动,而另一个数字根据扰动去预测 G 值,两个数字配合得分。这使得游戏环境变数更大,也使得策略的选取更加困难。


我们的核心算法

虽然我们最后采用的策略不包含深度模型,但实际上我们是在尝试深度模型失败了之后才不得已转向了普通的 Q-Learning。我先来简述一下 Q-Learning 和 DQN 的核心思路:

Q-Learning

整个游戏的核心思路就是:根据之前的数据,推测本轮的环境,给出对应的数字。假设有 N 种环境,则我们需要找到一个长度为 N 的表,表中每个值记录了对应环境应该给出的数字。每次通过之前的数据推算出当前环境是哪一种环境即可。但是这个表我们是得不到的。于是我们退而求其次,假设有 M 种给出数字的函数,我们把长度为 N 的表扩展成 N * M 的矩阵,矩阵中每个值代表环境为 i,选择方法 j 能得到的收益的期望。当 N 和 M 有限时,我们把环境称为状态,将函数称为策略。这个 N * M 的状态对应策略的表,即为 Q 表

如何得到这个 Q 表呢?直接求期望同样太过困难,我们可以通过强化学习的方式,每次将当前状态,当前策略,得到收益与转移到的状态作为一条经验,不断更新现在的 Q 表。具体公式网上有大批的讲解,我在这里就不赘述了。更新之后,每次选择收益最大的一种策略执行即可。当然,为了防止某些策略根本没有学习机会,每次选策略时,有一定概率随机选择,而不是取最大收益,通过“试错”学到更多的经验。

DQN

其实说起来也容易,由于状态不好表示,所以我们直接用深度模型代替 Q 表,直接从上一轮的数据中推测下一轮得分最高的策略,从而省去了状态的表示。由于最终没有采用 DQN,在这里只是简述下我们的尝试:网上用来玩游戏的 DQN 是将整个画面作为输入去训练,所以采用了 CNN。我们每次输入的只是一个序列,所以我用可以处理序列的 LSTM 模型代替了之前的 CNN, 后面接了两层全连接作为 DQN 的结构。但我觉得可能还是学习过程过于缓慢的原因,在和我自己写的简单 Bot 训练了 3000 轮之后,效果非常惨,于是被我抛弃掉了。。


我们的具体策略

大致的流程图如下:

软件工程 in MSRA 黄金点游戏-第一次结对编程-LMLPHP

预测策略:

老师给出的 Demo 里面的 action 都是直接预测两个数字。这样假设我有 N 种预测数的方式,那么我就有 N * (N - 1) / 2 种 action。这会使得 Q 表变得庞大起来,且没有必要。所以我们设定每个action 只预测出一个数,而当我们要预测两个数时,将期望最高的两个 action 同时返回即可。

最经典的预测策略,莫过于上一轮的黄金点,或是上一轮黄金点 * 0.618 了。我们假定很多人选择了这两种策略,那么这是我只需要比众数稍微大或小一点点,就很可能得到分数。所以我们在这两个数的基础上,加上或减去 0.001,形成了一些策略。同时,为处理其他组同学进行扰动的情况,我们还考虑了其中一个数从原数增加到 95,其他数不变,据此重新计算黄金点的策略。一共设计了 10 个策略。

扰动策略:

扰动策略需要的就是:让对手永远不知道自己如何扰动。最好自己也不知道。所以我们的扰动不会根据环境而有策略地扰动,而是完全随机。每次随机以 0.7 概率扰动,而每次扰动完成后将概率下调至 0.05,再经过几轮概率逐渐爬升回 0.7。扰动的值也是 50 - 100 之间的均匀分布。就算猜到了我要扰动,也没法作出准确的预测。

当然,对应的是,我的预测不能受到自己的扰动的影响。如果我当轮扰动,则我当轮的预测值会在预测后再加上当前扰动的影响。同时,我会在得到本轮的黄金点后修改数据,将我的扰动对黄金点造成的影响去除,从而将扰动与预测完全隔离开。

状态表示:

奥卡姆剃刀定律:简单有效。整个比赛只有 10000+ 轮。假设我有 1000+ 种状态,那么 Q 表就有 10000+ 格,平均一个格子只命中一次,那么我非常可能什么东西都学不到。所以,简单的状态表示是必要的。由于我的策略都是根据上一轮的黄金点确定的,所以没必要将上一轮黄金点的数值再放入状态里。Demo 里考虑的是近 10 轮的起伏变化,我们认为没有必要。我们只考虑一轮。我们考虑能不能将上一轮黄金点与上上轮黄金点的差作为状态。

由于浮点数状态仍然太多,我们考虑对浮点数分组。从 0 - 5 分了 40 组, 5 - 10 分了 9 组,10 以上统称第 50 组。这样分组,相当于强制将模型的注意力聚焦在 5 以下的数字变化。我们先算出上一轮黄金点与上上轮黄金点的分组,再将两个组号的差值作为状态。这样,状态数为 100,Q 表的大小为 1000,我们认为这是比较合适的。

小 trick:

为了防止其他 Bot 对我们的扰动与预测策略按照第一个数,第二个数进行推测,每次输出时,有 0.5 概率会调换输出数字的顺序。不知有没有影响到其他同学XD。


结果分析

第一名这个成绩确实没有想到。之前的预期只是前 5 名。原因是在比赛前一天另一组同学组织的训练赛中,我们的 Bot 完全打不过一个名叫 ‘phoebe’ 的 Bot,不知道是哪组同学的。看来 Bot 的得分率和环境之间的关系还是太大了。

比赛之前,我们自己写了几个简单策略的 Bot,和要训练的 Bot 放在一起比赛,最后在正式赛前一天参加另一组同学组织的训练赛跑了 2000 轮。自己的这些 Bot 得分率对比起来还是很明显的。包括那次训练赛我们也放入了 3 个我们的 Bot(房间1366中化名 Potter,Hermonie 与 Voldemort),选择了其中得分最高的作为正式赛模型。

如果将每轮可提交的数字变成 3 个,或者找更多的参赛者来参加比赛,我们的方法依然适用。因为我们将策略进行了拆分,每个策略只预测一个数,排除了两个预测数之间的关系,使得可提交的数字变多对我们的影响不会很大。参赛者的数量对我们的模型没有什么影响,大部分参赛者的策略才是主要影响我们模型得分率的因素。

队友最近也是事情比较多(我也是),整个模型实际上没有花多长时间,也就是一下午 + 一晚上的结果。我负责操刀整个程序,队友负责提出一些修改建议并对训练数据进行分析。我们是打竞赛的老队友了,默契还是非常不错的。说提出建议的话,只能说可以再多抽出一点时间就更好了(逃

05-12 07:25