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
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。