Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >专栏 >【参赛经验分享】鹅罗斯方块内部赛道Rank5——硬搜

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

原创
作者头像
用户5556120
修改于 2021-08-20 03:27:05
修改于 2021-08-20 03:27:05
7841
举报
文章被收录于专栏: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 删除。

评论
登录后参与评论
1 条评论
热度
最新
感谢选手带来的参赛经验分享!云加社区欢迎有技术比赛获奖经历的竞赛爱好者,入驻赛事俱乐部,首批成员可直接领取「限量礼包」。复制链接在浏览器查看「活动详情」:https://cloud.tencent.com/developer/article/1860760
感谢选手带来的参赛经验分享!云加社区欢迎有技术比赛获奖经历的竞赛爱好者,入驻赛事俱乐部,首批成员可直接领取「限量礼包」。复制链接在浏览器查看「活动详情」:https://cloud.tencent.com/developer/article/1860760
回复回复点赞举报
推荐阅读
编辑精选文章
换一批
【参赛经验分享】外部赛道Rank 2解题报告:状态取舍下的动态规划
在七月末,出于偶然了解到腾讯极客挑战赛这个充满趣味性和挑战性的竞赛,于是便报名参加。这次第四期的赛题叫做“鹅罗斯方块”,要求参赛者用所能尽到的各种方式,在一个JS开发的俄罗斯方块游戏中取得尽可能高的分数。经过一周多的持续思考与努力优化,最终通过动态规划+状态取舍,拿到1378178分,获得外部赛道银奖,也算是如愿以偿。下面是我的比赛经过:
Max.D.
2021/08/17
1.1K1
【参赛经验分享】论 1,413,876 分的成绩是怎么打出来的
七月末的时候看到了腾讯极客挑战赛第四期,发现这不是俄罗斯方块嘛,是之前 Botzone 玩过的 AI 游戏,于是决定来玩玩。没想到一玩玩了好几天,最后的程序也和之前在 Botzone 写的 AI 完全不一样了,最后以 1413876 的分数拿到了外网赛道的第一,同时该分数也是内外网赛道的最高分。
Nano
2021/08/12
1.9K4
【参赛经验分享】论 1,413,876 分的成绩是怎么打出来的
【参赛经验分享】腾讯内部赛道-鹅罗斯方块赛事笔记
我在过去,写过不少游戏AI,所以当看到公司有这样一个比赛很是高兴。不巧比赛的两周刚好项目组特别忙,但我仍希望能在有限的时间来做得更好。
Agent
2021/08/20
1K1
【参赛经验分享】腾讯内部赛道-鹅罗斯方块赛事笔记
【参赛经验分享】鹅罗斯方块解题报告: 遗传算法+分段策略
月初看到TEG公众号推送的极客挑战赛, 主题居然是完成俄罗斯方块的游戏, 顿时来了精神. 想起当初编写各种QQ游戏大厅外挂的快乐时光, 已经快十年了吧.
UME
2021/08/14
2.1K1
【参赛经验分享】鹅罗斯方块解题报告: 遗传算法+分段策略
【最强大脑】全球脑王的极客挑战赛之路:1413876分夺冠如何炼成?
导语 | 在腾讯云+社区联合腾讯码客、腾讯安全平台部全新打造的创新赛事【腾讯极客挑战赛 | 鹅罗斯方块】中,4570名参赛者为我们带来前所未有、异彩纷呈的作品。一场技术竞技,把一群志同道合的开发者聚集在一起,激发好奇心和极客精神,这是云+社区举办赛事的初衷。最终来自清华大学计算机科学与技术系的郑林楷在激烈的竞争中脱颖而出,斩获冠军!此次我们特地邀请郑林楷执笔撰稿,聊聊他以1413876超高分夺冠的那些事! 选手介绍 郑林楷,目前就读于清华大学计算机科学与技术系,主攻Web安全领域。第6季《最强大脑之燃
腾讯云开发者
2021/08/27
8150
【参赛经验分享】俄罗斯方块的Rust解题记录(腾讯内部赛道第7名)
最近一直在学习 Rust。想起以前每次学习新语言,都会实现一个俄罗斯方块来验证对语言的掌握,但是从来没有尝试去实现其AI。正好这次碰到这个挑战,所以没有多想就使用 Rust 来做此题了。
INmouse
2021/08/20
1.1K1
【参赛经验分享】俄罗斯方块的Rust解题记录(腾讯内部赛道第7名)
【参赛经验分享】一个全程DFS的解题总结(内部赛道)
第一件事是确定方块序列怎么生成的,看了下js有很友好的给出源文件地址,随机数生成核心: return (v * a + C) % M;`,种子也是固定的,就放弃了RL的想法。
CarsonZ
2021/08/19
7331
【参赛经验分享】[腾讯内部赛道Rank6]鹅罗斯方块半手打(TAS)心得
参与这个比赛的时候,最初的想法也是想依靠算法去实现的,毕竟手打得无论多好,最优解肯定得依靠算法实现,但是由于种种原因(比如大学被ACM折磨过一段时间之类的...)不想写算法,就以最单纯的玩家心态去解决这个问题了。
ZeroNinEX
2021/08/20
9793
【参赛经验分享】[腾讯内部赛道Rank6]鹅罗斯方块半手打(TAS)心得
【参赛经验分享】腾讯内部赛道139万分解题报告
我参加的是腾讯内部赛道,最后得分 1395326,在内部赛道排名第一。将内网的解题报告搬运一份到云+社区:
chys
2021/08/16
9351
【参赛经验分享】中年男人写的俄罗斯方块AI外挂,47W分只为爱妻拿一个腾讯视频会员卡
在盆友圈里收到消息,鹅厂举办了一场俄罗斯方块的刷分比赛,私聊一下发图的同学拿到了体验连接,好像还挺简单的嘛,遂决定抽空参赛。
熬夜拧魔方
2021/08/22
2.2K4
【参赛经验分享】中年男人写的俄罗斯方块AI外挂,47W分只为爱妻拿一个腾讯视频会员卡
【参赛经验分享】腾讯极客挑战赛第四期俄罗斯方块比赛复盘
七月底的时候在网络上看到了这样一个赛事,赛题大概总结起来就是用代码玩一款十分经典的游戏俄罗斯方块,通过游戏得分来排名评比,觉得挺有意思,抱着随便试试的想法就参加了,结果最后获得了全国第49名,最终获得的最高分数是31万多一点,虽然和第一名的一百多万还是有不小的差距,需要改进反省的地方还有很多,但这一成绩还是基本达到了我的预期的,同时我也是成功获得了腾讯招聘的绿色通道,丰富了自己的履历。
HellloWrold-Ian
2021/08/16
1.5K1
首篇极客解题报告意外泄出!亚军竟有神操作?
导语 | 腾讯云+社区联合腾讯码客、腾讯安全平台部全新打造的创新赛事【腾讯极客挑战赛 | 鹅罗斯方块】正式落幕。玩鹅罗斯方块,玩点不一样!在短暂10天内,4570名参赛者或以自己的硬核技术诠释着 “代码无所不能”;或坚持游戏主义,手玩出一片天。 最终11263次有效提交中,涌现出一批出众的作品。快跟上团队!一睹大牛精心贡献的解题报告。 本期为大家带来亚军大佬——北航研究生陈铭煊的报告。看完他的解题过程,小编直呼“我的强迫症治好了!”(请看下方视频) 大佬这样说 在七月末,出于偶然了解到腾讯极客挑战赛这
腾讯云开发者
2021/08/23
2990
【腾讯内部赛道-极客挑战赛第四期季军】GPU动态规划鹅罗斯方块
鹅罗斯方块挑战是由10000个方块序列构成的鹅罗斯方块游戏,其中包含了大量的s型和z型,以及少数的I型方块。
用户8813955
2021/08/20
7970
【参赛经验分享】[腾讯内部赛道破解大师]俄罗斯方块难?直接破解最简单!
前言:后面有事没时间打比赛怎么办?那当然是把游戏破解了啊。安全人,安全魂,安全人偏不走寻常路~
FDrag0n
2021/08/20
2.8K0
【参赛经验分享】无需关心算法的渐进式解题思路
这是一篇 腾讯极客挑战赛第四期:鹅罗斯方块 的参赛经验分享。这个参赛的主要内容大致是玩俄罗斯方块,最后比较得分。和正常俄罗斯方块不太一样的是这个比赛随机种子被固定了,方块落下的顺序是固定的(方块数量也固定了 10000 的上限),而且得分和你消行时场地上存在的方块数量有关。
白水
2021/08/16
1.4K1
【参赛经验分享】无需关心算法的渐进式解题思路
【参赛经验分享】外部赛道rank3,手打+AI的同时尝试解题
AI与手打同时尝试打分,最后提交的最高成绩是手打成绩,主要思路是尽可能堆高后进行消4,依据序列的情况妥协进行消3.2,通过本地实现一个模拟器提供各种信息来辅助整个流程。AI算法思路与内部赛道的139w分大佬类似,手打最终117.9w分
whoisdiao
2021/08/20
1.1K2
【参赛经验分享】【极客-腾讯内部赛道】一个菜鸡的解题思路
tetris是参加【极客技术挑战赛第四期】鹅罗斯方块 的项目,这个项目是给定一个俄罗斯方块的固定序列,看看谁能消除的分数最高。
esrrhs
2021/08/16
1K1
【参赛经验分享】【极客-腾讯内部赛道】一个菜鸡的解题思路
【参赛经验分享】游戏开发者在"鹅罗斯方块"比赛中的体验(82W)
在游戏开发者的角度来看这道题目的时候,我先想到的是上手打一打看看跟平常的俄罗斯方块有什么不同。结果发现不仅方块出现的顺序是一样的,而且感觉并不是通过随机得到的这一组序列。然后在F12里面看到了具体的规则和一些API,然后就想到可以把核心代码和game代码直接拷贝出来在本机运行,因为最后的答案只需要提交一个操作序列就可以。
京和
2021/08/23
9431
【参赛经验分享】分析js代码开启游玩新世界与Pierre Dellacherie算法本地验证
以下仅是我对于这个比赛的思考过程,可能是拿高分的技巧,但我并没有因此拿高分,本人算法水平有限大佬勿喷,对文章中的问题欢迎指出。
一颗小树
2021/08/13
2.8K2
【参赛经验分享】分析js代码开启游玩新世界与Pierre Dellacherie算法本地验证
【参赛经验分享】含可以手玩的网页版(带AI)
简单看了一下游戏源代码,可以发现:(1)游戏里面共有10000块;(2)游戏里面每一块都是确定的,和操作无关。
用户8875579
2021/08/22
1.1K1
推荐阅读
【参赛经验分享】外部赛道Rank 2解题报告:状态取舍下的动态规划
1.1K1
【参赛经验分享】论 1,413,876 分的成绩是怎么打出来的
1.9K4
【参赛经验分享】腾讯内部赛道-鹅罗斯方块赛事笔记
1K1
【参赛经验分享】鹅罗斯方块解题报告: 遗传算法+分段策略
2.1K1
【最强大脑】全球脑王的极客挑战赛之路:1413876分夺冠如何炼成?
8150
【参赛经验分享】俄罗斯方块的Rust解题记录(腾讯内部赛道第7名)
1.1K1
【参赛经验分享】一个全程DFS的解题总结(内部赛道)
7331
【参赛经验分享】[腾讯内部赛道Rank6]鹅罗斯方块半手打(TAS)心得
9793
【参赛经验分享】腾讯内部赛道139万分解题报告
9351
【参赛经验分享】中年男人写的俄罗斯方块AI外挂,47W分只为爱妻拿一个腾讯视频会员卡
2.2K4
【参赛经验分享】腾讯极客挑战赛第四期俄罗斯方块比赛复盘
1.5K1
首篇极客解题报告意外泄出!亚军竟有神操作?
2990
【腾讯内部赛道-极客挑战赛第四期季军】GPU动态规划鹅罗斯方块
7970
【参赛经验分享】[腾讯内部赛道破解大师]俄罗斯方块难?直接破解最简单!
2.8K0
【参赛经验分享】无需关心算法的渐进式解题思路
1.4K1
【参赛经验分享】外部赛道rank3,手打+AI的同时尝试解题
1.1K2
【参赛经验分享】【极客-腾讯内部赛道】一个菜鸡的解题思路
1K1
【参赛经验分享】游戏开发者在"鹅罗斯方块"比赛中的体验(82W)
9431
【参赛经验分享】分析js代码开启游玩新世界与Pierre Dellacherie算法本地验证
2.8K2
【参赛经验分享】含可以手玩的网页版(带AI)
1.1K1
相关推荐
【参赛经验分享】外部赛道Rank 2解题报告:状态取舍下的动态规划
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文