【参赛经验分享】鹅罗斯方块内部赛道Rank5——硬搜

前言

• 首先简要概括一下题目，是一个序列完全固定为10000个的俄罗斯方块游戏，需要给出一个操作序列来最大化得分，得分的多少与单次消除的行数和场上已有方块数有关。
• 主要使用到的算法有：
  1. 贪心
  2. 单步dfs搜索
  3. 蒙特卡罗搜索
  • 除了搜索我还能会点啥嘛，就硬搜
• 先上代码仓库：https://github.com/Suikasxt/tetris
  • 内容主要在以下两个文件中：
    • GameController.cpp：游戏主体逻辑
    • tetris.cpp：策略算法
  • 因为代码本来也不是奔着分享写出来的，就不要指望有多好看。

贪心

• 这里其实就是要做一个局面的估价函数，然后枚举当前可以进行的所有操作，选取一个使得局面估价最高的操作即可，先写这个算法主要是先调整一下这个估价函数，这是后面所有算法的基石。
• 由于以前参加过botzone上的tetris比赛，当时写的估价函数是完全可以作为参考的（当然由于游戏环境和计分方式变了需要做一些调整），主要包含以下几个方面：
  • 各列的最大高度、平均高度
  • 相邻格子占领与否状态的异或值之和（即空白区域和方块区域尽量分开）
  • 被完全挡住的空洞数量、长条形空洞的数量（防止程序陷入长条形空洞过多一直等待I型导致暴毙的情况）
• 使用了这么一个贪心，在再配合枚举（其实就是只有一层的搜索），已经可以有一定的智能表现，大约能够坚持100左右个方块。

搜索

• 在上述贪心的基础上，多搜索几步，就能得到十分优秀的算法。
• 具体来说，每一步的可行操作数量是很多的，可以只挑选其中估价最高的三个操作进行扩展，搜索10层左右，计算量是10000*3^10，前面乘上一个10000是因为我们每一步操作都是模拟之后10步，得到操作之后这次搜索得到的信息全部舍弃掉，在新的局面进一步搜索10步。这种操作实际上在本问题中很浪费，因为我们整个过程是单人且完全确定的，没有对手或者其他因素带来的随机性，不过直到最后我也没有优化掉这一点。
• 此时我们的算法已经能够安稳跑完10000个方块，为了得到更高的分数还要记得在估价函数中加入当前方块的数量，让算法有意识地屯方块。
• 最初使用这个方法搜索层数不深，能够达到70w左右的分数，后来使用MCTS不顺利，又转回搜索，改进到搜索11层，得分117w，但事实上搜索13层能得到122w左右，只是需要的时间比较长大约12小时，就没能在比赛结束前跑完。

蒙特卡洛搜索

• 我理解中MCTS的主要思路是，在搜索过程中每一步都分叉出3个左右状态，导致搜索并不能够很深，于是我们不做这个固定的分叉，而是每次搜索都一路走到底，但是多搜索几次，同时在策略中引入随机性，期望这个随机性能够替我们实现分叉的采样效果。这种做法因为能够做到较深的搜索层数，且一定程度上兼顾了策略的选择，往往能够得到较好的效果。
• 在我以往的游戏AI编写经验中，MCTS是能够比普通搜索带来很大提升的，但这次似乎不同，刚刚使用MCTS时，能够得到111w的得分，看起来比最初的逐步搜索70w要好很多，但只能说70w并不是逐步搜索的上限。后来尝试使用双层的MCTS也没有得到改进。

整体分数变化：

1. 贪心：不能跑完10000个方块。
2. 搜索：
   • 不屯方块：38w
   • 屯方块：68w
3. 蒙特卡洛：
   • 贪心作为单步策略：79w
   • 3层搜索作为单步策略：最终卷到111w
4. 回去调搜索
   • 11层：117w，跑2小时左右
   • 12层（结束前4小时跑出来但是暴毙了没拿到操作序列）：119w，跑5小时左右
   • 13层（跑不完）：预计122w，跑12小时左右

一些trick

1. 多线程：本来我的搜索13层是要跑一天多的，比赛结束前一天我就挂着跑，结束当天意识到跑不完了，才开始着手写多线程，但是为时已晚。以前没有c++上用过多线程，所以才一直没敢动手，写了才发现原来很简单嘛
2. 状态压缩：20行10列，一共200个bit的信息，其实可以压缩为10个int，每列一个，方便操作，不过因为觉得提升不会非常大（而且懒）就没写这个改进。

一点收获

• 赛后看dalao们的笔记还是很有收获的，见识到了集束搜索（解决我上面关于信息浪费的问题），见识到了动态规划的奇技淫巧，见识到jemalloc等优化技巧。
• 感谢主办方，让我跟dalao们有一次交流的机会，感谢让我这个鹅厂小白秀一秀coding，还有梦寐以求的机械键盘。