ASE高级软件工程 第一次结对编程

问题定义

问题的定义

​ 在邹欣老师的博客有游戏介绍:创新的时机 – 黄金点游戏

​ N个玩家,每人写一个或两个0~100之间的有理数 (不包括0或100),提交给服务器,服务器在当前回合结束时算出所有数字的平均值,然后乘以0.618(所谓黄金分割常数),得到G值。提交的数字最靠近G(取绝对值)的玩家得到N分,离G最远的玩家得到-2分,其他玩家得0分。只有一个玩家参与时不得分。

问题的难点

  • 很难知道其他人的策略,只能通过黄金点的历史值进行一定的估计,如何利用信息是一个难点。
  • 首先从游戏规则上来看,游戏中一次胜利的收益是很高的(得到等同于玩家人数的分数),离黄金点最远的玩家会倒扣2分,风险的损失不是很大,感觉上游戏机制是鼓励冒险的,但是如何在黄金点变化剧烈的时候让预测值"冒险"到黄金点附近很难。
  • 赢者通吃的规则使得只有预测最准的bot才能得分,得分的难度很大,如何可靠的得分是一个难点。

方法建模

动机及算法简介

​ 我们觉得黄金点游戏比较类似一个序列预测问题,在线下几个小组开房间组织测试游戏时,我们发现使用过去5个黄金点的平均值作为下一个黄金点的预测值的Demo的成绩很好,不输给强化学习的Demo,直观上感觉这个问题很像通信里的序列预测,我们就觉得RNN可能就能很好的解决这个问题,学习到比用取平均的方法更好的预测手段,于是就使用pytorch里的LSTM来解决这个问题。

​ 将问题作为一个序列预测问题处理,一条曲线很重要的就是曲线本身的值和其变化率,于是我们选取了两种输入方式,第一种输入方式选择过去的k个黄金点值作为输入序列,第二种输入方式选择过去k个黄金点的一次差分,即k-1个差分值作为输入,来得到两个预测值number1和number2,我们觉得这样的预测方式应该可以得到较好的结果。

流程图

  • 最开始的流程

ASE高级软件工程 第一次结对编程

  • 第一次测试后为了上分*营业的流程

ASE高级软件工程 第一次结对编程

其他的一些想法

​ 由于黄金点游戏在多人博弈理论上会趋于很小的数,且玩家人数较少,所以一个很大的数可以影响黄金点的走势,于是可以利用允许提交两个数的规则,用一个大数进行扰动,同时适当提高自己的另一个数来增加得分的可能性。

​ 首先,这个扰动应该是随机的,因为确定的扰动相当于给游戏结果加上了一个偏置,无法干扰到其他玩家。

​ 一个简单的想法就是将一个数(number1)置为99(允许的最大值),另一个数(number2)加上 0.618 (99 - 原预测值)/ (玩家数 2),精确来说,number2增加的值对黄金点也会有影响,但在玩家人数不是特别少的时候应该可以忽略。当时一想,啊这个扰动对我来说是先验已知的,我可以利用这个信息来影响获得一些主动,后来发现效果其实一般。

​ 但实际中测试的时候发现扰动很容易坑到自己,因为将两个number其中一个置为大数值其实也相当于自断了一条后路,与别人相比少了一个number去预测黄金点,如果不能确保高得分率就很亏,反而增加了失分的风险,所以另一个数的增加可以搞的相对保守一点,即使恰不到分也尽量别总是去扣分。

结果分析

第一轮游戏

​ 第一次集体测试1000轮游戏的结果发现我们排名很靠后(倒数第三),我们事后分析了一下原因,因为大家很多都是从Demo中改过来的,保留了Demo中的扰动策略,所以曲线有很大的波动,有一小部分的黄金点值都很大,我们的RNN应该是受到了这个影响,预测的值都总是偏大,极少得到小于1的预测值,这样一来有很大一部分黄金点的得分与我们毫无关系,这样的游戏环境下我们的Bot很被动。

​ 另一方面,我们发现了很多bot都有使用 使用上一个黄金点,使用上一个黄金点乘以0.618 的策略,于是有很多回合都出现了使用相同策略的群体一起开黑上分的现象,而不使用这样的策略的群体在相应的回合就得不到分,而且这种现象出现的频率很高,我们也没办法,只能打不过就加入了,于是将其中一个数的方式改成了上一个黄金点乘以0.618来和别的Bot一起上分。

正式游戏

​ 正式游戏我们排在了第5名,感觉确实RNN不太适合这样波动很大的序列预测,前几名都是用强化学习取得了很好的效果。虽然看着总体来说波动很大的黄金点走势图感觉问题好玄学,但仔细看确实有一些回合有一些局部的规律的,比如连续下降或者在峰值反弹的场景,可能做的好的组就是在这些情况下采取的策略比较好,所以能得到高分。

反思总结

  • 黄金点比赛的结果符合你们的预期吗?

    第一轮游戏的结果不是很符合预期,因为之前同学们私下里也有建房间测试过,当时的测试结果上看预期能取得中上结果,但结果1000轮下来却是倒数,事后分析觉得是测试房间中有一些bot采取了更激进的策略,防止了我们扣分,我们的扰动策略设计的不好,所以在第一轮游戏中有很多扣分的情况,导致成绩较差。

  • 在正式的比赛前,你们采取了怎样的策略来评价模型的好坏?

    在正式比赛前和其他同学的bot提前进行测试,观察我们得分和扣分情况。

  • 如果将每轮可提交的数字变成 3个,或者找更多的参赛者来参加比赛,你们的方法还适用吗?

    我们采用的是RNN,所以很好进行扩展,但是从结果上看我们的模型受到大数值扰动的影响很大,不能保证取得较好的成绩

  • 请评价合作伙伴的工作,评价方式请参考书中关于三明治方法的论述。并提出结对伙伴可以改进的地方。

    我的合作伙伴是 Shengnan_An, 他是一个很积极,有效率的人,结对编程作业布置的那几天我很忙,他和我分享了自己的想法,并很快的完成了一个Demo。我们最终的代码中大部分也都是他写的,我觉得我们的结果一般问题主要还是时间安排上的,我开始几天比较忙,而小伙伴后边几天需要回学校,所以讨论的时间不多,完成的比较匆忙,测试的时候分析不足吧。时间上的问题确实也没办法,我觉得小伙伴还是挺给力的。

上一篇:LWIP 的socket接口下接收超时的处理


下一篇:有没有办法在Android上运行Python?