tetris是参加【极客技术挑战赛第四期】鹅罗斯方块 的项目,这个项目是给定一个俄罗斯方块的固定序列,看看谁能消除的分数最高。
本项目最终得分881136,操作的序列参考result.txt文件。内部赛道名次17名。
解题的步骤主要分为了上手、实现、优化。
<!-- 浏览器控制台快速调试方法(可直接复制到控制台中运行) --> <!-- 1、回放操作序列:game.pause();game.playRecord('N,D19,N,D17,N,D16,N,D14,N,D11,N,D9,N,D6,N,D4,N,D3,N,D1'.split(',')); --> <!-- 2、提交上传成绩(会消耗提交次数):axios.post(`api/upload`, { record: 'N,D19,N,D17,N,D16,N,D14,N,D11,N,D9,N,D6,N,D4,N,D3,N,D1', score: 0 }).then(({ data }) => { console.log('提交结果', data); if(data.info) {console.log(data.info)} }); -->
type Random struct { a int64 // 乘子 M int64 // 模数 C int64 // 增量 v int64 // 随机数种子 } func (r *Random) Reset() { r.a = 27073 r.M = 32749 r.C = 17713 r.v = 12358 } func (r *Random) Rand() int64 { v := r.v r.v = (v*r.a + r.C) % r.M return r.v }
type Brick struct { Ty int Stat int } type Grid struct { area [MaxCol][MaxRow]bool }
game.playFreq=1000 game.replayFreq=1 step='N,D19,N,D17,R2,D1,R1,D1,N,D17,L3,D2,N,D16,R1,D1,N,D15,R1,D1,R1,D2,N,C1,D15,R3,D1,R1,D2,N,C1,D14,R3,D1,R2,D1,N,C1,D14,L1,D2,L3,D2,N,C1,D15,R2,D1,N,C2,D15,L1,D3,N,D18,L1,D1,N,D16,L2,D1,L1,D1,N,C1,D16,L1,D1,N,D14,L1,D1,L1,D1,N,D15,R3,D3,N,D15,R1,D2,R1,N,C1,D14,L2,D1,L1,D1,N,C1,D16,N,D15,R3,D1,R1,D2,N,C3,D15,R3,D1,R2,D1,N,C1,D17,L1,D1,N,D18,N,D14,R2,D2,N,C1,D15,R3,D2,R1,N,C1,D15,L1,D1,N,D13,L2,D1,L1,D3,N,C1,D15,N,C1,D13,R1,D1,R1,D1,N,C1,D13,N,D10,L1,D1,L1,D3,N,C1,D10,L1,D1,L1,D1,N,C1,D11,R3,D7,N,C1,D12,R1,D1,R3,D3,N,D12,R1,D1,R3,D1,N,C1,D13,N,C3,D10,R1,D4,N,D12,R1,D1,N,D11,N,C1,D9,L1,D2,N,D8,R2,D1,R1,D3,N,C1,D8,L1,D1,N,D9,N,D7,R2,D1,R1,D3,N,D6,L1,D1,L1,D1,L1,D5,N,D7,L3,D1,L1,D1,N,D6,R2,D2,N,D7,N,D5,L1,D2,N,C3,D4,R2,D1,R2,D1,R1,D1,N,D6,L4,D1,N,D6,R2,D1,N,D5,L1,D1,N,D5,R4,D1,N,D4,L3,D1,N,D6,N,D3,R1,D1,R1,D1,N,D4,L2,D1,N,D2,R2,D1,R1,D1,R2,D1,N,C1,D2,L3,D1,L1,D1,N,D2,R2,D1,R1,D1,N,D4,N,D2,L3,D1,N,D2,R2,D1,R1,D1,N,D2,R4,D1,N,D3,L2,D1,N,D3,N,D1,L2,D1,N,R2,D1,R2,D1,N,D1,R1,D1,N' game.pause();game.playRecord(step.split(',')); axios.post(`api/upload`, { record: step, score: 0 }).then(({ data }) => { console.log('提交结果', data); if(data.info) {console.log(data.info)} });
现在开始要找一个能打高分的序列了。实现这里又分为了穷举路径、估值函数、选择路径几部分。
{ newpos := curpos newpos.Y++ opl.Add(OP_D) g.findMovPath(brick, newpos, walkGrid, opl, ret, stat) opl.Pop() } { newpos := curpos newpos.X-- opl.Add(OP_L) g.findMovPath(brick, newpos, walkGrid, opl, ret, stat) opl.Pop() } { newpos := curpos newpos.X++ opl.Add(OP_R) g.findMovPath(brick, newpos, walkGrid, opl, ret, stat) opl.Pop() }
# ./tetris -algo 0
result is N,D19,N,D17,R2,D1,R1,D1,N,D17,R1,D1,R3,N,D16,R1,D1,N,D15,L2,D2,L1,D2,R1,N,D15,L2,D1,L1,D2,N,C1,D14,L1,D2,N,D15,N,C1,D13,L2,D1,L1,D2,N,C3,D14,R4,D2,L1,D2,N,C1,D14,R3,D1,N,D12,R3,D1,N,C1,D14,L3,D1,N,D12,L3,D1,N,C1,D11,L1,D4,N,D10,L3,D1,N,C1,D8,L3,D1,N,C3,D14,R1,N,D11,R3,D1,R1,D5,N,C1,D12,L1,D2,L1,D1,N,C1,D11,R3,D1,N,D10,R3,D1,R1,D5,N,C2,D14,L1,D2,N,C1,D12,R3,D1,R1,D3,N,C1,D12,R3,D1,N,D13,R1,D2,N,C1,D10,R3,D1,R1,D1,R1,D2,N,D10,R3,D1,R2,D1,N,D14,N,D12,L1,D1,N,D14,N,D12,R2,D1,N,C1,D11,L1,D1,L2,D1,N,D10,L3,D1,N,C1,D11,R5,D1,N,C3,D10,L2,D2,N,C1,D10,L3,D1,N,D14,R2,N,D14,N,D12,R1,D1,N,D11,R1,D1,R1,D1,N,D11,N,C1,D9,L1,D4,N,D9,L1,D2,N,D9,R2,D2,R1,D1,R1,D1,N,D9,L2,D1,L2,D1,N,D10,R2,D2,R2,N,C1,D10,N,D8,R2,D1,R1,D1,R2,N,C1,D6,R1,D1,R3,N,D8,R1,D1,R1,D3,N,D10,L1,N,C1,D8,L2,D1,L1,D2,N,D8,L4,D1,N,D9,L1,N,D7,R1,D1,R1,D1,R1,D3,N,C1,D8,R1,D1,R1,D1,R1,D1,N,D9,R3,D1,N,C3,D9,R1,D1,N,C1,D10,L3,D1,N,D9,R3,D1,R1,D1,N,D10,R3,N,D10,L1,D1,N,D10,N,C1,D8,L2,D1,L1,D1,N,C3,D9,R3,D1,R2,N,C1,D8,L3,D1,N,D6,L3,D1,N,D9,L2,D1,N,C1,D9,N,C3,D6,L2,D1,N,D4,L3,D1,N,C1,D2,L3,D1,N,D6,L2,N,C1,D3,R1,D2,R1,D2,R3,N,D6,R1,D2,R1,D2,N,C1,D5,R1,D2,N,D4,R1,D1,N,C1,D2,R2,D1,R1,D3,R2,N,D2,R2,D1,R1,D1,R2,N,C1,D2,R1,D1,N,D1,L3,D1,N,D1,R1,D1,R1,D7,N,D1,R1,D1,R1,D1,R2,N,D2,R1,D1,R1,D5,N,D1,R5,D1,N,C1,D3,L1,N,D1,L3,D1,N,C1,D1,R2,D1,R1,D4,N,D1,R2,D1,R1,D2,N,D2,L1,N,R2,D1,R1,D1 total:91, score:2074
也就是只跑了91步就挂了,分数2074分,显然不能满足。 3. 只看当前步的估值不够,那么多看几步,比如看后4步的估值,选择累加值最大的。实现参考algo_next.go 文件。输入命令如下,algo=1表示选择algo_next算法,calcstep=4表示往后看4步。slowfilter的作用后面再涉及,这里先不管。
# ./tetris -algo 1 -calcstep 4 -slowfilter 0
total:9999, score:172724
现在可以顺利跑完1w块了,积分为172724。
优化分为两步,分数优化、性能优化。
积分规则:当前方块的消除得分 = 画布中已有的格子数 * 当前方块落定后所消除行数的系数,每消除 1、2、3、4 行的得分系数依次为:1、3、6、10(例:画布当前一共有 n 个格子,当前消除行数为2,则得分为:n * 3)
# ./tetris -algo 2 -calcstep 4 -calcquickstep 6 -base_height 12 -slowfilter 0
total:9999, totalquick:8482, score:704320, usetime:7m16.11465151s
现在可以顺利跑完1w块了,积分为704320,其中有8482块是以积分优先的方式跑的。
type Grid struct { area [MaxCol][MaxRow]bool colline [MaxCol]int rowline [MaxRow]int }
func (g *Grid) GetColumnHeight(col int, quick bool) int { if quick { return gGridColHeightCache[g.colline[col]] } first := -1 for j := 0; j < MaxRow; j++ { if g.area[col][j] { first = j break } } if first >= 0 { return MaxRow - first } return 0 }
本项目的方法,其实是属于暴力流派。最终跑分的参数为地基10层,计算18步:
# ./tetris -algo 2 -base_height 10 -calcquickstep 18
运行48小时后,结果为
total:9999, totalquick:9963, score:881136, usetime:48h17m47.522467465s
1. 接口描述 接口请求域名: cvm.tencentcloudapi.com 。 本接口 (DisassociateS...
随着云计算和虚拟化技术的不断升温和普及,使得如今的CIO从业务支持角色向业务流...
已经聊了三期和安全相关的话题 涉及安全审计和洞察、源码安全检测、数据备份和恢...
来源 | 阿里巴巴云原生公众号 2021 年,由中国开源软件推进联盟 COPU 牵头发布了...
本文转载自微信公众号「Java大数据与数据仓库」,作者刘不二。转载本文请联系Jav...
大带宽给用户和企业带来的快速便捷服务是众多人追求实用大带宽的主要原因。大带...
3月5日 记者采访获悉 江门农商银行日前完成自助分析平台的升级换代 由阿里云云原...
本文主要介绍饿了么大数据团队如何通过对计算引擎入口的统一,降低用户接入门槛...
在云开发的帮助下,潮办科技平均每月不到千元服务器成本,支撑2000多万销售业绩...
不需要备案的 域名 哪里买?备案是我国内的要求,如果想要购买不需要备案的域名...