首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【参赛经验分享】鹅罗斯方块内部赛道Rank5——硬搜

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

原创
作者头像
用户5556120
修改2021-08-20 11:27:05
7261
修改2021-08-20 11:27:05
举报
文章被收录于专栏:BotBot

前言

  • 首先简要概括一下题目,是一个序列完全固定为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,还有梦寐以求的机械键盘

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 贪心
  • 搜索
  • 蒙特卡洛搜索
  • 整体分数变化:
  • 一些trick
  • 一点收获
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档